Связные списки

← →
Anatoly Podgoretsky © (2007-03-18 23:56) [40]

> Zeqfreed (18.03.2007 23:54:39) [39]

Неудачный пример.
Эта задача также мгновенно решается и с помощью массива.

← →
@!!ex © (2007-03-18 23:58) [41]

> [40] Anatoly Podgoretsky © (18.03.07 23:56)

С помошью массива указателей...
Меняем два указателя местами и все....

ИМХО списки нужны только там, где скорость критична.

← →
Zeqfreed © (2007-03-18 23:59) [42]

> Anatoly Podgoretsky © (18.03.07 23:56) [40]

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

← →
Zeqfreed © (2007-03-19 00:04) [43]

> @!!ex © (18.03.07 23:58) [41]

А список сильно отличается от массива указателей?

← →
Anatoly Podgoretsky © (2007-03-19 00:05) [44]

> Zeqfreed (18.03.2007 23:59:42) [42]

Какие еще большие данные, при копировании, обмене указателей. Да хоть и так, для закладок ни тот объем и ни та моторика, пока ты будешь отпускать кнопку мышки, выполнятся миллионы таких операций. Более того данная операция для массива будет немного быстрее, чем даже для двухсвязного списка.

← →
vuk © (2007-03-19 00:09) [45]

Где я бы подумал насчет списков. Вариант - какой-нибудь сетевой сервис, в отдельном потоке принимающий данные и складывающий их в список для обработки другими потоками.

← →
Zeqfreed © (2007-03-19 00:10) [46]

> Anatoly Podgoretsky © (19.03.07 00:05) [44]

Ну вот видимо создатели браузеров также считают, поэтому они [браузеры] тормозят по страшному.

← →
Eraser © (2007-03-19 00:19) [47]

> Ант (18.03.07 23:27) [31]
> > @!!ex © Пафоса много, а конкретики опять ноль.

когда-нибудь разрабатывал какой-нибудь серьезный кэш чего нибудь?

← →
Anatoly Podgoretsky © (2007-03-19 00:19) [48]

> Zeqfreed (19.03.2007 00:10:46) [46]

Они тормозят не из-за этого.

← →
Anatoly Podgoretsky © (2007-03-19 00:22) [49]

> vuk (19.03.2007 00:09:45) [45]

Ну возможно здесь и обычный массив неплох будет, а вот деревья самое то, у них природа списочная.
Или список большого размера с реалтайм сортировкой, правда вопрос что более ресурсо-емко вставка или двоичный поиск.

← →
Zeqfreed © (2007-03-19 00:22) [50]

> Anatoly Podgoretsky © (19.03.07 00:19) [48]

> Они тормозят не из-за этого.

Разумеется, не от механизма реализации списка табов, но от направления мыслей разработчиков.

> Eraser (19.03.2007 00:19:47) [47]

Кеш это линейная структура. Данные (списки) с приоритетами другое дело, вставка в произвольное место, удаление из головы, типичная задача для реал тайм ОС.

Спискам конечно есть место, но оно очень узкое.

to Anatoly Podgoretsky © (19.03.07 00:22) [49]:
>Ну возможно здесь и обычный массив неплох будет
Тормозить будет при увеличении количества элементов, т.к. требуется выделение памяти и копирование всех данных. Чем больше данных, тем больше тормоза (плюс все это к фрагментации кучи ведет). У списков такой проблемы нет, скорость добавления всегда постоянна.

>а вот деревья самое то, у них природа списочная.
Если сортировка нужна, то деревья будут лучше.

>Или список большого размера с реалтайм сортировкой, правда вопрос что
>более ресурсо-емко вставка или двоичный поиск.
А вот двоичный поиск, он хорошо на массивах работает. Ну или на двоичных деревьях. На линейных списках - плохо.

> vuk (19.03.2007 00:33:52) [52]

Только нахождения места вставки время переменное и не очень приятное.
Надо просто исходить из задачи и объемов, постоянно взвешивая поиск и вставку/удаление.

> Anatoly Podgoretsky © (19.03.07 00:24) [51]

к примеру, страничный кэш памяти - да, а если кэш каких-то сложных объектов, которые так просто линейно в памяти не разместишь.. кончено на практике можно TList в качестве "индекса" использовать, но я вот сталкивался с тем, что пришлось именно "чистый" список делать.

Связные списки Найти похожие ветки