Софтуерно Инженерство
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
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