То есть слияние первых двух значений полностью завершиться только при вставке следующих двух значений. И что ещё важно — вставка всегда происходит в «голову» структуры, поэтому поиск последних добавленных будет всегда быстрее «старых» значений.
O(N) было бы, если бы мы при каждой вставке производили слияние, но мы хитрее. Мы дожидаемся пока оба сливаемых массива полностью заполнены(предполагая, что они изменяться не будут) и только после этого начинаем слияние — создаём массив в 2 раза больших размеров и начинаем процесс слияния пошагово — по одному элементу за раз из одного из под массивов. А каждый шаг запускается при вставке нового элемента.
Для первых вставок:
1. Вставляем элемент первый одноэлементный массив.
2. Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
За одну вставку в результирующие массивы каждого уровня будет вставляться по одному элементу.
Не-не-не. Именно поэтому слияние не просто отложенное, но ещё и пошаговое. Один шаг выполняет добавление в создаваемый массив всего ОДНОГО элемента из 2-х массивов, в зависимости от того, какой очередной элемент меньше — так нагрузка распределяется.
Я вообще считаю, что люди не умеют придумывать ничего нового, только брать немного там, немного там и объединять во что-то, чего ещё не было.
Согласен, общие черты есть. Хотя отталкивался не от B-деревьев, а от обычных отсортированных массивов. В любых бинарных деревьях может быть 2 указателей на такую-же структуру, а здесь только один.
Хотя это тоже натолкнуло на мысль, спасибо) Предположим мы реализуем B-tree с порядками-степенями двойки, зависящими от уровня — это может быть даже лучше. Но мне не попадались статьи, где описывалось подобное использование B-tree, или они есть?
Эта структура пока не закончена — это одна из идей. Сейчас я собираюсь реализовать несколько оптимизации, в т.ч. бинарного поиска и ещё парочку, о чём, по-возможности, напишу здесь статьи и в конце планирую написать статью, объединяющую все идеи в конечную структуру. Все сравнения-замеры обязательно будут проведены когда идея примет более полный вид. Я не жалею, что написал эту сыроватую статью, ибо умные люди здесь навели меня на целых 3 идеи по дальнейшему развитию структуры да и ценные комментарии по-поводу оформления статьи мне будут крайне полезны.
Спасибо за лаконичные и справедливые замечание и пожелания, буду стремиться, но эту статью писал в режиме обеда на работе и не было времени более тщательно подойти к написанию. Да и очень хотелось поделиться идеей.
NULL — это да. Ох уж эта автозамена)
По-поводу Франкенштейна — в точку. В статье написано, что пока писал код, то иногда действовал чуть ли не наугад, ибо идея плавала на поверхности и я сам не о конца понимал как это работает — многовато разного нужно было держать в памяти — это слегка сложнее реализации уже готовых алгоритмов, но вообще согласен. В следующей статье, когда буду описывать оптимизацию бинарного поиска, постараюсь учесть все пожелания комментаторов.
А на счёт 10 указателей — это Вы зря. Они не значимы в пересчёте оверхеада, потому что каждый новый массив-уровень будет содержать в 2 раза больше элементов, чем предыдущий, а количество указателей при этом не изменится.
Хорошо, я не заставляю никого ничего проводить. Статья ориентирована на идею. Если человек увидит в идее смысл, то без проблем реализует лучше и понятнее меня. Я алгоритмист. Если Вам не нравится код, то вы можете использовать данный класс исходя из идеологии «Чёрного ящика», и использовать ИМХО понятные методы get и set, или же просто проигнорировать. У меня было 2 варианта: просто использовать идею или поделиться соображениями с умными людьми. Я выбрал 2-е. Извините, если что-то не правильно оформил.
K — количество уровней(аналогично с деревьями). Основной плюс — экономия памяти. Текущая версия 1.0 ну или бета и имеет куда расти(один из комментаторов подкинул идею) — можно добиться логарифмического времени, если и сами подмассивы будут отсортированы(в ближайшем будущем попытаюсь это реализовать). Реальный анализ ещё не проводился(пока нет времени), но при желании любой желающий сможет это сделать сам — работающий код приводится. Если память важнее, то каждый сам может решить, есть ли смысл. Моё дело было — подать идею на общее рассмотрение. По пути комментирования может будет создано что-то крутое, ибо здесь люди не глупее меня и если вникнуть в общие положения идеи, то наверняка смогут предложить какие-то хорошие доработки. Это скорее не алгоритм, который вытеснит деревья в принципе, а скорее вектор, по которому можно обнаружить нечто новое, надеюсь на понимание.
Там всего 4 типа имен: key, val,i,nxt.
Key(0,1,2,3) — подмассивы ключей,
Val(0,1,2,3) — подмассивы значений,
i(0,1,2) — счётчики позиций слияния для отложенного пошагового слияния,
nxt — ссылка на следующий уровень…
Простите, подскажите какие имена поменять, ибо мне казалось имена соответствуют…
По-идее это будет k*log(N). Но один из комментариев натолкнул на идею сортировки и самих массивов, тогда можно прийти к логарифмической сложности. В общем нужно думать.
Нет. Здесь все подмассивы разных размеров(степени двойки) и не наблюдается закономерность: все элементы следующего подмассива меньше/больше предыдущих — это если грубо взаимо-независимые массивы. Хотя спасибо за комментарий… родилась идея использовать эти особенности развёрнутых связанных списков для ускорения поиска вплоть до логарифмической сложности.
Спасибо за замечание по коду — действительно при редактировании видимо не то скопировал, во втором условии должен стоять 2-й счётчик. Поправил.
Удаление — действительно я так же склонялся к флагу удаления, при обновлении массива просто «перешагивать удалённое» — дело возможной будущей реализации.
Время на поиск… в моей задаче речь шла о 64-битных числах. По представлению это будет логарифмическая проверка каждого уровня массива. С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения. Исходная задача была — снизить overhead памяти при приемлемом замедлении поиска — вставки, в конкретном случае моей задачи эта структура себя оправдала и видится, что есть потенциал развивать идею дальше — собственно причина публикации. Возможно читающие увидят ещё варианты и совместными усилиями удастся сделать нечто крутое)
Асимптотика декартового дерева — действительно интересная тема обсуждения. Но опять же в моей конкретной задаче была необходимость максимального снижения overhead и тягать вероятностные параметры исключалось. И предсказуемая «реальная» сложность алгоритма всё-таки хорошо. Ведь в маловероятном случае декартово дерево всё же выродится, а здесь всё предсказуемо. Но спасибо за комментарий, есть над чем подумать.
Спасибо за комментарии, действительно слегка спутал терминологию. Я имел в виду пересортировку случая двух уже отсортированных массивов в один — так же линейная сложность, хотя да, терминология — это не моё). Извиняюсь, первая публикация, пока не набил руку. Если необходимо, могу написать комментарии к коду, просто кода не так много и сама идея алгоритма изложена. Код — исключительно для указания на работоспособность метода.
Для первых вставок:
1. Вставляем элемент первый одноэлементный массив.
2. Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
За одну вставку в результирующие массивы каждого уровня будет вставляться по одному элементу.
Согласен, общие черты есть. Хотя отталкивался не от B-деревьев, а от обычных отсортированных массивов. В любых бинарных деревьях может быть 2 указателей на такую-же структуру, а здесь только один.
Хотя это тоже натолкнуло на мысль, спасибо) Предположим мы реализуем B-tree с порядками-степенями двойки, зависящими от уровня — это может быть даже лучше. Но мне не попадались статьи, где описывалось подобное использование B-tree, или они есть?
По-поводу Франкенштейна — в точку. В статье написано, что пока писал код, то иногда действовал чуть ли не наугад, ибо идея плавала на поверхности и я сам не о конца понимал как это работает — многовато разного нужно было держать в памяти — это слегка сложнее реализации уже готовых алгоритмов, но вообще согласен. В следующей статье, когда буду описывать оптимизацию бинарного поиска, постараюсь учесть все пожелания комментаторов.
А на счёт 10 указателей — это Вы зря. Они не значимы в пересчёте оверхеада, потому что каждый новый массив-уровень будет содержать в 2 раза больше элементов, чем предыдущий, а количество указателей при этом не изменится.
Key(0,1,2,3) — подмассивы ключей,
Val(0,1,2,3) — подмассивы значений,
i(0,1,2) — счётчики позиций слияния для отложенного пошагового слияния,
nxt — ссылка на следующий уровень…
Простите, подскажите какие имена поменять, ибо мне казалось имена соответствуют…
Удаление — действительно я так же склонялся к флагу удаления, при обновлении массива просто «перешагивать удалённое» — дело возможной будущей реализации.
Время на поиск… в моей задаче речь шла о 64-битных числах. По представлению это будет логарифмическая проверка каждого уровня массива. С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения. Исходная задача была — снизить overhead памяти при приемлемом замедлении поиска — вставки, в конкретном случае моей задачи эта структура себя оправдала и видится, что есть потенциал развивать идею дальше — собственно причина публикации. Возможно читающие увидят ещё варианты и совместными усилиями удастся сделать нечто крутое)
Асимптотика декартового дерева — действительно интересная тема обсуждения. Но опять же в моей конкретной задаче была необходимость максимального снижения overhead и тягать вероятностные параметры исключалось. И предсказуемая «реальная» сложность алгоритма всё-таки хорошо. Ведь в маловероятном случае декартово дерево всё же выродится, а здесь всё предсказуемо. Но спасибо за комментарий, есть над чем подумать.