Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>в любом случае, я бы отказался от такого кода в продакшене I>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
IE>B-Tree помоему из совсем другой оперы — это множество
это аналог map|multimap|... только оптимизированный под страничное использование памяти и большее оснвание при логарифме
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>в любом случае, я бы отказался от такого кода в продакшене I>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
к сожалению, необходимость заранее знать размер портит картину ((
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, IgushevEdward, Вы писали:
IE>>Здравствуйте, ilnar, Вы писали:
I>>>в любом случае, я бы отказался от такого кода в продакшене I>>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
I>к сожалению, необходимость заранее знать размер портит картину ((
Ну в случае со стандартным вектором это тоже желательно знать))
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>Здравствуйте, IgushevEdward, Вы писали:
IE>>>Здравствуйте, ilnar, Вы писали:
I>>>>в любом случае, я бы отказался от такого кода в продакшене I>>>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>>>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
I>>к сожалению, необходимость заранее знать размер портит картину ((
IE>Ну в случае со стандартным вектором это тоже желательно знать))
там такое незнание не дает такую клоссальную деградацию в производительности
Здравствуйте, IgushevEdward, Вы писали:
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
Идея неплохая, но с неизменным размером страницы (очереди) оценка сложности некорректная. О-нотация подразумевает предел. Если одна страница имеет размер K, то вставка отнимает О(К) + О(N/K) операций, т.е. O(N). То, что при некоторых значениях N и K (K=N^1/2) получается число N^1/2, еще не дает правильную асимптотику. Нужен механизм динамического изменения размеров страниц, и тут нужно аккуратно с его сложностью.
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, IgushevEdward, Вы писали:
IE>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
DM>Идея неплохая, но с неизменным размером страницы (очереди) оценка сложности некорректная. О-нотация подразумевает предел. Если одна страница имеет размер K, то вставка отнимает О(К) + О(N/K) операций, т.е. O(N). То, что при некоторых значениях N и K (K=N^1/2) получается число N^1/2, еще не дает правильную асимптотику. Нужен механизм динамического изменения размеров страниц, и тут нужно аккуратно с его сложностью.
Хороший поинт! Для этого следует заранее резервировать необходимый размер функцией reserve()
Это как в хэш-таблицах, они тоже дают О(1), но надо следить за размерами, а не то выродится в O(N)
Здравствуйте, IgushevEdward, Вы писали:
IE>B-Tree помоему из совсем другой оперы — это множество
Б-дерево — это многоярусная страничная структура.
На его основе можно сделать как дерево поиска (set/map/multiset/multimap), так и как-бы-массив с доступом по индексу.
Изначально Б-деревья разрабатывались именно как страничные структуры — чтобы влезать в страницу оперативной памяти (минимизировать подкачку с диска), блок кучи или линейку кэша. Опять же, полупустые страницы с перспективой их заполнения уменьшают фрагментацию кучи.
Поэтому асимптотики там как на доступ, так и на изменение не O(1), а O(logN), но с хорошей константой.
Важный момент: у Б-дерева высота зависит от количества данных, а у ИнгушАррея — высота всегда равна 3 (массив деков, дек сам по себе двухуровневый).
Почему бы не сделать многоуровневый дек "по мотивам"? Формально, его высота — это O(logN), а следовательно, доступ будет логарифмический. Но какое основание у этого логарифма, э?
Выгода здесь, во-первых, в быстрой арифметике (размер каждой страницы — степень 2); во-вторых, перебалансировка будет случаться реже (не на каждое квадратное число, а на каждую степень степени 2).
Перекуём баги на фичи!
Re[3]: Массив с быстрой вставкой/удалением
От:
Аноним
Дата:
03.02.12 18:28
Оценка:
Здравствуйте, IgushevEdward, Вы писали:
IE>Хороший поинт! Для этого следует заранее резервировать необходимый размер функцией reserve()
Чтобы заранее резервировать размер, его нужно заранее знать.
Тогда уж ведем еще одно требование, для круглого счета: нужно заранее знать,в каком порядке мы будем вставлять элементы в свой массив.
И в этом случае нам не нужен ни супер-контейнер, ни даже функция reserve(): аллоцировали сразу весь нужный нам массив и записали в него значения в цикле тупо индексацией через operator[].
Сравним производительность std::vector и IgushArray в таких условиях?
Здравствуйте, Кодт, Вы писали:
К>Важный момент: у Б-дерева высота зависит от количества данных, а у ИнгушАррея — высота всегда равна 3 (массив деков, дек сам по себе двухуровневый).
Я так понял, что 2 — в деках строго по одному массиву.
К>Почему бы не сделать многоуровневый дек "по мотивам"? Формально, его высота — это O(logN), а следовательно, доступ будет логарифмический. Но какое основание у этого логарифма, э?
К>Выгода здесь, во-первых, в быстрой арифметике (размер каждой страницы — степень 2); во-вторых, перебалансировка будет случаться реже (не на каждое квадратное число, а на каждую степень степени 2).
В скале и кложуре так как раз вектора сделаны. Там основание 32.
Здравствуйте, D. Mon, Вы писали:
К>>Важный момент: у Б-дерева высота зависит от количества данных, а у ИнгушАррея — высота всегда равна 3 (массив деков, дек сам по себе двухуровневый). DM>Я так понял, что 2 — в деках строго по одному массиву.
Если там "дек на коленке", чисто proof of concept, то да. Но у такого дека дорогая вставка в голову.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>За счет фиксированного размера дек получился простой, как плинтус. По реализации близок к кольцевому списку.
А, ну да. У нас же типичные операции групповые: вставить в голову и выдернуть из хвоста; вставить в хвост и выдернуть из головы. Для кольцевого списка такая пара вставить-выдернуть стоит O(1).
Единственно, что при перебалансировке будут одиночные вставки/удаления.
Отсюда мораль, кстати. Нужно ввести гистерезис — увеличивать размеры очередей при достижении верхнего порога количества элементов; уменьшать размеры при достижении нижнего порога. А в промежутке — только менять количество очередей (размер массива верхнего уровня).
Иначе у нас будет очень дорогой дребезг вокруг квадратного числа.
SVZ>На мой взгляд реализация контейнера получилась неплохая. Если додумать, что делать с начальным размером, то можно использовать и в рабочем коде.
В принципе, да.
Автору можно посоветовать — для красоты кода — сделать отдельно реализацию с примитивным интерфейсом (доступ по индексу), и отдельно — STL-like фронтэнд к нему.
Тогда и разные политики с начальным размером, с гистерезисом и т.д. легче вводить.
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, IgushevEdward, Вы писали:
IE>>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)! LVV>Очевидно, что вам не знакома вот эта книга: Флорес И. Структуры и управление данными. М.: Радио и связь, 1982. LVV>В ней подобные структуры описаны. И проведен анализ производительности.
А в более современных книжках такое есть? А то Флорес как-то не находится.
Здравствуйте, Mazay, Вы писали:
IE>>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)! LVV>>Очевидно, что вам не знакома вот эта книга: Флорес И. Структуры и управление данными. М.: Радио и связь, 1982. LVV>>В ней подобные структуры описаны. И проведен анализ производительности.
M>А в более современных книжках такое есть? А то Флорес как-то не находится.
Бумажного Флореса можно купить на ALIB.ru — это букинистический магазин. Компьютерного просто нет.
С момента изобретения Б-дереьев подобные структуры как-то исчезли из книжек.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
M>>Из результатов видно, что время операции удаления std::vector растет линейно вместе с количеством элементов, а время операции удаления IgushArray растет как N1/2
M>>Ага. А N1/2 — это не линейно?
IE>При копировании из word'а спетенное написание 1/2 пропало. Надо читать N^1/2. Сейчас поправлю
Так бы сразу и писал что на кольцевых очередях сделал. Список очередей это прикольно, ага.
С тестами что-то непонятное. Ты что, оптимизацию компилятора не включал? Я сейчас прогоняют твои тесты и у меня время совсем другое:
Accessing elements by number
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 0 vector: 0 Same time OK
Size: 100000 IgushArray: 0 vector: 0 Same time OK
Size: 1000000 IgushArray: 0 vector: 0 Same time OK
Size: 10000000 IgushArray: 0 vector: 0 Same time OK
---------------------------------------------------------------------------
Accessing elements by iterator
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 90 vector: 0 Worse: Infinity OK
Size: 100000 IgushArray: 870 vector: 0 Worse: Infinity OK
Size: 1000000 IgushArray: 11580 vector: 0 Worse: Infinity OK
Size: 10000000 IgushArray: 119840 vector: 0 Worse: Infinity OK
---------------------------------------------------------------------------
Inserting one element int the middle
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 0 vector: 0 Same time OK
Size: 100000 IgushArray: 0 vector: 60 Better: Infinity OK
Size: 1000000 IgushArray: 20 vector: 670 Better: 34 OK
Size: 10000000 IgushArray: 110 vector: 7960 Better: 72 OK
---------------------------------------------------------------------------
Erasing one element from the middle
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 0 vector: 0 Same time OK
Size: 100000 IgushArray: 10 vector: 20 Better: 2 OK
Size: 1000000 IgushArray: 10 vector: 670 Better: 67 OK
Size: 10000000 IgushArray: 60 vector: 7950 Better: 1.3e+02 OK
---------------------------------------------------------------------------
Inserting a number of elements at the middle
Size: 1000 Count: 1 IgushArray: 0 vector: 10 Better: Infinity OK
Size: 1000 Count: 10 IgushArray: 0 vector: 0 Same time OK
Size: 1000 Count: 100 IgushArray: 0 vector: 0 Same time OK
Size: 1000 Count: 1000 IgushArray: 20 vector: 0 Worse: Infinity OK
Size: 10000 Count: 1 IgushArray: 0 vector: 10 Better: Infinity OK
Size: 10000 Count: 10 IgushArray: 0 vector: 0 Same time OK
Size: 10000 Count: 100 IgushArray: 10 vector: 0 Worse: Infinity OK
Size: 10000 Count: 1000 IgushArray: 10 vector: 10 Same time OK
Size: 10000 Count: 10000 IgushArray: 80 vector: 20 Worse: 4 OK
Size: 100000 Count: 1 IgushArray: 10 vector: 70 Better: 7 OK
Size: 100000 Count: 10 IgushArray: 30 vector: 50 Better: 1.7 OK
Size: 100000 Count: 100 IgushArray: 310 vector: 50 Worse: 6.2 OK
Size: 100000 Count: 1000 IgushArray: 180 vector: 50 Worse: 3.6 OK
Size: 100000 Count: 10000 IgushArray: 620 vector: 60 Worse: 10 OK
Size: 100000 Count: 100000 IgushArray: 800 vector: 250 Worse: 3.2 OK
Size: 1000000 Count: 1 IgushArray: 10 vector: 800 Better: 80 OK
Size: 1000000 Count: 10 IgushArray: 110 vector: 830 Better: 7.5 OK
Size: 1000000 Count: 100 IgushArray: 940 vector: 750 Worse: 1.3 OK
Size: 1000000 Count: 1000 IgushArray: 30 vector: 720 Better: 24 OK
Size: 1000000 Count: 10000 IgushArray: 90 vector: 860 Better: 9.6 OK
Size: 1000000 Count: 100000 IgushArray: 790 vector: 1080 Better: 1.4 OK
Size: 1000000 Count: 1000000 IgushArray: 8030 vector: 3050 Worse: 2.6 OK
Size: 10000000 Count: 1 IgushArray: 90
Здравствуйте, Mazay, Вы писали:
M>С тестами что-то непонятное. Ты что, оптимизацию компилятора не включал? Я сейчас прогоняют твои тесты и у меня время совсем другое:
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
С теоретической точки зрения, поскольку у тебя очереди фиксированного размера, то они не зависят от числа элементов N и по отношению к нему являются константой, то есть сложность все равно линейная. Это, подчеркиваю, чисто логические рассуждения, и доводы про заранее приблизительно известное количество элементов здесь не работают.
С практической, если у тебя заранее есть оценка количества элементов, то это сильно меняет дело. std::vector'у тоже, вообще-то, можно сделать reserve.
Ну и вроде про std::vector сразу говорится, что он для вставки в середину и удаление из середины неоптимален. Так что выбор контейнера для сравнения неадекватен.
Здравствуйте, Аноним, Вы писали:
А>С теоретической точки зрения, поскольку у тебя очереди фиксированного размера, то они не зависят от числа элементов N и по отношению к нему являются константой, то есть сложность все равно линейная. Это, подчеркиваю, чисто логические рассуждения, и доводы про заранее приблизительно известное количество элементов здесь не работают.
Что-то не очень логические рассуждения.
Если у нас есть K очередей фиксированного размера M (K*M >= N), то
операция вставки складывается из
— вставки в произвольное место очереди и выпихивания с хвоста — O(M)
— O(K) переносов: вставка в голову и выпихивание с хвоста — для кольцевого буфера это O(1)
— вставки в голову у последней незаполненной очереди — O(1), либо создание новой очереди — O(M)
Итого O(K+M).
Аналогично, удаление складывается из
— выпихивания с головы последней очереди — O(1)
— O(K) переносов: вставка в хвост и выпихивание с головы
— удаление из произвольного места и вставка в хвост — O(M)
Итого, O(K+M).
Можно рассмотреть время заполнения массива N элементами в худшем случае, с учётом перебалансировок.
Не считал, но полагаю, что будет что-то вида O(N*sqrt(N)).
И это смотря как резервировать память под кольцевые буферы. Если как с векторами, с двукратным запасом... Надо тщательно посчитать.
Перекуём баги на фичи!
