[Homework] Algorithms - Sorting and Searching - Problem 2 - Софтуерен университет

djc_bg2015 923 Точки

[Homework] Algorithms - Sorting and Searching - Problem 2

Здравейте,

стигнах до задача 2 от домашното: Implement Interpolation Search

Използвайки псевдо кодове които намерих из нета a и този който е в слайдовете, успявам да го докарам до работещ вариант, когато колекцията е от числа.

Но как да стане когато елемента който търсим е от тип Т и няма как да намеря Mid позицията по формулата:

int mid = low + ((needle - list[low]) * (high - low)) / (list[high] - list[low]);

тъй като няма как от нещо което незнам какво е да извадя число

Тагове:

06/10/2015 00:00:31 Структури от данни и алгоритми 06/10/2015 00:04:02

enevlogiev 1168 Точки

Best Answer

Винаги можеш да овърлоуднеш, стига да ти се занимава, разбира се.

Правиш си единия метод да приема int, супер. Другия метод много лесно може да се направи да работи с класове. Достатъчно е да си дефинираш един интерфейс Interpolatable, примерно, където имаш

int Interpolate(IList<T> list, int high, int low, Т needle)

след това лесно ще можеш да го разпишеш в класовете, които го наследяват, стига да имаш някакво пропърти, което да интерполираш. Примерно имаш клас Person, който има пропърти Age и този Person имплементира Interpolatable<Person>

public int Interpolate(IList<Person> list, int high, int low, Person needle)
{
    return low + ((needle.Age - list[low].Age) * (high - low)) / (list[high].Age - list[low].Age);
}

След това самия овърлоуд на InterpolationSearch би трябвало да изглежда така:

public int InterpolationSearch<T>(IList<T> list, T needle) where T : IComparable<T>, Interpolatable<T>
{
    int mid = needle.Interpolate(list, 0, list.Count, needle);
}

Всеки клас, който имплементира и двата интерфейса, би трябвало да може да се ползва.

Но в основата си InterpolationSearch работи с интове, да. Ако някой клас не може да се сравни по някво int property, няма да може и да се интерполира.

Пс: нямам си никаква идея какво значи интерполирам. Важното е, че го използвах 52 пъти като термин ; )

07/10/2015 21:21:14 07/10/2015 21:23:42

djc_bg2015 923 Точки

Харесва ми идеята - ще я използвам в домашаното си :)

Благодаря ти!

07/10/2015 21:28:15

Innos 419 Точки

Интересна идея, цяла вечер мислих върху нея снощи, но удрям до следния проблем. Ако T -то в Sortable Collection имплементира Interpolatable, то цялата колекция не може да работи с примитвни числови типове (int, double, long и т.н.) защото те не имплементират интерфейса. Ако пък обратно се опиташ да зададеш че само T то в методът е Interpolatable, то не може да го сравниш със Т то на SortableCollection, защото нито едно от тях не имплементира IComparable със другото (а са 2 различни generic-а вече - едното е Interpolatable, другото не е), дори и да му зададеш че е IComparable със другото Т (което е доста измислено, защото значи че всеки клас който е interpolatable, ще знае как да се сравнява със всеки generic клас, който могат да му подадат), то удряш друг проблем как подаваш на овърлоуднатият метод InterpolateSearch<T>(IList<T> list, T needle) where T: IComparable<T>, Interpolatable<T>
колекцията с която ще работи. Колекцията очевидно трябва да е this.Items но обектите в Items не имплементират Interpolatable и съответно колекцията не може да бъде подадена към методът. За жалост се оказва че не може да има овърлоуди на оператори в интерфейс, иначе работата щеше да е бая по лесна.

Та в крайна сметка разбрах че само int-ове ще са, но да прекастваме всеки елемент към инт в методът изглежда като бая лоша практика, някой измислил ли е по елегантно решение на проблема?

10/10/2015 14:52:59

enevlogiev 1168 Точки

Ами, единия метод приема List<int>, int needle, другия List<T>, T needle. Лесно се разграничават двата. Проблемите идват от класа, който наистина е ограничен.

10/10/2015 15:59:40

Покажи всички коментари

Den1eD 5 Точки

Колега,

би ли споделил ако си намерил решение, понеже и аз стигнах до там

07/10/2015 15:50:13

djc_bg2015 923 Точки

Ами не съм,

препдолагам че може да кастем Т-то към инт, но тогава се губи смисъла да е генерик функцията...

Надявам се някой да даде по - смислен отговор ...

07/10/2015 15:52:06

aanguelov 219 Точки

Всъщност от това, което прочетох като коментари из нета се подразбира, че за T value различно от инт няма смисъл да се прилага Interpolation Search.

Това, което печелим от бързината на въпросното сортиране, го губим при изчисляване на midPoint за Т стойности различни от int.

07/10/2015 17:01:59

djc_bg2015 923 Точки

Съгласен съм напълно с теб.

07/10/2015 19:52:05

ttitto 1153 Точки

Този проблем, че на генеричен клас не можем да зададем условие Т да имплементира някакъв оператор го разреших чрез делегати. На сортабъл колекцията подавам в нов конструктор два делегата Func<T, T, int> Multiply и Func<T,T,int> Subtract. В класа, който ползва колекцията (в случая компонентните тестове) се имплементират два метода, които връщат инт и се подават при инициализацията на сортабъл колекцията. Кодът може да се види тук ред 23 и 95 и употреба в тестовете

Другото, което си мислех е, дали не може да се използва getHashCode за приравняване на обект от тип T към int и на тази основа да се прави интерполацията. Но първият вариант ми се стори по-привлекателен и реших да се занимавам само с него.

11/10/2015 11:08:59

dim4o 288 Точки

Интересно е решението с делегатите. Единствено на 111-ти и 115-ти ред според мен изразите в условията трябва да са с различни знаци, за да работи правилно.

И аз мислех за GetHashCode(), но не съм го пробвал, защото ако o1.CompareTo(o2) > 0 то o1.GetHashCode() > o2.GetHashCode() изобщо не е задължително. Дори по някакъв GetHashCode() имплементацията да се обвърже с CompareTo() пак няма да стане в общия случай.

11/10/2015 15:17:14

ttitto 1153 Точки

Да, трябва да обърна знака на 115ти ред. Благодаря!

11/10/2015 15:30:35

dim4o 288 Точки

Относно тестовете: аз правя нещо от сорта Assert.AreEqual(element, collection[result]). Така независимо дали има повтарящи се елементи пак може да се тества за правилна работа. Иначе е вярно, че ако имаме {.....3, 4, 4, 4.....} и търсим 4 няма как да знаем на кой индекс ще ударим.

11/10/2015 15:38:05