Četnost stringů ve stringovém poli – .NET – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

Pepa_z_Depa
~ Anonymní uživatel
1 příspěvek
9. 8. 2008   #1
-
0
-

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

Nahlásit jako SPAM
IP: 77.48.127.–
MZetko0
Stálý člen
9. 8. 2008   #2
-
0
-

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...

Nahlásit jako SPAM
IP: 83.208.235.–
"Přirozená inteligence bude umělou brzy překonána. Přirozenou blbost však umělá nemůže nahradit nikdy"
Jára da CIMRMAN
http://www.newgame.cz
bukaj0
Věrný člen
9. 8. 2008   #3
-
0
-

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.

Nahlásit jako SPAM
IP: 85.70.13.–
Jak se správně ptát? -> http://www.hash.cz/inferno/otazky.html[br][br] Po programování je člověk hladovej.
velurex0
Stálý člen
9. 8. 2008   #4
-
0
-

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

Nahlásit jako SPAM
IP: 62.77.91.–
KIIV
~ Moderátor
+43
God of flame
4. 9. 2008   #5
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
dannyk0
Věrný člen
4. 9. 2008   #6
-
0
-

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.

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
bukaj0
Věrný člen
4. 9. 2008   #7
-
0
-

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/

Nahlásit jako SPAM
IP: 85.70.13.–
Jak se správně ptát? -> http://www.hash.cz/inferno/otazky.html[br][br] Po programování je člověk hladovej.
dannyk0
Věrný člen
4. 9. 2008   #8
-
0
-

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...

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
Prosím vás
~ Anonymní uživatel
1 příspěvek
4. 8. 2009   #9
-
0
-

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.

Nahlásit jako SPAM
IP: 83.208.235.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 6 hostů

Podobná vlákna

Četnost známek — založil cmoudek

Četnost vstupních čísel — založil elijax

četnost znaků ve vb6 — založil Milan Pavel

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý