SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Вступление


Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.

Что не так с деревом?


Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).

А почему не сортированные массивы?


Бинарный поиск в отсортированном массиве реализуется с той же логарифмической сложностью, что и в бинарном дереве поиска, но нет необходимости тягать за собой ссылки на меньшие-большие поддеревья, как в двоичном дереве поиска.

Но что же не так с сортированными массивами?

Да всё так, можно заканчивать статью и использовать сортированные массивы вместо бинарных деревьев поиска радоваться сэкономленным ресурсам, если только нам не нужно добавлять-удалять элементы из такого массива, ведь если добавлять новые элементы (удалять старые), то массив скажет: "ломай пересортируй меня полностью". Но беда сортировки в том, что она медленная, если нужно вставить новый элемент где-то между остальными, тем более в начало.

Но есть и идеальный случай — когда новый элемент больше остальных и его достаточно просто дописать в конец. Это идеально — всего одна операция, но вероятностная оценка такого идеального случая заставляет нас использовать бинарные деревья или хеш-таблицы, или огромное множество других действительно красивых и хитроумных механизмов. Исходя из теории вероятности, такая ситуация редкая — только если все элементы добавляются в массив по-возрастанию (ирония-аналогия с бинарным деревом поиска, когда отсортированные входные данные как раз являются наихудшим случаем с вырождением дерева в связанный список с линейной сложностью).

Частный случай, как закономерность?


Но давайте рассмотрим массив всего из одного элемента. Не важно, какое значение вносится — оно всегда вписывается в начало пустого до этого массива и одно-элементный массив, естественно, всегда отсортирован. А если мы захотим вписать 2-й элемент в нашу структуру данных? Давайте просто создадим ещё один одно-элементный массив и получим два отсортированных одно-элементных массива. Получить новый отсортированный массив из двух отсортированных — простая задача, хотя не очень быстрая… Но в таком случае нам уже нужно сортировать массив не при каждой вставке, а при каждой второй вставке. Мы используем «отложенную сортировку».

А если мы хотим внести больше 2-х элементов? Хотеть-не вредно — запишем новый 2-х элементный массив куда-то и продолжим вносить элементы в одно-элементные массивы и так же на 4-м элементе у нас появится 2 2-х элементных отсортированных массива, которые мы точно так же сможем объединить в один 4-х элементный и так далее, пока не выскочит синий экран смерти и взрыв процессора с попутным образованием чёрной дыры, втягивающей в себя всё окружающее пространство-время (что-то меня понесло...) пока нам это позволит память.

Распределение нагрузки


Понятно, что этот алгоритм уже значительно сокращает количество сортировок, относительно сортировки обычного массива, ведь первый уровень массивов нужно сортировать через раз, 2-й уровень — каждую 4-ю вставку, 3-й уровень — каждую 8-ю вставку — собственно, это логарифмическая сложность.

На этом можно было бы успокоиться, но это для слабаков попробуем распределить нагрузку при каждой вставке равномерно, дополнив нашу «отложенную сортировку» пошаговостью и выполняя каждый шаг при вставке очередного элемента для всех уровней — это позволит равномерно распределить нагрузку на все вставки — что и требуется.

Поиск


Поиск представляет из себя классический бинарный поиск по отсортированному массиву с той лишь разницей, что здесь массивов много и искать необходимо по-очереди по всем. Поэтому логарифмичность сложности поиска оспариваема(если не ошибаюсь, это удвоенная логарифмическая сложность). Но в поставленной задаче это вполне приемлемо, учитывая сэкономленную память.

Реализация


Пока закипал чайник, я вспомнил, что хотел ещё написать, но потом чайник закипел и его свист заставил меня обратно забыть то, что я хотел ещё написать…

Реализация была достаточно запутанной, ибо в голове было лишь поверхностное представление о том, как вся эта машина будет ехать — код писался чуть ли не наугад, поэтому пойду посплю с горя, в то же время программная структура алгоритма класса содержит всего 3 метода, (не считая конструктора и деструктора). Код не содержит ничего кроме работы с массивами, циклов и ООП-идеологии — всё до гениальности безумия просто и, я надеюсь, понятно.

Собственно код


#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;
}


ЗЫ:
В алгоритме не реализовано удаление, хотя некоторые эротические фантазии есть. Но это уже отдельная статья. Здесь же я попытался по умничать донести саму идею и если у кого-то есть свои мысли по реализации удаления — велком. Хотя на самом деле данная структура разрабатывалась для специфической задачи, не требующей удаления да и вообще ничего кроме быстрой вставки и быстрого поиска, появилось желание доработать класс, реализовав прочие, часто нужные в повседневной жизни работе методы, чем и займусь когда рак на горе свиснет — нибудь.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 91

    +10
    я не использую никаких комментариев в коде — там всё достаточно просто и не содержит ничего кроме работы с массивами, циклов и ООП-идеологии — всё до безумия просто.

    Угу.


    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++;}
      +2
      ведь если добавлять новые элементы (удалять старые), то массив скажет: «ломай пересортируй меня полностью»

      Массив скажет «найди нужное место и сдвинь хвост». Это тоже не сахар, но всё же намного лучше полной сортировки. У поиска сложность логарифмическая, у сдвига, очевидно, линейная плюс амортизация расширения.
        0
        Спасибо за комментарии, действительно слегка спутал терминологию. Я имел в виду пересортировку случая двух уже отсортированных массивов в один — так же линейная сложность, хотя да, терминология — это не моё). Извиняюсь, первая публикация, пока не набил руку. Если необходимо, могу написать комментарии к коду, просто кода не так много и сама идея алгоритма изложена. Код — исключительно для указания на работоспособность метода.
        0

        У меня есть идея по удалению — пометить удалённым, и просто игнорировать при поиске (используя компаратор по исходным полям), при следующей пересортировке удалить (используя компаратор, который считает элемент бОльшим, если он удалён).


        По поводу сложности, время на поиск — 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)

        А метод достаточно оригинальный, спасибо за идею.

          0
          Спасибо за замечание по коду — действительно при редактировании видимо не то скопировал, во втором условии должен стоять 2-й счётчик. Поправил.
          Удаление — действительно я так же склонялся к флагу удаления, при обновлении массива просто «перешагивать удалённое» — дело возможной будущей реализации.
          Время на поиск… в моей задаче речь шла о 64-битных числах. По представлению это будет логарифмическая проверка каждого уровня массива. С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения. Исходная задача была — снизить overhead памяти при приемлемом замедлении поиска — вставки, в конкретном случае моей задачи эта структура себя оправдала и видится, что есть потенциал развивать идею дальше — собственно причина публикации. Возможно читающие увидят ещё варианты и совместными усилиями удастся сделать нечто крутое)
          Асимптотика декартового дерева — действительно интересная тема обсуждения. Но опять же в моей конкретной задаче была необходимость максимального снижения overhead и тягать вероятностные параметры исключалось. И предсказуемая «реальная» сложность алгоритма всё-таки хорошо. Ведь в маловероятном случае декартово дерево всё же выродится, а здесь всё предсказуемо. Но спасибо за комментарий, есть над чем подумать.
            0
            С учётом того, что каждый предыдущий уровень содержит в 2 раза меньше элементов — так же логарифмическая закономерность, то видится достаточно не плохое время выполнения.

            Неплохое — это какое (в терминах big-O)?

              0
              По-идее это будет k*log(N). Но один из комментариев натолкнул на идею сортировки и самих массивов, тогда можно прийти к логарифмической сложности. В общем нужно думать.
                0

                А k — это что? Ну и да, "по идее" — это, конечно, хорошо, но где реальный анализ?

                  0
                  K — количество уровней(аналогично с деревьями). Основной плюс — экономия памяти. Текущая версия 1.0 ну или бета и имеет куда расти(один из комментаторов подкинул идею) — можно добиться логарифмического времени, если и сами подмассивы будут отсортированы(в ближайшем будущем попытаюсь это реализовать). Реальный анализ ещё не проводился(пока нет времени), но при желании любой желающий сможет это сделать сам — работающий код приводится. Если память важнее, то каждый сам может решить, есть ли смысл. Моё дело было — подать идею на общее рассмотрение. По пути комментирования может будет создано что-то крутое, ибо здесь люди не глупее меня и если вникнуть в общие положения идеи, то наверняка смогут предложить какие-то хорошие доработки. Это скорее не алгоритм, который вытеснит деревья в принципе, а скорее вектор, по которому можно обнаружить нечто новое, надеюсь на понимание.
                    +3
                    K — количество уровней(аналогично с деревьями).

                    В деревьях, извините, используется h. И как зависит k от n?


                    Основной плюс — экономия памяти

                    … и какие же у вас — в терминах big-O — требования к памяти?


                    Реальный анализ ещё не проводился(пока нет времени), но при желании любой желающий сможет это сделать сам — работающий код приводится

                    Извините, но качество вашего кода таково, что делать по нему анализ нет никакого желания. Не говоря уже о том, что для таких алгоритмов обычно считают на псевдокоде.

                      –1
                      Хорошо, я не заставляю никого ничего проводить. Статья ориентирована на идею. Если человек увидит в идее смысл, то без проблем реализует лучше и понятнее меня. Я алгоритмист. Если Вам не нравится код, то вы можете использовать данный класс исходя из идеологии «Чёрного ящика», и использовать ИМХО понятные методы get и set, или же просто проигнорировать. У меня было 2 варианта: просто использовать идею или поделиться соображениями с умными людьми. Я выбрал 2-е. Извините, если что-то не правильно оформил.
                        +3
                        Я алгоритмист

                        И что вам мешало изложить свой алгоритм в псевдокоде, как это делают в Стэнфорде?


                        Если человек увидит в идее смысл

                        Проблема в том, что сейчас увидеть смысл вашей идеи по вашему описанию весьма сложно. Я вот не осилил.

              0

              Если честно, мне этот код напомнил один из вариантов сортировки черпаком или бор. Кстати если использовать бор в лоб по основанию d(можно по основанию 2 ,10, 16 и по любому другому) то это будет Nlog(d,MAX_INT)d памяти, поиск будет происходить за log(d,MAX_INT) операций. В пределе при d --> MAX_INT мы получим обычный массив. Мне кажется это будет быстрее чем log^2(N) при N начиная уже с 10 тысяч.

              0
              А можно вставлять маркер удаления в самый недавний массив и учитывать его при сляинии с более старыми массивами… и получаем LSM дерево.
              +1
              Не развернутый ли связный список спрятан за этим поражающем понятностью кодом?
              https://en.wikipedia.org/wiki/Unrolled_linked_list
                0
                Нет. Здесь все подмассивы разных размеров(степени двойки) и не наблюдается закономерность: все элементы следующего подмассива меньше/больше предыдущих — это если грубо взаимо-независимые массивы. Хотя спасибо за комментарий… родилась идея использовать эти особенности развёрнутых связанных списков для ускорения поиска вплоть до логарифмической сложности.
                +2
                Идея интересная, но подача… В злоупотребляете всякими глупыми вставками зачёркнутыми фразами. Очень утомляет и отвлекает.
                  +1
                  Отрефакторите, пожалуйста, код. Сейчас в таком он очень трудно читается. Можно хотя бы нормальные имена переменных сделать?
                    –1
                    Там всего 4 типа имен: key, val,i,nxt.
                    Key(0,1,2,3) — подмассивы ключей,
                    Val(0,1,2,3) — подмассивы значений,
                    i(0,1,2) — счётчики позиций слияния для отложенного пошагового слияния,
                    nxt — ссылка на следующий уровень…
                    Простите, подскажите какие имена поменять, ибо мне казалось имена соответствуют…
                      +2
                      Почему читатель должен помнить, что 0 — это результат, 1 и 2 — это части, а 3 — это временное хранилище?
                        –1
                        Вы правы, не должен. Подскажите на что — мне не сложно заменить.
                          +2
                          Например, key_result, key_left, key_right, key_temp. Вы же создатель кода, вы должны лучше знать, как все должно называться

                          И кстати, негоже указатели инициализировать нулем, когда есть nullptr или хотя бы NULL.
                        0
                        Отрефакторил.
                          +2
                          Здравствуйте, прочитал Вашу статью. Попытался прочитать код. Идея интересная. Но я хочу поделиться опытом (на|о)писания кода.

                          Первое:
                          Всегда наперед напишите «сказку», которую код должен делать, например алгоритм в пунктах.
                          1. открою это, 2. запишу туда, 3. итд…
                          А после у каждого метода, который отвечает за конкретный пункт тоже самое, тем самым дробя логику написанного программного кода.
                          В последствии не понадобиться всматриваться в код.

                          Второе:
                          Сделайте код самоописуемым. Когда бы вы проснулись после пъянки и посмотрели, глянули на строчку 69 и увидели написанное, сразу поняли:
                          ко второму пивоту, который отвечает за нахождение в том-то массиве причетаем +1, потому-что тото и тото…

                          Третье:
                          l=0;r=len; <<< это буквы без смысла и значения. Не используйте переменные короче 3 букв, сейчас они для вас понятны, завтра сами запутаетесь.

                          Четвёртое:
                          Делите логику. Не обязательно, что-бы был один большой метод, который делает всё. Дробите его.

                            –2
                            Спасибо за лаконичные и справедливые замечание и пожелания, буду стремиться, но эту статью писал в режиме обеда на работе и не было времени более тщательно подойти к написанию. Да и очень хотелось поделиться идеей.
                            +2
                            О качестве кода говорит тот факт, что после рефакторинга в счетчики пишется NULL.

                            При этом идея выглядит так, будто вы создали Франкенштейна из массивов, деревьев и сортировки слиянием.
                            Попробуйте описать результат после вставки 3 элементов в пустое хранилище в виде диаграмм. Это более наглядно.

                            Так же около 10 указателей в узле непохоже на уменьшение оверхеда по памяти.
                              0
                              NULL — это да. Ох уж эта автозамена)
                              По-поводу Франкенштейна — в точку. В статье написано, что пока писал код, то иногда действовал чуть ли не наугад, ибо идея плавала на поверхности и я сам не о конца понимал как это работает — многовато разного нужно было держать в памяти — это слегка сложнее реализации уже готовых алгоритмов, но вообще согласен. В следующей статье, когда буду описывать оптимизацию бинарного поиска, постараюсь учесть все пожелания комментаторов.
                              А на счёт 10 указателей — это Вы зря. Они не значимы в пересчёте оверхеада, потому что каждый новый массив-уровень будет содержать в 2 раза больше элементов, чем предыдущий, а количество указателей при этом не изменится.
                          +3

                          Оригинальный стиль изложения, интересная идея, но где самое вкусное — реальные замеры производительности в сравнении с классическими структурами?

                            0
                            Эта структура пока не закончена — это одна из идей. Сейчас я собираюсь реализовать несколько оптимизации, в т.ч. бинарного поиска и ещё парочку, о чём, по-возможности, напишу здесь статьи и в конце планирую написать статью, объединяющую все идеи в конечную структуру. Все сравнения-замеры обязательно будут проведены когда идея примет более полный вид. Я не жалею, что написал эту сыроватую статью, ибо умные люди здесь навели меня на целых 3 идеи по дальнейшему развитию структуры да и ценные комментарии по-поводу оформления статьи мне будут крайне полезны.
                            0
                            Интересная идея. А не похожа ли ваша структура на B-tree где порядок вершин не задан жестко а меняется как 1, 2, 4, 8 и т.д., в зависимости от уровня?
                            Т.е. листья имеют по одному элементу и при росте дерева и появления нового уровня, корень становится в два раза больше.
                              0
                              Кстати, может я и не прав, но у меня получается оценка сложности O(N^2) вот из каких соображений:
                              допустим у нас есть пустая структура и мы начинаем добавлять элементы:
                              1 — элемент O(1). Здесь мы не сортируем и экономим по сложности.
                              2 — элемент O(1). Здесь мы создаем двумерный массив и делаем слияние. Это сортировка со сложностью O(N).
                              Теперь, допустим, мы добавляем еще два элемента. Получаем два двумерных массива, каждый за O(N). Но теперь мы должны из них создать массив из четырех элементов что будет тоже O(N). Получается O(N * O(N)) = O(N^2).
                                0
                                Не-не-не. Именно поэтому слияние не просто отложенное, но ещё и пошаговое. Один шаг выполняет добавление в создаваемый массив всего ОДНОГО элемента из 2-х массивов, в зависимости от того, какой очередной элемент меньше — так нагрузка распределяется.
                                  0
                                  Ну тогда O(N) будет, или я опять не понял? Вы не могли бы, еще раз по шагам расписать как происходит добавление в пустую структуру. По коду просто очень тяжело понять.
                                    0
                                    O(N) было бы, если бы мы при каждой вставке производили слияние, но мы хитрее. Мы дожидаемся пока оба сливаемых массива полностью заполнены(предполагая, что они изменяться не будут) и только после этого начинаем слияние — создаём массив в 2 раза больших размеров и начинаем процесс слияния пошагово — по одному элементу за раз из одного из под массивов. А каждый шаг запускается при вставке нового элемента.
                                    Для первых вставок:
                                    1. Вставляем элемент первый одноэлементный массив.
                                    2. Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).
                                    3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.
                                    За одну вставку в результирующие массивы каждого уровня будет вставляться по одному элементу.
                                      0
                                      :) А можно пример для последовательности 8.7.6.5.4.3.2.1?
                                        0
                                        Окей, сейчас даже графически нарисую «блуждание» по структуре)
                                          0
                                          Слева нулевой уровень, справа первый.
                                          Каждая строка отображает значения после вставки.
                                          image
                                          0
                                          1. Вставляем элемент первый одноэлементный массив.
                                            1 операция.
                                          2. Вставляем элемент во второй одноэлементный массив и создаём двухэлементный массив для слияния и делаем первый шаг слияния(в массив слияния попадает один из элементов — меньший).


                                          +2 операции.


                                          3,4. — То же, что 1,2, но только мы дополнительно запускаем очередной шаг слияния.

                                          На третьем шаге: +3 операции (сначала слияние внутри стартового уровня, потом создание следующего уровня, потом создание нового элемента в стартовом уровне).


                                          На четвертом шаге: +2 операции (как на втором).


                                          На пятом шаге: +6 операций (слияние, пересылка на следующий уровень, слияние там, еще одно слияние там, простановка значения на этом уровне, еще одно слияние на следующем уровне).


                                          Итого я насчитал 14 операций на пять шагов. И из динамики выглядит так, что это будет расти нифига не линейно, и даже не логарифмически (потому что по мере продвижения вперед количество слияний на одну операцию будет вырастать вместе с "глубиной" конструкции).


                                          А еще хочу заметить, что у вас двухкратный расход памяти, потому что пока данные не перенесены в следующий уровень, они хранятся одновременно в result, left и right.


                                          PS Так напомните, какая у вас сложность поиска?

                                            0
                                            Насчёт двойного расхода памяти я в курсе. В дереве тройное-четверное для аналогичных типов данных.
                                            Не слияние, а шаг слияния — это копирование одного значения. В деревьях для балансировки при вставке происходят «повороты», не считали сколько это?
                                            Линейно — это же вроде хуже, чем логарифмически… в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?
                                              0
                                              Насчёт двойного расхода памяти я в курсе. В дереве тройное-четверное для аналогичных типов данных.

                                              Откуда?


                                              Линейно — это же вроде хуже, чем логарифмически…

                                              Я имел в виду n log n, типичное для операций сортировки.


                                              в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?

                                              Это так не выглядит.

                                                0
                                                Откуда… мы храним ключ — 4 байт + значение — 4 байта + 2 ссылки на лево-право + балансирующий параметр, иногда родителя хранят. Здесь только ключ и значение, хотя, конечно, в 2 местах.
                                                Слияние происходит по одному элементу на каждом уровне за одну вставку и происходит оно только после того, как оба подмассива полностью заполнены. Результирующий массив отправляется на уровень ниже и просто висит там, пока в этот уровень не придёт ещё один аналогичный по размеру массив. На 1 уровне 2 одноэлементных массива. На втором — 2 двухэлементных. На третьем 2 четырёх элементных. С каждым уровнем размерность массива удваивается относительно предыдущего. Если бы размерность не менялас, то для чего бы я вводил свойство класса len?
                                                  0
                                                  Здесь только ключ и значение, хотя, конечно, в 2 местах.

                                                  И вот тут возникает вопрос, что больше — ссылки, или ключи/значения. Впрочем ладно, будем считать, что убедили.


                                                  Слияние происходит по одному элементу на каждом уровне за одну вставку
                                                  Нет. Когда у вас начинает заполняться следующий уровень, слияние на нем вызывается больше одного раза за вставку на верхний уровень, и дальше это распространяется на каждый следующий уровень тоже.
                                                    0
                                                    Так скорее всего может показаться из-за того, что для наглядности я вызываю upd с каждой вставкой. Но первое условие проверяет готов ли массив к слиянию — если под result память не выделена, то пытаемся спустится на уровень ниже, но здесь ничего не произойдёт.
                                                      0
                                                      если под result память не выделена, то пытаемся спустится на уровень ниже, но здесь ничего не произойдёт.

                                                      На уровень ниже вы спускаетесь всегда, когда он есть (а это дважды за вставку на этом уровне), и если там память под result выделена, то там будет два слияния безотносительно состояния текущего уровня, и в любом случае будет переход на уровень еще ниже (конечно, если он есть), далее аналогично.

                                                        0
                                                        Да, при вставке нового значение происходит по шагу слияния на каждом уровне. — Что и при вставке в дерево, когда нужно перебалансировать его и поэтому мы делаем повороты «всплывая» или наоборот. В этом случае наоборот.
                                                          0

                                                          Корректировка деревьев происходит не на каждом шаге, и стоимость каждой корректировки ограничена O(log n).

                                                            0
                                                            А здесь на каждом шаге, но тоже логарифм, ибо нужно сделать по одному шагу слияния на каждый уровень, а количество уровней, как и в дереве, описывается логарифмом.
                                                              0
                                                              А здесь на каждом шаге, но тоже логарифм, ибо нужно сделать по одному шагу слияния на каждый уровень,

                                                              А по одному ли?

                                                                0
                                                                «На всякий случай» я делаю по 2(не помню, сейчас вот удалил нижний upd() — тоже работает), но с точки зрения алгоритма достаточно одного.
                                                                По примеру — внесли 16 элементов (2 по 8) и полностью досортированный результирующий массив (1 по 16) нам понадобится когда насобираем ещё 16 элементов. На самом деле нам не хватает одного шага слияния, ведь когда придёт 16-й элемент, оба 8-ми элементных массива уже должны быть пусты, а 16-ти элементный должен быть на сл. уровне, но на 16 шаге перенос указателя на сл.уровень ещё не произойдёт, поэтому 1 дополнительное слияние мы делаем ещё и в момент создания временного массива.
                                                                  +1
                                                                  «На всякий случай» я делаю по 2(не помню, сейчас вот удалил нижний upd() — тоже работает), но с точки зрения алгоритма достаточно одного.

                                                                  Вот именно поэтому и надо писать в псевдокоде и объяснять каждый шаг. Нет никакого "всякого случая", когда вы оптимизируете под производительность.

                                                                    –2
                                                                    Так и поступлю, если решу ещё две структуры описать. Хотя сложно утверждать. Я понимаю, что в основном критика уместна, но когда ты бесплатно описываешь то, над чем ломал голову кучу времени, а тебя не поняли, «переменные не так назвал», замеры делай — не весело, лень берёт верх)
                                                                      –2
                                                                      Точно, про дизлайк ещё забыл — тоже желание отбивает что-то описывать)
                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                          0
                                                                          Это как с телевизором: не хочешь смотреть рекламу — выключи телевизор. Но давайте на секунду предположим, что алгоритм хорош. И после такого шквала наездов я что-то кому-то должен доказывать? Ну не знаю. Мне кажется это не целесообразные потуги. А цели своей я добился некоторые люди заинтересовались идеей.
                                                                          0
                                                                          Для бесплатного изложения потока мыслей есть личные бложики, контактик и т.п. Хабр все-таки позиционируется как технический ресурс, где присутствуют специалисты. И вы бесплатно получаете фидбэк и обмен идеями, обсуждение вашей идеи, поиск косяков в ней и т.п. Если вас не поняли из-за кошмарного кода и невнятных объяснений, вы имеете полное право обидеться и уйти, но вы подумайте об этом с другой стороны: чем больше человек поймет вашу идею, тем больше шансов получить на нее отклик и больше шансов ее улучшить. Если вы ее реально используете в коде, то вы забесплатно получите улушение своего кода.
                                                        0
                                                        Откуда… мы храним ключ — 4 байт + значение — 4 байта + 2 ссылки на лево-право + балансирующий параметр, иногда родителя хранят. Здесь только ключ и значение, хотя, конечно, в 2 местах.

                                                        Зато есть занятное встречное наблюдение: для вашего решения нужна память последовательными кусками. Для дерева — нет.

                                                          0
                                                          Идеально для файловых структур, когда в пределах одного кластера может находится куча актуальных данных)
                                                            0
                                                            Для файлов в деревьях специально группирую сразу несколько значений внутри ноды, чтобы за одно чтение можно было больше пользы получить. B-tree вроде.
                                                          0
                                                          Почему не выглядит если вот же — результирующий массив в 2 раза больше обоих исходных. После заполнения мы его пробрасываем в сл. уровень. Там происходит то же самое, только len там удвоенная от первоначального…
                                                          keyResult=new unsigned int[len*2];
                                                          valResult=new unsigned int[len*2];
                                                            0
                                                            Почему не выглядит если вот же — результирующий массив в 2 раза больше обоих исходных. После заполнения

                                                            Потому что его заполнение тоже стоит вам операций, количество которых накапливается с глубиной.

                                                              0
                                                              массив 1: 2 4 6 8
                                                              массив 2: 1 3 5 7
                                                              Один шаг слияния — это когда мы берём одно значение из массива 1 или 2 в зависимости от того какой текущий элемент сравнения меньше. За один шаг в результирующий массив дописывается только одно значение из уж сформированных отсортированных массивов. Не слияние в принципе, а только один шаг — одно значение.

                                                              Пример.
                                                              Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты, в 4-м содержится 2 полностью заполненных и отсортированных 8-ми элементных массива. Чтобы слить их в 16-ти элементный массив, необходимо 16 шагов слияния. А сколько нужно вписать новых элементов, чтобы получить новый уровень — тоже 16. В этом и состоит отложеность слияния.
                                                                0
                                                                Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты,

                                                                А вот и нет. На первом уровне — все массивы заполнены (полезной информации — два элемента), на всех последующих — заполнены temp (2, 4 и 8 элементов соответственно). Суммарно 16, что логично. И к этому моменту мы уже сделали 35 шагов слияния (85 операций всего).

                                                                  0
                                                                  То есть «нет»?) По логике моего алгоритма — да…
                                                                    0

                                                                    А по факту выполнения — нет. Я просто встал в дебаггере и показал вам, что получается. Когда вставляется 16 элемент, в первом уровне заполнен temp, мы перемещаем его в right, новый элемент идет в left. Теперь мы аллоцируем result и вызываем upd — который передвинет один элемент (left или right) в result. Поскольку result не полон, его передача на следующий уровень не случится.


                                                                    (Лишний аргумент в пользу строгого псевдокода)

                                                                      0
                                                                      странно. Надо будет глянуть что там происходит…
                                                                        +1

                                                                        Просто если вы не понимаете даже состояние своей структуры данных на n-ом шаге, как вы делаете утверждения о ее алгоритмической сложности?

                                                                          –1
                                                                          А для определения сложности нужно понимать состояние структуры на n-ом шаге?..
                                                                          Достаточно критики, надоело уже. Всё до безумия просто — не используйте эту структуру, если не нравится. А я вижу в ней потенциал и буду развивать дальше.
                                                                            +1

                                                                            Нужно, конечно. Иначе исходя из чего вы оцениваете потребление ресурсов?


                                                                            Ну и да, я уже давно не пишу/использую кастомные коллекции данных, если нет сильного обоснования: встроенных хватает практически на любой случай.

                                                                              0
                                                                              На каждом уровне по одному массиву слияния. Шаг слияния — одна операция(сравнение и копирование). Для полноценной работы алгоритма достаточно делать по одному шагу слияния на вставку для каждого уровня. А количество уровней логарифмическое, так как каждый следующий уровень в 2 раза больше предыдущего. Исходя из этого — сложность должна быть логарифмической.
                                                                                0

                                                                                Не сходится. На 16 внесенных значений (четыре уровня) сделано 35 слияний, это больше чем четыре слияния на вставку. Это ваш реальный код.

                                                                0
                                                                При каждом добавлении элемента мы плавно пошагово готовим все уровни по одному значению на уровень.
                                                            0

                                                            Я тут малость переписал вашу программу на 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 считает, что это полиномиальная зависимость.

                                                          0
                                                          И опять же, здесь двойной расход памяти — худший случай. А лучший случай — +1 временное пустое. А в дереве оверхед на ссылки-балансирующие данные гарантированы.
                                                            0
                                                            И опять же, здесь двойной расход памяти — худший случай.

                                                            Не худший, а возникающий с заданной периодичностью.

                                                              0
                                                              Заданная периодичность звучит будто через каждые N вставок. Но тут опять же логарифмическая зависимость. А так да, появление этого случая предсказуемо.
                                                                0
                                                                Заданная периодичность звучит будто через каждые N вставок.

                                                                Так и есть. После каждых двух вставок на первом уровне будут аллоцированы все массивы.

                                                                  0
                                                                  Аллоцированы все массивы? Каждую вторую вставку? Аллоцированы будут все 2 массива следующего уровня каждую вторую вставку. А следующего — каждую его вторую вставку, но так как в него вставка происходит через раз, то это каждая четвёртая вставка, 3 уровень — восьмая и остальные степени двойки.
                                                                    0
                                                                    Аллоцированы все массивы? Каждую вторую вставку?

                                                                    Да, на первом уровне.


                                                                    А следующего — каждую его вторую вставку, но так как в него вставка происходит через раз, то это каждая четвёртая вставка

                                                                    Но и массивы там в два раза больше. Поэтому потребление памяти будет описываться суммой периодических функций, каждая "в два раза больше" (как по амплитуде, так и по периоду) предыдущей.

                                                                      0
                                                                      Я к тому, что когда у нас заполнены пусть 5 уровней, пара лишних одноэлементных массива не слишком тянут на худший перерасход памяти. В принципе вы правы, просто я исхожу относительно текущего N.
                                                                        0

                                                                        Это не отменяет того факта, что в некий (полностью предсказуемый) момент времени у вас на всех уровнях будут аллоцированы все массивы.

                                                                          0
                                                                          Я к тому, что с рост количества вставок для «предсказуемого момента» зависит от количества уровней и далеко не линейно.
                                                            0
                                                            Так напомните, какая у вас сложность поиска?

                                                            Так вот, сложность поиска — это сумма сложностей поиска на каждом уровне. Те, в свою очередь, логарифмичны, но проблема в том, что сумма логарифмов — это не логарифм суммы, а логарифм произведения.

                                                              0

                                                              … что, вкупе с геометрической прогрессией размеров, дает нам чуть ли не O(sqrt(n)) время поиска в худшем случае (что стабильно больше логарифма). Выглядит дико, конечно, я практически уверен, что налажал в преобразованиях.

                                                          0
                                                          То есть слияние первых двух значений полностью завершиться только при вставке следующих двух значений. И что ещё важно — вставка всегда происходит в «голову» структуры, поэтому поиск последних добавленных будет всегда быстрее «старых» значений.
                                                    0
                                                    Я вообще считаю, что люди не умеют придумывать ничего нового, только брать немного там, немного там и объединять во что-то, чего ещё не было.
                                                    Согласен, общие черты есть. Хотя отталкивался не от B-деревьев, а от обычных отсортированных массивов. В любых бинарных деревьях может быть 2 указателей на такую-же структуру, а здесь только один.
                                                    Хотя это тоже натолкнуло на мысль, спасибо) Предположим мы реализуем B-tree с порядками-степенями двойки, зависящими от уровня — это может быть даже лучше. Но мне не попадались статьи, где описывалось подобное использование B-tree, или они есть?
                                                      0
                                                      Нет, я, во всяком случае, не видел. Но ваше желание избавиться от оверхеда по пямяти, за счет усложнения вычислений, и похожая результирующая структура натолкнула на такую мысль.
                                                        0
                                                        Иногда к одной и той же идее можно прийти разными путями)
                                                      0

                                                      Впрочем, я понял, что меня тут всю дорогу смущало. Ваш код не может быть альтернативой бинарному дереву поиска, потому что на нем нельзя выбрать диапазон; следовательно, сравнивать его надо с key-value структурами — читай, хэш-таблицами с их O(1) на операцию (и существенно меньшей памятью).


                                                      (BTW, в случае, когда на уровне заполнены result, left и right, а элемент не входит в этот уровень, стоимость прохода уровня при get увеличивается вдвое)

                                                        0
                                                        BTW, в случае, когда на уровне заполнены result, left и right, а элемент не входит в этот уровень, стоимость прохода уровня при get увеличивается вдвое

                                                        Неправ, нет такого кейса.

                                                        0
                                                        del

                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                        Самое читаемое