Вступление
Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных 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;
}
ЗЫ:
В алгоритме не реализовано удаление, хотя некоторые