Comments 91
я не использую никаких комментариев в коде — там всё достаточно просто и не содержит ничего кроме работы с массивами, циклов и ООП-идеологии — всё до безумия просто.
Угу.
if(key1[i1]<key2[i2]){key0[i0]=key1[i1];val0[i0]=val1[i1];i0++;i1++;}
else{key0[i0]=key2[i2];val0[i0]=val2[i2];i0++;i2++;}
ведь если добавлять новые элементы (удалять старые), то массив скажет: «ломай пересортируй меня полностью»
Массив скажет «найди нужное место и сдвинь хвост». Это тоже не сахар, но всё же намного лучше полной сортировки. У поиска сложность логарифмическая, у сдвига, очевидно, линейная плюс амортизация расширения.
У меня есть идея по удалению — пометить удалённым, и просто игнорировать при поиске (используя компаратор по исходным полям), при следующей пересортировке удалить (используя компаратор, который считает элемент бОльшим, если он удалён).
По поводу сложности, время на поиск — O( K log (N/K) ) = O(K (log N — log K) ) где K — число массивов. Отсюда если мы хотим сложность порядка log^2(N) то K должно быть порядка log N, что вполне логично. Удвоенная сложность почти бесполезна — это всего 2 массива.
Если сравнивать с деревом (например Декартово). То с такой ассимптотикой можно вообще не делать балансировку, когда всё станет плохо перестроить дерево (перестроить можно не больше чем за M log M). Учесть что это дерево (помним, у нас же случайные веса) вырождается крайне редко то в целом думаю будет быстрее чем log^2.
В практических целях, думаю реализации в stl или иной библиотеки дерева (хеш-таблицы) уже содержат неплохую балансировку и писать свою реализацию большого смысла не имеет, больше багов наделаете чем пользы будет. Кстати почему у вас такой странный код в строчках (метод void upd() )
if(i1<len)
{
if(i1<len)А метод достаточно оригинальный, спасибо за идею.
Удаление — действительно я так же склонялся к флагу удаления, при обновлении массива просто «перешагивать удалённое» — дело возможной будущей реализации.
Время на поиск… в моей задаче речь шла о 64-битных числах. По представлению это будет логарифмическая проверка каждого уровня массива. С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения. Исходная задача была — снизить overhead памяти при приемлемом замедлении поиска — вставки, в конкретном случае моей задачи эта структура себя оправдала и видится, что есть потенциал развивать идею дальше — собственно причина публикации. Возможно читающие увидят ещё варианты и совместными усилиями удастся сделать нечто крутое)
Асимптотика декартового дерева — действительно интересная тема обсуждения. Но опять же в моей конкретной задаче была необходимость максимального снижения overhead и тягать вероятностные параметры исключалось. И предсказуемая «реальная» сложность алгоритма всё-таки хорошо. Ведь в маловероятном случае декартово дерево всё же выродится, а здесь всё предсказуемо. Но спасибо за комментарий, есть над чем подумать.
С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения.
Неплохое — это какое (в терминах big-O)?
А k — это что? Ну и да, "по идее" — это, конечно, хорошо, но где реальный анализ?
K — количество уровней(аналогично с деревьями).
В деревьях, извините, используется h. И как зависит k от n?
Основной плюс — экономия памяти
… и какие же у вас — в терминах big-O — требования к памяти?
Реальный анализ ещё не проводился(пока нет времени), но при желании любой желающий сможет это сделать сам — работающий код приводится
Извините, но качество вашего кода таково, что делать по нему анализ нет никакого желания. Не говоря уже о том, что для таких алгоритмов обычно считают на псевдокоде.
Если честно, мне этот код напомнил один из вариантов сортировки черпаком или бор. Кстати если использовать бор в лоб по основанию d(можно по основанию 2 ,10, 16 и по любому другому) то это будет Nlog(d,MAX_INT)d памяти, поиск будет происходить за log(d,MAX_INT) операций. В пределе при d --> MAX_INT мы получим обычный массив. Мне кажется это будет быстрее чем log^2(N) при N начиная уже с 10 тысяч.
https://en.wikipedia.org/wiki/Unrolled_linked_list
Key(0,1,2,3) — подмассивы ключей,
Val(0,1,2,3) — подмассивы значений,
i(0,1,2) — счётчики позиций слияния для отложенного пошагового слияния,
nxt — ссылка на следующий уровень…
Простите, подскажите какие имена поменять, ибо мне казалось имена соответствуют…
Первое:
Всегда наперед напишите «сказку», которую код должен делать, например алгоритм в пунктах.
1. открою это, 2. запишу туда, 3. итд…
А после у каждого метода, который отвечает за конкретный пункт тоже самое, тем самым дробя логику написанного программного кода.
В последствии не понадобиться всматриваться в код.
Второе:
Сделайте код самоописуемым. Когда бы вы проснулись после пъянки и посмотрели, глянули на строчку 69 и увидели написанное, сразу поняли:
ко второму пивоту, который отвечает за нахождение в том-то массиве причетаем +1, потому-что тото и тото…
Третье:
l=0;r=len; <<< это буквы без смысла и значения. Не используйте переменные короче 3 букв, сейчас они для вас понятны, завтра сами запутаетесь.
Четвёртое:
Делите логику. Не обязательно, что-бы был один большой метод, который делает всё. Дробите его.
При этом идея выглядит так, будто вы создали Франкенштейна из массивов, деревьев и сортировки слиянием.
Попробуйте описать результат после вставки 3 элементов в пустое хранилище в виде диаграмм. Это более наглядно.
Так же около 10 указателей в узле непохоже на уменьшение оверхеда по памяти.
По-поводу Франкенштейна — в точку. В статье написано, что пока писал код, то иногда действовал чуть ли не наугад, ибо идея плавала на поверхности и я сам не о конца понимал как это работает — многовато разного нужно было держать в памяти — это слегка сложнее реализации уже готовых алгоритмов, но вообще согласен. В следующей статье, когда буду описывать оптимизацию бинарного поиска, постараюсь учесть все пожелания комментаторов.
А на счёт 10 указателей — это Вы зря. Они не значимы в пересчёте оверхеада, потому что каждый новый массив-уровень будет содержать в 2 раза больше элементов, чем предыдущий, а количество указателей при этом не изменится.
Оригинальный стиль изложения, интересная идея, но где самое вкусное — реальные замеры производительности в сравнении с классическими структурами?
Т.е. листья имеют по одному элементу и при росте дерева и появления нового уровня, корень становится в два раза больше.
допустим у нас есть пустая структура и мы начинаем добавлять элементы:
1 — элемент O(1). Здесь мы не сортируем и экономим по сложности.
2 — элемент O(1). Здесь мы создаем двумерный массив и делаем слияние. Это сортировка со сложностью O(N).
Теперь, допустим, мы добавляем еще два элемента. Получаем два двумерных массива, каждый за O(N). Но теперь мы должны из них создать массив из четырех элементов что будет тоже O(N). Получается O(N * O(N)) = O(N^2).
Для первых вставок:
1. Вставляем элемент первый одноэлементный массив.
2. Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
За одну вставку в результирующие массивы каждого уровня будет вставляться по одному элементу.
- Вставляем элемент первый одноэлементный массив.
1 операция.
- Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
+2 операции.
3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
На третьем шаге: +3 операции (сначала слияние внутри стартового уровня, потом создание следующего уровня, потом создание нового элемента в стартовом уровне).
На четвертом шаге: +2 операции (как на втором).
На пятом шаге: +6 операций (слияние, пересылка на следующий уровень, слияние там, еще одно слияние там, простановка значения на этом уровне, еще одно слияние на следующем уровне).
Итого я насчитал 14 операций на пять шагов. И из динамики выглядит так, что это будет расти нифига не линейно, и даже не логарифмически (потому что по мере продвижения вперед количество слияний на одну операцию будет вырастать вместе с "глубиной" конструкции).
А еще хочу заметить, что у вас двухкратный расход памяти, потому что пока данные не перенесены в следующий уровень, они хранятся одновременно в result, left и right.
PS Так напомните, какая у вас сложность поиска?
Не слияние, а шаг слияния — это копирование одного значения. В деревьях для балансировки при вставке происходят «повороты», не считали сколько это?
Линейно — это же вроде хуже, чем логарифмически… в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?
Насчёт двойного расхода памяти я в курсе. В дереве тройное-четверное для аналогичных типов данных.
Откуда?
Линейно — это же вроде хуже, чем логарифмически…
Я имел в виду n log n, типичное для операций сортировки.
в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?
Это так не выглядит.
Слияние происходит по одному элементу на каждом уровне за одну вставку и происходит оно только после того, как оба подмассива полностью заполнены. Результирующий массив отправляется на уровень ниже и просто висит там, пока в этот уровень не придёт ещё один аналогичный по размеру массив. На 1 уровне 2 одноэлементных массива. На втором — 2 двухэлементных. На третьем 2 четырёх элементных. С каждым уровнем размерность массива удваивается относительно предыдущего. Если бы размерность не менялас, то для чего бы я вводил свойство класса len?
Здесь только ключ и значение, хотя, конечно, в 2 местах.
И вот тут возникает вопрос, что больше — ссылки, или ключи/значения. Впрочем ладно, будем считать, что убедили.
Слияние происходит по одному элементу на каждом уровне за одну вставку
Нет. Когда у вас начинает заполняться следующий уровень, слияние на нем вызывается больше одного раза за вставку на верхний уровень, и дальше это распространяется на каждый следующий уровень тоже.
если под result память не выделена, то пытаемся спустится на уровень ниже, но здесь ничего не произойдёт.
На уровень ниже вы спускаетесь всегда, когда он есть (а это дважды за вставку на этом уровне), и если там память под result выделена, то там будет два слияния безотносительно состояния текущего уровня, и в любом случае будет переход на уровень еще ниже (конечно, если он есть), далее аналогично.
Корректировка деревьев происходит не на каждом шаге, и стоимость каждой корректировки ограничена O(log n).
А здесь на каждом шаге, но тоже логарифм, ибо нужно сделать по одному шагу слияния на каждый уровень,
А по одному ли?
По примеру — внесли 16 элементов (2 по 8) и полностью досортированный результирующий массив (1 по 16) нам понадобится когда насобираем ещё 16 элементов. На самом деле нам не хватает одного шага слияния, ведь когда придёт 16-й элемент, оба 8-ми элементных массива уже должны быть пусты, а 16-ти элементный должен быть на сл. уровне, но на 16 шаге перенос указателя на сл.уровень ещё не произойдёт, поэтому 1 дополнительное слияние мы делаем ещё и в момент создания временного массива.
«На всякий случай» я делаю по 2(не помню, сейчас вот удалил нижний upd() — тоже работает), но с точки зрения алгоритма достаточно одного.
Вот именно поэтому и надо писать в псевдокоде и объяснять каждый шаг. Нет никакого "всякого случая", когда вы оптимизируете под производительность.
Откуда… мы храним ключ — 4 байт + значение — 4 байта + 2 ссылки на лево-право + балансирующий параметр, иногда родителя хранят. Здесь только ключ и значение, хотя, конечно, в 2 местах.
Зато есть занятное встречное наблюдение: для вашего решения нужна память последовательными кусками. Для дерева — нет.
keyResult=new unsigned int[len*2];
valResult=new unsigned int[len*2];
Почему не выглядит если вот же — результирующий массив в 2 раза больше обоих исходных. После заполнения
Потому что его заполнение тоже стоит вам операций, количество которых накапливается с глубиной.
массив 2: 1 3 5 7
Один шаг слияния — это когда мы берём одно значение из массива 1 или 2 в зависимости от того какой текущий элемент сравнения меньше. За один шаг в результирующий массив дописывается только одно значение из уж сформированных отсортированных массивов. Не слияние в принципе, а только один шаг — одно значение.
Пример.
Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты, в 4-м содержится 2 полностью заполненных и отсортированных 8-ми элементных массива. Чтобы слить их в 16-ти элементный массив, необходимо 16 шагов слияния. А сколько нужно вписать новых элементов, чтобы получить новый уровень — тоже 16. В этом и состоит отложеность слияния.
Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты,
А вот и нет. На первом уровне — все массивы заполнены (полезной информации — два элемента), на всех последующих — заполнены temp (2, 4 и 8 элементов соответственно). Суммарно 16, что логично. И к этому моменту мы уже сделали 35 шагов слияния (85 операций всего).
А по факту выполнения — нет. Я просто встал в дебаггере и показал вам, что получается. Когда вставляется 16 элемент, в первом уровне заполнен temp, мы перемещаем его в right, новый элемент идет в left. Теперь мы аллоцируем result и вызываем upd — который передвинет один элемент (left или right) в result. Поскольку result не полон, его передача на следующий уровень не случится.
(Лишний аргумент в пользу строгого псевдокода)
Просто если вы не понимаете даже состояние своей структуры данных на n-ом шаге, как вы делаете утверждения о ее алгоритмической сложности?
Достаточно критики, надоело уже. Всё до безумия просто — не используйте эту структуру, если не нравится. А я вижу в ней потенциал и буду развивать дальше.
Нужно, конечно. Иначе исходя из чего вы оцениваете потребление ресурсов?
Ну и да, я уже давно не пишу/использую кастомные коллекции данных, если нет сильного обоснования: встроенных хватает практически на любой случай.
Я тут малость переписал вашу программу на C#, потому что C++ мне гонять негде, и добавил подсчет операций при set. Вот, что получилось (слева — количество set, справа — количество операций):
3, 8
10003, 153844
20003, 327665
30003, 513505
40003, 695310
50003, 898366
60003, 1086974
70003, 1260379
80003, 1470603
90003, 1693627
100003, 1896699WA считает, что это полиномиальная зависимость.
И опять же, здесь двойной расход памяти — худший случай.
Не худший, а возникающий с заданной периодичностью.
Заданная периодичность звучит будто через каждые N вставок.
Так и есть. После каждых двух вставок на первом уровне будут аллоцированы все массивы.
Аллоцированы все массивы? Каждую вторую вставку?
Да, на первом уровне.
А следующего — каждую его вторую вставку, но так как в него вставка происходит через раз, то это каждая четвёртая вставка
Но и массивы там в два раза больше. Поэтому потребление памяти будет описываться суммой периодических функций, каждая "в два раза больше" (как по амплитуде, так и по периоду) предыдущей.
Так напомните, какая у вас сложность поиска?
Так вот, сложность поиска — это сумма сложностей поиска на каждом уровне. Те, в свою очередь, логарифмичны, но проблема в том, что сумма логарифмов — это не логарифм суммы, а логарифм произведения.
Согласен, общие черты есть. Хотя отталкивался не от B-деревьев, а от обычных отсортированных массивов. В любых бинарных деревьях может быть 2 указателей на такую-же структуру, а здесь только один.
Хотя это тоже натолкнуло на мысль, спасибо) Предположим мы реализуем B-tree с порядками-степенями двойки, зависящими от уровня — это может быть даже лучше. Но мне не попадались статьи, где описывалось подобное использование B-tree, или они есть?
Впрочем, я понял, что меня тут всю дорогу смущало. Ваш код не может быть альтернативой бинарному дереву поиска, потому что на нем нельзя выбрать диапазон; следовательно, сравнивать его надо с key-value структурами — читай, хэш-таблицами с их O(1) на операцию (и существенно меньшей памятью).
(BTW, в случае, когда на уровне заполнены result, left и right, а элемент не входит в этот уровень, стоимость прохода уровня при get увеличивается вдвое)
SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска