Задача 2 - СТАТИСТИКА - Анализ |
|
Стана традиция една от задачите в задочната част на Конкурса на PC Magazine да е посветена на ефективнатата организация на данните. Когато в някакво приложение се поддържат големи обеми от данни, ефективността на имплементацията на обичайните опeрации - за добавяне, изтриване и търсене, както и на специфичните операции на приложението е от голямо значение. Статистически, всяка една от операциите се изпълнява достатъчно често и неефективността на само една от тях може да компрометира цялото приложение.
Да вземем за пример Конкурсната задача с номер 2 - Статистика. Да означим с N броя на съхраняваните в определен момент характеристики. Ако за запазване на данните (множество от естествени числа) използваме масив, в който да ги добавяме в реда на регистрирането им в структурата, като новопостъпилата характеристика винаги отива на първото свободно място в масива. Oперацията добавяне ще се изпълнява много бързо (сложност O(1)). Изтриването на характеристика, обаче, както и намирането на броя на характеристиките в зададен интервал изискват преглеждане на всички елементи на масива и като цяло сложността на една "средно статистическа операция" на приложението ще бъде O(N). Ако решим да съхраняваме текущо регистрираните характеристики в сортиран вид, тогава с помощта на двоично търсене намирането на броя на характеристиките в зададен интервал може да бъде редуцирано до O(log2N) стъпки, но вмъкването на нова характеристика и изтриването на съществуваща ще запазят средната сложност на операция на О(N).
Общата идея в подобен род приложения е не да се подобрява колкото може сложността на една операция (или на част от операциите) за сметка на останалите, а да се търси такава организация на данните, че сложността на "най-лошата" операция да е колкото може по-добра - амортизирана сложност. Традиционен подход за подобряване на амортизираната сложност са различните дървовидни структури.
Първообраз на всички подобни структури е добре известното дърво за двоично търсене, с помощта на което всички класически операции се имплементират със сложност O(h), където h е височината на дървото. Неприятното е, че добавянето и изтриването на елементи може да дебалансира структурата, т.е. височината й да нарастне доста в сравнение с минимумa от log2N, и изпълнението на операциите да се забави. Решението на този проблем е дървовидната структура непрекаснато да се подлага на "балансиране", когато това се налага. Така текущата височина на дървото се държи близо до теоретичния минимум и операциите остават бързи.
Най-известните форми на балансирани дървета за двоично търсене са така наречените AVL (от имената на създателите на структурата Адельсон-Вельский и Ландис) и Red-Black (или RB, заради оцветявянето на върховете в два цвята и използването на оцветяването като критерий за проверка баланса на дървото). Не е случайно, че повечето от участниците и по-специално победителите са се насочили към тези две структури (които са и най-добре описани в литературата, виж например Cormen, Leiserson, Rivest, Introduction to Algorithms) или към някакви други, повече или по малко познати форми на балансиране на дървото за двоично търсене.
Особеното в задача 2 е операцията за търсене на броя на елементите на структурата в зададен интервал, която не е присъща на балансираните дървета за двоично търсене. За имплементирането на тази операция с логаритмична сложност е необходимо да се направи не сложна модификация, която за случая с RB дървета е описана в посочената вече книга. Да се спрем малко по подробно на тази модификация.
Към обичайните за всяко дърво за двоично търсене полета key, parent, left и right да добавим в записа на всеки връх X полето size, което ще съдържа брoя на върховете в поддървото с корен Х, включително и корена. Поддържането на това поле при изпълнението на операциите за добавяне и изтриване (и неизбежното пребалансиране на дървото) ще бъде със сложност O(log2N). За целта е необходимо само да се нанесат необходимите поправки в полетата size на всички върхове по пътя от мястото където е настъпило изменението до корена на дървото.
Колкото до операцията за намиране броя на запомнените характеристики в зададен интервал [A,B], тя също се имплементира с логаритмична слойност. За целта първо намираме в дървото записът, чийто ключ Х е най-големият, който е по-малък или равен на B и съответно записът, чийто ключ Y е най-малкият, който е по-голям или равен на А. Да означим с pX и pY съответните записи. Тогава търсеният брой характеристики в интервала [A,B] е 1+ pX.left.size - pY.left.size.
|
Анализи на решения изпратени от участници:
|
Владимир Молотков
|
|
За въпроси можете да ни пишете на адрес: konkurs@musala.com.
Supported by Musala Soft Ltd.
Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.
|