Keskustelu: Nettisivujen teko: Samanlaisten rivien poisto tiedostosta

Moikka,

Mikä olisi nopein koodi / tapa poistaa samanlaiset rivit tekstitiedostosta?
Tiedostosta löytyy id, workid, machid jne pilkulla eroteltuna tosin tällä ei taida olla väliä kun olisi pelkästään samanlaiset rivit tarkoitus poistaa.

eli esimerkiksi nämä rivit:
4, 2338, 32
5, 219, 84
4, 2338, 32
4, 2338, 32

muuttuvat tähän muotoon:
4, 2338, 32
5, 219, 84

Eli tämä on töistä tehtävä kuukausikooste, mitä ei voi ymmärtää suoraa avaamalla tiedostoa, mutta voidaan kuitenkin lukea myöhemmin sivuilta löytyvän automatiikan avulla.

Muuten olen saanut tehtyä tiedoston käsittelyt vaikken näitä kovin hyvin osaakkaan, yleensä tietokannan kanssa teen näitä asioita, mutta tätä en ymmärrä.

Rivejä voi tiedostossa olla parikymmentätuhatta ja tämän siistimisen jälkeen niitä jää oletettavasti tuhat taikka kaksi.

Onko ainoa keino käydä kaikki rivit jokaisen rivin kanssa? Tuntuu melko tehottomalta ja aikaa vievältä..

Nopein algoritmi on luokkaa O(n), missä n on rivien lukumäärä tiedostossa. Tämä siksi, että jokaista riviä on tarkasteltava ainakin kerran. Miten tähän päästään? Voit järjestää rivit pikajärjestämisalgoritmilla ajassa O(log_2 n). Sitten vertailet jokaista riviparia (i,i+1) ja poistat tuplat.

Jaskalta tuli nopea vastaus, mutta ainoa minkä ymmärsin oli tuo riviparien vertailu (i,i+1). Mikä on tuo pikajärjestämisalgoritmi?

"SORT text1.txt text2.txt" komentoriville

(tiedostot polkuineen tai siirry niiden hakemistoon)

text1.txt = sortattava tiedosto
text2.txt = muodostuva sortattu tiedosto

Kokeile vaikka :

$arvot = array_unique(file("source.txt"));
$fp = fopen('target.txt', 'w');
foreach($arvot as $rivi)
   fwrite($fp, $rivi);

jtha tuo on hyvä tietää!

Kokeilin makumakun koodia ja toimii muuten loistavasti muttei ota huomioon tiedoston viimeistä riviä?

Eli esimerkkirivit: (source)

4, 2338, 32
5, 219, 84
5, 219, 84
4, 2338, 32
4, 2338, 32
4, 2338, 38
4, 2338, 32

Tuli tämmöiset: (target)

4, 2338, 32
5, 219, 84
4, 2338, 38
4, 2338, 32

Useampi testi näytti että kyse on aina viimeisestä rivistä.
Mistä moinen johtuu?
Kokeilussa ainoastaan tuo makumakun koodi ilman lisäyksiä/muutoksia.

Edit, mikäli kenellekkään ei tule mieleen miten asian voisi yksinkertaisesti korjata niin tyydyn tähän ja pistän koodinpätkän mikä lisää 0,0,0 rivin tiedoston loppuun ja poistaa sen rivin kun on tehnyt hommansa. Oikotie? juu...

Tiedoston lopettava rivinvaihto puuttunee, joten viimeinen rivi on erilainen ja tulostetaan.

Tässä on toinen ratkaisu:

<?php
$mukana = array();
$rivit = file("tiedosto.txt");
$uusi = fopen("tiedosto.txt", "w");
foreach ($rivit as $rivi) {
    if (@$mukana[trim($rivi)]) continue;
    $mukana[trim($rivi)] = true;
    fwrite($uusi, $rivi);
}
fclose($uusi);
?>

Ideana on tallentaa taulukkoon $mukana, onko tietty rivi esiintynyt aiemmin. Funktion trim ansiosta rivinvaihdoilla ei ole merkitystä.

Jaska kirjoitti:

Nopein algoritmi on luokkaa O(n), missä n on rivien lukumäärä tiedostossa. Tämä siksi, että jokaista riviä on tarkasteltava ainakin kerran. Miten tähän päästään? Voit järjestää rivit pikajärjestämisalgoritmilla ajassa O(log_2 n). Sitten vertailet jokaista riviparia (i,i+1) ja poistat tuplat.

Pikajärjestämisen aikavaativuus on O(n^2) eikä O(log n). Nopeammilla algoritmeilla järjestäminen onnistuu ajassa O(n log n), mutta tuolla tavalla ei voi saavuttaa aikavaativuutta O(n).

Off topic:
Erikoista tekstiä mm. Wikipediassa! Sanovat pikalajittelun vaativan enemmän aikaa jos taulukko on valmiiksi järjestyksessä???? Ei pidä paikkaansa! Vain Heap-lajittelulla käy niin.

jtha kirjoitti:

Erikoista tekstiä mm. Wikipediassa! Sanovat pikalajittelun vaativan enemmän aikaa jos taulukko on valmiiksi järjestyksessä???? Ei pidä paikkaansa!

Aikavaativuuteen vaikuttaa, miten järjestettävän taulukon osan jakoalkio valitaan. Jos jakoalkioksi valitaan aina ensimmäinen alkio, aikavaativuus on O(n^2), kun taulukko on valmiiksi järjestyksessä. Mutta tämä on huono valintatapa eikä pikajärjestämistä toteuteta käytännössä näin. Jos jakoalkioksi valitaan esimerkiksi keskimmäinen alkio, aikavaativuus on O(n log n), kun taulukko on valmiiksi järjestyksessä.

jtha kirjoitti:

Vain Heap-lajittelulla käy niin.

Kekojärjestäminen vie aina aikaa O(n log n), myös silloin, kun alkiot ovat valmiiksi järjestyksessä.

Kumpi annetuista esimerkeistä on sitten nopeampi? makumakun vai Antin?
Kymmenellätuhannella rivillä nopeusero ei uskoakseni ole suurehko, mutta mitä nopeammin sitä nopeammin.

Tässä on HEAP-koodi jonka 15 vuotta sitten löysin. Se toimii kaksivaiheisesti. Eka vaihe kestää huomattavasti kauemmin jos taulukkko on valmiiksi järjestyksessä. Onhan tuo voinut kehittyä tuosta (epäilen)

Sub Heap(A As Long, L As Long)
        'A = eka alkio, L = viimeinen alkio
        'T() = järjestettävä taulukko

  Dim I As Long, J As Long, Iso As Long, Mini As Long

  For I = A + 1 To L
    J = I
    Do Until J <= A
      Iso = J \ 2
      If T(J) < T(Iso) Then
        Swap T(J), T(Iso)
        J = Iso
      Else
        Exit Do
      End If
    Loop
  Next

  For J = L To A + 1 Step -1
    Swap T(A), T(J)
    I = A
    Do
      Mini = 2 * I
      If Mini >= J Then Exit Do
      If Mini < J - 1 Then
        If T(Mini + 1) < T(Mini) Then Mini = Mini + 1
      End If
     If T(I) > T(Mini) Then
        Swap T(Mini), T(I)
        I = Mini
      Else
        Exit Do
      End If
    Loop
  Next

End Sub

Lisäys: sorry, tämä edelleen 'off topic', Antin huomioon vastasin...

t0ll0 kirjoitti:

Kumpi annetuista esimerkeistä on sitten nopeampi? makumakun vai Antin?

Kymmenellätuhannella rivillä olisit jo käsitellyt tiedoston siinä ajassa, joka asian kysymiseen kului. Minulla nimittäin 10000 riviä satunnaista dataa pyörähti molemmilla tavoilla 0,07 sekunnissa. Isommilla syötteillä Antin tapa näyttäisi yllättäen olevan jopa selvästi nopeampi. (Ei voi kuin ihmetellä, miten PHP:n natiivi funktio voi hävitä PHP:llä toteutetulle vastineelle.)

Metabolix: taitaa sieltä päästä löytyä hieman tehokkaampi kone kuin täältä!
Kummallakin tavalla noin 10 000 rivin käsittelyyn kului 2-4 minuuttia.
Tosin testasin wampserverillä tässä windowsin ohessa joka varmasti vaikuttaa tulokseen ja testikonekin on juuri ja juuri tältä vuosituhannelta :)

Mielenkiintoista että Antin koodi pyörii nopeammin, ja vielä trimmailee rivejä muun työn ohessa. Ilmeisesti tuo php:n array_unique funkkari on "pullonkaula", olisiko siellä erinäisiä sisäisiä tyyppimuunnoksia ja tarkistuksia enemmän. En tiedä olisko array_unique($array, SORT_REGULAR) nopeampi.
t0ll0, mitä sinä sait nopeuseroksi?

Pistin tuon koneen jo laskemaan lottorivejä (taas vaihteeksi), mutta Antin oli kuitenkin nopeampi..

Pitihän sitä sitten itsekin kokeilla.
Itseasiassa tuo nopeus riippuu datasta.

Tein 100000 riviä satunnaisia dataa (40 merkkiä pitkiä rivejä).

case 1 : kaikki rivit erilaisia
Antin koodi 1.12 sekuntia
Minun koodi 1.03 sekuntia

case 2: 100000 riviä mutta vain 20000 erilaista
Antin koodi 0.412 sekuntia
Minun koodi 0.622 sekuntia

case 3: kaikki 100000 samoja
Antin koodi 0.228 sekuntia
Minun koodi 0.520 sekuntia

Eli mitä enemmän samoja rivejä on sitä nopeampi on Antin koodi.
Jos minullakin 100k riviä menee alle sekunnin, niin tarkista koneesi. Ei kai jokin levykirjoitus töki tai jotain.

ps. Antin koodi toimisi vielä vajaa 10% nopeammin jos ottaisi trimmit pois.

t0ll0 kirjoitti:

Kummallakin tavalla noin 10 000 rivin käsittelyyn kului 2-4 minuuttia.

Kyllä se 10000 riviä näyttäisi menevän 333 megahertsin koneellakin alle 0,4 sekunnissa, joten joko Windows on aivan käsittämättömän huono tai olet järjestänyt itsellesi erittäin pahan pullonkaulan johonkin muualle. Kolmas mahdollisuus on, että rivisi ovat hillittömän pitkiä; testasin 76-merkkisillä riveillä.

makumaku kirjoitti:

Itseasiassa tuo nopeus riippuu datasta.

Näin havaitsin itsekin, mutta minulla ilman samoja rivejä koodit olivat juuri yhtä nopeat, joten raportoin vain olennaisen tuloksen. Tulos voi toki riippua PHP:n versiosta, minulla on PHP 5.3.5. Ja muistitko itse eliminoida levyltä lukemisen ja kirjoittamisen? Omassa testissäni data oli Linuxin tmpfs-osiolla eli valmiiksi keskusmuistissa.

PHP:n manuaali kertoo seuraavaa funktiosta array_unique:

https://www.php.net/manual/en/function.array-unique.php:

array_unique() sorts the values treated as string at first, then will keep the first key encountered for every value, and ignore all following keys.

Funktion toimintatapa eroaa siis omasta toteutuksestani.

Itsellä levyoperaatiot oli mukana mittausajoissa mutta yritin eliminoida kaikki cache-tyyppiset jutut pois. Generoin uuden datan joka ajolla, tai sitten ajoin vanhaa dataa useamman kerran vuoron perään kummallakin scriptillä.
Tulokset oli aina samat.
Kokeilin vielä 80 merkkiä pitkillä riveillä, ja sama tulos silläkin. Jos kaikki rivit ovat uniikkeja niin oma koodi on noin 10% nopeampi. PHP versio on 5.2.9.

EDIT: Myöskin tässä testissä array_unique($array, SORT_REGULAR) oli noin 10% hitaampi kuin array_unique($array, SORT_STRING), joka on siis defaultti.

makumaku kirjoitti:

Jos minullakin 100k riviä menee alle sekunnin, niin tarkista koneesi. Ei kai jokin levykirjoitus töki tai jotain.

Uskoisin että tuon koneen ongelma on vioittuneissa muistikammoissa.
Kasasin koneen tuota lottotehtävää varten ja on aika turhauttavaa rivejä laskea kun php heittää fatal erroria sekä kone boottaa joko muistin tai ylikuumentumisen takia jos on yhtään vaativampia laskuja kuten kombinaatioita ja niiden tulostamisia.
Eli meikäläisen tulokset eivät ole millään tasolla vertailtavissa koodin todelliseen suorituskykyyn.

Antti Laaksonen kirjoitti:

Funktion toimintatapa eroaa siis omasta toteutuksestani.

Totta turiset, enpä tullut tätä ajatelleeksi. Tältä pohjalta tein kuitenkin vielä pari muuta versiota ja sain kuin sainkin optimoitua muutaman millisekunnin pois. Alla on kattavampi lista tuloksistani. Testiaineistona käytin 800000 rivin tiedostoa, jossa sama 100000 rivin satunnaisdata toistui 8 kertaa peräkkäin.

8,1 s, makumakun array_unique. Käytin seuraavanlaista ytimekästä toteutusta:

file_put_contents("out.txt", array_unique(file("rnd.txt")));

2,27 s, Antin foreach-tekniikka trim-funktion kanssa.
1,91 s, Antin foreach-tekniikka ilman trim-funktiota.

$mukana = array();
$tulos = "";
foreach (file("rnd.txt") as $rivi) {
	if (!isset($mukana[$rivi])) {
		$mukana[$rivi] = true;
		$tulos .= $rivi;
	}
}
file_put_contents("out.txt", $tulos);

1,91 s, array_flip.

file_put_contents("out.txt", array_keys(array_flip(file("rnd.txt"))));

1,83 s, array_flip + implode, vaikka toiminta on täsmälleen sama!

file_put_contents("out.txt", implode(array_keys(array_flip(file("rnd.txt")))));

1,77 s, array_flip + foreach, eli yhdistetään rivit itse ilman implodea.

$tulos = "";
foreach (array_flip(file("rnd.txt")) as $rivi => $turha) {
	$tulos .= $rivi;
}
file_put_contents("out.txt", $tulos);

Jos käytössä on *nix, niin asia hoituu todella helposti:

sort -u input > output

Missä input on syötetiedosto ja output on tulostetiedosto.