|
Решение на задача 1
(КАТАЛОГ) от конкурса по
програмиране на Musala Soft и PC Magazine/Bulgaria
На пръв поглед първата задача от конкурса
изглеждаше тривиална. Наистина, не е трудно да се напише набързо едно елементарно
решение, но намирането на качествено такова е достойно предизвикателство. Идеята
на решението, което описвам тук, позволява всяка една от седемте команди (ADD, FS,
FN, FL, DS, DN, DL) да се изпълнява за време от порядъка на O(log N), където N е
броят на стоките, намиращи се в каталога в дадения момент.
Нека започнем с кратко въведение в принципите на структурите, които се използват.
Ще се опитам да го направя достъпно за повечето хора, но няма да навлизам в прекалени
подробности. Предполага се, че читателят има известна подготовка в тази област.
Двоично Дърво за Търсене (ДДТ) е дърво, в което за всеки възел е изпълнено,
че ключът му е по-голям от ключовете на всички елементи от лявото му поддърво и
по-малък от ключовете на всички елементи от дясното. В такова дърво е тривиално
да намерим даден елемент, ако знаем ключа му. Включването и изтриването на елемент
също са лесни за реализиране. Времето, необходимо за всяка от тези три операции
е пропорционално на височината на дървото, която в средния случай е приблизително
log N (т.е. двоичен логаритъм от броя на елементите в дървото). За съжаление, при
определени обстоятелства е възможно дървото да се изроди и височината му да стане
пропорционална на N. Например, ако последователно включим естествените числа от
1 до 1000, дървото ще се изроди в линеен списък (коренът му ще е единицата) и съответно
височината му ще бъде 1000.
Балансирано ДДТ е ДДТ, в което са предприети мерки против въпросното "израждане".
Логиката на алгоритмите за включване и изтриване на елемент е усложнена, но осигурява
че височината на дървото в най-лошия случай е пропорционална на log N. Съществуват
различни начини за реализация на Балансирано ДДТ. Тук ще спомена някои от тях, а
подробности могат да бъдат намерени в интернет (конкретни адреси са посочени в края
на този документ):
- AVL дървета - може би най-известните Балансирани
ДДТ.
- Red-Black дървета - малко по-бързи от
AVL дърветата при включване и изтриване, поради по-простите алгоритми. Малко по-бавни
при търсене, защото средната височина на дървото е малко по-голяма. Като цяло, са
малко по-бързи от AVL дърветата.
- Randomized Treaps - хибрид между ДДТ и
пирамида (heap). В общия случай, може би най-бързата структура от посочените.
- Randomized Binary Search Trees (RBST)
- така, както са описани са от Conrado Martinez и Salvador Roura през 1997.
- Skip Lists - въведени от Bill Pugh. Не са дървета,
но имат аналогични свойства и отлични характеристики.
За конкретната задача трябва да поставим едно важно изискване към използваната структура:
тя трябва да поддържа "индексиране". Т.е. трябва да можем да намираме даден елемент
по поредния му номер (индекс) и обратното. Например, индекс 1 отговаря на елемента
с най-малък ключ, а индекс N - на елемента с най-голям ключ. RBST дърветата имат
тази възможност по дефиниция, а останалите трябва да бъдат модифицирани за тази
цел. Това може да се осъществи, като във всеки възел пазим като допълнителна информация
размерът на лявото и/или дясното поддърво.
В края на краищата, дървото което ще използваме в решението на задачата трябва да
може да изпълнява следните операции:
- включване на нов елемент - за време O(log N)
- изтриване на елемент по зададен ключ или индекс -
за време O(log N)
- намиране на елемент по зададен ключ или индекс -
за време O(log N)
- намиране на индекса на елемент по ключа му - за време
O(log N)
В моята програма използвах модифицирано AVL дърво, но както вече беше отбелязано,
има и малко по-бързи възможности.
Между другото, на пръв поглед изглежда логично да използваме хеш-таблица вместо
Балансирано ДДТ, тъй като в нея всички операции отнемат константно време в средния
случай, т.е. тя е по-бърза. Но за съжаление, елементите в една хеш-таблица не притежават
определена наредба, което не позволява бързо търсене по пореден номер (индекс).
Ето защо за конкретната задача няма реална полза от използването на хеш-таблици.
Сега ще пристъпим към описание на самото решение:
Ще поддържаме две дървета. Първото ще означим с TreeNum и в него за ключ
на елементите ще използваме поредния номер на командата ADD, с която стоката е била
включена в каталога (ще означим този пореден номер накратко с ПК - от Пореден
Ключ). Иначе казано, в това дърво стоките ще бъдат подредени по реда на добавянето
им. Важно е да не се бърка ПК с поредния номер на стоката - това са различни
неща, въпреки че си приличат. ПК на дадена стока не се променя никога, докато
поредният й номер може да намалява при изтриване на стоки.
Второто дърво ще означим с TreeLex и за ключ в него ще използваме името на
стоката, т.е. то ще съдържа стоките подредени лексикографски.
Нека отбележим, че не е нужно да правим две копия от информацията за дадена стока
във всяко дърво - елементите на дърветата могат да бъдат просто указатели към структури,
съдържащи информация за съответна стока. В частност, структурата трябва да пази
името на стоката и нейният ПК.
Ще опишем накратко и как може да бъде реализирана всяка една от седемте команди
с помощта на тези две дървета:
ADD: Включваме стоката в TreeNum и в TreeLex.
FS: Намираме стоката в TreeLex по името й. Следователно, вече знаем
и нейния ПК. По него, намираме индекса на стоката в TreeNum и го извеждаме
като резултат.
FN: Намираме стоката в TreeNum по индекса й. Извеждаме името й като
резултат.
FL: Намираме стоката в TreeLex по индекса й. Извеждаме името й като
резултат.
DS: Намираме стоката в TreeLex по името й. Вече знаем нейния ПК.
По него, намираме индекса й в TreeNum и го извеждаме като резултат. Изтриваме
стоката от TreeNum и от TreeLex.
DN: Намираме стоката в TreeNum по индекса й. Извеждаме името
й като резултат. Изтриваме стоката от TreeNum и от TreeLex
(вече знаем името й).
DL: Намираме стоката в TreeLex по индекса й. Извеждаме името
й като резултат. Изтриваме стоката от TreeNum (вече знаем нейния ПК)
и от TreeLex.
При горните описания не са разгледани специалните случаи като "DUPLICATES
NOT ALLOWED" и "NOT FOUND". Обработката им е тривиална.
Това е всичко, от алгоритмична гледна точка. За бързодействието на решението има
голямо значение и конкретната реализация. Няма да се спирам детайлно на нея. Ще
отбележа само, че при "огромни" каталози слабото място в програмата може да се окаже
управлението на паметта, или по-точно заемането и освобождаването на блокове памет.
То е единствената част от програмата, чиято скорост при съвременните програмни езици
е в линейна зависимост от броя на стоките. Хубаво е да се направи нещо по този въпрос.
Например, в C++ може да се използват STL алокатори, които в добрите имплементации
на STL са доста бързи.
Петър Иванов Петров (piettropro@bigfoot.com,
pesho@pesho.com)
СУ / ФМИ, спец. Информатика, 3 курс
19 Декември, 2000 г.
P.S. Ето и някои полезни интернет-адреси по темата:
- http://hissa.nist.gov/dads/
- online речник по алгоритми и структури от данни. Има дефиниции на AVL дървета
и Red-Black дървета. Има и дефиниции на treap и RBST, но не са напълно коректни.
- http://swww.ee.uwa.edu.au/~plsd210/ds/red_black.html,
http://wannabe.guru.org/alg/node18.html
- информация за Red-Black дървета.
- http://swww.ee.uwa.edu.au/~plsd210/ds/AVL.html,
http://www.msu.edu/user/pfaffben/avl/
- информация за AVL дървета.
- http://www-tcs.cs.uni-sb.de/papers/rst.ps.gz
- описание на Randomized Treaps от R. Seidel и C. Aragon.
- http://www-lsi.upc.es/dept/techreps/ps/R97-8.ps.gz
- описание на Randomized Binary Search Trees от C. Martinez и S. Roura.
- http://www.cs.umd.edu/~pugh/
- сайт на Bill Pugh, създателя на Skip Lists.
|
