Re[21]: опять односвязанный список
От: Muxa  
Дата: 16.08.10 09:29
Оценка:
S>Хорош извращаться. Так академические задачи не решают.
да вот, не знаю, зацепило что-то.
Re[15]: опять односвязанный список
От: Кодт Россия  
Дата: 16.08.10 10:05
Оценка:
Здравствуйте, ., Вы писали:

.>По-моему ты какой-то фигнёй страдаешь.


Естественно :) Только не "страдаешь", а "наслаждаешься" :)

>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);

.>Вот это не удастся посчитать без промежуточного регистра.

Это смотря какое АЛУ.
Мы же можем сделать специальный процессор, в которм эта страхолюная конструкция реализована аппаратно.
Ячейка памяти — для хранения данных между шагами — будет одна (и будет содержать e), а все промежуточные данные внутри выражения — не более, чем состояния шин.
Правда, память нам потребуется трёхпортовая.
Перекуём баги на фичи!
Re[16]: опять односвязанный список
От: . Великобритания  
Дата: 16.08.10 10:23
Оценка: :)
On 16/08/10 13:05, Кодт wrote:

> Это смотря какое АЛУ.

> Мы же можем сделать специальный процессор, в которм эта страхолюная
> конструкция реализована аппаратно.
> Ячейка памяти — для хранения данных между шагами — будет одна (и будет
> содержать e), а все промежуточные данные внутри выражения — не более,
> чем состояния шин.
> Правда, память нам потребуется трёхпортовая.
А если сделать специальный процессор для этой задачи, с единственной командой "очистить список с конца"...

Вообще говоря, от вычислителя зависит алгоритмическая сложность... И линейные алгоритмы вполне могут вдруг становиться квадратными.
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[16]: опять односвязанный список
От: Muxa  
Дата: 16.08.10 10:31
Оценка:
К>Естественно Только не "страдаешь", а "наслаждаешься"
ну, хоть кто-то меня понимает.

К>...

я тут глянул на ассемблерный код, в который компилируется моя бодяга.
регистров там конечно много использовано. я его модифицировал, оставив только два регистра eax и edx, плюс осталась какая-то непонятная e (видимо та что из сишного кода (указатель на элемент), я так и не понял что это и где хранится)

  тем, кому я уже тут надоел, под кат не лезть
struct list_elem {
    list_elem *next;
    int *value;
};

int main(int argc, char* argv[]) {
    // формируем список
    list_elem e5; e5.next = NULL; e5.value = (int*)malloc(sizeof(int)*1); *e5.value = 5;
    list_elem e4; e4.next = &e5;  e4.value = (int*)malloc(sizeof(int)*1); *e4.value = 4;
    list_elem e3; e3.next = &e4;  e3.value = (int*)malloc(sizeof(int)*1); *e3.value = 3;
    list_elem e2; e2.next = &e3;  e2.value = (int*)malloc(sizeof(int)*1); *e2.value = 2;
    list_elem e1; e1.next = &e2;  e1.value = (int*)malloc(sizeof(int)*1); *e1.value = 1;
    list_elem e0; e0.next = &e1;  e0.value = (int*)malloc(sizeof(int)*1); *e0.value = 0;
    list_elem *e = &e0;

    // первые 8 бит адреса используем для хранения информации необходимой для прохождения списка в обратном порядке
    __asm{
    //do {
    //    ((list_elem *)(((int)e->next) & 0x00FFFFFF))->next = (list_elem *)((((int)e->next ^ (int)e) << 24) | (int)((list_elem *)(((int)e->next) & 0x00FFFFFF))->next);
start_reverse_loop:
        mov         eax,dword ptr [e] 
        mov         eax,dword ptr [eax] 
        xor         eax,dword ptr [e] 
        shl         eax,18h
        mov         edx,dword ptr [e] 
        mov         edx,dword ptr [edx] 
        and         edx,0FFFFFFh 
        or          eax,dword ptr [edx] 
        mov         edx,dword ptr [e] 
        mov         edx,dword ptr [edx] 
        and         edx,0FFFFFFh 
        mov         dword ptr [edx],eax 
        // e = (list_elem *)((int)e->next & 0x00FFFFFF);
        mov         eax,dword ptr [e] 
        mov         eax,dword ptr [eax] 
        and         eax,0FFFFFFh 
        mov         dword ptr [e],eax 
        // } while(e->next != NULL && ((int)((((list_elem *)(((int)e->next) & 0x00FFFFFF))->next)) & 0x00FFFFFF) != NULL);
        mov         eax,dword ptr [e] 
        cmp         dword ptr [eax],0 
        je          end_loop 
        mov         eax,dword ptr [e] 
        mov         eax,dword ptr [eax] 
        and         eax,0FFFFFFh 
        mov         eax,dword ptr [eax] 
        and         eax,0FFFFFFh 
        jne         start_reverse_loop
end_loop:
    };

    __asm{
// обходим спискок с конца, удаляя данные из узлов
//do{
start_free_loop:
    };
    free(((list_elem *)((int)e->next & 0x00FFFFFF))->value);
    __asm{
        // e = (list_elem *)(((int)e->next >> 24)^((int)e & 0x00FFFFFF));
        mov         eax,dword ptr [e] 
        mov         eax,dword ptr [eax] 
        sar         eax,18h 
        mov         edx,dword ptr [e] 
        and         edx,0FFFFFFh 
        xor         eax,edx 
        mov         dword ptr [e],eax 
        // } while (((int)e->next &0xFF000000) != NULL);
        mov         eax,dword ptr [e] 
        mov         eax,dword ptr [eax] 
        and         eax,0FF000000h 
        jne         start_free_loop
    };
    free(e->next->value);
    free(e->value);

    return 0;
}
Re[17]: опять односвязанный список
От: Кодт Россия  
Дата: 16.08.10 10:38
Оценка:
Здравствуйте, ., Вы писали:

.>А если сделать специальный процессор для этой задачи, с единственной командой "очистить список с конца"... :)


Ну, перетащим решение в микрокод.
Оно всё равно будет не менее O(N) по времени, и, вероятно, таки потребует дополнительную память данных.

.>Вообще говоря, от вычислителя зависит алгоритмическая сложность... И линейные алгоритмы вполне могут вдруг становиться квадратными.


Максимум, тут будет фигурировать разрядность.
То есть, *log(N), если адресная арифметика сделана в big-int.

Хотя, *N или даже *N², если это машина Тьюринга...
Перекуём баги на фичи!
Re[12]: :-)
От: Erop Россия  
Дата: 17.08.10 05:18
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.

Дело не в пяти строчках, а в чистоте подхода. Если ты что-то где-то делаешь не так, как обычно, то у тебя должна быть на это какая-то веская причина, которую ты там же и должен указать в комментарии.
В частности, если ты на время работы метода хочешь нарушить инвариант класса, хотя этого очевидно можно не делать, то тоже должна быть причина. Или ты считаешь нарушение инварианта класса на время работы метода нормой?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[13]: :-)
От: Pavel Dvorkin Россия  
Дата: 17.08.10 10:07
Оценка:
Здравствуйте, Erop, Вы писали:

PD>>О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.

E>Дело не в пяти строчках, а в чистоте подхода.

О да!

>Если ты что-то где-то делаешь не так, как обычно


Я многое делаю не так как обычно

>, то у тебя должна быть на это какая-то веская причина, которую ты там же и должен указать в комментарии.


Причина обычно есть, в комментариях иногда пишу.

E>В частности, если ты на время работы метода хочешь нарушить инвариант класса, хотя этого очевидно можно не делать, то тоже должна быть причина. Или ты считаешь нарушение инварианта класса на время работы метода нормой?


Я считаю нормой все, что мне в данный момент подходит. Даже если это противоречить третьему каноническому правилу, второму безусловному табу, четвертому инварианту и мнению святых апостолов.
With best regards
Pavel Dvorkin
Re[14]: :-)
От: Erop Россия  
Дата: 17.08.10 11:21
Оценка: :)
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Я считаю нормой все, что мне в данный момент подходит. Даже если это противоречить третьему каноническому правилу, второму безусловному табу, четвертому инварианту и мнению святых апостолов.


При чём тут святые апостолы? Для успешной работы в команде надо стремиться писать максимально простой и понятный и однообразный код. А не впендриваться то так то этак
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[15]: :-)
От: Pavel Dvorkin Россия  
Дата: 17.08.10 14:29
Оценка:
Здравствуйте, Erop, Вы писали:

E>При чём тут святые апостолы? Для успешной работы в команде надо стремиться писать максимально простой и понятный и однообразный код. А не впендриваться то так то этак


Апостолами даны заповеди написания максимально простого и понятного кода.
Увы. я атеист . Так что гореть мне в геенне.

Если без шуток. Максимально простой и понятный код — это одно из неплохих требований к коду. Но не более, чем одно из. И если есть некие соображения, побуждающие написать не очень простой и совсем плохо понятный код, получив при этом серьезный профит в другой области — я без сожаления пожертвую простотой и понятностью.

Не сотвори себе кумира
With best regards
Pavel Dvorkin
Re[13]: :-)
От: vdimas Россия  
Дата: 17.08.10 21:53
Оценка:
Здравствуйте, Erop, Вы писали:

E>Или ты считаешь нарушение инварианта класса на время работы метода нормой?


Конечно норма, коль практически все операции внутри метода императивны и не атомарны. Главное, чтобы объект был валиден на выходе из метода или в момент вызова других неприватных методов.
Re[16]: :-)
От: Erop Россия  
Дата: 18.08.10 09:02
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Если без шуток. Максимально простой и понятный код — это одно из неплохих требований к коду. Но не более, чем одно из. И если есть некие соображения, побуждающие написать не очень простой и совсем плохо понятный код, получив при этом серьезный профит в другой области — я без сожаления пожертвую простотой и понятностью.


Дык твоё решение ничем не лучше, а код хуже
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[17]: :-)
От: Pavel Dvorkin Россия  
Дата: 18.08.10 11:16
Оценка:
Здравствуйте, Erop, Вы писали:

E>Дык твоё решение ничем не лучше, а код хуже


Ну если ты считаешь, что однопроходной алгоритм ничем не лучше двухпроходного, причем в ситуации, когда два прохода попросту не нужны, тогда конечно. У меня на сей счет иное мнение.
With best regards
Pavel Dvorkin
Re[13]: :-)
От: Pavel Dvorkin Россия  
Дата: 18.08.10 11:25
Оценка:
Здравствуйте, Erop, Вы писали:

E>Или ты считаешь нарушение инварианта класса на время работы метода нормой?


А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?


// insert at the end
ListElement * tmp = new ListElement;
tmp->data = ...
tmp->next = NULL;
end->next = tmp;
// и вот сейчас список совсем невалиден. Указатель на конец показывает совсем не на конец. 
// исправляемся
end = tmp;
// и он опять валиден.


Это тебе не инвариант, это гораздо хуже.
With best regards
Pavel Dvorkin
Re[18]: :-)
От: Erop Россия  
Дата: 18.08.10 12:02
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ну если ты считаешь, что однопроходной алгоритм ничем не лучше двухпроходного, причем в ситуации, когда два прохода попросту не нужны, тогда конечно. У меня на сей счет иное мнение.


А почему ты считаешь свой алгоритм "однопроходным"?

Он у тебя состоит из двух фаз: найти конец списка и закольцевать список; удалять элементы кольцевого списка вплоть до полного его исчерпания.
У меня алгоритм состоит тоже из двух фаз: найти конец списка и разрушить его; удалять элементы из начала списка вплоть до его исчерпания.

Честно говоря, я не вижу каких-то существенных отличий, кроме того, что в твоём случае надо нарушать инвариант списка.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[14]: :-)
От: Erop Россия  
Дата: 18.08.10 12:06
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?

Либо, как к неизбежному злу, либо, как в случае односвязанного списка, как к лошеству автора


PD>
PD>// и вот сейчас список совсем невалиден. Указатель на конец показывает совсем не на конец. 
PD>// исправляемся
PD>end = tmp;
PD>// и он опять валиден.
PD>

Интересно, зачем в односвязанном списке нужен этот указатель?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[19]: :-)
От: Pavel Dvorkin Россия  
Дата: 18.08.10 14:10
Оценка:
Здравствуйте, Erop, Вы писали:

E>А почему ты считаешь свой алгоритм "однопроходным"?


E>Он у тебя состоит из двух фаз: найти конец списка и закольцевать список; удалять элементы кольцевого списка вплоть до полного его исчерпания.

E>У меня алгоритм состоит тоже из двух фаз: найти конец списка и разрушить его; удалять элементы из начала списка вплоть до его исчерпания.

Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.
With best regards
Pavel Dvorkin
Re[20]: :-)
От: Erop Россия  
Дата: 18.08.10 14:14
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.



И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[20]: :-)
От: Erop Россия  
Дата: 18.08.10 14:16
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.


Так и в моём алгоритме тогда искать не нужно

В общем я так тебя понял, что ты предложил разрушить последний элемент списка, потом первый, второй и т. д. до исчерпания списка.
Вот я утверждаю, что это можно сделать прямо, не создавая закольцованных списков
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[15]: :-)
От: Pavel Dvorkin Россия  
Дата: 18.08.10 14:19
Оценка:
Здравствуйте, Erop, Вы писали:

PD>>А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?

E>Либо, как к неизбежному злу, либо, как в случае односвязанного списка, как к лошеству автора

Ну-ну. Ты это Вирту скажи, я когда-то впервые осваивал списки по его книге, там как раз это решение и приводилось.


PD>>end = tmp;

PD>>// и он опять валиден.
PD>>[/ccode]
E>Интересно, зачем в односвязанном списке нужен этот указатель?

Чтобы вставлять в конец списка без его прохода . Например, реализация очереди на базе однонаправленного списка. Удалять из конца невозможно, поэтому удалять будем из начала, а добавлять в конец списка. И если при добавлении в конец ты будешь каждый раз проходить весь список — ты превратишь O(1) в O(N).
Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.
With best regards
Pavel Dvorkin
Re[21]: :-)
От: Pavel Dvorkin Россия  
Дата: 18.08.10 14:21
Оценка: :)
Здравствуйте, Erop, Вы писали:

PD>>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.


E>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?


А мне вовсе и не надо его удалять.
With best regards
Pavel Dvorkin
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.