Loading...
djc_bg2015 avatar 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]);

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

Тагове:
5
Структури от данни и алгоритми 06/10/2015 00:04:02
ttitto avatar ttitto 1153 Точки

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

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

2
dim4o avatar dim4o 288 Точки

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

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

1
ttitto avatar ttitto 1153 Точки

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

0
dim4o avatar dim4o 288 Точки

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

2
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.