Unikalus teksto failas

Sveiki,

Norėčiau paprašyti jūsų pagalbos.

Gal žinot programą ar kokį nors būdą išspręsti šią problemą :

Du teksto failai

Failas A (400 tūkst. eilučių)

Failas B (600 tūkst. eilučių)

Reikia,kad visus žodžius iš Failo A, kurie dublikuojasi su failo B žodžiais ištrintų ir liktų tik unikalūs.

Bandžiau kažką per excel, per daug eilučių - užlūšta. Bandžiau ieškot kitų programų bet artimiausią variantą ką radau tai tiesiog lygina pirmą eilutę A failo su pirma eilute B failo.

O reikia kad paimtu pirmos eilutės žodį A failo ir patikrintų 600 tūkst eilučių B failo ar nėra atitikmens:)

Gal turit ką nors pasiūlyt?

Jei nori pats programą parašyti, tai pirmas žingsnis būtų išrikiuoti žodžius abiejose failuose, taip galėsi parašyti efektyvesnį paieškos algoritmą. Rikiavimas aišku yra O(nlogn), o per du išrikiuotus masyvus praeiti ir beieškant sutampančių/nesutampančių žodžių gali per O(n), tai sumoje gaunasi O(nlogn) sudėtingumas. Kažkiek laiko užtruks, bet jei tau to nereikia kiekvieną sekundę daryti, tai manau nebus problemų nueiti ir pasidaryti kavos, kol programa dirba.

O jei nenori pats programuoti, tai nepadėsiu, jokių įrankių tam skirtų nežinau.

Susisiekta. Teoriškai O(N*N) sudėtingumas tokiu mastu nelabai veiks reikia sugalvot kažkokį apėjimą nebent tu nori laukt tris valandas ar net ilgiau ;D. Dar viena bėda gali būti jeigu tavo eilutėse yra po dar 100k žodžių tai nemanau kad apsimoka vargti ;D

Numečiau į PM

Jei kamnors įdomu raštelkit į pm numesiu kodą.

Jei kamnors įdomu raštelkit į pm numesiu kodą.

Ką nors įdomesnio sugalvojai nei aš parašiau?

Ką nors įdomesnio sugalvojai nei aš parašiau?

Su HashMap'u amortizuotas laikas būtų O(n).

C++ turi setus, čia hashmapo perdaug būtu kadang storinam tik vieną value.

Tai teoriškai sudėtingumas būtu O(N + M + C), jei

N - pirmo failo dydis (žodžių kiekis)

M - antro failo dydis (žodžių kiekis)

C - tie likę žodžiai kuriuos reikia išvesti.

C++ turi setus, čia hashmapo perdaug būtu kadang storinam tik vieną value.

 

Tai teoriškai sudėtingumas būtu O(N + M + C), jei

N - pirmo failo dydis (žodžių kiekis)

M - antro failo dydis (žodžių kiekis)

C - tie likę žodžiai kuriuos reikia išvesti.

Taip, hashset'as tinkamesnis.

Šiaip dar galim įskaičiuoti kokio ilgio vidutinis žodis ir parašyti O(SN + SM + SC), bet sudėtingumas vis tiek tiesinis ir pakankamai kvailai atrodo tas bandymas perspjauti vienas kitą su smulkmenom…

Pritariu ;D

If N elements are inserted, Nlog(size+N) in general, but linear in size+N if the elements are already sorted according to the same ordering criterion used by the container ( http://www.cplusplus.com/reference/set/set/insert/ ). Tačiau šis metodas vis tiek turėtų būti greitesnis nei mano, nors aišku paprasčiausia būtų patestuoti tai, bet kas tam turi laiko :)

Jo atvėju jam nereikia surikiuotų elementų tai galima naudoti http://www.cplusplus.com/reference/unordered_set/unordered_set/

Kuris teoriškai veikia greičiau.