Upozornění na nový obsah pomocí RSS.
Upozornění na nový obsah pomocí e-mailu.
Analýza DNA - nejčastější výskyt nejdelšího řetězce
Takové je zadání mé semestrální práce na algoritmizaci. Pokud mám dostat A, musím tento řetězec najít v 1MB souboru plném znaků za <= 3 vteřiny (bez použití superpočítače).
Pokud máte tip na algoritmus nebo jen nápad, jakým směrem se vydat, určitě se ozvěte. Může to pro mne být klíčový bod.
29.11 /2008 - 16:16 
6 komentářů
Akademická roadshow - seminář microsoftu »« Tipy na dárky - Vánoce 2008
Nenechte si ujít
Nejčtenější články za poslední půlrok.
- Bylo nás pět a byli jsme v Thajsku během povodní 2011
(přečteno 968x | komentováno: 2x)
Nejkomentovanější články za poslední půlrok.
- Bylo nás pět a byli jsme v Thajsku během povodní 2011
(přečteno 968x | komentováno: 2x)
Nejčastěji komentující čtenáři za poslední půlrok.
- Veronika (3)
- Vlak (2)
- Václav (2)
- Antonín Daněk (2)
- MArtin (2)
Výběr zajímavých stránek.
delicious (profil)
blogy
- Weblog Tomáše Kápla / ČVUT FEL
- Alenčin Bložínek / ČVUT FEL
- Co de asi ? / ČVUT FEL
- Weblog Michala Frdlíka / JČU PF
- Noční pták
- Weblog Petra Mika / ZČU FAV
v angličtině
Zaujala vás tato bleskovka? Nezapomeňte, že je ve vaší moci ukázat stovkám dalších lidí, že tento text se vám libí. Stačí kliknout na následující tlačítko.
Chcete být upozorňován(a) na nové texty? Pak si přidejte do své RSS čtečky zdroj pro články, bleskovy nebo komentáře a buďte tak informování o všem novém.
Neváhejte napsat k bleskovce komentář (Co je to komentář ?), pokud máte k danému tématu co říci.
Pomohla by struktura toho souboru (taky přesně nechápu, co má být výsledkem).
Ty řetězce určitě musí být oddělený nějakým znakem. Tak bych ten soubor převed do paměti ve formě pole (má java integrovanou funkci split?), který bych pak vysortoval (dobře napsaným heapsortem) ne podle obsahu prvků, ale podle "length" jejich prvků (java určitě něco takovýho má). Potom už se s tím dá jednoduše pracovat.
- Na komentář odpověděl(a) Antonín Daněk v komentáři #2
comV tom souboru je řetězec skládající se z asi 5 znaků, náhodně se opakujících. Máš najít nejdelší opakující se podřetězec. Příklad:
ABCDAADEABCDAD
Výsledek: ABCD 1 9
(1 a 9 je pozice, kde ten opakující se řetězec je, ale to už je kosmetika, kterou neni problém dopsat, tak jsem jí ani nezmiňoval.)
Žádný oddělovače tam nejsou. Split asi Java nemá, ale nebyl by problém ho napsat, kdyby to k něčemu bylo. Length má.
Ty jsi vážně myslel, že máme jako semestrální práci najít nejdelší prvek pole? 
A ještě dodatek. Opět se ukázalo, že se stačí umět správně zeptat a odpověď už neni tak složitá. Včera jsem chvíli Googlil, pročetl pár článku a dostal jsem se k tý správný otázce. Takže tahle bleskovka už tak úplně neplatí, resp. si myslim, že už vim, jak to vyřešit rychle.
- Na komentář odpověděl(a) Antonín Daněk v komentáři #3
- Tento komentář je reakcí na příspěvek #1, který napsal(a) Michael
Ups ten příklad jsem udělal moc složitej.
Výsledek je taky: BCDA 2 10
Řetězce se mohou překrývat. Tzn. výsledek pro BBBB je: BBB 1 2
- Tento komentář je reakcí na příspěvek #2, který napsal(a) Antonín Daněk
Tak to už je zajímavější. První, co mě napadá je hrozně časově náročný :).
Měl bych
ABCDAADEABCDADABCDAADEABCDAD
ABCDAADEABCDAD ABCDAADEABCDAD
(rozdělil bych napůl, protože polovina je maximální velikost, která se ještě může opakovat)
|AB CDAADEABCDAD | ABCDAADEABCDAD|
(porovnal bych to AB z první části se druhou, když se vyskutuje, jdu dál)
|ABC DAADEABCDAD | ABCDAADEABCDAD|
(porovnám ABC s druhou částí... a když narazím na něco, co se neshoduje, je logický, že od Ačka už to řadu nebudu navyšovat a předchozí řetězec si uložím. pak budu zkoušet takhle)
(A)|B CDAADEABCDAD | ABCDAADEABCDAD|
(Ačko vynechám a budu tvořit řady od dalšího písmene a budu postupovat stejně jako prve)
A když dojdu do fáze, že řada, kterou mám uloženou v paměti jako zatím největší shodující se, je větší než zkoumaná část prvního řetězce, můžu hledání ukončit, protože nic, co najdu už nebude větší.
Určitě v tom najdeš chyby, nebo to minimálně bude hrozně pomalý... vymyslel jsem to teď namístě :).
Jj, něco podobnýho mě taky napadlo bez čtení nějakých nápadů na internetu.
Teda úplně první nápad byl čistě hrubou silou. Ale složitost byla exponenciální (navíc ještě základ byl násobenej), což je asi nejhorší složitost algoritmu jaká může bejt a pro mých 1 000 000 znaků by to celý trvalo pár let.
Pak mě napadlo něco podobnýho co tebe. Jenom bych nejel od nejkratšího ale od nejdelšího.
Totiž pro porovnání dlouhýho řetězce bude třeba jen pár průchodů, ale třeba hned první test když pojedeš od začátku (1 znak) zabere 1 000 000 průchodů. A o DNA je známo, že se v ní opakují dost velký části (z bezpečnostních důvodů, nižší náchylnost k mutacím).
Taky bych nekontroloval jenom řetězec z první půlky s druhou půlkou, protože ten řetězec se může klidně opakovat i v první půlce a navíc by se mohlo stát, že by opakovaný řetězec byl zrovna na předělu (tam kde jsi řetězec rozpůlil).
Jenže tady v tomhle způsobu je jeden problém a to jak narvat tak dlouhej řetězec do jednoho Stringu.
No je to docela složitý, i když to na první pohled tak nevypadá. 
- Tento komentář je reakcí na příspěvek #4, který napsal(a) Michael
Tak pardon, nenapadlo mě něco podobnýho.
Už ta prvotní úvaha, že polovina je maximální velikost, která se ještě může opakovat, je špatná. Jak jsem napsal:
Řetězce se mohou překrývat. Tzn. výsledek pro BBBB je: BBB 1 2
Takže opakovat se může klidne řetězec n-1, kde n je dělka prohledávaného řetězce.
- Tento komentář je reakcí na příspěvek #4, který napsal(a) Michael