[Data Structures] Exam 13 Sept 2015
Здравейте, тъй като наближава изпита по структури от данни, започнах да се подготвям решавайки изпита, който беше даван на миналата инстанция на курса. Тъй като в този курс най-вече се учим да използваме подходящи структури от данни, за конкретната ситуация, за да имаме максимално добра оптимизация, е изключително важно времето, за което минават тестовете, и затова е изключително важно да няма random лагвания на Judge конкретно за този изпит, но ето какво се случва. Тъй като не съм сигурен дали проблема се проявява от самия Judge или от конкретно моето решение, нека започна малко от по-назад. Първо, задачата не е трудна за реализация, тънкостите се проявяват в 1-3 теста, където има тест на това колко бързо ни работят структурите(ако видите начина на оценяване, ще ви е ясно, че дори и един тест е критично важен за крайния резултат). Та общо взето важния момент, който забелязвам е, че трябва да се използват такива структури, че хем бързо да добавяме игри, хем после, когато ги търсим по prefix да са ни сортирани, за да можем максимално бързо да ги извлечем. Затова в Хеш Речник добавям играта заедно с нейната парола, и в SortedSet пазя имената на регистрираните игри, за да мога после максимално бързо да извлека по даден префикс. Добавяйки обаче в този SortedSet, който се имплементира върху подредено дърво, вече при командата RegisterGame аз имам сложност, която не е константа ами е log(n). И ETO какво се получава в джъдж, тестовете, които съм задраскал са с променен код, но останалите са с един и същ код, и е факт, че 2 пъти получвам 100 точки, но повече пъти не ги получавам. Та общо взето пиша тук, за да попитам дали използваните стуктури и алгоритъм от мен не е "стабилен", и затова да се получава това разминаване и евентуално ако е нещо свързано със самия джъдж, да бъде нещо като "бъг репорт". Тук оставям и целия си код ако се интересувате от друга част свързана с него.
А може ли да обясниш, каква е разликата между OrderedSet и SortedSet. Това, което аз знам, е че в OrderedSet, можеш да достъпваш елемнтите с индексатор, и те отново са сортирани. Не ми е ясно обаче това достъпване с чупените скоби каква сложност има, отново ли е log n? И какво е точно предимството на OrderedSet пред SortedSet? Също така, не знаех какво точно прави този ординал компаратор, сега вече знам, но ми се появява въпроса ако не се подаде това в конструктора, по какъв начин ги сравнява? Много ще се радвам ако ми обясниш тези неща, защото наистина ми са доста мъгляви! Също така метода .Range(), каква сложност има? Също в моето решение, в кейса където търся игра по префикс, мисля че само в най-лошия случай сложноста се пада O(n), защото аз така или иначе брейквам foreach-a, когато взема 10 елемента, освен ако те не са в края разбира се. Доста въпроси зададох, но така пък ми се изясняват доста повече неща! Благодаря за оказаната помощ.
Да, има индексация при OrderedSet<T>, сложността е дълбочината на дървото (т.е. О(log n) при едно балансирано дърво). Другото предимство са Range, RangeFrom и RangeTo методите за изваждане на всички елементи в даден интервал (виж демата от презентацията за Collections and Libraries). Има още няколко бонус метода като IsSupersetOf, Difference, GetFirst (връща най-малкия), GetLast (връща най-големия).
Range() има сложност O(log n + k), k е броят елементи. log n, защото има значение колко е дълбоко дървото. Той работи като пуска един In-Order DFS обаче без да обхожда ненужни поддървета (такива каквито не може да са в интервала).
Твоят вариант прави линейно търсене. В конкретния случай имаш ограничение до 10 елемента, затова и не е толкова бавно. Но пък представи си, ако често правиш префиксно търсене по Z на 1 000 000 елемента (измежду които няма такава дума) по твоя начин. :) В същия случай Range() ще направи едно log n спускане и ще установи, че няма такива елементи.
SortedSet няма метод Range(). Относно сложността не мога да цитирам конкретно, но е много бързо, то е просто отрязване на поддърво, което предполагам е логаритмична сложност или близка (търсене на границите в балансираното дърво).
Едит: според документацията, която намерих, дори е константно време взимането на рейндж. Потърси го, в момента не мога да копирам линк.
@a_rusenov, супер мерси много за обяснението, доста ми се изясниха нещата, само не разбрах каква е разликата ако в конструктора има ((s1, s2) => String.CompareOrdinal), имам предвид, да, с това ще сравнява по АSCII кода, а без него как го прави сравняването?
Ами да да сравни тежестите на два елемнта, ще използва CompareTo(). До колкото съм наясно обаче без други опции овърлоудът на този метод за обект от тип стринг е culture specific.
Тогава, каква е причината да се подава в конструктура, за оптимизация или за да се подсигурим, че ако нещо не е наред с culture на машината, това сравнение няма да гръмне?
Културата на машината може да е всякаква, да. Виж в документацията на String.CompareTo (s1, s2) има разни примери
@Filkolev, е ти изби рибата. Как така range query с константна сложност в дърво?
Знам, няма логика. Или аз не разбирам какво точно имат предвид, или някой гений действително е избил рибата: линк.
Фил, извикването на Range() е lazy и затова връщането на View отнема константно време. Тъй като се извиква функцията DoubleRoundedRangeTester на червео-черното дърво. Тя връща делегат, а не оценява реално. Подава се после на коструктора на View, който дава тестера на GetEnumerator(). Когато обаче поискаш елемент от този Range, View-то ще се енумерира и тогава ще обходи дървото по регистрирания енумератор (пак от линка горе - EnumerateRangeInOrder)
Мисля, че структурата е OrderedSet и е част от Wintellect.PowerCollections