Identtisten rivien poisto

[viesti Survo-keskustelupalstalla (2001-2013)]

Yleisessä keskusteluryhmässä sfnet.atk.ohjelmointi.moderoitu
Markus Hakalin kirjoitti 19.2.2002 otsikolla
"Identtisten rivien poisto" seuraavaa:

> Minulla on tekstitiedostoja joissa on 600 000 - 1000 000 riviä
> xyz-koordinaatteja. Ongelma on seuraava: tiedostoissa on 1/2-2/3
> riveistä liikaa eli ovat siis 2 tai 3 kertaan samassa tiedostossa.
> Identtiset rivit pitäisi saada pois. Joissakin tapauksissa 2
> peräkkäistä riviä voivat olla identtiset mutta pienen tarkastuksen
> jälkeen siihenkään ei voi luottaa. Eli käytännössä rivit ovat aika
> sekalaisessa järjestyksessä.
> 
> Tein pienen c-ohjelman joka toimii siten että minulla on alkuperäinen
> tiedosto ja sitten toinen, tulostiedosto jossa on alkup. tiedoston 1.
> rivi. Ohjelmani ottaa ensin karsittavasta tiedostosta rivin ja tutkii
> sitten että onko sitä tulostiedostossa. Jos ei niin sitten laitetaan
> rivi sinne, jos on niin skipataan rivi ja otetaan lähtötiedostosta
> seur. rivi ja tutkitaan taas.
> 
> Tuo kestää pirullisen kauan per tiedosto. Onko olemassa mitään
> tehokkaampaa tapaa tehdä tuota? En ole mikään
> algoritmi-/ohjelmointiekspertti joten jos vastailet niin kirjoita
> vastaus niin että kadunmieskin ymmärtää :)
> 
> Markus

Ongelmaan on tähän mennessä tullut useita päteviä ratkaisuja, joista
osa perustui aineiston lajitteluun ja osa mm. hash-taulukkotekniikkaan.
Niitä voi käydä katselemassa ao. keskustelusäikeestä.
Koska jollain tapaa vastaukset olivat pikemmin ammattiohjelmoijan
kuin "kadunmiehen" tasoisia, päätin kirjoittaa seuraavanlaisen
viestin tuohon ryhmään:

> Palaisin vielä Markus Hakalinin esittämään alkuperäiseen kysymykseen:
>> Minulla on tekstitiedostoja joissa on 600 000 - 1000 000 riviä
>> xyz-koordinaatteja. Ongelma on seuraava: tiedostoissa on 1/2-2/3
>> riveistä liikaa eli ovat siis 2 tai 3 kertaan samassa tiedostossa.
>> Identtiset rivit pitäisi saada pois....
>> ...
>> ... jos vastailet niin kirjoita vastaus niin että kadunmieskin
>> ymmärtää :)
> 
> Kysymykseen on saatu asiallisia ja ansiokkaita vastauksia, jotka
> tyydyttivät kysyjää (koska hänellä koordinaattien esitykset olivat
> mitä ilmeisimmin yksikäsitteiset).
> Kuitenkin jos asiaa tarkastelee aidon kadunmiehen (s.o. mitä
> "kadunmiehellä" normaalisti tarkoitetaan eli esim. tavallisen PC-
> käyttäjän) tasolta, en olisi aivan tyytyväinen mihinkään esitetyistä
> ratkaisuehdotuksista.
> 
> Ymmärrän kyllä, että koska kysymys esitettiin ohjelmointia koskevassa
> keskustelussa, siihen vastattiin ohjelmoinnillisin ja käyttö-
> järjestelmätasoisin keinoin.
> Oma pointtini on kuitenkin siinä, että itse ongelma on erikoistapaus
> laajemmasta ylimääräisen tiedon suodatustehtävästä ja sitä ainakin
> kadunmiehen tasolla tulisi mieluummin lähestyä sopivien, valmiiden
> sovellusohjelmien avulla.
> 
> Oman pitkän työkokemukseni aikana olen havainnut tavantakaa, miten
> tärkeätä on tunnistaa ongelman olennaiset elementit ja yleisyys-
> aste ennenkuin lähtee laatimaan ratkaisua joko ohjelmoimalla itse tai
> käyttäen valmiita ohjelmia.
> 
> Jori Mäntysalo jo kyseli mm.
>>  ... kerro saako rivien järjestys muuttua, millaisia rivit ovat
>> (kuinka pitkiä, vaihteleeko pituus) ja onko riveillä esimerkiksi
>> ylimääräisiä välilyöntejä jotka pitää huomioida tms? ...
> 
> Siis, jos ei voitaisikaan luottaa identtisiksi tarkoitettujen rivien
> identtisyyteen tavutasolla, mikään esitetyistä ratkaisusta ei olisi
> mielestäni kelvollinen.
> 
> Tässä tapauksessa luonteva yleistys on eristää kultakin riviltä
> koordinaatit x,y,z omiksi muuttujikseen tarvittaessa sopivin
> pyöristyksin, lajitella syntynyt kolmen muuttujan aineisto
> hierarkisesti näiden muuttujien suhteen, sitten laskea jokin
> peräkkäisten pisteiden samuutta kuvaava tunnusluku, esim. euklidisen
> etäisyyden neliö ja lopuksi karsia ne pisteet, joiden poikkeama
> edellisestä pisteestä alittaa sovellutuksen kannalta sopivan
> kynnysarvon.
> 
> Ratkaisu eri vaiheineen on tietenkin selvästi raskaampi pelkkään
> suoraan rivien identtisyyteen perustuviin menettelyihin verrattuna
> mutta kelvollinen yleisemmissä tilanteissa.
> Sitä ei nähdäkseni kuitenkaan pysty tekemään suorilla käyttö-
> järjestelmäkomennoilla. Oman ohjelman teko tulee sekin
> kysymykseen lähinnä vain tilanteissa, joissa halutaan maksimaalista
> tehoa ja omataan (kadunmiehen taidot ylittävä) ohjelmointitaito.
> 
> Puuttumatta siihen, miten tuo yleistetty ongelma ratkaistaan muilla
> työkaluohjelmilla, laadin SURVO MM -ohjelmistolla muutaman lyhyen
> rivin mittaisen ratkaisun, johon voi tutustua Survon verkkosivuilla
> www.survo.fi kohdassa Keskustelu (Identtisten rivien poisto).
> 
> Seppo Mustonen

Tässä on nyt eräs edellisen kuvauksen mukainen ratkaisu Survolla
tehtynä.
Tehdäkseni asian konkreettisesti luon aluksi mallitiedoston, joka
vastaa luonteeltaan alkuperäistä tilannetta.

Tehdään miljoonan havainnon ja 3 muuttujan X1,X2,X3 Survo-
datatiedosto KOE0, jossa kaikki havaintoarvot ovat toisistaan
riippumattomia satunnaislukuja välin [0,39] diskreetistä
tasajakaumasta.
............................................
FILE MAKE KOE0,3,1000000,X,2         / Tiedostokehikon luominen
TRANSFORM KOE0 BY int(40*rand(2002)) / Satunnaislukujen laskenta
FILE LOAD KOE0 TO KOE.TXT    / Aineiston siirto tekstitiedostoon
FILE DEL KOE0                / Datatiedoston KOE0 hävittäminen
............................................
Tekstitiedosto KOE.TXT, joka nyt toimii varsinaisen ratkaisun
mallikohteena näyttää alkupäästään seuraavalta:
LOADP KOE.TXT,1,10,CUR+1
     X1     X2     X3
     11     14     23
     22     18     11
     33     27     22
      9     32     32
      2      4     16
     32      5      8
     25     14     33
     10      5     29
      2     39      7

Miljoonan pisteen (X1,X2,X3) tekstitiedosto, joka on ratkaisun
lähtökohtana, on siis luotu.
Varsinainen ratkaisu on seuraava:
............................................
FILE SAVE KOE.TXT TO KOE / Kopioidaan KOE.TXT Survo-dataksi KOE.
Sitten lajitellaan KOE hierarkisesti muuttujien X1,X2,X3 suhteen:
FILE SORT KOE BY X1,X2,X3 TO KOE_SORT
............................................
Lasketaan järjestetystä aineistosta KOE_SORT peräkkäisten pisteiden
etäisyyksien neliöt:
VAR D2=if(ORDER=1)then(10000)else(D) TO KOE_SORT
                D=(X1-X1[-1])^2+(X2-X2[-1])^2+(X3-X3[-1])^2
............................................
FILE DEL KOE2 / Tuhotaan varmuuden vuoksi lopullinen tulostiedosto.
Kopioidaan vain ne havainnot, joilla poikkeama on >0, tiedostoksi KOE2.
FILE COPY KOE_SORT TO KOE2 / IND=D2,1,10000
............................................
Jos halutaan, voidaan vielä hävittää apumuuttuja D2
FILE REDUCE KOE2,3
ja kopioida datatiedosto KOE2 vastaavaksi tekstitiedostoksi:
FILE LOAD KOE2 TO KOE2.TXT
............................................

Näin on tehtävä ratkaistu. Tässä tapauksessa, koska mahdollisia
koordinaattikolmikkoja on 40^3=64000 kpl, tulostiedosto sisältää
juuri tuon määrän havaintoja, mikä osoittaa, että kaikki "löysät"
on otettu pois.

Tässä ratkaisussa alkuperäisten pisteiden järjestys on lajittelun
ansiosta muuttunut (tuloksena systemaattinen luettelo).
Jos halutaan palauttaa alkuperäinen järjestys, riittää, että em.
ratkaisua täydennetään niin, että ennen lajittelua dataan
KOE luodaan järjestysnumeromuuttuja esim. komennolla
VAR NRO:8=ORDER TO KOE
ja lopuksi lajitellaan KOE2 tuon muuttujan suhteen uudelleen.

Yleensäkin tämänmuotoista ratkaisutapaa voi muutella ja kehitellä
eri suuntiin tarvitsematta ryhtyä varsinaiseen ohjelmointiin.
Muuntelua helpottaa sekin, että Survolle ominaiseen tapaan
työ on dokumentoinut itsensä (juuri tässä näkyvään muotoon).

Tämän kokeen jälkeen on vielä syytä poistaa kaikki koetiedostot
esim. komennoin
FILE DEL KOE
FILE DEL KOE_SORT
FILE DEL KOE2
FILE DEL KOE.TXT
FILE DEL KOE2.TXT

Seppo Mustonen

Luettelo keskustelunaiheista

Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!