Вступление
Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.
Что не так с деревом?
Да, всё так и можно
А почему не сортированные массивы?
Бинарный поиск в отсортированном массиве реализуется с той же логарифмической сложностью, что и в бинарном дереве поиска, но нет необходимости тягать за собой ссылки на меньшие-большие поддеревья, как в двоичном дереве поиска.
Но что же не так с сортированными массивами?
Да всё так, можно
Но есть и идеальный случай — когда новый элемент больше остальных и его достаточно просто дописать в конец. Это идеально — всего одна операция, но вероятностная оценка такого идеального случая заставляет нас использовать бинарные деревья или хеш-таблицы, или огромное множество других действительно красивых и хитроумных механизмов. Исходя из теории вероятности, такая ситуация редкая — только если все элементы добавляются в массив по-возрастанию (ирония-аналогия с бинарным деревом поиска, когда отсортированные входные данные как раз являются наихудшим случаем с вырождением дерева в связанный список с линейной сложностью).
Частный случай, как закономерность?
Но давайте рассмотрим массив всего из одного элемента. Не важно, какое значение вносится — оно всегда вписывается в начало пустого до этого массива и одно-элементный массив, естественно, всегда отсортирован. А если мы захотим вписать 2-й элемент в нашу структуру данных? Давайте просто создадим ещё один одно-элементный массив и получим два отсортированных одно-элементных массива. Получить новый отсортированный массив из двух отсортированных — простая задача, хотя не очень быстрая… Но в таком случае нам уже нужно сортировать массив не при каждой вставке, а при каждой второй вставке. Мы используем «отложенную сортировку».
А если мы хотим внести больше 2-х элементов?
Распределение нагрузки
Понятно, что этот алгоритм уже значительно сокращает количество сортировок, относительно сортировки обычного массива, ведь первый уровень массивов нужно сортировать через раз, 2-й уровень — каждую 4-ю вставку, 3-й уровень — каждую 8-ю вставку — собственно, это логарифмическая сложность.
На этом можно было бы успокоиться, но
Поиск
Поиск представляет из себя классический бинарный поиск по отсортированному массиву с той лишь разницей, что здесь массивов много и искать необходимо по-очереди по всем. Поэтому логарифмичность сложности поиска оспариваема(если не ошибаюсь, это удвоенная логарифмическая сложность). Но в поставленной задаче это вполне приемлемо, учитывая сэкономленную память.
Реализация
Пока закипал чайник, я вспомнил, что хотел ещё написать, но потом чайник закипел и его свист заставил меня обратно забыть то, что я хотел ещё написать…
Реализация была достаточно запутанной, ибо в голове было лишь поверхностное представление о том, как вся эта машина будет ехать — код писался чуть ли не наугад,
Собственно код
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <windows.h>
#define undefined 2147483648
class ARRAY
{
private:
ARRAY*nextLevel;
unsigned int
*keyResult, // Здесь будет указатель на вновь создаваемый массив из двух - keyLeft, keyRight
*keyLeft, // Указатель на первый подмассив
*keyRight, // Указатель на второй подмассив
*keyTemp, // Указательно на временный подмассив
*valResult, // То же самое,
*valLeft, // но для
*valRight, // массивов
*valTemp, // значений
countResult,countLeft,countRight, // Счётчики позиции для отложенного пошагового слияния массивов 1 и 2 в массив 0 соответственно.
len;// Размерность массивов(размерность 0-го в 2 раза больше)
void upd() //пошаговое отложенное слияние двух массивов в один
{
if(keyResult)
{
if(countLeft<len)
{
if(countRight<len)
{
if(keyLeft[countLeft]<keyRight[countRight])//если текущий элемент 1-го подмассива меньше 2-го - вносим его
{
keyResult[countResult]=keyLeft[countLeft];
valResult[countResult]=valLeft[countLeft];
countResult++;
countLeft++;
}
else//если текущий элемент 2-го подмассива меньше 1-го - вносим его в массив слияния
{
keyResult[countResult]=keyRight[countRight];
valResult[countResult]=valRight[countRight];
countResult++;
countRight++;
}
}
else //значит 2-й массив уже весь перемещён и необходимо добавить сл. элемент из первого подмассива
{
keyResult[countResult]=keyLeft[countLeft];
valResult[countResult]=valLeft[countLeft];
countResult++;
countLeft++;
}
}
else
{
if(countRight<len) //значит 1-й массив уже весь перемещён - добавляем сл. элемент из второго подмассива
{
keyResult[countResult]=keyRight[countRight];
valResult[countResult]=valRight[countRight];
countResult++;
countRight++;
}
//в противном случае все элементы обоих массивов уже присутствуют в результирующем - ничего не делаем
}
if(countResult==len*2) //Если после очередного шага слияние завершилось
{
if(!nextLevel)nextLevel=new ARRAY; //Создаём сл. уровень, если он ещё не существует
nextLevel->set(keyResult,valResult,len*2);
keyResult=NULL;
keyLeft=NULL;
keyRight=NULL;
keyTemp=NULL;
valResult=NULL;
valLeft=NULL;
valRight=NULL;
valTemp=NULL;
}
}
if(nextLevel)nextLevel->upd();
}
void set(unsigned int*Key,unsigned int*Val,unsigned int Len)
{
len=Len;
if(!keyTemp){keyTemp=Key;valTemp=Val;}
else
{
keyLeft=Key;
valLeft=Val;
keyRight=keyTemp;
valRight=valTemp;
keyTemp=NULL;
valTemp=NULL;
countResult=0;
countLeft=0;
countRight=0;
keyResult=new unsigned int[len*2];
valResult=new unsigned int[len*2];
}
upd();
}
public:
~ARRAY()
{
if(keyResult)delete[]keyResult;
if(keyLeft)delete[]keyLeft;
if(keyRight)delete[]keyRight;
if(keyTemp)delete[]keyTemp;
if(valResult)delete[]valResult;
if(valLeft)delete[]valLeft;
if(valRight)delete[]valRight;
if(valTemp)delete[]valTemp;
if(nextLevel)delete nextLevel;
}
ARRAY()
{
keyResult=NULL;
keyLeft=NULL;
keyRight=NULL;
keyTemp=NULL;
valResult=NULL;
valLeft=NULL;
valRight=NULL;
valTemp=NULL;
countResult=0;
countLeft=0;
countRight=0;
len=0;
nextLevel=NULL;
}
void set(unsigned int Key,unsigned int Val)
{
unsigned int*k=new unsigned int[1];k[0]=Key;
unsigned int*v=new unsigned int[1];v[0]=Val;
set(k,v,1);
}
unsigned int get(unsigned int Key)
{
unsigned int l,r,i;
if(keyTemp)
{
l=0;r=len;
while(l!=r-1)
{
i=(l+r)/2;
if(keyTemp[i]<Key)l=i;
else if(keyTemp[i]>Key)r=i;
else return valTemp[i];
}
if(keyTemp[l]==Key)return valTemp[l];
}
if(keyLeft)
{
l=0;r=len;
while(l!=r-1)
{
i=(l+r)/2;
if(keyLeft[i]<Key)l=i;
else if(keyLeft[i]>Key)r=i;
else return valLeft[i];
}
if(keyLeft[l]==Key)return valLeft[l];
}
if(keyRight)
{
l=0;r=len;
while(l!=r-1)
{
i=(l+r)/2;
if(keyRight[i]<Key)l=i;
else if(keyRight[i]>Key)r=i;
else return valRight[i];
}
if(keyRight[l]==Key)return valRight[l];
}
if(nextLevel)return nextLevel->get(Key);
else return undefined;
}
};
void main()
{
ARRAY*arr=new ARRAY;
char inp[256];
unsigned int Key,Val;
while(gets(inp)&&inp[0])
{
if(inp[0]=='+'){Key=atoi(&inp[1]);gets(inp);Val=atoi(inp);arr->set(Key,Val);}
else if(inp[0]=='='){Key=atoi(&inp[1]);Val=arr->get(Key);if(Val!=undefined)printf("%d\n",Val);else printf("undefined\n");}
else system("cls");
}
delete arr;
}
ЗЫ:
В алгоритме не реализовано удаление, хотя некоторые
Комментарии (91)
OldFisher
02.08.2016 11:07+2ведь если добавлять новые элементы (удалять старые), то массив скажет: «ломай пересортируй меня полностью»
Массив скажет «найди нужное место и сдвинь хвост». Это тоже не сахар, но всё же намного лучше полной сортировки. У поиска сложность логарифмическая, у сдвига, очевидно, линейная плюс амортизация расширения.retYrn0
02.08.2016 11:30Спасибо за комментарии, действительно слегка спутал терминологию. Я имел в виду пересортировку случая двух уже отсортированных массивов в один — так же линейная сложность, хотя да, терминология — это не моё). Извиняюсь, первая публикация, пока не набил руку. Если необходимо, могу написать комментарии к коду, просто кода не так много и сама идея алгоритма изложена. Код — исключительно для указания на работоспособность метода.
ptyrss
02.08.2016 11:31У меня есть идея по удалению — пометить удалённым, и просто игнорировать при поиске (используя компаратор по исходным полям), при следующей пересортировке удалить (используя компаратор, который считает элемент бОльшим, если он удалён).
По поводу сложности, время на поиск — 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)
А метод достаточно оригинальный, спасибо за идею.
retYrn0
02.08.2016 11:56Спасибо за замечание по коду — действительно при редактировании видимо не то скопировал, во втором условии должен стоять 2-й счётчик. Поправил.
Удаление — действительно я так же склонялся к флагу удаления, при обновлении массива просто «перешагивать удалённое» — дело возможной будущей реализации.
Время на поиск… в моей задаче речь шла о 64-битных числах. По представлению это будет логарифмическая проверка каждого уровня массива. С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения. Исходная задача была — снизить overhead памяти при приемлемом замедлении поиска — вставки, в конкретном случае моей задачи эта структура себя оправдала и видится, что есть потенциал развивать идею дальше — собственно причина публикации. Возможно читающие увидят ещё варианты и совместными усилиями удастся сделать нечто крутое)
Асимптотика декартового дерева — действительно интересная тема обсуждения. Но опять же в моей конкретной задаче была необходимость максимального снижения overhead и тягать вероятностные параметры исключалось. И предсказуемая «реальная» сложность алгоритма всё-таки хорошо. Ведь в маловероятном случае декартово дерево всё же выродится, а здесь всё предсказуемо. Но спасибо за комментарий, есть над чем подумать.
lair
02.08.2016 12:53С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения.
Неплохое — это какое (в терминах big-O)?
retYrn0
02.08.2016 13:20По-идее это будет k*log(N). Но один из комментариев натолкнул на идею сортировки и самих массивов, тогда можно прийти к логарифмической сложности. В общем нужно думать.
lair
02.08.2016 13:23А k — это что? Ну и да, "по идее" — это, конечно, хорошо, но где реальный анализ?
retYrn0
02.08.2016 13:44K — количество уровней(аналогично с деревьями). Основной плюс — экономия памяти. Текущая версия 1.0 ну или бета и имеет куда расти(один из комментаторов подкинул идею) — можно добиться логарифмического времени, если и сами подмассивы будут отсортированы(в ближайшем будущем попытаюсь это реализовать). Реальный анализ ещё не проводился(пока нет времени), но при желании любой желающий сможет это сделать сам — работающий код приводится. Если память важнее, то каждый сам может решить, есть ли смысл. Моё дело было — подать идею на общее рассмотрение. По пути комментирования может будет создано что-то крутое, ибо здесь люди не глупее меня и если вникнуть в общие положения идеи, то наверняка смогут предложить какие-то хорошие доработки. Это скорее не алгоритм, который вытеснит деревья в принципе, а скорее вектор, по которому можно обнаружить нечто новое, надеюсь на понимание.
lair
02.08.2016 13:49+3K — количество уровней(аналогично с деревьями).
В деревьях, извините, используется h. И как зависит k от n?
Основной плюс — экономия памяти
… и какие же у вас — в терминах big-O — требования к памяти?
Реальный анализ ещё не проводился(пока нет времени), но при желании любой желающий сможет это сделать сам — работающий код приводится
Извините, но качество вашего кода таково, что делать по нему анализ нет никакого желания. Не говоря уже о том, что для таких алгоритмов обычно считают на псевдокоде.
retYrn0
02.08.2016 14:10-1Хорошо, я не заставляю никого ничего проводить. Статья ориентирована на идею. Если человек увидит в идее смысл, то без проблем реализует лучше и понятнее меня. Я алгоритмист. Если Вам не нравится код, то вы можете использовать данный класс исходя из идеологии «Чёрного ящика», и использовать ИМХО понятные методы get и set, или же просто проигнорировать. У меня было 2 варианта: просто использовать идею или поделиться соображениями с умными людьми. Я выбрал 2-е. Извините, если что-то не правильно оформил.
lair
02.08.2016 14:14+3Я алгоритмист
И что вам мешало изложить свой алгоритм в псевдокоде, как это делают в Стэнфорде?
Если человек увидит в идее смысл
Проблема в том, что сейчас увидеть смысл вашей идеи по вашему описанию весьма сложно. Я вот не осилил.
ptyrss
02.08.2016 16:38Если честно, мне этот код напомнил один из вариантов сортировки черпаком или бор. Кстати если использовать бор в лоб по основанию d(можно по основанию 2 ,10, 16 и по любому другому) то это будет Nlog(d,MAX_INT)d памяти, поиск будет происходить за log(d,MAX_INT) операций. В пределе при d --> MAX_INT мы получим обычный массив. Мне кажется это будет быстрее чем log^2(N) при N начиная уже с 10 тысяч.
kmu1990
02.08.2016 12:55А можно вставлять маркер удаления в самый недавний массив и учитывать его при сляинии с более старыми массивами… и получаем LSM дерево.
ov7a
02.08.2016 12:22+1Не развернутый ли связный список спрятан за этим поражающем понятностью кодом?
https://en.wikipedia.org/wiki/Unrolled_linked_listretYrn0
02.08.2016 12:47Нет. Здесь все подмассивы разных размеров(степени двойки) и не наблюдается закономерность: все элементы следующего подмассива меньше/больше предыдущих — это если грубо взаимо-независимые массивы. Хотя спасибо за комментарий… родилась идея использовать эти особенности развёрнутых связанных списков для ускорения поиска вплоть до логарифмической сложности.
bfDeveloper
02.08.2016 12:56+2Идея интересная, но подача… В злоупотребляете
всякими глупыми вставкамизачёркнутыми фразами. Очень утомляет и отвлекает.
ov7a
02.08.2016 13:08+1Отрефакторите, пожалуйста, код. Сейчас в таком он очень трудно читается. Можно хотя бы нормальные имена переменных сделать?
retYrn0
02.08.2016 13:26-1Там всего 4 типа имен: key, val,i,nxt.
Key(0,1,2,3) — подмассивы ключей,
Val(0,1,2,3) — подмассивы значений,
i(0,1,2) — счётчики позиций слияния для отложенного пошагового слияния,
nxt — ссылка на следующий уровень…
Простите, подскажите какие имена поменять, ибо мне казалось имена соответствуют…ov7a
02.08.2016 13:30+2Почему читатель должен помнить, что 0 — это результат, 1 и 2 — это части, а 3 — это временное хранилище?
retYrn0
02.08.2016 13:46-1Вы правы, не должен. Подскажите на что — мне не сложно заменить.
ov7a
02.08.2016 13:56+2Например, key_result, key_left, key_right, key_temp. Вы же создатель кода, вы должны лучше знать, как все должно называться
И кстати, негоже указатели инициализировать нулем, когда есть nullptr или хотя бы NULL.
retYrn0
02.08.2016 14:29Отрефакторил.
Norraxx
03.08.2016 01:23+2Здравствуйте, прочитал Вашу статью. Попытался прочитать код. Идея интересная. Но я хочу поделиться опытом (на|о)писания кода.
Первое:
Всегда наперед напишите «сказку», которую код должен делать, например алгоритм в пунктах.
1. открою это, 2. запишу туда, 3. итд…
А после у каждого метода, который отвечает за конкретный пункт тоже самое, тем самым дробя логику написанного программного кода.
В последствии не понадобиться всматриваться в код.
Второе:
Сделайте код самоописуемым. Когда бы вы проснулись после пъянки и посмотрели, глянули на строчку 69 и увидели написанное, сразу поняли:
ко второму пивоту, который отвечает за нахождение в том-то массиве причетаем +1, потому-что тото и тото…
Третье:
l=0;r=len; <<< это буквы без смысла и значения. Не используйте переменные короче 3 букв, сейчас они для вас понятны, завтра сами запутаетесь.
Четвёртое:
Делите логику. Не обязательно, что-бы был один большой метод, который делает всё. Дробите его.
retYrn0
03.08.2016 11:14-2Спасибо за лаконичные и справедливые замечание и пожелания, буду стремиться, но эту статью писал в режиме обеда на работе и не было времени более тщательно подойти к написанию. Да и очень хотелось поделиться идеей.
Deosis
03.08.2016 08:50+2О качестве кода говорит тот факт, что после рефакторинга в счетчики пишется NULL.
При этом идея выглядит так, будто вы создали Франкенштейна из массивов, деревьев и сортировки слиянием.
Попробуйте описать результат после вставки 3 элементов в пустое хранилище в виде диаграмм. Это более наглядно.
Так же около 10 указателей в узле непохоже на уменьшение оверхеда по памяти.retYrn0
03.08.2016 11:12NULL — это да. Ох уж эта автозамена)
По-поводу Франкенштейна — в точку. В статье написано, что пока писал код, то иногда действовал чуть ли не наугад, ибо идея плавала на поверхности и я сам не о конца понимал как это работает — многовато разного нужно было держать в памяти — это слегка сложнее реализации уже готовых алгоритмов, но вообще согласен. В следующей статье, когда буду описывать оптимизацию бинарного поиска, постараюсь учесть все пожелания комментаторов.
А на счёт 10 указателей — это Вы зря. Они не значимы в пересчёте оверхеада, потому что каждый новый массив-уровень будет содержать в 2 раза больше элементов, чем предыдущий, а количество указателей при этом не изменится.
augur
02.08.2016 14:50+3Оригинальный стиль изложения, интересная идея, но где самое вкусное — реальные замеры производительности в сравнении с классическими структурами?
retYrn0
03.08.2016 11:21Эта структура пока не закончена — это одна из идей. Сейчас я собираюсь реализовать несколько оптимизации, в т.ч. бинарного поиска и ещё парочку, о чём, по-возможности, напишу здесь статьи и в конце планирую написать статью, объединяющую все идеи в конечную структуру. Все сравнения-замеры обязательно будут проведены когда идея примет более полный вид. Я не жалею, что написал эту сыроватую статью, ибо умные люди здесь навели меня на целых 3 идеи по дальнейшему развитию структуры да и ценные комментарии по-поводу оформления статьи мне будут крайне полезны.
Videoman
03.08.2016 11:24Интересная идея. А не похожа ли ваша структура на B-tree где порядок вершин не задан жестко а меняется как 1, 2, 4, 8 и т.д., в зависимости от уровня?
Т.е. листья имеют по одному элементу и при росте дерева и появления нового уровня, корень становится в два раза больше.Videoman
03.08.2016 11:38Кстати, может я и не прав, но у меня получается оценка сложности O(N^2) вот из каких соображений:
допустим у нас есть пустая структура и мы начинаем добавлять элементы:
1 — элемент O(1). Здесь мы не сортируем и экономим по сложности.
2 — элемент O(1). Здесь мы создаем двумерный массив и делаем слияние. Это сортировка со сложностью O(N).
Теперь, допустим, мы добавляем еще два элемента. Получаем два двумерных массива, каждый за O(N). Но теперь мы должны из них создать массив из четырех элементов что будет тоже O(N). Получается O(N * O(N)) = O(N^2).retYrn0
04.08.2016 17:37Не-не-не. Именно поэтому слияние не просто отложенное, но ещё и пошаговое. Один шаг выполняет добавление в создаваемый массив всего ОДНОГО элемента из 2-х массивов, в зависимости от того, какой очередной элемент меньше — так нагрузка распределяется.
Videoman
04.08.2016 17:49Ну тогда O(N) будет, или я опять не понял? Вы не могли бы, еще раз по шагам расписать как происходит добавление в пустую структуру. По коду просто очень тяжело понять.
retYrn0
04.08.2016 19:04O(N) было бы, если бы мы при каждой вставке производили слияние, но мы хитрее. Мы дожидаемся пока оба сливаемых массива полностью заполнены(предполагая, что они изменяться не будут) и только после этого начинаем слияние — создаём массив в 2 раза больших размеров и начинаем процесс слияния пошагово — по одному элементу за раз из одного из под массивов. А каждый шаг запускается при вставке нового элемента.
Для первых вставок:
1. Вставляем элемент первый одноэлементный массив.
2. Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
За одну вставку в результирующие массивы каждого уровня будет вставляться по одному элементу.lair
05.08.2016 00:41- Вставляем элемент первый одноэлементный массив.
1 операция.
- Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
+2 операции.
3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
На третьем шаге: +3 операции (сначала слияние внутри стартового уровня, потом создание следующего уровня, потом создание нового элемента в стартовом уровне).
На четвертом шаге: +2 операции (как на втором).
На пятом шаге: +6 операций (слияние, пересылка на следующий уровень, слияние там, еще одно слияние там, простановка значения на этом уровне, еще одно слияние на следующем уровне).
Итого я насчитал 14 операций на пять шагов. И из динамики выглядит так, что это будет расти нифига не линейно, и даже не логарифмически (потому что по мере продвижения вперед количество слияний на одну операцию будет вырастать вместе с "глубиной" конструкции).
А еще хочу заметить, что у вас двухкратный расход памяти, потому что пока данные не перенесены в следующий уровень, они хранятся одновременно в
result,leftиright.
PS Так напомните, какая у вас сложность поиска?
retYrn0
05.08.2016 01:11Насчёт двойного расхода памяти я в курсе. В дереве тройное-четверное для аналогичных типов данных.
Не слияние, а шаг слияния — это копирование одного значения. В деревьях для балансировки при вставке происходят «повороты», не считали сколько это?
Линейно — это же вроде хуже, чем логарифмически… в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?lair
05.08.2016 01:14Насчёт двойного расхода памяти я в курсе. В дереве тройное-четверное для аналогичных типов данных.
Откуда?
Линейно — это же вроде хуже, чем логарифмически…
Я имел в виду n log n, типичное для операций сортировки.
в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?
Это так не выглядит.
retYrn0
05.08.2016 01:25Откуда… мы храним ключ — 4 байт + значение — 4 байта + 2 ссылки на лево-право + балансирующий параметр, иногда родителя хранят. Здесь только ключ и значение, хотя, конечно, в 2 местах.
Слияние происходит по одному элементу на каждом уровне за одну вставку и происходит оно только после того, как оба подмассива полностью заполнены. Результирующий массив отправляется на уровень ниже и просто висит там, пока в этот уровень не придёт ещё один аналогичный по размеру массив. На 1 уровне 2 одноэлементных массива. На втором — 2 двухэлементных. На третьем 2 четырёх элементных. С каждым уровнем размерность массива удваивается относительно предыдущего. Если бы размерность не менялас, то для чего бы я вводил свойство класса len?lair
05.08.2016 01:29Здесь только ключ и значение, хотя, конечно, в 2 местах.
И вот тут возникает вопрос, что больше — ссылки, или ключи/значения. Впрочем ладно, будем считать, что убедили.
Слияние происходит по одному элементу на каждом уровне за одну вставку
Нет. Когда у вас начинает заполняться следующий уровень, слияние на нем вызывается больше одного раза за вставку на верхний уровень, и дальше это распространяется на каждый следующий уровень тоже.retYrn0
05.08.2016 01:39Так скорее всего может показаться из-за того, что для наглядности я вызываю upd с каждой вставкой. Но первое условие проверяет готов ли массив к слиянию — если под result память не выделена, то пытаемся спустится на уровень ниже, но здесь ничего не произойдёт.
lair
05.08.2016 01:42если под result память не выделена, то пытаемся спустится на уровень ниже, но здесь ничего не произойдёт.
На уровень ниже вы спускаетесь всегда, когда он есть (а это дважды за вставку на этом уровне), и если там память под result выделена, то там будет два слияния безотносительно состояния текущего уровня, и в любом случае будет переход на уровень еще ниже (конечно, если он есть), далее аналогично.
retYrn0
05.08.2016 02:00Да, при вставке нового значение происходит по шагу слияния на каждом уровне. — Что и при вставке в дерево, когда нужно перебалансировать его и поэтому мы делаем повороты «всплывая» или наоборот. В этом случае наоборот.
lair
05.08.2016 02:09Корректировка деревьев происходит не на каждом шаге, и стоимость каждой корректировки ограничена O(log n).
retYrn0
05.08.2016 02:34А здесь на каждом шаге, но тоже логарифм, ибо нужно сделать по одному шагу слияния на каждый уровень, а количество уровней, как и в дереве, описывается логарифмом.
lair
05.08.2016 02:34А здесь на каждом шаге, но тоже логарифм, ибо нужно сделать по одному шагу слияния на каждый уровень,
А по одному ли?
retYrn0
05.08.2016 02:47«На всякий случай» я делаю по 2(не помню, сейчас вот удалил нижний upd() — тоже работает), но с точки зрения алгоритма достаточно одного.
По примеру — внесли 16 элементов (2 по 8) и полностью досортированный результирующий массив (1 по 16) нам понадобится когда насобираем ещё 16 элементов. На самом деле нам не хватает одного шага слияния, ведь когда придёт 16-й элемент, оба 8-ми элементных массива уже должны быть пусты, а 16-ти элементный должен быть на сл. уровне, но на 16 шаге перенос указателя на сл.уровень ещё не произойдёт, поэтому 1 дополнительное слияние мы делаем ещё и в момент создания временного массива.lair
05.08.2016 02:49+1«На всякий случай» я делаю по 2(не помню, сейчас вот удалил нижний upd() — тоже работает), но с точки зрения алгоритма достаточно одного.
Вот именно поэтому и надо писать в псевдокоде и объяснять каждый шаг. Нет никакого "всякого случая", когда вы оптимизируете под производительность.
retYrn0
05.08.2016 03:07-2Так и поступлю, если решу ещё две структуры описать. Хотя сложно утверждать. Я понимаю, что в основном критика уместна, но когда ты бесплатно описываешь то, над чем ломал голову кучу времени, а тебя не поняли, «переменные не так назвал», замеры делай — не весело, лень берёт верх)
Sirikid
05.08.2016 05:24+2Когда тебе говорят «быстрее, дешевле», но не показывают результаты бенчмарков это странно.
retYrn0
05.08.2016 11:12Это как с телевизором: не хочешь смотреть рекламу — выключи телевизор. Но давайте на секунду предположим, что алгоритм хорош. И после такого шквала наездов я что-то кому-то должен доказывать? Ну не знаю. Мне кажется это не целесообразные потуги. А цели своей я добился некоторые люди заинтересовались идеей.
ov7a
05.08.2016 11:06Для бесплатного изложения потока мыслей есть личные бложики, контактик и т.п. Хабр все-таки позиционируется как технический ресурс, где присутствуют специалисты. И вы бесплатно получаете фидбэк и обмен идеями, обсуждение вашей идеи, поиск косяков в ней и т.п. Если вас не поняли из-за кошмарного кода и невнятных объяснений, вы имеете полное право обидеться и уйти, но вы подумайте об этом с другой стороны: чем больше человек поймет вашу идею, тем больше шансов получить на нее отклик и больше шансов ее улучшить. Если вы ее реально используете в коде, то вы забесплатно получите улушение своего кода.
lair
05.08.2016 01:50Откуда… мы храним ключ — 4 байт + значение — 4 байта + 2 ссылки на лево-право + балансирующий параметр, иногда родителя хранят. Здесь только ключ и значение, хотя, конечно, в 2 местах.
Зато есть занятное встречное наблюдение: для вашего решения нужна память последовательными кусками. Для дерева — нет.
retYrn0
05.08.2016 02:06Идеально для файловых структур, когда в пределах одного кластера может находится куча актуальных данных)
retYrn0
05.08.2016 02:08Для файлов в деревьях специально группирую сразу несколько значений внутри ноды, чтобы за одно чтение можно было больше пользы получить. B-tree вроде.
retYrn0
05.08.2016 01:49Почему не выглядит если вот же — результирующий массив в 2 раза больше обоих исходных. После заполнения мы его пробрасываем в сл. уровень. Там происходит то же самое, только len там удвоенная от первоначального…
keyResult=new unsigned int[len*2];
valResult=new unsigned int[len*2];lair
05.08.2016 01:52Почему не выглядит если вот же — результирующий массив в 2 раза больше обоих исходных. После заполнения
Потому что его заполнение тоже стоит вам операций, количество которых накапливается с глубиной.
retYrn0
05.08.2016 02:29массив 1: 2 4 6 8
массив 2: 1 3 5 7
Один шаг слияния — это когда мы берём одно значение из массива 1 или 2 в зависимости от того какой текущий элемент сравнения меньше. За один шаг в результирующий массив дописывается только одно значение из уж сформированных отсортированных массивов. Не слияние в принципе, а только один шаг — одно значение.
Пример.
Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты, в 4-м содержится 2 полностью заполненных и отсортированных 8-ми элементных массива. Чтобы слить их в 16-ти элементный массив, необходимо 16 шагов слияния. А сколько нужно вписать новых элементов, чтобы получить новый уровень — тоже 16. В этом и состоит отложеность слияния.lair
05.08.2016 02:41Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты,
А вот и нет. На первом уровне — все массивы заполнены (полезной информации — два элемента), на всех последующих — заполнены
temp(2, 4 и 8 элементов соответственно). Суммарно 16, что логично. И к этому моменту мы уже сделали 35 шагов слияния (85 операций всего).retYrn0
05.08.2016 02:54То есть «нет»?) По логике моего алгоритма — да…
lair
05.08.2016 02:59А по факту выполнения — нет. Я просто встал в дебаггере и показал вам, что получается. Когда вставляется 16 элемент, в первом уровне заполнен
temp, мы перемещаем его вright, новый элемент идет вleft. Теперь мы аллоцируемresultи вызываемupd— который передвинет один элемент (leftилиright) вresult. Посколькуresultне полон, его передача на следующий уровень не случится.
(Лишний аргумент в пользу строгого псевдокода)
retYrn0
05.08.2016 03:10странно. Надо будет глянуть что там происходит…
lair
05.08.2016 03:11+1Просто если вы не понимаете даже состояние своей структуры данных на n-ом шаге, как вы делаете утверждения о ее алгоритмической сложности?
retYrn0
05.08.2016 04:57-1А для определения сложности нужно понимать состояние структуры на n-ом шаге?..
Достаточно критики, надоело уже. Всё до безумия просто — не используйте эту структуру, если не нравится. А я вижу в ней потенциал и буду развивать дальше.lair
05.08.2016 09:42+1Нужно, конечно. Иначе исходя из чего вы оцениваете потребление ресурсов?
Ну и да, я уже давно не пишу/использую кастомные коллекции данных, если нет сильного обоснования: встроенных хватает практически на любой случай.
retYrn0
05.08.2016 11:00На каждом уровне по одному массиву слияния. Шаг слияния — одна операция(сравнение и копирование). Для полноценной работы алгоритма достаточно делать по одному шагу слияния на вставку для каждого уровня. А количество уровней логарифмическое, так как каждый следующий уровень в 2 раза больше предыдущего. Исходя из этого — сложность должна быть логарифмической.
lair
05.08.2016 11:37Не сходится. На 16 внесенных значений (четыре уровня) сделано 35 слияний, это больше чем четыре слияния на вставку. Это ваш реальный код.
retYrn0
05.08.2016 02:31При каждом добавлении элемента мы плавно пошагово готовим все уровни по одному значению на уровень.
lair
05.08.2016 01:25Я тут малость переписал вашу программу на 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, 1896699
WA считает, что это полиномиальная зависимость.
retYrn0
05.08.2016 01:13И опять же, здесь двойной расход памяти — худший случай. А лучший случай — +1 временное пустое. А в дереве оверхед на ссылки-балансирующие данные гарантированы.
lair
05.08.2016 01:14И опять же, здесь двойной расход памяти — худший случай.
Не худший, а возникающий с заданной периодичностью.
retYrn0
05.08.2016 01:28Заданная периодичность звучит будто через каждые N вставок. Но тут опять же логарифмическая зависимость. А так да, появление этого случая предсказуемо.
lair
05.08.2016 01:31Заданная периодичность звучит будто через каждые N вставок.
Так и есть. После каждых двух вставок на первом уровне будут аллоцированы все массивы.
retYrn0
05.08.2016 01:46Аллоцированы все массивы? Каждую вторую вставку? Аллоцированы будут все 2 массива следующего уровня каждую вторую вставку. А следующего — каждую его вторую вставку, но так как в него вставка происходит через раз, то это каждая четвёртая вставка, 3 уровень — восьмая и остальные степени двойки.
lair
05.08.2016 01:49Аллоцированы все массивы? Каждую вторую вставку?
Да, на первом уровне.
А следующего — каждую его вторую вставку, но так как в него вставка происходит через раз, то это каждая четвёртая вставка
Но и массивы там в два раза больше. Поэтому потребление памяти будет описываться суммой периодических функций, каждая "в два раза больше" (как по амплитуде, так и по периоду) предыдущей.
retYrn0
05.08.2016 01:55Я к тому, что когда у нас заполнены пусть 5 уровней, пара лишних одноэлементных массива не слишком тянут на худший перерасход памяти. В принципе вы правы, просто я исхожу относительно текущего N.
lair
05.08.2016 03:25Так напомните, какая у вас сложность поиска?
Так вот, сложность поиска — это сумма сложностей поиска на каждом уровне. Те, в свою очередь, логарифмичны, но проблема в том, что сумма логарифмов — это не логарифм суммы, а логарифм произведения.
lair
05.08.2016 03:43… что, вкупе с геометрической прогрессией размеров, дает нам чуть ли не O(sqrt(n)) время поиска в худшем случае (что стабильно больше логарифма). Выглядит дико, конечно, я практически уверен, что налажал в преобразованиях.
- Вставляем элемент первый одноэлементный массив.
retYrn0
04.08.2016 19:07То есть слияние первых двух значений полностью завершиться только при вставке следующих двух значений. И что ещё важно — вставка всегда происходит в «голову» структуры, поэтому поиск последних добавленных будет всегда быстрее «старых» значений.
retYrn0
03.08.2016 11:34Я вообще считаю, что люди не умеют придумывать ничего нового, только брать немного там, немного там и объединять во что-то, чего ещё не было.
Согласен, общие черты есть. Хотя отталкивался не от B-деревьев, а от обычных отсортированных массивов. В любых бинарных деревьях может быть 2 указателей на такую-же структуру, а здесь только один.
Хотя это тоже натолкнуло на мысль, спасибо) Предположим мы реализуем B-tree с порядками-степенями двойки, зависящими от уровня — это может быть даже лучше. Но мне не попадались статьи, где описывалось подобное использование B-tree, или они есть?
lair
05.08.2016 02:55Впрочем, я понял, что меня тут всю дорогу смущало. Ваш код не может быть альтернативой бинарному дереву поиска, потому что на нем нельзя выбрать диапазон; следовательно, сравнивать его надо с key-value структурами — читай, хэш-таблицами с их O(1) на операцию (и существенно меньшей памятью).
(BTW, в случае, когда на уровне заполнены
result,leftиright, а элемент не входит в этот уровень, стоимость прохода уровня приgetувеличивается вдвое)lair
05.08.2016 03:47BTW, в случае, когда на уровне заполнены result, left и right, а элемент не входит в этот уровень, стоимость прохода уровня при get увеличивается вдвое
Неправ, нет такого кейса.
lair
Угу.