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.
michaelf.ms<zavináč>gmail
com
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.
danek<zavináč>antonindanek
cz
V 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.
danek<zavináč>antonindanek
cz
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
michaelf.ms<zavináč>gmail
com
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ě :).
danek<zavináč>antonindanek
cz
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á.
danek<zavináč>antonindanek
cz
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.