Rotiranje fajla

[ leka @ 21.05.2003. 19:30 ] @

Elem problem je sledeci i veoma jednostavan - rotirati fajl tako da na izlazu dobijete prvo zadnju liniju istog, potom predzadnju i tako dalje...

Dakle ako imate u fajlu:

Code:

12
a2
4b
c2

Onda skript treba da da na izlazu

Code:

c2
4b
a2
12

P.S. Fajlovi su MNOGO veliki (skoro gigabajt)...

[ leka @ 21.05.2003. 20:35 ] @

Ma moze bilo koji shell skript jezik (da se pokrene iz shell-a), s tim da procesiranje fajla od skoro GB ne traje vise od 2h :) ...

[ CONFIQ @ 21.05.2003. 20:45 ] @

Ovaj, izbrisao sam poruku koja je bila pre tvoje (slučajno).
Pitao sam da li može PHP-om. pokušavao sam 10 minuta i odustajem.
Nisam znao da ako koristim fwind(); file pointer se vraća na početak i briše sve na šta sretne...
Tako da odustajem...

Jedino ako se koristi file() pa onda arrayom da se čita iz poslednjeg do prvog ali nisam tako dobar u array-u a i mrzime da se sada time bakćem.Da vidim kako će ostali da reše ovo. ;)

[ -zombie- @ 21.05.2003. 20:52 ] @

ma ne valja ni jedan skript jezik za ovo.. čak ni perl majka nije dobra pri baš velikim količinama memorije..

moja prva ideja je da se fajl u letu iscepka na delove (od par mega, recimo od po 10M), i da se oni okrenu.. ali je problem što i ti delovi treba da se ispišu nazad u obrnutom poretku..

naravno, pretpostavljam da snimanje na disk ovivh iscepkanih delova fajla nije dozvoljeno (tj jednostavno nema mesta ;)

[ Gojko Vujovic @ 22.05.2003. 00:02 ] @

Za sve unix ima rešenje. Pogledaj tac komandu iz textutils paketa. Suprotno od cat, jel'te. :)

Negde će to biti i gtac (od GNU valjda), zavisi već od sistema.

[ leka @ 22.05.2003. 23:45 ] @

Gojko,
hvala - nisam znao za ovo programče! :)

Pozdrav svima!

[ Gojko Vujovic @ 23.05.2003. 01:31 ] @

Nisam stigao prošlog puta da se pozabavim ostalim alatkama, ali pošto me tOwk još uvek nije preduhitrio i dao rešenje, uradiću to sada:

Perl:

Code:
cat fajl.txt | perl -e 'print reverse <>'

Awk:

Code:
cat fajl.txt | awk '{g[NR]=$0}END{for(n=NR;n>0;n--)print g[n]}'

Sed:

Code:
cat fajl.txt | sed -n '1!G;h;$p'

Sa velikim fajlovima perl ubedljivo najbrži od ova tri. Sa sedom ni ne pokušavaj, udavi se bukvalno kad je veliki fajl u pitanju.

Ja mislim da sad imaš dovoljno rešenja, Leko. :) Aj' molim te testiraj performanse perl rešenja u odnosu na "tac", baš me zanima kako će se ponašati u realnoj upotrebi.

[ Gojko Vujovic @ 23.05.2003. 01:44 ] @

Mada nije za scripting forum, evo ti Leko i u C-u isto to:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXREAD 4096

int main(int argc, char *argv[]) {
    int nread, len = 0, size = (4 * MAXREAD);
    char *cp, *offset, *buf = malloc(size + 1);

    while (1) {
    if ((nread = read(0, (buf + len), MAXREAD)) > 0) {
        len += nread;
        if (MAXREAD > (size - len)) {
        size <<= 1;
        if (0 == (buf = realloc(buf, size + 1))) {
            fprintf(stderr, "realloc failed\n");
            exit(1);
        }
        }
    } else {
        if ( 0 == nread) break;
        if (-1 == nread) {
        perror("read");
        exit(1);
        }
    }
    }
    offset = buf + len;
    *offset = 0;
    for (cp = offset; cp > buf; --cp) {
    if ('\n' == *cp) {
        *offset = 0;
        if (cp < offset)
        fputs(offset = cp+1, stdout);
    }
    }
    if (cp < offset) {
    *offset = 0;
    fputs(cp, stdout);
    }
    free(buf);
    return(0);
}

Nije moj kod, naleteo sam na nekoj njuzgrupi na to..

Zatim pascal:

Code:

Program reversefile;
uses SysUtils, Classes;

var
    i, N : longint;
    list : TList;
    line : string;
    pline : pointer;
begin
    list := TList.Create;
    While Not Eof(input) do
    begin
        Readln(input, line);
        Getmem(pline, Length(line)+1);
        Move(line, pline^, Length(line)+1);
        list.Add( pline );
    end;
    N := list.Count;
    For i := N-1 Downto 0 do WriteLn( string(list.items[i]^) );
end.

Java:

Code:

import java.io.*;
import java.util.*;

public class reversefile {
    public static void main(String[] args) {
        ArrayList al = new ArrayList(4096);

        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String strLine;
            while((strLine = in.readLine()) != null)
                al.add(strLine);
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }

        String strArray[] = new String[al.size()];
        al.toArray(strArray);

        for(int i = strArray.length - 1; i >= 0; i--)
            System.out.println(strArray[i]);
    }
}

[ Gojko Vujovic @ 23.05.2003. 01:49 ] @

Igri nikad kraja. Ne snalaze se svi sa velikim fajlovima ali sa malima rade.

Evo i php rešenja:

Code:

$fd = fopen("php://stdin", "r");
$lines = array();
while (!feof ($fd)) { array_push($lines, fgets($fd, 4096)); }
fclose($fd);
foreach (array_reverse($lines) as $line) print $line;

Zatim python:

Code:

def main():
    from sys import stdin, stdout
    w = stdin.readlines()
    w.reverse()
    stdout.writelines(w)

main()

Pokrao sam kod ali nema veze, uživajte.

TCL:

Code:

proc main {} {
    set lines [split [read stdin] "\n"]

    fconfigure stdout -buffering full

    for {set i [expr {[llength $lines]-2}]} {$i >= 0} {incr i -1} {
        puts [lindex $lines $i]
    }
}

main

Može čak i VBSCRIPT to:

Code:

FileBlob = WScript.StdIn.ReadAll
Lines = Split(FileBlob, Chr(10))
For A = UBound(Lines) To LBound(Lines) Step -1
If Len(Lines(A)) > 0 Then WScript.Echo Lines(A)
Next

Naravno i c++:

Code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    typedef vector<string> LINES;
    LINES l;
    char line[256];
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin.getline(line, 256)) {
        l.push_back(line);
    }
    for (LINES::reverse_iterator j = l.rbegin(); j != l.rend(); j++) {
    cout << (*j) << endl;
    }
}

[ Gojko Vujovic @ 23.05.2003. 02:16 ] @

Evo još jednog:

Code:

nl fajl.txt | sort -r | cut -c8-

Hvala t0wk-u za inspiraciju! :)

[ tOwk @ 23.05.2003. 02:28 ] @

Kad već idemo, evo i bash skripte:

Code:

#!/bin/sh
function unazad {
    local RED
    read RED
    if [ ! $? = 1 ]; then
        unazad
        echo $RED
    fi
}
unazad

Takođe, ovo možete definisati u .profile, i onda koristiti „unazad“ za isti posao ;-) Naravno, ovo je samo za manje fajlove

[Ovu poruku je menjao tOwk dana 23.05.2003. u 02:50 GMT]

[ Gojko Vujovic @ 23.05.2003. 02:31 ] @

Merenje performansi na nekim manjim fajlovima, po zauzeću procesora, daje sledeći poredak (prvi najbrži):

1.tac
2.gcc
3.g++
4.java
5.perl
6.tcl
7.gawk
8.php

A po zauzeću memorije (prvi zauzima najmanje memorije):

1.tac
2.gcc
3.g++
4.tcl
5.java
6.perl
7.gawk
8.php

Neverovatno kakvo je đubre ovaj php a opet tako popularan.

[ _owl_ @ 23.05.2003. 10:10 ] @

Citat:

Neverovatno kakvo je đubre ovaj php a opet tako popularan.

Nije php djubre nego si ti napisao najgori moguci kod za ovaj zadatak. Procitao si ceo fajl i smestio ga u niz (bas bi bilo zanimljivo da si probao sa onim fajlom od 10GB).
Vidi da prebaci kod u C-u u PHP pa onda uporedi (ne znam samo sta radi funkcija nread, a nisam pri *nix-u da pogledam man). U svakom slucaju php bi morao da bude sporiji od C-a.

[ leka @ 23.05.2003. 11:27 ] @

Aman narode, da sam hteo da sednem i iskodiram ovo ja bih to odradio, bio sam zapravo uveren da za tako jednostavnu stvar postoji jednolinijsko resenje u shell-u, i ponovo zahvaljujem Gojku za komandu tac , ovo ostalo sto ste kucali mozda je interesantno za neke ljude koji uce programiranje, tako da i to treba postovati...

[ Gojko Vujovic @ 23.05.2003. 13:19 ] @

OWL: i Java kod je isto loš i radi tako što sve gura u arraylist pa onda kroz petlju čita unazad. Pa je opet Java odradila sve za skoro upola kraće vreme.

Hajde napišite bolji PHP kod, meni nešto ne ide. :)

[ tOwk @ 23.05.2003. 17:15 ] @

Gojko, radi li ti sada ovo moje rešenje? Ako radi, 'ajde ga uporedi i sa ostalima ;-) Ja mu dajem neko 7, 8 mesto.

[ Goran Rakić @ 23.05.2003. 23:37 ] @

Code:

#!/usr/local/bin/php

<?php
$fd = fopen("php://stdin", "r");
$fd1 = fopen("php://stdout", "w");

$i=-1;
$red=array();
$prvi = fgetc($fd);

  fseek($fd,0,SEEK_END);

   while( ftell ($fd) != 0 ) {

         $c=fgetc($fd);
    array_push($red, $c);

         if($c=="\n") {
        $red=array_reverse($red);
        foreach($red as $r) fwrite($fd1,$r);
        $red=array();
    }

           fseek($fd,$i,SEEK_END);
    $i--;

   }

        fwrite($fd1,"\n$prvi");
        $red=array_reverse($red);
        foreach($red as $r) fwrite($fd1,$r);
        fwrite($fd1,"\n");

fclose($fd);
fclose($fd1);
?>

./obrni.php < dat daje izlaz na ekran...

mana je što na vrhu postoji nekoliko \n oznaka, zato što zadnji red završava sa novom linijom.

[ tOwk @ 24.05.2003. 00:27 ] @

Pa to je lako ispraviti. Takođe, ja bih koristio stringove svuda umesto niza, a ako već koristiš niz, onda je bolje array_unshift (da ne bi morao reverse).

Evo (nadam se) poboljšane verzije:

Code:

#!/usr/local/bin/php -q
<?php
$fd = fopen("php://stdin", "r");

$red='';
fseek($fd,-1,SEEK_END);

while( (($c=fgetc($fd))!=NULL) && (ftell ($fd) != 1 )) {

  if($c=="\n") {
    echo $red;
    $red=$c;
  } else {
    $red=$c.$red;
  }

  fseek($fd,-2,SEEK_CUR);
}
echo $c.$red;

fclose($fd);

?>

Dopuna: bila mi je ostala jedna Goranova greška :-), sad je i to sređeno. Takođe još neka pojednostavljenja. Ispravljena i jedna moja greška pošto PHP ASCII 0x30 (nulu) tretira takođe kao FALSE... ehhh...

[ tOwk @ 24.05.2003. 01:35 ] @

Testirajući ovaj PHP skript koji je praktično urađen onako kako bi C verzija trebala da bude urađena zaključio sam da PHP i dalje „kešira“ izlaz, i primetite ovaj rezultat na fajlu od oko 900kb i oko 9000 linija:

Code:

# time tac ~/rad/katalogizacija/spisak/sve >/dev/null

real    0m0.063s
user    0m0.040s
sys     0m0.000s
# time php -q ./proba2.php <~/rad/katalogizacija/spisak/sve  >/dev/null

real    0m50.984s
user    0m26.440s
sys     0m0.880s

Zato, mada bi u suštini ovaj kod trebao da radi i na beskonačnim fajlovima, PHP to zbog internog procesiranja čini nemogućim.

[ Gojko Vujovic @ 24.05.2003. 01:40 ] @

Tac verovatno nije isto što i ona C verzija odozgo, dakle treba pogledati source tac-a.

Uglavnom na testu mi je tac ispao brži od onog c koda gore.

[ tOwk @ 24.05.2003. 02:09 ] @

Pa najbrži rezultat bi bio:

Code:
odavde:
fseek(file,-BLOCKSIZE,SEEK_CUR);
fread(file,BLOCKSIZE,&buf);
buf=spoji(buf,ostalo_iz_prethodnog);
izbacuj_linije_unazad_i_prazni(buf);
ostalo_iz_prethodnog=buf;
goto odavde

Najverovatnije tako tac i radi, ne postoji drugi način koji radi i za ogromne fajlove, a ipak ne žrtvuje brzinu (znači, koristi neki veći blok memorije, i njega obrađuje).

[ -zombie- @ 24.05.2003. 02:23 ] @

prvo, šta tačno podrazumevaš pod "beskonačnim fajlovima", i kako bi bilo koji kod (c, perl, php..) mogao da čita fajl unazad beskonačno..

pa po samoj definiciji bi morao da zna odakle da počne (tj od kraja ;), pa tera unazad do početka, što ni u kom slučaju ne može biti beskonačno..

drugo, što se tiče keširanja, zavisi koju verziju imaš, i kako je podešena, ali dodaj ob_implicit_flush(1); na početak skripte da bi isključio keširanje (mada bi novije verzije php CLI SAPI-a trebale da to imaju isključeno po defaultu)

i na kraju, po kojoj to logici je čitanje bajta po bajt potencijalno najbrže rešenje.. (moj predlog za ubrzanje programa, u bilo kom jeziku. definisati konstantu za buf_size, i čitati od kraja fajla po buf_size bajtova, i okretati ih u memoriji.. experimentalnom metodom utvrditi najbolji buf_size)

btw, sad mi pade na pamet, kako bi preveo "default"?

// edit: evo, sad videh da je u međuvremenu i towk postovao slično kako sam ja predložio.. naravno, pošto je to jedino logično..

[ tOwk @ 24.05.2003. 02:35 ] @

Za „beskonačno“, mislio sam na „nije unapred postavljeno ograničenje veličine fajla“. Svakako, upotreba loše reči, i priznajem da si u pravu :-)

Za „default“: www.prevod.org/recnik/default

Citat:

-zombie-:
// edit: evo, sad videh da je u međuvremenu i towk postovao slično kako sam ja predložio.. naravno, pošto je to jedino logično..

kad je towk veoma logičan tip ;-)

A zapravo, ti si predložio slično kako sam ja poslao, a nisam ja poslao slično kako si ti predložio! Vidimo se u patentnom zavodu za ovako dobar algoritam, pravo prvog je nenadmašno!

[ Au197/79 @ 24.05.2003. 10:41 ] @

Ovaj kod u pythonu radi suštinski drugačijim algoritmom nego što je to slučaj sa implementacijama u ostalim jezicima pa je rezultate nemoguće porediti. Tako je python ispao sa svih rang lista a na testvima koje sam čitao obično je rame uz rame sa perlom, a ponekad i bolji. Pogledajte http://www.bagley.org/~doug/shootout/ Na osnovu podrazumevane liste gde se meri samo brzina python je na 13. mestu. Čudno da je i tu PHP truba.

[ leka @ 26.05.2003. 18:43 ] @

Au197/79,
zaista, ali ZAISTA ti hvala na linku! ODLICAN JE! Nema veze sto nije povezan sa temom o kojoj pricamo ovde, ali je link vredan pomena stakako - otisao je u moj bookmark ODMAH! :)

[ Au197/79 @ 27.05.2003. 19:07 ] @

Taj link je već neko vreme u smešten u moje bookmarks :)

U prethodnom postu nisam napomenuo da se jezici rangiraju na osnovu nekoliko testova kojima se ocenjuju po važnosti.

Jedan od testova je rotiranje fajla. Tu se mogu videti najbolja rešenja u dosta jezika (+ koji je kompajler ili interpreter korišćen) kao i lista rezultata u brzini i zazeću memorije. Čak se i test podaci menjaju po veličini i može se videti grafik uspešnosti rada sa obimnijim podacima.

Tu je i bash rešenje, ali mi se čini da se loše pokazalo.

[ leka @ 04.06.2003. 01:03 ] @

Ovo će na kraju da ode na nešto slično 99 bottles of beer sajtu ( http://99-bottles-of-beer.ls-la.net/ ) koji je naravno odavno u mom bookmark-u :)

[ -zombie- @ 04.06.2003. 04:07 ] @

nema ništa od tog sajta.. kad sam video da nema implementacije u mom omiljenom (najlepšem) asembleru za motorolu 68k..

eh.. ;)

[ Ivan Stanojevic @ 05.06.2003. 02:02 ] @

to mozes da uradi siz ASP-a bez problema, samo da mi je znati sta ces dobiti kada izokrenes vrednosti (mislim , za sta ti ovo treba?)?

[ leka @ 05.06.2003. 07:24 ] @

Pa nikad nije kasno da sedneš i napišeš to...

Citat:

-zombie-:
nema ništa od tog sajta.. kad sam video da nema implementacije u mom omiljenom (najlepšem) asembleru za motorolu 68k..

eh..

[ Goran Rakić @ 05.06.2003. 17:10 ] @

Napiši, pa da testiramo (danas podešavam jedan IIS sa PHP-om, taman na istoj mašini...)

[ Ivan Stanojevic @ 05.06.2003. 19:36 ] @

nemam vremena , zaista, da se jos i sa tim patim...
otprilike bi islo ovako

1. fajl se podeli na delove , recimo 10 mb...
2. koristi se adoStream da se ucita fajl od 10mb,

Code:

// Strimuj fajl

Dim BinaryStream
Set BinaryStream = CreateObject("ADODB.Stream")
BinaryStream.Mode = 3
BinaryStream.Open
BinaryStream.Type = 1
BinaryStream.position = 0
BinaryStream.LoadFromFile ("c:/temp/delic001.temp")

// zapisi fajl na disk

Dim FS
Set FS = CreateObject("Scripting.FileSystemObject")

Dim TextStream
Set TextStream = FS.CreateTextFile("c:/temp/gotovo/" & broj_fajla)

TextStream.Write RSBinaryToString(BinaryStream.read)

Response.Flush
BinaryStream.Close
Set BinaryStream = Nothing

ovde ispod sam postavio funkciju koja ce taj strimovani fajl da pretvori u jedan veliki string...

ovu funkciju bi trebalo malo promeniti tako da slaze 'odnapacke' ili napraviti neku drugu funkciju koja ce string da slozi 'odnapacke'

Code:

// Konverzija Raw u String

Function RSBinaryToString(xBinary)

  Dim Binary
  If vartype(xBinary)=8 Then Binary = MultiByteToBinary(xBinary) Else Binary = xBinary

  Dim RS, LBinary
  Const adLongVarChar = 201
  Set RS = CreateObject("ADODB.Recordset")
  LBinary = LenB(Binary)

  If LBinary>0 Then
    RS.Fields.Append "mBinary", adLongVarChar, LBinary
    RS.Open
    RS.AddNew
      RS("mBinary").AppendChunk Binary
    RS.Update
    RSBinaryToString = RS("mBinary")
  Else
    RSBinaryToString = ""
  End If
End Function

Function MultiByteToBinary(MultiByte)
  Dim RS, LMultiByte, Binary
  Const adLongVarBinary = 205
  Set RS = CreateObject("ADODB.Recordset")
  LMultiByte = LenB(MultiByte)
  If LMultiByte>0 Then
    RS.Fields.Append "mBinary", adLongVarBinary, LMultiByte
    RS.Open
    RS.AddNew
      RS("mBinary").AppendChunk MultiByte & ChrB(0)
    RS.Update
    Binary = RS("mBinary").GetChunk(LMultiByte)
  End If
  MultiByteToBinary = Binary
End Function

3. postupak se ponovi za svaki delic od po 10 mb, kada se svi fajlovi snime, treba ih spojiti od poslednjeg k aprvom, i to snimiti u jedan fajl...

kome treba , moze iskoristiti ovo sto sam napisao da napravi taj skript (i nek mi posalje kopiju)

pozdrav