Četnost stringů ve stringovém poli – .NET – Fórum – Programujte.com

Dobrý den,
mám algoritmickou otázku. :)
Mám relativně velké pole stringů (jeden string = 20 znaků a stringů je kolem 2000) s tím, že někde se stringy opakují. Potřeboval bych vytáhnout ty stringy, kterých je nejvíce, druhých nejvíce a třetích. Jediná možnost jak toto udělat mě napadlo udělat si vlastní třídu, která bude obsahovat string a četnost. Pak nějaké dynamické pole (třeba List<>) a postupně do něj ukládat četnosti k jednotlivým stringům (vždy si kontrolovat jestli už tam daný string je..). Toto pole se potom vyhodnotí. Nicméně zdá se mi to jako jít s kanónem na komára.
Máte nějaké lepší obecné řešení nebo přímo kód v C#?
Díky

Určitě to takhle jde. Nebo bys je mohl seřadit a potom jenom počítat ve foreach. Určitě to sice jde lépe, ale nenapadá mě jak...

Možná než kontrolovat, jestli už v poli řetězec je, si vytvořit hash, kde by klíči byly ty řetězce a hodnotami jejich četnost.

Možná že vhodným objektem pro ukládání by mohl být Dictionary<string, int>

To velurex : o takovy class sem nikdy neslysel... mozna Map

No 100% bych vyuzil nejakou hash funkci.K tomu bych pouzil asi binarni strom,ve kterem by byla ulozena ta hash a pocet vyskytu dane hashe.Tim by se zajistilo nejrychlejsi prirazovani a pocitani stringu.Pak je akorat mensi problem v setrizeni tech vysledku.Ale na to by se dal opet pouzit nejaky binarni strom v tom samem principu.Ale hodne to zalezi na konkretnich vstupnich datech.

dannyk
K tomu bych pouzil asi binarni strom … Ale na to by se dal opet pouzit nejaky binarni strom v tom samem principu.
Ty jsi asi hodně zatížený na binární stromy, že? :o) Binární strom by navíc při přidávání měl složitost O(log N), normální hash O(1). Seřazení by podle mě nejjednodušší bylo procházet hash a použít heapsort (doufám, že to říkám správně; takové to třídění, jak tam „zaplouvá“ jeden prvek za druhým, čímž se řadí :o)).

velurex, KIIV
hash, hashmapa, map, mapa, slovník, dictionary, table (v Lue[1], i když tam je to kombinace hashe a pole)… Není to všechno jedno a to samé? :o)

[1] http://lua.org/

Jo,sem na ne docela zatizeny,protoze se mi v praxi uz docela osvedcily a hlavne nam to docela tvrde valili do hlavy :D
Hash me napadl taky,konkretne pro c# napr. Hashtable,kterej by byl idealni,ale nevim,jak je na tom s rychlosti vyhledavani apod.Proto to muze bejt treba jeste pomalejsi nez u toho stromu :),ale je to o testovani...

Chtělo by to tady udělat pořádek. Hash funkce by mohla fungovat sice dobře, ale v nehorším případě může spadnout na složitost O(n) u vyhledávání (kolize indexů).
Nejlepší řešení je rozhodně lineární trie s četnostmi.