OS
А то переписал приложеньку на списках, она даже медленнее стала работать
Вполне
Size: a a a
2020 July 09
OS
Списки вроде во всяких функциональщинах и локфри
Лично я видел использование листов лишь в таком случае
OS
Я не помню, как называется структура данных точно и правильно, но там лист из векторов
FY
Я не помню, как называется структура данных точно и правильно, но там лист из векторов
Дек?
JC
OS
Дек?
Я тоже так запомнил, но не смог найти в инете быстро инфы
YS
Я не помню, как называется структура данных точно и правильно, но там лист из векторов
Помню только структу из 2-х списков - нормального, и прореженного
AO
Что дойти до середины списка О(n), что сдвинуть половину веткора O(n)
Это если вектору не придётся память переаллочивать.
JC
Ну константа другая получится, но один черт O(n)
JC
Похоже вопрос в константах
A
Что дойти до середины списка О(n), что сдвинуть половину веткора O(n)
Так доступ ж можна оптимізувати до логарифму
A
Хоча від цієї оптимізації, об'єм реалізації зростає в рази
JC
ну это уже дерево тогда
JC
Деревья это топ
YS
Деревья это топ
Разве список это не частный случай дерева?
JC
Ну вырожденный случай, да
A
ну это уже дерево тогда
Нє-нє-нє, якщо я не помиляюсь, то список залишався списком просто в нього зберігалися елементи, які мають його індекс +2**н, а якщо той елемент має вже невідповідний індекс, тоді аналогічними стрибками через 2**н доходили до потрібного елементу паралельно виправляючи індекси елементів+їхні стрибки
JC
Это сколько там метаинформации получается на каждый узел?
A
Те ж що й мав+логарифм від н
A
Нє-нє-нє, якщо я не помиляюсь, то список залишався списком просто в нього зберігалися елементи, які мають його індекс +2**н, а якщо той елемент має вже невідповідний індекс, тоді аналогічними стрибками через 2**н доходили до потрібного елементу паралельно виправляючи індекси елементів+їхні стрибки
І, чисто в теорії, реально знайти випадок, коли цей алгоритм працюватиме довше за звичайний список, але на випадковому наборі даних воно працює значно швидше