Вступление
Здравствуйте, читатели. Это моя первая публикация, в которой хочу поделиться структурой данных 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*nxt;
unsigned int*key0,*key1,*key2,*key3,*val0,*val1,*val2,*val3,i0,i1,i2,len;
void upd()
{
if(key0)
{
if(i1<len)
{
if(i1<len)
{
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++;}
}
else{key0[i0]=key1[i1];val0[i0]=val1[i1];i0++;i1++;}
}
else{if(i2<len){key0[i0]=key2[i2];val0[i0]=val2[i2];i0++;i2++;}}
if(i0==len*2)
{
if(!nxt)nxt=new ARRAY;
nxt->set(key0,val0,len*2);
key0=0;key1=0;key2=0;key3=0;
val0=0;val1=0;val2=0;val3=0;
}
}
if(nxt)nxt->upd();
}
void set(unsigned int*Key,unsigned int*Val,unsigned int Len)
{
upd();
len=Len;
if(!key3){key3=Key;val3=Val;}
else
{
key1=Key;val1=Val;key2=key3;val2=val3;key3=0;val3=0;i0=0;i1=0;i2=0;
key0=new unsigned int[len*2];val0=new unsigned int[len*2];
}
upd();
}
public:
~ARRAY()
{
if(key0)delete[]key0;if(key1)delete[]key1;if(key2)delete[]key2;if(key3)delete[]key3;
if(val0)delete[]val0;if(val1)delete[]val1;if(val2)delete[]val2;if(val3)delete[]val3;if(nxt)delete nxt;
}
ARRAY()
{
key0=0;key1=0;key2=0;key3=0;
val0=0;val1=0;val2=0;val3=0;
i0=0;i1=0;i2=0;len=0;
nxt=0;
}
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(key3)
{
l=0;r=len;
while(l!=r-1)
{
i=(l+r)/2;
if(key3[i]<Key)l=i;
else if(key3[i]>Key)r=i;
else return val3[i];
}
if(key3[l]==Key)return val3[l];
}
if(key1)
{
l=0;r=len;
while(l!=r-1)
{
i=(l+r)/2;
if(key1[i]<Key)l=i;
else if(key1[i]>Key)r=i;
else return val1[i];
}
if(key1[l]==Key)return val1[l];
}
if(key2)
{
l=0;r=len;
while(l!=r-1)
{
i=(l+r)/2;
if(key2[i]<Key)l=i;
else if(key2[i]>Key)r=i;
else return val2[i];
}
if(key2[l]==Key)return val2[l];
}
if(nxt)return nxt->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("%dn",Val);else printf("undefinedn");}
else system("cls");
}
delete arr;
}
ЗЫ:
В алгоритме не реализовано удаление, хотя некоторые эротические фантазии есть. Но это уже отдельная статья. Здесь же я попытался по умничать донести саму идею и если у кого-то есть свои мысли по реализации удаления — велком. Хотя на самом деле данная структура разрабатывалась для специфической задачи, не требующей удаления да и вообще ничего кроме быстрой вставки и быстрого поиска, появилось желание доработать класс, реализовав прочие, часто нужные в повседневной жизни работе методы, чем и займусь когда рак на горе свиснет — нибудь.
Автор: retYrn0
