Софтуерно Инженерство
Loading...
+ Нов въпрос
djc_bg2015 avatar djc_bg2015 922 Точки

[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]);

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

Тагове:
5
Структури от данни и алгоритми 06/10/2015 00:04:02
enevlogiev avatar 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 пъти като термин ; )

9
07/10/2015 21:23:42
djc_bg2015 avatar djc_bg2015 922 Точки

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

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

1
Innos avatar Innos SoftUni Team 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-ове ще са, но да прекастваме всеки елемент към инт в методът изглежда като бая лоша практика, някой измислил ли е по елегантно решение на проблема?

2
enevlogiev avatar enevlogiev 1168 Точки

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

1
Den1eD avatar Den1eD 5 Точки

Колега,

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

0
djc_bg2015 avatar djc_bg2015 922 Точки

Ами не съм,

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

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

0
aanguelov avatar aanguelov 219 Точки

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

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

2
djc_bg2015 avatar djc_bg2015 922 Точки

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

0
ttitto avatar ttitto 1154 Точки

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

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

2
dim4o avatar dim4o 289 Точки

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

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

1
ttitto avatar ttitto 1154 Точки

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

0
dim4o avatar dim4o 289 Точки

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

2