Ejla!
Uporabljam BinarySearch metodo od Array objekta nad enim izmed polj zaradi boljše perfomance. Ker je moj array neurejen, ga morm še prej sortirat, da mi BinarySearch dela pravilno. Zanima me, ali obstaja kaka druga metoda, ki je O(log(n)) - v najboljšem sposobna poiskat en element v seznamu?
Avtor: bojanv, objavljeno na portalu SloDug.si (Arhiv)
bojanv - torek, 09. januar 2007
To počnem za zabavo in delno tudi za job, ker bi rad mel nekaj efektivnega v rokavu, ko pride do zapletov. Ko boš mel, mi kr pošlji na mail. Itak ga maš al pa daj pod files na CodeZone-u.
spirit1 - torek, 09. januar 2007
tole je implementacija FindAll-a:public List<T> FindAll(Predicate<T> match){ if (match == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); } List<T> list1 = new List<T>(); for (int num1 = 0; num1 < this._size; num1++) { if (match(this._items[num1])) { list1.Add(this._items[num1]); } } return list1;} jah v 1.1 bi lahko dal kvecjemu generalni objekt...aja pa da se ne bos zezal z odkrivanjem tople vode: IL generation rules!http://weblogs.sqlteam.com/mladenp/articles/10488.aspxodvisno je seveda koliko je zate "veliko" elementov.jaz sem moj sorter recimo uporabljal na milijonu objektov z dosti propertiji itd... pa je bil sorting hiter ko strela. find je potem samo se stvar O(n)-ace ti pa to ni sprejemljivo pa se vedno lahko implementiras multithreaded map-reduce algoritem... to imam celo en base library ki mi bo sluzil za diplomo in ga bom postal cez kak mesec ali dva...ce se ti da pocakat...
bojanv - torek, 09. januar 2007
Iščem nekaj, kar ni z generiki, da lahko uporabljam tudi za kasnejše verzije, ker imam določene produkte narejene še v 1.1. Lahko mi pa razložiš, kako naj v 1.1 uporabim generike. Recimo, rad bi imel vmesnik za 1.1. in 2.0:public interface ISortable<T> : ISorting<T> {T[] Sort(params T[] items);.........}Kako naj dosežem, da mi bo to delalo v 1.1.?Hm, no, trenutno naj bi bila najhitrejša sorting algoritma (vsaj po Wikipediji in knjigah) QuickSort in RadixSort (za nekatere je to najboljši), čeprav je LibrarySort kr primerjiv, samo pade pri velikih podatkih oziroma te košta placa Kateri algoritem pa uporablja FindAll?
spirit1 - ponedeljek, 08. januar 2007
isces nekaj kar ni z generiki da zozas svoj izbor???emm.... huh? oksimoron mogoce? a generiki ti niso dovolj ozki? in pa dejstvo je da pod O(n) pri nesoritanem ne prides.... ce pa ze prides te pa nominiram za neko nagrado
bojanv - ponedeljek, 08. januar 2007
Z List<T>.FindAll ni nič narobe. Je sicer O(n) perfomansa, iščem pa nekaj, kar ni povezano z generiki, da zožam svoj izbor. Ukvarjam se trenutno z perfomansami pa iščem primerne rešitve za boljšo kodo in mojo osebno zadovoljstvo
spirit1 - petek, 05. januar 2007
in kaj je narobe z List<T>.FindAll metodo?
bojanv - petek, 05. januar 2007
Gre za nekaj tisoč elementov (nekaj tisoč zaradi tega, ker se dinamično število spreminja). Iskanje pa izvajam pogostokrat, ker je ključni del moje objektne strukture. Ker bi rad čimbolje izkoristil framework in zmanjšal čas iskanja, me zanimajo opcije, ki so mi na voljo. Pogosto sem uporabljal že ta način oziroma z generiki ter overload operatorji, zanimam se pa tudi za druge rešitve.
ExAmigan - četrtek, 04. januar 2007
Za neurejen seznam teorija uči, da pod O(n) ne boš prišel. Najboljša rešitev je sprehod čez vse elemente, za katerega v povprečju velja T(n) = n/2. Sortiranje in naknadno iskanje z bisekcijo je slabša rešitev, saj zaradi sortiranja zahteva O(n log(n)). Se pa to na dolgi rok lahko spremeni, če po nespremenjenem seznamu iščeš večkrat, ker sortiranja ni potrebno ponavljati.V situaciji, ko je iskanje bolj pogosto od spreminjanja, se ti verjetno bolj splača imeti podatke že urejene v podatkovni strukturi. Vse je odvisno od tipičnega scenarija uporabe.Sicer pa, o kolikšnem številu elementov in kako pogostem iskanju sploh govorimo? Verjamem, da pri zgolj nekaj elementih tega ne bi spraševal.