Повечето книги разглеждат основни структури от данни като дървета и хеш таблици като започват с масиви с фиксиран размер. Въпреки че са бързи, масивите с фиксиран размер рядко са ефективни за практически цели -- модерният софтуер трябва да работи с каквито и да е входни данни, а предварително оразмерените даннови структури не са достатъчно гъвкави, за да изпълнят подобни изисквания. От друга страна свързаните структури са по -гъвкави, но са по-сложни и фрагментацията на паметта може намали производителността. Джон Бойер обяснява лесен и бърз начин за промяна на големината на масиви и данновите структури, които ги изпозват.
-- Тим Кницъл
Едуард Ситарски обясни как Хеширани Дървета от Масиви, чрез добавяне на сложни програмни техники могат да се използват за нарастващи и намаляващи масиви.В тази статия аз ще покажа как да правите същото, използвайки толкова прости техники, че може веднага да се добавят към вашия програмен репертоар. Още повече , че можете да добавите тези техники към съществуващи програми, без да променъате структурите от данни или случайно да се появи нов бъг.
Аз разработих тези техники, докато добавях променяеми хеш таблици към Universal Forms Description Language (http:// www.uwi.com/). Сорс кода за променяемите хеш таблици, които използват масиви с променлива дължина моеже да бъде намерен в електронен вариант.
Малко Напрежение
Предимствата на хеширането се намляват, когато хеш таблицата се препълни. Но промяната на големината на таблицата изисква наново вмъкване на всичките елементи, защото последната операция за определяне на хеш ключа е модул по големината на таблицата. Без някои трикове програмата ви ще страда при всяко уголемяване и намаляване на таблицата.
Наскоро правих лексически анализатор като част от нов парсър. Този анализатор трябваше да чете затворени в кавички низове с произволна дължина . Тъй като синтаксиса на много езици не позволява да се ограничава сължината на затворен в кавички литерал е необходимо низът д анараства динамично, докато не се стигне до затварящата кавичка.
Като част от статия за дърво на Фибоначи през Януари 1997 аз сравних двоично и Ф-дърво. Тъй като Ф-дървото може да стане произволно голямо, моето двоично дърво заделяше наново масива си, когато се напълни. Предполага се, че двоичните сървета имат O(log n) вмъкване, но ако се погледне внимателно се вижда, че това се базира на предположението ,че място за нов елемент може да се осигури за O(log n) или по-малко време. В повечето книги се изполват фиксирани масиви за съхранение,така че няма допълнителни разходи за осигуряване на място на новите елементи. Въпреки това показах ,че моят код има O(n) при вмъкване.
Проблемът за разширяващия се масив
Всички тези проблеми могат да се решат с масив,които може да расте динамично. Очевидният подход е да се добавят k елементи всеки път, когато има нужда от повече място. За съжаление функцията на C realloc() може да копира целия масив на ново място. Ако се използват операторите на C++ new/delete трябва ръчно да се заделя място, което гарантира, че елементите на масива трябва да се преместят. Така ако масивът порастне до произволен размер n елементите ще се преместят общо k+2k+3k+4k+...+n-k пъти. Крайният резултат е O(n2) или O(n) за елемент
Представете си предните примери. На лексикалният анализатор ще му трябва O(n2) време за прочитане на n символа, което е неприемливо за парсър(който трябва да има O(n) представяне). Двоичното върво се забави от O(log n) до O(n) и вмъкването в хеш таблицата от O(1) до O(n). Може да намалите скритата константа чрез увеличаване на уголемяването k, но крайния резултат все още е O(n) за елемент от масива.
Решението
Решението е да се удвоява размера на масива всеки път, когато трябва да се увеличи
char *lex_growbuffer(char *Buffer, long *pBufferSize){
char *TempP;
long NewSize;
if (*pBufferSize==0) NewSize = 16;
else NewSize = *pBufferSize * 2;
TempP = (char *) realloc(Buffer, NewSize+1);
if (TempP != NULL) *pBufferSize = NewSize;
return TempP;
}
... /* Snippet to add a character to the lex buffer */
if (BufferLen == BufferSize)
Buffer = lex_growbuffer(Buffer, &BufferSize);
if (Buffer == NULL) return NULL;
Buffer[BufferLen++] = NewChar;
Buffer[BufferLen] = '\0';
return Buffer;
...
/* After string is read, reduce to exact size */
Buffer = (char *) realloc(Buffer, BufferLen+1);
Листингът е lex_growbuffer() , който е типичен за променливите масиви. Размерът на буферът се удвоява, вместо да се променя с константна стойност.Също така този пример връща масива до първоначалния му размер след като се достигне до завършването на низа.
В C++ няма друг избор за промяна на размера освен копиране на масива. С удвояването на масива 2,4,8,...,n трябва да се копират масиви с размери 1,2,4,...n/2. Това са общо n-1 копирани елементи. Размерът се увеличава до n, когато се вмъква елемент (n/2+1). Следователно цената за копирането по време на заделянето на място никога не надвишава два времеви интервала, което е константно време за елемент.
В най-лошите моменти масивът ще е два оъти по-голям от необходимото, но това се уравновесява от увеличената скорост на заделяне на място и простотата от използването на тази техника е нов или съществуващ код.
А намаляването ?
В някои приложения може да се наложи извършването на изтриване от масив с променлива дължина. Двоичното дърво е добър пример. Добре ще е ако след произволна поредица от операции за добавяне/изтриване големината на масива на дървото е линейно зависим от броя на елементите в дървото. Това трябва да осигури,че локално натрупване на операции вмъкване няма да предизвика дървото да продължи да заема ненужна памет.
Вариант може да бъде намалянето на масива наполовина, точн окогато е наполовина пълен. По принцип това е правилната идея, но има слабости. Представете си случайната поредица е 1024 вмъквания, последвани от редуващи се операции за вмъкване и изтриване.Първото вмъкване от редуваната поредица ще накара масива на дървото да се увеличи до 2048 елемента, тъй като това е най-малката степен на две, която е по-голяма от 1025. Първото изтриване ще намали размера на таблицата до 1024 лемента, което ще доведе до намаляне на масива до 1024. Следващото вмъкване ще увеличи масива отново, а следващото изтриване ще го намали. Тъй като всяка операция ще променя масива тя ще има представяне O(n) .
Повечето произволни поредици от операции за вмъкване и изтриване нямат да доведат до този проблем, но аз исках да се гарантира, че в най-лошия случай ще има константно време за операция.За да се постиген това аз намалям масива до половината му размер, когато той е една четвърт пълен. В най-лошия случай размера ще се променя от 2k до 2(k+1) след вмъквания, а изтриванията ще променятброя на елементите от 2(k-1) до 2k+1. Когато се достигнат 2k+1 елемента се преместват 2k елемента в нов масив, преди да се вмъкне новият елемент. След това са необходими поредица от най-малко 2(k-1)+1 изтривания, за да се предизвика намаляне на масива, което ще премести 2(k-1) оставащи елементи в по-малък масив. След това трябва да има още 2(k-1)+1 вмъквания, за да се върне масива до 2k+1 елементи и да се предизвика увеличаване. Следователно всяка поредица от 2(k-1)+1 изтривания, последвана от 2(k-1)+1 вмъквания ще причини намаляне и увеличаване. Тази промяна на размера ще се появи 2(k-1) хода след фазата на изтриване и 2k хода сле вмъкване. Това е очевидно константно време за операция, тъй като се правят по-малко от 2k+2k-1 местения на елементи за всеки 2k+2 операции.
Следователно, дори и при изтриване, може да се поддържа константно време за операция и данновата структура никога няма да използва повече от четири пъти от необходимата памет - дори ако в поредицата има големи интервали от операции за вмъкване .
Хеш таблица
Аз се запознах с хеш таблици с променлив размер от книгата на T. Cormen, C. Leiserson, R. Rivest Introduction to Algorithms, (MIT Press, 1990). Докато създавах двоичното дърво за статията ми за дървото на Фибоначи аз осъзнах възможността за прилагане на удвоителната техника към всички проблеми на масивите с променяема дължина.
Ключът към променянето на хеш таблици е в простото създаване на нов масив, както е описано по-горе, копиране на съществуващите елементи в него, използвайки хеш функция за вмъкване и след това да се премахва старият масив . Изграждането наново на цялата таблица може да изглежда като груба сила, но няма разлика между копирането на елемент(константно време) и вмъкване в хеш таблица (което се очаква да е константно време). Използването на хеш функция може да е по-дълго от копиране в паметта, но това е просто по-голяма константа.
realloc() не е подходящо за пробразуване на хеш таблица, защото две таблици с различни размери ще съдържат много елемнти на съвършенно различни места.Следователно сте принудени ръчно да местите обектите от стария в новия масив.
Java и STL
Имплементацията на хеш таблица в Java използва удвояване на масива при увеличаване на размера на хеш таблицата, но не се намаля, когато се намали таблицата. Класът vector от C++ Standard Template Library (STL) , който се използва като база за приритетната опашка(двоично дърво), също използва удвояване на масива за увеличаване на размера на вектора, но игнорира заявката за запазване на памет, по-малка от сегашния капацитет на контеинера. Това трябва да се промени, защото структурите от данни (като дърветата, използвани в програми,работещи дълго време, като сървъри) трябва да могат да намаляват използваната памет след пик от данни.
Текущата имплементация на хеш таблица в STL не увеличава или намалява автоматично броят на позициите в хеш таблицата (всяка позиция нараства зада събере колизиите, което увеличава зареждането на хеш таблицата). Там има функция resize() ,която създава наново хеш таблица с брой позиции, зьададени като параметър. Така че , ако използвате STL хеш таблица, трябва да използвате функцията resize() само, за да удвоите или намалите наполовина броя на позициите, когато хеш таблицата е съответно пълна или само една четвърт е пълна. Това ще подсигури очакваният размер O(1) на списъка на колизиите.
Добри Хеш Функции
Когато се използва тази техника за промяна на броя позиции в хвш таблицата за запазване на малко натоварване е много важно да има добра хеш функция, която постига голямо разпръсване независимо от размера на таблицата. Ефективността на хеш функцията се измерва чрез разделяне на броя на позициите на броя на елемнтите в хеш таблицата. Идеалният хеш има 100% ефективност, защото всеки елемент има собствена позиция.
typedef unsigned long ulong;typedef unsigned char uchar;
ulong HashJB(uchar *KeyStr, ulong N)
{
ulong Hash=0, I=0;
uchar Ch;
for (;Ch=*KeyStr++; I^=1)
if (I)
Hash *= Ch;
else Hash += Ch;
Hash += ((Hash&0xFFFF0000)>>16);
Hash += ((Hash&0x0000FF00)>>8);
return Hash & (N-1);
}
Това в прост пример за хеш фунйция, която извършва изчисления върху двоичните кодове на символите в ключа. Позицията на записа в таблицата се изчислява само на базата на ключа, а не на колко елемента има в таблицата. Това обяснява защо операциите вмъкване, изтриване и търсене заемат константно време.
HashJB редува добавяне и умножение. Добавянето е много по-бързо, но умножението дава бързо нарастване на хеш стойността(така че тя може да достигне всяка позиция в таблицата , без значение колко голяма тя стане). Забележете и използването на Key&(N-1) за извършване на модул Key%N. Тъй като големината на масива се удвоява N винаги е степен на две и модулът може да се замине с много по-бързата операция на изваждане и побитово AND.
Проблем е отрязването на резилтатния ключ , защото се изхвърля информацията от старшите битове от стойността на хеша. По-късно добавих два реда код, който добавя старшите битове в младшите, което намали броят на колизиите в моите тестове.
Заключение
Забелязал съм в повече от половин дузина проекти, че техниката за удвояване/намаляване на половина на масива е довела до разтърсващо подобрение в производителността, сравнено с променянето с константна дълйина. Още повече, че идеята обикновенно се прилага в големи проекти за минути, вместо продължителната промяна на дизайна и на кода, които се налагат поради нови структури от данни. Тази техника ползва излишна памет, но понякога това може да бъде премахнато( както с лексическия анализатор, който намаля низовете). Но дори и когато излишното заемане на памет не може да бъде премахнато(както с хеш таблица), се разменя памет за скорост на изпълнение и простотата на тази техника.
Джон Бойер е ИТ мениджър в UWI Unisoft Wares Inc.
