Здравствуйте, ., Вы писали:
.>По-моему ты какой-то фигнёй страдаешь.
Естественно :) Только не "страдаешь", а "наслаждаешься" :)
>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL); .>Вот это не удастся посчитать без промежуточного регистра.
Это смотря какое АЛУ.
Мы же можем сделать специальный процессор, в которм эта страхолюная конструкция реализована аппаратно.
Ячейка памяти — для хранения данных между шагами — будет одна (и будет содержать e), а все промежуточные данные внутри выражения — не более, чем состояния шин.
Правда, память нам потребуется трёхпортовая.
On 16/08/10 13:05, Кодт wrote:
> Это смотря какое АЛУ. > Мы же можем сделать специальный процессор, в которм эта страхолюная > конструкция реализована аппаратно. > Ячейка памяти — для хранения данных между шагами — будет одна (и будет > содержать e), а все промежуточные данные внутри выражения — не более, > чем состояния шин. > Правда, память нам потребуется трёхпортовая.
А если сделать специальный процессор для этой задачи, с единственной командой "очистить список с конца"...
Вообще говоря, от вычислителя зависит алгоритмическая сложность... И линейные алгоритмы вполне могут вдруг становиться квадратными.
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
К>Естественно Только не "страдаешь", а "наслаждаешься"
ну, хоть кто-то меня понимает. К>...
я тут глянул на ассемблерный код, в который компилируется моя бодяга.
регистров там конечно много использовано. я его модифицировал, оставив только два регистра eax и edx, плюс осталась какая-то непонятная e (видимо та что из сишного кода (указатель на элемент), я так и не понял что это и где хранится)
Здравствуйте, ., Вы писали:
.>А если сделать специальный процессор для этой задачи, с единственной командой "очистить список с конца"... :)
Ну, перетащим решение в микрокод.
Оно всё равно будет не менее O(N) по времени, и, вероятно, таки потребует дополнительную память данных.
.>Вообще говоря, от вычислителя зависит алгоритмическая сложность... И линейные алгоритмы вполне могут вдруг становиться квадратными.
Максимум, тут будет фигурировать разрядность.
То есть, *log(N), если адресная арифметика сделана в big-int.
Хотя, *N или даже *N², если это машина Тьюринга...
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.
Дело не в пяти строчках, а в чистоте подхода. Если ты что-то где-то делаешь не так, как обычно, то у тебя должна быть на это какая-то веская причина, которую ты там же и должен указать в комментарии.
В частности, если ты на время работы метода хочешь нарушить инвариант класса, хотя этого очевидно можно не делать, то тоже должна быть причина. Или ты считаешь нарушение инварианта класса на время работы метода нормой?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
PD>>О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа. E>Дело не в пяти строчках, а в чистоте подхода.
О да!
>Если ты что-то где-то делаешь не так, как обычно
Я многое делаю не так как обычно
>, то у тебя должна быть на это какая-то веская причина, которую ты там же и должен указать в комментарии.
Причина обычно есть, в комментариях иногда пишу.
E>В частности, если ты на время работы метода хочешь нарушить инвариант класса, хотя этого очевидно можно не делать, то тоже должна быть причина. Или ты считаешь нарушение инварианта класса на время работы метода нормой?
Я считаю нормой все, что мне в данный момент подходит. Даже если это противоречить третьему каноническому правилу, второму безусловному табу, четвертому инварианту и мнению святых апостолов.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я считаю нормой все, что мне в данный момент подходит. Даже если это противоречить третьему каноническому правилу, второму безусловному табу, четвертому инварианту и мнению святых апостолов.
При чём тут святые апостолы? Для успешной работы в команде надо стремиться писать максимально простой и понятный и однообразный код. А не впендриваться то так то этак
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>При чём тут святые апостолы? Для успешной работы в команде надо стремиться писать максимально простой и понятный и однообразный код. А не впендриваться то так то этак
Апостолами даны заповеди написания максимально простого и понятного кода.
Увы. я атеист . Так что гореть мне в геенне.
Если без шуток. Максимально простой и понятный код — это одно из неплохих требований к коду. Но не более, чем одно из. И если есть некие соображения, побуждающие написать не очень простой и совсем плохо понятный код, получив при этом серьезный профит в другой области — я без сожаления пожертвую простотой и понятностью.
Здравствуйте, Erop, Вы писали:
E>Или ты считаешь нарушение инварианта класса на время работы метода нормой?
Конечно норма, коль практически все операции внутри метода императивны и не атомарны. Главное, чтобы объект был валиден на выходе из метода или в момент вызова других неприватных методов.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Если без шуток. Максимально простой и понятный код — это одно из неплохих требований к коду. Но не более, чем одно из. И если есть некие соображения, побуждающие написать не очень простой и совсем плохо понятный код, получив при этом серьезный профит в другой области — я без сожаления пожертвую простотой и понятностью.
Дык твоё решение ничем не лучше, а код хуже
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Дык твоё решение ничем не лучше, а код хуже
Ну если ты считаешь, что однопроходной алгоритм ничем не лучше двухпроходного, причем в ситуации, когда два прохода попросту не нужны, тогда конечно. У меня на сей счет иное мнение.
Здравствуйте, Erop, Вы писали:
E>Или ты считаешь нарушение инварианта класса на время работы метода нормой?
А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?
// insert at the end
ListElement * tmp = new ListElement;
tmp->data = ...
tmp->next = NULL;
end->next = tmp;
// и вот сейчас список совсем невалиден. Указатель на конец показывает совсем не на конец.
// исправляемся
end = tmp;
// и он опять валиден.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну если ты считаешь, что однопроходной алгоритм ничем не лучше двухпроходного, причем в ситуации, когда два прохода попросту не нужны, тогда конечно. У меня на сей счет иное мнение.
А почему ты считаешь свой алгоритм "однопроходным"?
Он у тебя состоит из двух фаз: найти конец списка и закольцевать список; удалять элементы кольцевого списка вплоть до полного его исчерпания.
У меня алгоритм состоит тоже из двух фаз: найти конец списка и разрушить его; удалять элементы из начала списка вплоть до его исчерпания.
Честно говоря, я не вижу каких-то существенных отличий, кроме того, что в твоём случае надо нарушать инвариант списка.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?
Либо, как к неизбежному злу, либо, как в случае односвязанного списка, как к лошеству автора
PD>
PD>// и вот сейчас список совсем невалиден. Указатель на конец показывает совсем не на конец.
PD>// исправляемся
PD>end = tmp;
PD>// и он опять валиден.
PD>
Интересно, зачем в односвязанном списке нужен этот указатель?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>А почему ты считаешь свой алгоритм "однопроходным"?
E>Он у тебя состоит из двух фаз: найти конец списка и закольцевать список; удалять элементы кольцевого списка вплоть до полного его исчерпания. E>У меня алгоритм состоит тоже из двух фаз: найти конец списка и разрушить его; удалять элементы из начала списка вплоть до его исчерпания.
Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.
И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.
Так и в моём алгоритме тогда искать не нужно
В общем я так тебя понял, что ты предложил разрушить последний элемент списка, потом первый, второй и т. д. до исчерпания списка.
Вот я утверждаю, что это можно сделать прямо, не создавая закольцованных списков
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
PD>>А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ? E>Либо, как к неизбежному злу, либо, как в случае односвязанного списка, как к лошеству автора
Ну-ну. Ты это Вирту скажи, я когда-то впервые осваивал списки по его книге, там как раз это решение и приводилось.
PD>>end = tmp; PD>>// и он опять валиден. PD>>[/ccode] E>Интересно, зачем в односвязанном списке нужен этот указатель?
Чтобы вставлять в конец списка без его прохода . Например, реализация очереди на базе однонаправленного списка. Удалять из конца невозможно, поэтому удалять будем из начала, а добавлять в конец списка. И если при добавлении в конец ты будешь каждый раз проходить весь список — ты превратишь O(1) в O(N).
Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.
Здравствуйте, Erop, Вы писали:
PD>>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.
E>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?