LINUX.ORG.RU

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


0

0

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

★★★★★

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

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

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

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

anonymous_incognito ★★★★★ ()

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

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

bugmaker ★★★★☆ ()

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

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

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

Begemoth ★★★★★ ()
Ответ на: Re: Быстрое перемещение по списку от dilmah

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

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

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

seiken ★★★★★ ()
Ответ на: Re: Быстрое перемещение по списку от seiken

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

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

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

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

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

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

anonymous ()
Ответ на: Re: Быстрое перемещение по списку от seiken

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

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

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

Pi ★★★★★ ()
Ответ на: Re: Быстрое перемещение по списку от seiken

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

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

YesSSS ★★★ ()

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

Что мешает к текущему указателю прибавить нужное значение?

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