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
идеотский вопрос по прологу →