LINUX.ORG.RU
Форум — Development  

Быстрое перемещение по списку


0

0

Имеет ли смысл для ускорения работы со списком создавать доп. связи, соединяющие элементы списка через один (в общем случае через n) элементов. Например, если нужно перейти от i-го до j-го элемента, понадобится ок. | j - i |/n переходов. Например, если нужно поддерживать структуру с очень большим количеством элементов, к которой новые элементы добавляются редко, а перемещение должно выполняться быстро.

★★★★★

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

Сделай и проверь на сколько это ускорит твою задачу.

Может проще сделать индексацию: завести массив ссылок на элементы?

anonymous_incognito ★★★★★
()

Конечно, многосвязные списки как раз для этого. Ещё можно использовать древеса и хеш-таблицы, в зависимости от конкретной задачи.

bugmaker ★★★★☆
()

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

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

Begemoth ★★★★★
()
Ответ на: комментарий от seiken

> Если элементов очень много, такой массив просто может не поместиться в памяти.

видится мне каша в твоих представлениях о мире..

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

>видится мне каша в твоих представлениях о мире..

Этого я не отрицаю. Но массив действительно может не влезть в адресное пространство процесса, если оно сильно фрагментированно.

seiken ★★★★★
() автор топика
Ответ на: комментарий от seiken

> Этого я не отрицаю. Но массив действительно может не влезть в адресное пространство процесса, если оно сильно фрагментированно.

а) весь мир уже давно ползет на 64 бита, по крайней мере на десктопах и серверах. Там сия проблема отсутсвует

б) если вы не будете аллоцировать списки из миллионов элементов - то у вас не будет такой жуткой фрагментации памяти ;)

в) используйте правильные аллокаторы

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

anonymous
()
Ответ на: комментарий от seiken

есть такая структура данных -- список массивов. Готовая реальзация -- CvSeq в opencv

dilmah ★★★★★
()
Ответ на: комментарий от seiken

>Но массив действительно может не влезть в адресное пространство процесса, если оно сильно фрагментированно.

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

Pi ★★★★★
()
Ответ на: комментарий от seiken

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

YesSSS ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development