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

в 7:51, , рубрики: SMAS, Алгоритмы, бинарный поиск, структуры данных, упорядоченные массивы, метки:

Вступление

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

Источник

Поделиться новостью

* - обязательные к заполнению поля