[Java] Zo efficient mogelijk speciale karakters filteren

[Deddiekoel]

Een collega van me heeft gevraagd of ik mbv Java niet een manier heb om snel een text bestand van speciale karakters te ontdoen. Aangezien mijn Java kennis niet zo erg "diep" gaat wilde het hier eens voorleggen. Het gaat om vrij grote bestanden (100+ Mb) en dus wil ik voorkomen om deze in het geheugen te laden. Voor zover mijn kennis gaat kom je dan uit op streams (iets waar ik weinig) vanaf weet.

Wat ik dus wil weten welke aanpak het snelst zal werken. Dit zijn mijn ideeen erbij:

1) Een bestand kopieren en het doelbestand in een bepaalde karakterset, die wel wordt geaccepteerd wordt, opslaan.

2) Middels een (buffered?) bytestream het bestand inlezen en wegschrijven en elke bij elke byte controleren of het een speciaal karakter is of niet.

3) Een andere manier om snel (niet geheugen intensief) een soort van find & replace te doen.

Momenteel wordt het gedaan middels TCL (?) wat momenteel niet de beoogde performance heeft. Het TCL script loopt door de verschillende regels en doet daar een find en replace op. Aangezien ik TCL niet ken weet ik dus ook niet hoe efficient dit is, maar het lijkt mij dat dit in Java sneller kan.

[BtM909]

Het zal vast aan mij liggen, maar het doel is weer een text file te krijgen toch? Waarom dan moeite steken in Java als je wellicht in andere talen sterker bent?

[zwippie]

Wat moet er eigenlijk gebeuren met de speciale karakters? Verwijderen, vervangen? Moet een é een e worden, een ă een a? Mogen er karakters zo maar verdwijnen?
Of moet de tekst in principe alleen worden omgezet van ASCII naar utf-8 of 16 (unicode)?

Hier staat wel iets over het omzetten van non-unicode naar unicode middels een StreamWriter.


Tevens vraag ik me af of dit soort bewerkingen nou echt veel langer zullen duren in TCL dan in Java. Lijkt me eerder een kwestie van een 'matige' implementatie in TCL (al ken ik TCL niet goed en overschat ik het nu misschien).

[Deddiekoel]

BtM909 schreef op maandag 16 oktober 2006 @ 16:52:
Het zal vast aan mij liggen, maar het doel is weer een text file te krijgen toch? Waarom dan moeite steken in Java als je wellicht in andere talen sterker bent?

Java is de taal waarin ik het sterkst ben. Daarnaast is het wel prettig dat het platform onafhankelijk is.

zwippie schreef op maandag 16 oktober 2006 @ 16:57:
Wat moet er eigenlijk gebeuren met de speciale karakters? Verwijderen, vervangen? Moet een é een e worden, een ă een a? Mogen er karakters zo maar verdwijnen?
Of moet de tekst in principe alleen worden omgezet van ASCII naar utf-8 of 16 (unicode)?
...
Tevens vraag ik me af of dit soort bewerkingen nou echt veel langer zullen duren in TCL dan in Java. Lijkt me eerder een kwestie van een 'matige' implementatie in TCL (al ken ik TCL niet goed en overschat ik het nu misschien).

Dat is inderdaad een goed punt, voor zover ik kan zien moeten de tekens voor zover mogelijk vervangen worden met een leesbaar equivalent. Dit is het TCL script:

Tcl:

### TCL ###

proc specialchars {filetochange} {

global env
set fromext ".in"
set extension ".out"
set file [open $env(prog_exp)/$filetochange$fromext]
set file2 [open $env(prog_exp)/$filetochange$extension w+]

# Loop through the file
while { [eof $file] == 0} {
    gets $file row

    # Find the stringlength of the row
    set strl [string length $row]

    # Loop through the line 
    for {set a 0} {$a <= $strl} {incr a} {
    
        # Find the specific character
        set st [string range $row $a $a]
        set b [expr $a+1]
        set stb [string range $row $a $b]

        #If the character is a slash, change this char to a dash (PDP desktop crashes on '/')
        if {$st == "/"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]-[string range $row $nextchar end]"

        set strl [string length $row]
        set stb [string range $row $a $b]
        } elseif {$stb == "\@\@" } {
            set untilchar [expr $a - 1]
            set nextchar [expr $b + 1]
            set row "[string range $row 0 $untilchar][string range $row $nextchar end]"

        #If the character is a tilde, change this char to a double quote
        set strl [string length $row]
        } elseif {$st == "~"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]\"[string range $row $nextchar end]"

        #If the character is a pipe, change this char to a comma
        set strl [string length $row]
        } elseif {$st == "|"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar],[string range $row $nextchar end]"

        #the format section below removes the special characters
        #If the character is an ÀÁÂÃÄÅÆ, change this char to an A
        } elseif {$st == "À" || $st == "Á" || $st == "Â" || $st == "Ã" || $st == "Ä" || $st == "Å" || $st == "Æ"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]A[string range $row $nextchar end]"

        #If the character is a Ç, change this char to a C
        } elseif {$st == "Ç" || $st == "ç"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]C[string range $row $nextchar end]"

        #If the character is an ÈÉÊË, change this char to an E
        } elseif {$st == "É" || $st == "Ë" || $st == "È" || $st == "Ê"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]E[string range $row $nextchar end]"

        #If the character is an ÌÍÎÏ, change this char to an I
        } elseif {$st == "Ï" || $st == "Í" || $st == "Ì" || $st == "Î"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]I[string range $row $nextchar end]"

        #If the character is a Ñ, change this char to an N
        } elseif {$st == "Ñ"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]N[string range $row $nextchar end]"

        #If the character is an ÒÓÕÖØÔ, change this char to an O
        } elseif {$st == "Ò" || $st == "Ó" || $st == "Õ" || $st == "Ö" || $st == "Ø" || $st == "Ô"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]O[string range $row $nextchar end]"

        #If the character is a ÙÚÛÜ, change this char to a U
        } elseif {$st == "Ù" || $st == "Ú" || $st == "Û" || $st == "Ü"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]U[string range $row $nextchar end]"

        #If the character is a Ý, change this char to a Y
        } elseif {$st == "Ý"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]Y[string range $row $nextchar end]"

        #If the character is an àáâãäåæ, change this char to an a
        } elseif {$st == "à" || $st == "á" || $st == "â" || $st == "ã" || $st == "ä" || $st == "å" || $st == "æ"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]a[string range $row $nextchar end]"

        #If the character is an èéêë, change this char to an e
        } elseif {$st == "é" || $st == "è" || $st == "ê" || $st == "ë"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]e[string range $row $nextchar end]"

        #If the character is an ìí¡îï, change this char to an i
        } elseif {$st == "ì" || $st == "í" || $st == "¡" || $st == "î" || $st == "ï"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]i[string range $row $nextchar end]"

        #If the character is a ñ, change this char to an n
        } elseif {$st == "ñ"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]n[string range $row $nextchar end]"

        #If the character is an òóôõöø, change this char to an o
        } elseif {$st == "ò" || $st == "ó" || $st == "ô" || $st == "õ" || $st == "ö" || $st == "ø"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]o[string range $row $nextchar end]"

        #If the character is a ùúûüµ, change this char to a u
        } elseif {$st == "ù" || $st == "ú" || $st == "û" || $st == "µ" || $st == "ü"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]u[string range $row $nextchar end]"

        #If the character is a ýÿ, change this char to a y
        } elseif {$st == "ý" || $st == "ÿ"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]y[string range $row $nextchar end]"

        #If the character is an ß, change this char to an S
        } elseif {$st == "ß"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]S[string range $row $nextchar end]"

        #If the character is an ´, change this char to an '
        } elseif {$st == "´" || $st == "¨"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]'[string range $row $nextchar end]"

        #If the character is an ª, change this char to an a
        } elseif {$st == "ª"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]a[string range $row $nextchar end]"

        #If the character is a ° or º, change this char to an o
        } elseif {$st == "°" || $st== "º"} {
            set untilchar [expr $a - 1]
            set nextchar [expr $a + 1]
            set row "[string range $row 0 $untilchar]o[string range $row $nextchar end]"

        } ;# end if

    } ;# end for
    #puts $row
    puts $file2 $row

} ;# end for file



close $file
close $file2
} ; # end proc


# Run script

Ik denk dus dat er wel winst behaald moet worden door gebruik te maken van een stream, zodat je niet geheugenintensief bezig bent.

[DaCoTa]

Uitgaande van een 8 bit ASCII bestand, geen unicodes ofzo, maak een mapping array van 256 tekens, lees blokken van 4K in, map alle tekens via de lookup array en schrijf ze weer weg. 100Mb is echt niet zo veel, dat kan in een paar seconden gebeurd zijn.

[matthijsln]

Met gewoon een recht-toe-rechtaan implementatie zoals DaCoTa voorstelt hoeft dit inderdaad niet langer dan een paar seconden te duren. Dat het nu traag is is het gevolg van een naieve implementatie in TCL (bij elk speciaal karakter een nieuwe string maken... ).

[Confusion]

Deddiekoel schreef op maandag 16 oktober 2006 @ 16:06:
2) Middels een (buffered?) bytestream het bestand inlezen en wegschrijven en elke bij elke byte controleren of het een speciaal karakter is of niet.

Dat kan je alleen doen als je weet wat de encoding van de input file is en dan is het onnodig lastig als het bijvoorbeeld een utf-8 encoded file is. Dan kan je beter een FileInputStream in een InputStreamReader met de juiste encoding wrappen en vervolgens een FileOutputStream in een OutputStreamWriter wrappen om het weer weg te schrijven met de gewenste encoding. Maar het vervangen van tekens bereik je daar niet mee, want er is waarschijnlijk geen encoding waarin ~ op " gemapped wordt, laat staan een encoding waarin alles op elkaar gemapped wordt zoals je wenst.

Daarvoor kan je waarschijnlijk het beste de methode van DaCoTa gebruiken (met een HashMap dan). Dan heb je nog twee opties: 1 is de char[] buffer van de InpuStreamReader naar een String vertalen en in bijvoorbeeld StringBuilder stoppen, daar replace op loslaten voor ieder entry in de table en vervolgens het resultaat terugstoppen in de OutputStreamWriter. Mooier is misschien die vervanging op character basis te laten gebeuren in een FilterReader, maar ik durf niets over performance verschillen te zeggen.

[matthijsln]

Confusion schreef op maandag 16 oktober 2006 @ 18:12:
[...]
Daarvoor kan je waarschijnlijk het beste de methode van DaCoTa gebruiken (met een HashMap dan). Dan heb je nog twee opties: 1 is de char[] buffer van de InpuStreamReader naar een String vertalen en in bijvoorbeeld StringBuilder stoppen, daar replace op loslaten voor ieder entry in de table en vervolgens het resultaat terugstoppen in de OutputStreamWriter.

Elke loop nieuw geheugen alloceren is niet goed voor de performance, vooral als het niet nodig is (gewoon direct in de buffer werken). En zelfs het TCL script loopt niet meerdere keren door dezelfde karakters heen voor alle te vervangen karakters!

[ Voor 3% gewijzigd door matthijsln op 16-10-2006 18:37 ]

[Verwijderd]

Eigenlijk wat Matthijs al zegt. Direct characters streamen, nergens (onnodig) memory allocaten, en niet voor elke character een hele beslissings boom gaan aflopen, maar direct naar de juiste case springen. Een default implementatie zal er ongeveer zo uit zien:

code:

        BufferedReader inReader = new BufferedReader( new FileReader("file_in") );
        BufferedWriter outWriter = new BufferedWriter( new FileWriter("file_out") );
        
        int character = 0;
        while ( (character = inReader.read() ) != -1  ) {
            switch ( character ) {
                case 'ý':
                case 'ÿ':
                    outWriter.write( 'y' );
                break;
                
                case 'é':
                case 'è':                   
                    outWriter.write('e');
                break;
                
                default:
                    outWriter.write(character);                 
            }           
        }

Dergelijke stream operaties zie je ook vrij veel in de implementatie code van JSP en JSF gebeuren (dwz, in de source van Tomcat en bv MyFaces). Daar wordt het vrij vaak ook op ongeveer deze manier gedaan.

De juiste encodings (voor je input file) kun je zelf goed zetten door andere readers te gebruiken. Als je ook muli-char dingen wilt afhandelen kun je bijvoorbeeld switchen op het eerste karakter (de &) en dan de opeenvolgende chars in een vaste buffer inlezen. Verzin zelf maar hoe je deze dan verder afhandelt

[Confusion]

matthijsln schreef op maandag 16 oktober 2006 @ 18:36:
Elke loop nieuw geheugen alloceren is niet goed voor de performance, vooral als het niet nodig is (gewoon direct in de buffer werken). En zelfs het TCL script loopt niet meerdere keren door dezelfde karakters heen voor alle te vervangen karakters!

De vraag is hoeveel performance nodig is. Op deze manier doe je 100 Mb nog steeds sneller dan in TCL verwacht ik. Maargoed, de methode met de FilterWriter verdient mijn voorkeur, maar als iemand die niet zelf kan bedenken, weet ik niet of het een goed idee is iemand die aan te raden.

Wat betreft performance: ik heb database import scripts in Python die 8 uur over het importeren van ongeveer 12 Gb aan XML data doen. Ze kunnen sneller, maar dan wordt de code minder doorzichtig en aangezien die imports niet vaak hoeven te gebeuren vinden we dit acceptabel.

Verwijderd schreef op maandag 16 oktober 2006 @ 22:44:
Een default implementatie zal er ongeveer zo uit zien:

Zou de lookup array (HashMap) die DaCoTa voorstelt niet efficienter zijn dan zo'n switch?

[ Voor 12% gewijzigd door Confusion op 17-10-2006 07:43 ]

[Soultaker]

Erm, ros het gewoon door tr en sed heen, of denk ik nu te makkelijk?

code:

cat invoer.txt | tr 'áâ...éè' 'aa...ee' | sed -r "s/´|¨/'/g" > uitvoer.txt

Zou behoorlijk snel moeten zijn.

[ Voor 19% gewijzigd door Soultaker op 17-10-2006 15:28 ]

[Soultaker]

Confusion schreef op dinsdag 17 oktober 2006 @ 07:41:
Zou de lookup array (HashMap) die DaCoTa voorstelt niet efficienter zijn dan zo'n switch?

Waarschijnlijk zijn de meeste karakters gewoon in de 7-bit ASCII range, en daarvoor is de jump table sowieso efficiënter, omdat die karakters buiten het bereik van de select-statements vallen. Hoe efficiënt 'ie is met karakters die wél gematcht worden hangt er vooral van af of de compiler een echte jump table genereert of een reeks vergelijkingen en dat hangt weer af van de gebruikte range.

Typisch een gevalletje van benchmarken, of gewoon coden wat het makkelijkst is omdat beide methodes waarschijnlijk wel snel genoeg zijn.

[Confusion]

Soultaker schreef op dinsdag 17 oktober 2006 @ 15:25:
Erm, ros het gewoon door tr en sed heen, of denk ik nu te makkelijk?

code:

cat invoer.txt | tr 'áâ...éè' 'aa...ee' | sed -r "s/´|¨/'/g" > uitvoer.txt

Zou behoorlijk snel moeten zijn.

Het lijkt me dat de tr ieder karakter uit het input bestand zal vergelijken met ieder karakter in de input set (tot er een match is). Efficienter dan de TCL is het qua algoritme dan niet, maar de C implementatie zal allicht sneller zijn dan hetzelfde uitgeschreven in TCL .

[Deddiekoel]

Ik denk dat een combinatie van de de oplossing van henk_de_man en DaCoTa voor mij het beste werkt.
Ik wil dus de characters via een stream doorlopen en elk character door een "lookup" hashMap gooien. Als er niets in de HashMap staan pak ik het origineel.
Ik ga even bouwen en laat hier even weten wat het resultaat is.

[Deddiekoel]

Heb het volgende geproduceerd:

Java:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

import java.util.HashMap;

public class CharacterReplacer {
    private HashMap<Character, Character> dictionary = new HashMap<Character, Character>(0);
    
    public CharacterReplacer() {
        buildDictionary();
        processFile("C:\\input.txt", "C:\\output.txt");
    }

    public static void main(String[] args) {
        new CharacterReplacer();
    }
    
    private void buildDictionary(){
        //Specific characters: ~|/
        dictionary.put('~', '"');
        dictionary.put('|', ',');
        dictionary.put('/', '-');        
        //ÀÁÂÃÄÅÆ range
        dictionary.put('À', 'A');
        dictionary.put('Á', 'A');
        dictionary.put('Â', 'A');
        dictionary.put('Ä', 'A');
        dictionary.put('Å', 'A');
        dictionary.put('Æ', 'A');
        //Ç range
        dictionary.put('Ç', 'C');
        //ÈÉÊË range
        dictionary.put('È', 'E');
        dictionary.put('É', 'E');
        dictionary.put('Ê', 'E');
        dictionary.put('Ë', 'E');
        //ÌÍÎÏ range
        dictionary.put('Ì', 'I');
        dictionary.put('Ì', 'I');
        dictionary.put('Ì', 'I');
        dictionary.put('Ì', 'I');
        //Ñ range
        dictionary.put('Ñ', 'N');
        //ÒÓÕÖØÔ range
        dictionary.put('Ò', 'O');
        dictionary.put('Ó', 'O');
        dictionary.put('Õ', 'O');
        dictionary.put('Ö', 'O');
        dictionary.put('Ø', 'O');
        dictionary.put('Ô', 'O');
        //ÙÚÛÜ range
        dictionary.put('Ù', 'U');
        dictionary.put('Ú', 'U');
        dictionary.put('Û', 'U');
        dictionary.put('Ü', 'U');
        //Ý range
        dictionary.put('Ý', 'Y');
        //àáâãäåæ range
        dictionary.put('à', 'a');
        dictionary.put('á', 'a');
        dictionary.put('â', 'a');
        dictionary.put('ä', 'a');
        dictionary.put('å', 'a');
        dictionary.put('æ', 'a');
        //ç range
        dictionary.put('ç', 'c');
        //èéêë range
        dictionary.put('è', 'e');
        dictionary.put('é', 'e');
        dictionary.put('ê', 'e');
        dictionary.put('ë', 'e');
        //ìíîï range
        dictionary.put('ì', 'i');
        dictionary.put('ì', 'i');
        dictionary.put('ì', 'i');
        dictionary.put('ì', 'i');
        //ñ range
        dictionary.put('ñ', 'n');
        //òóõöøô range
        dictionary.put('ò', 'o');
        dictionary.put('ó', 'o');
        dictionary.put('õ', 'o');
        dictionary.put('ö', 'o');
        dictionary.put('ø', 'o');
        dictionary.put('ô', 'o');
        //ùúûü range
        dictionary.put('ù', 'u');
        dictionary.put('ú', 'u');
        dictionary.put('û', 'u');
        dictionary.put('ü', 'u');
        //ý range
        dictionary.put('ý', 'y');

    }
    
    public void processFile(String fileIn, String fileOut){
        try {
            BufferedReader inReader = new BufferedReader( new FileReader(fileIn) );
            BufferedWriter outWriter = new BufferedWriter( new FileWriter(fileOut) );
            
            int character = 0;
            while ( (character = inReader.read() ) != -1  ) {
                Character translation = dictionary.get(new Character((char)character));
                //System.out.println((char)character +" -> "+translation);
                if(translation==null) outWriter.write(character);  
                else outWriter.write(translation.charValue());  
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Performance is in mijn ogen best aardig (verwerkt 10 Mb bestand in een paar seconden) en het doet wat het moet doen. Prettige is wel dat dit nu een vrij flexibele manier is om bestanden te "vertalen".
Morgenvroeg eens een 200 Mb bestand voeren kijken hoe het dan gaat.
Wat is een makkelijke manier om het geheugengebruik te zien?

[ Voor 3% gewijzigd door Deddiekoel op 17-10-2006 19:07 ]

[Maxxi]

Als je een scanner gebruikt met System.in kan je gewoon per regel dingen veranderen.

En aan het eind file.append(String line)
Dit voegt de lijn weer toe. Zo laat je het hele bestand in 1 regel per keer.

[Deddiekoel]

Nu lees ik het toch per character, dat is toch efficienter?

[ Voor 26% gewijzigd door Deddiekoel op 17-10-2006 19:44 ]

[Soultaker]

Confusion schreef op dinsdag 17 oktober 2006 @ 16:40:
Het lijkt me dat de tr ieder karakter uit het input bestand zal vergelijken met ieder karakter in de input set (tot er een match is).

Absoluut niet. De precieze implementatie is natuurlijk platformafhankelijk, maar dit soort standaardtools zijn juist gemaakt om een beetje efficiënt te zijn. De GNU implementatie doet iets met een look-up table voor de eerste 128 karakters en een splay tree voor de rest.

Efficienter dan de TCL is het qua algoritme dan niet, maar de C implementatie zal allicht sneller zijn dan hetzelfde uitgeschreven in TCL .

Absoluut niet; die TCL code maakt elke keer een nieuwe string en dat doen tr en sed allebei zeker niet, daarom zullen ze al heel wat sneller zijn. Ik zal eens even een benchmark doen.

Deddiekoel schreef op dinsdag 17 oktober 2006 @ 19:44:
Nu lees ik het toch per character, dat is toch efficienter?

Yep, in combinatie met buffered streams is dat prima. (Die bufferen zelf wel wat, niet noodzakerlijkerwijs regels.)

[ Voor 14% gewijzigd door Soultaker op 17-10-2006 19:58 ]

[zwippie]

Overbodige opmerking misschien, maar het is nooit onverstandig om een zwik testbestanden los te laten op zowel de TCL als Java filteraar, om vervolgens de resultaten te gaan vergelijken.

_{Er zit bijvoorbeeld nog een fout in de I en i series zie ik nu ook nog!}

[BalusC]

Java:

dictionary.get(new Character((char)character));

Met de generics en autoboxing hoef je niet te casten en wrappen

Trouwens ..

Java:

processFile("C:\\input.txt", "C:\\output.txt"); 

Forward slashes werken ook prima in Windows en je hoeft ze ook niet eens te escapen Biedt ook lekker crosscompatibiliteit met UNIX systemen. De "/" wijst in Windows overigens altijd naar de systeemschijf (standaard is dat C:\). Mocht dat boeiend zijn

[ Voor 58% gewijzigd door BalusC op 17-10-2006 21:00 ]

[Soultaker]

@zwippie: die zag ik ook, en de ã en à missen.

Ik heb even gebenchmarkt met een 100 MB bestand met random data, en de Java code doet er ~14 seconde over, terwijl de tr/sed-combinatie er slechts ~1.5 seconde over doet. Java is dus tien keer zo traag als de brain-dead 1-regel oplossing (en kost heel wat meer moeite).

Merk ook op dat dit zowel tr als sed samen zijn (sed voor het vervangen van ´ en ¨ naar een quote) terwijl de gepostte Java code alleen nog maar enkele karakters vervangt! Moraal van het verhaal: standaard systeem tools zijn best snel en kun je prima gebruiken voor dit soort taken.

edit:
Ik heb overigens de code aangepast om ISO-8559-1 readers/writers te maken. De default encoding is op mijn systeem blijkbaar iets anders. Gebruikte code en testmethode staan hier.

[ Voor 17% gewijzigd door Soultaker op 17-10-2006 21:06 ]

[MSalters]

Je pakt alle karakters door een NFD decompositie te doen en dan simpelweg alle karakters >127 weg te gooien. Omdat je in de decompostie alle accenten log hebt gehaald van hun base characters, blijven die wel over. Je pakt dan ook bv Pools en Tsjechisch mee.

[DaCoTa]

Denk dat de meeste tijd zit in de Character boxing en unboxing. Probeer het eens met de volgende (untested) code:

Java:

char[] lookup  = new char[256];

// defaults
for(int i = 0; i < 256; i++) {
    lookup[i] = (char)i;
}

// vertalingen:
lookup['à'] = 'a';

// schrijven:
outWriter.write((char)lookup[character]);   

[ Voor 15% gewijzigd door DaCoTa op 18-10-2006 14:39 ]

[Soultaker]

Dat verlaagt de tijd van ~15 naar ~10 seconde; helpt dus wel, maar het verschil is nog steeds groot. Ik denk dat de vertraging in de I/O libraries en het converteren van chars zit (hoewel tr dat ook doet).

Het blijft dus geen overtuigende casus om zelf te gaan programmeren als er standaard tools zijn die doen wat je wil.

[ Voor 23% gewijzigd door Soultaker op 18-10-2006 15:15 ]

[Confusion]

Soultaker schreef op dinsdag 17 oktober 2006 @ 19:58:
Absoluut niet. De precieze implementatie is natuurlijk platformafhankelijk, maar dit soort standaardtools zijn juist gemaakt om een beetje efficiënt te zijn. De GNU implementatie doet iets met een look-up table voor de eerste 128 karakters en een splay tree voor de rest.

Mijn gedachtegang was dat het voor de kleine hoeveelheid karakters in je voorbeeld efficienter zou zijn om het direct te vergelijken dan om het via een map te doen, maar ik zag over het hoofd dat karakters een ordening hebben.

[Verwijderd]

Confusion schreef op dinsdag 17 oktober 2006 @ 07:41:
Zou de lookup array (HashMap) die DaCoTa voorstelt niet efficienter zijn dan zo'n switch?

No way!

Kijk eens in een HashMap implementatie wat voor bewerkingen er allemaal worden gedaan. Normaliter is er voor 1 enkele lookup geen verschil te merken, maar als je zo'n operatie enorm vaak herhaald dan merk je het wel zeker.

Zelfs als je hash zo uitkomt dat je in 1 keer op dezelfde entry zit, heb je nog de overhead van meerdere method calls (1 tje naar de map en enkele intern zoals het berekenen van de hashwaarde) for ELKE(!) character die je doorloopt. Komt nog bij dat in Java Maps helemaal geen chars kunnen bevatten, en je dus ook nog voor ELKE character de allocatie van een Character (let op hoofdletter) betaalt.

Voor de non-believers, de typische implementatie voor HashMap.put uit de 5.0 JDK ziet er zo uit:

code:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

Een switch op een char kan vertaald worden naar 2 bytecode instructies en als dat een hotspot wordt naar slechts 2 native instructies, zonder een enkele memory allocatie te doen.

Aangezien de TS in z'n implementatie alleen single chars opzoekt, is het echt een beetje d*m om geen switch te gebruiken. (als het om strings ging ipv chars is het wel te verdedigen kwa implementatie gemak).

Soultaker schreef op dinsdag 17 oktober 2006 @ 20:59:
Ik heb even gebenchmarkt met een 100 MB bestand met random data, en de Java code doet er ~~14 seconde over, terwijl de tr/sed-combinatie er slechts ~~1.5 seconde over doet. Java is dus tien keer zo traag als de brain-dead 1-regel oplossing (en kost heel wat meer moeite).

Hoe heb je de tijden gemeten? Vanaf de commandline met time util of in Java zelf? Als je vanaf de commandline getimed hebt, dan meet je ook nog de opstart tijd van de VM. Practisch gezien is dat wel eerlijk, maar als je alleen de tijd van de feitelijke filtering wilt meten geeft dat een beetje vertroebeld beeld. Zonder de code aan te passen kun je dit al testen door bij een 10MB, 100MB en 1000MB bestand de timings te vergelijken. Blijft dit een constante factor ~10?

[ Voor 18% gewijzigd door Verwijderd op 18-10-2006 20:11 ]

[.oisyn]

Verwijderd schreef op woensdag 18 oktober 2006 @ 20:01:
Zelfs als je hash zo uitkomt dat je in 1 keer op dezelfde entry zit, heb je nog de overhead van meerdere method calls (1 tje naar de map en enkele intern zoals het berekenen van de hashwaarde) for ELKE(!) character die je doorloopt.

Je bedoelt net zoiets als voor elke char die je leest/schrijft van een steam een read()/write() op die stream aanroepen, zoals jij voorstelde?

Overigens zou ik gewoon een mapping array gebruiken ipv een hele grote switch statement. Is vaak ook efficienter dan een jumptable (wegens geen branch misprediction)

[ Voor 15% gewijzigd door .oisyn op 18-10-2006 20:16 ]

[Verwijderd]

.oisyn schreef op woensdag 18 oktober 2006 @ 20:06:
[...]

Je bedoelt net zoiets als voor elke char die je leest/schrijft van een steam een read()/write() op die stream aanroepen, zoals jij voorstelde?

Inderdaad Maar in de implementatie die er nu gedaan is wordt die ook al betaald. De switch en map aanpak verschillen amper of eigenlijk totaal niet van elkaar in implementatie gemak, maar om het lezen en schrijven naar streams te doen moet je wel wat meer moeite doen. Ik heb daarbij in een vorig project, waarbij files van max 2GB doorlopen moesten worden trouwens gebruik gemaakt van NIO en direct memory mapped files. Dat scheelde ook wel weer iets. Omdat de performance 'voldoende' was ben ik daar niet verder gaan optimaliseren.

Ik kan me trouwens nog herinneren dat jij een bericht poste waarin je vertelde dat in -echte- high performance code je bijvoorbeeld ook geen HashMap gebruikt als het aantal entries heel klein is. Een simpele linked list kan dan al sneller zijn.

[Soultaker]

@henk_DE_man: maar die twee native instructies gaat alleen op als de compiler een jump table genereert, en dat doet 'ie niet als de labels te ver uit elkaar liggen (een grote jump-table is niet zo cache-vriendelijk). _{En dan nog kost een range check minimaal twee instructies, met de jump maakt drie.}

Ik heb het eens getest, op deze manier:

Java:

                switch(character)
                {
                case '~': character = '"'; break;
                case '|': character = ','; break;
                case '/': character = '-'; break;
                //ÀÁÂÃÄÅÆ range
                case 'À':
                case 'Á':
                case 'Â':
                case 'Ã':
                case 'Ä':
                case 'Å':
                case 'Æ': character = 'A'; break;
                //Ç range
                case 'Ç': character = 'C'; break;
                //ÈÉÊË range
                case 'È':
                case 'É':
                case 'Ê':
                case 'Ë': character = 'E'; break;
                //ÌÍÎÏ range
                case 'Ì':
                case 'Í':
                case 'Î':
                case 'Ï': character = 'I'; break;
                //Ñ range
                case 'Ñ': character = 'N'; break;
                //ÒÓÕÖØÔ range
                case 'Ò':
                case 'Ó':
                case 'Õ':
                case 'Ö':
                case 'Ø':
                case 'Ô': character = 'O'; break;
                //ÙÚÛÜ range
                case 'Ù':
                case 'Ú':
                case 'Û':
                case 'Ü': character = 'U'; break;
                //Ý range
                case 'Ý': character = 'Y'; break;
                //àáâãäåæ range
                case 'à':
                case 'á':
                case 'â':
                case 'ã':
                case 'ä':
                case 'å':
                case 'æ': character = 'a'; break;
                //ç range
                case 'ç': character = 'c'; break;
                //èéêë range
                case 'è':
                case 'é':
                case 'ê':
                case 'ë': character = 'e'; break;
                //ìíîï range
                case 'ì':
                case 'í':
                case 'î':
                case 'ï': character = 'i'; break;
                //ñ range
                case 'ñ': character = 'n'; break;
                //òóõöøô range
                case 'ò':
                case 'ó':
                case 'õ':
                case 'ö':
                case 'ø':
                case 'ô': character = 'o'; break;
                //ùúûü range
                case 'ù':
                case 'ú':
                case 'û':
                case 'ü': character = 'u'; break;
                //ý range
                case 'ý': character = 'y'; break;
                }

Maar dan is 'ie nauwelijks sneller (~14 seconde) dan met de hash map.

[Soultaker]

Verwijderd schreef op woensdag 18 oktober 2006 @ 20:01:
Hoe heb je de tijden gemeten? Vanaf de commandline met time util of in Java zelf?

Precies, zie de Makefile. De TS had het over bestanden van 100+MB dus 100MB leek me aardig om mee te testen.

Bij kleinere bestanden wordt de relatieve tijd die Java nodig heeft flink groter. 1000MB duurt 136 seconde in Java; is nog wel minder dan de verwachtte 150 seconde, maar het zit aardig in de buurt (Java is altijd een beetje grillig met dit soort dingen). tr/sed doen er dan 22 seconde over (in plaats van de verwachtte 15 seconde), waar ik geen verklaring voor heb.

Al met al zijn het geen echt wetenschappelijk verantwoorde tests, maar dat was de bedoeling niet. Ik wilde alleen aantonen dat standaardtools prima geschikt zijn voor de taken waarvoor ze gemaakt zijn, zoals deze, en dat het dus niet zinnig is om daar zelf voor te gaan coden. De verschillen zijn sowieso nog wel groot genoeg om dat punt te maken (maar zelfs als tr/sed iets trager waren had ik dat gedaan).

(Overigens doet Java er met een leeg invoerbestand er <0.2 seconde over, dus de opstartproblemen vallen wel mee, al is het misschien zo dat de JIT compiler dan nog niets gedaan heeft.)

[.oisyn]

Java:

byte[] createConversionTable()
{
    byte[] table = new byte[256];
    for (int i = 0; i < 256; i++)
    {
        switch(i)
        {
            case 'è': 
            case 'é': 
            case 'ê':
                table[i] = (byte)'e';
                break;

            // etc

            default:
                table[i] = (byte)i;
        }
    }

    return table;
}

void convert(InputStream in, OutputStream out)
{
    byte[] data = new byte[65536];
    byte[] table = createConversionTable();

    int readBytes;
    do
    {
        readBytes = in.read(data);
        if (readBytes != 0)
        {
            for (int i = 0; i < readBytes; i++)
                data[i] = table[data[i]];
            out.write(data, 0, readBytes);
        }
    }
    while (readBytes == data.length);
}

Overigens heb ik nog wel m'n twijfels of de suggesties in deze topic (die van mij incluis) ook echt goed werken. Je werkt hier namelijk met bytes, niet met unicode chars. Het is dus maar de vraag of de codepage van Java die speciale chars ook op dezelfde manier mapt als dat ze in de file staan.

[ Voor 14% gewijzigd door .oisyn op 18-10-2006 21:16 ]

[Verwijderd]

Onder het motto meten is weten en omdat ik (kuch) toch nix beters heb te doen

Java:

package testing;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

import java.util.HashMap;

public class FilterSwitch {
    private HashMap<Character, Character> dictionary = new HashMap<Character, Character>(0);
    
    public FilterSwitch() {
        
        long startTime = System.currentTimeMillis();        
        
        processFile("C:\\input.txt", "C:\\output.txt");
        
        long timeElapsed = System.currentTimeMillis() - startTime;
        
        System.out.print( "Filtering took: " + timeElapsed );
        
    }

    public static void main(String[] args) {
        new FilterSwitch();
    }
    
    public void processFile(String fileIn, String fileOut){
        try {
            BufferedReader inReader = new BufferedReader( new FileReader(fileIn) );
            BufferedWriter outWriter = new BufferedWriter( new FileWriter(fileOut) );
            
            int character = 0;
            while ( (character = inReader.read() ) != -1  ) {
                
                switch ( character ) {
                //              Specific characters: ~|/
                case '~' :
                    outWriter.write( '"' );
                    break;

                case '|' :
                    outWriter.write( ',' ); break;                  
               
                case '/': outWriter.write( '-'); break;        
                //ÀÁÂÃÄÅÆ range
                case 'À':
                case 'Á':
                case 'Â' :
                case 'Ä' :
                case 'Å' :
                case 'Æ' : outWriter.write( 'A'); break;
                
                //Ç range
                case 'Ç': outWriter.write( 'C'); break;
                //ÈÉÊË range
                case 'È':
                case 'É':
                case 'Ê':
                case 'Ë': outWriter.write( 'E'); break;
                
                //ÌÍÎÏ range
                case 'Ì':
                case 'Í':
                case 'Î':
                case 'Ï': outWriter.write( 'I'); break;
                //Ñ range
                case 'Ñ': outWriter.write( 'N'); break;
                //ÒÓÕÖØÔ range
                case 'Ò':
                case 'Ó':
                case 'Õ':
                case 'Ö':
                case 'Ø':
                case 'Ô': outWriter.write( 'O'); break;
                //ÙÚÛÜ range
                case 'Ù':
                case 'Ú':
                case 'Û':
                case 'Ü': outWriter.write( 'U'); break;
                //Ý range
                case 'Ý': outWriter.write( 'Y'); break;              
                //àáâãäåæ range
                case 'à':
                case 'á':
                case 'â':
                case 'ä':
                case 'å':
                case 'æ': outWriter.write( 'a'); break;
                //ç range
                case 'ç': outWriter.write( 'c'); break;
                //èéêë range
                case 'è':
                case 'é':
                case 'ê':
                case 'ë': outWriter.write( 'e'); break;
                //ìíîï range
                case 'ì':
                case 'í':
                case 'î':
                case 'ï': outWriter.write( 'i'); break;
                //ñ range
                case 'ñ': outWriter.write( 'n'); break;
                //òóõöøô range
                case 'ò':
                case 'ó':
                case 'õ':
                case 'ö':
                case 'ø':
                case 'ô': outWriter.write( 'o'); break;
                //ùúûü range
                case 'ù':
                case 'ú':
                case 'û':
                case 'ü': outWriter.write( 'u'); break;
                //ý range
                case 'ý': outWriter.write( 'y');

                default:
                    outWriter.write(character); 
                
                }                
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

vs

Java:

package testing;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

import java.util.HashMap;

public class FilterMap {
    private HashMap<Character, Character> dictionary = new HashMap<Character, Character>(0);
    
    public FilterMap() {
        
        long startTime = System.currentTimeMillis();
        
        buildDictionary();
        processFile("C:\\input.txt", "C:\\output.txt");
        
        long timeElapsed = System.currentTimeMillis() - startTime;
        
        System.out.print( "Filtering took: " + timeElapsed );
        
    }

    public static void main(String[] args) {
        new FilterMap();
    }
    
    private void buildDictionary(){
        //Specific characters: ~|/
        dictionary.put('~', '"');
        dictionary.put('|', ',');
        dictionary.put('/', '-');        
        //ÀÁÂÃÄÅÆ range
        dictionary.put('À', 'A');
        dictionary.put('Á', 'A');
        dictionary.put('Â', 'A');
        dictionary.put('Ä', 'A');
        dictionary.put('Å', 'A');
        dictionary.put('Æ', 'A');
        //Ç range
        dictionary.put('Ç', 'C');
        //ÈÉÊË range
        dictionary.put('È', 'E');
        dictionary.put('É', 'E');
        dictionary.put('Ê', 'E');
        dictionary.put('Ë', 'E');
        //ÌÍÎÏ range
        dictionary.put('Ì', 'I');
        dictionary.put('Í', 'I');
        dictionary.put('Î', 'I');
        dictionary.put('Ï', 'I');
        //Ñ range
        dictionary.put('Ñ', 'N');
        //ÒÓÕÖØÔ range
        dictionary.put('Ò', 'O');
        dictionary.put('Ó', 'O');
        dictionary.put('Õ', 'O');
        dictionary.put('Ö', 'O');
        dictionary.put('Ø', 'O');
        dictionary.put('Ô', 'O');
        //ÙÚÛÜ range
        dictionary.put('Ù', 'U');
        dictionary.put('Ú', 'U');
        dictionary.put('Û', 'U');
        dictionary.put('Ü', 'U');
        //Ý range
        dictionary.put('Ý', 'Y');
        //àáâãäåæ range
        dictionary.put('à', 'a');
        dictionary.put('á', 'a');
        dictionary.put('â', 'a');
        dictionary.put('ä', 'a');
        dictionary.put('å', 'a');
        dictionary.put('æ', 'a');
        //ç range
        dictionary.put('ç', 'c');
        //èéêë range
        dictionary.put('è', 'e');
        dictionary.put('é', 'e');
        dictionary.put('ê', 'e');
        dictionary.put('ë', 'e');
        //ìíîï range
        dictionary.put('ì', 'i');
        dictionary.put('í', 'i');
        dictionary.put('î', 'i');
        dictionary.put('ï', 'i');
        //ñ range
        dictionary.put('ñ', 'n');
        //òóõöøô range
        dictionary.put('ò', 'o');
        dictionary.put('ó', 'o');
        dictionary.put('õ', 'o');
        dictionary.put('ö', 'o');
        dictionary.put('ø', 'o');
        dictionary.put('ô', 'o');
        //ùúûü range
        dictionary.put('ù', 'u');
        dictionary.put('ú', 'u');
        dictionary.put('û', 'u');
        dictionary.put('ü', 'u');
        //ý range
        dictionary.put('ý', 'y');

    }
    
    public void processFile(String fileIn, String fileOut){
        try {
            BufferedReader inReader = new BufferedReader( new FileReader(fileIn) );
            BufferedWriter outWriter = new BufferedWriter( new FileWriter(fileOut) );
            
            int character = 0;
            while ( (character = inReader.read() ) != -1  ) {
                Character translation = dictionary.get(new Character((char)character));
                //System.out.println((char)character +" -> "+translation);
                if(translation==null) outWriter.write(character);  
                else outWriter.write(translation.charValue());  
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Op een JDK 5.0 update 8, default memory allocatie grote (=64MB heap), hotspot client VM, op een P4 2.8Ghz, 1.5GB RAM, Windows XP SP2, kwam ik op de volgende tijden:

code:

switch
22mb - 6604 ms
715mb - 218047 ms

map
22mb - 8203 ms
715mb - 266531 ms

Ik heb de test meerdere keren gedraait, en de getallen veranderde niet significant. Het verschil is een niet geringe maar ook weer niet super grote factor 1.2. De tijd schaalt nagenoeg lineair met de bestands grote.

Dit test alleen het verschil tussen de Map lookup en de switch methode. Inderdaad vermoed ik dat met een betere mapping tussen source encoding en reader nog wel wat performance winst te halen is.

edit:

Hmmppff... naar het blijkt is het wellicht verstandiger om toch voornamelijk in de I/O laag te gaan optimizen bij dit soort kwesties. Ik heb even de triviale case getest die de chars meteen wegschrijft:

Java:

package testing;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

import java.util.HashMap;

public class FilterNoOp {
    private HashMap<Character, Character> dictionary = new HashMap<Character, Character>(0);
    
    public FilterNoOp() {
        
        long startTime = System.currentTimeMillis();        
        
        processFile("C:\\input.txt", "C:\\output.txt");
        
        long timeElapsed = System.currentTimeMillis() - startTime;
        
        System.out.print( "Filtering took: " + timeElapsed );
        
    }

    public static void main(String[] args) {
        new FilterNoOp();
    }
    
    public void processFile(String fileIn, String fileOut){
        try {
            BufferedReader inReader = new BufferedReader( new FileReader(fileIn) );
            BufferedWriter outWriter = new BufferedWriter( new FileWriter(fileOut) );
            
            int character = 0;
            while ( (character = inReader.read() ) != -1  ) {               
                outWriter.write(character);
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

En deze heeft als executie tijd: 216421ms. Oftewel, de bulk van de tijd gaat in de domme I/O zitten (zoals verwacht), maar de switch constructie voegt nagenoeg 0 overhead toe, terwijl de map constructie dus relatief veel overhead toe voegt (niet heel t.o.v. de I/O wel heel veel t.o.v. de switch).
Bij de kleinere file zie je het zelfde, zelfs bij meerdere keren testen:

code:

NoOp
22mb - 6439, 6453, 6469, etc
715mb - 216421

switch
22mb - 6604,6610, 6610, etc
715mb - 218047

map
22mb - 8203, 8172, 8172, etc
715mb - 266531

[ Voor 19% gewijzigd door Verwijderd op 18-10-2006 23:01 ]

[Confusion]

Verwijderd schreef op woensdag 18 oktober 2006 @ 20:01:
Voor de non-believers, de typische implementatie voor HashMap.put uit de 5.0 JDK ziet er zo uit:
[..]
Een switch op een char kan vertaald worden naar 2 bytecode instructies en als dat een hotspot wordt naar slechts 2 native instructies, zonder een enkele memory allocatie te doen.

Maar de overhead van de put operatie heb je niet telkens, want je vult die HashMap maar één keer . Je moet dan de HashMap.get voor ieder karakter vergelijken met die switch. Die is nog steeds complexer dan een switch op char (grappig trouwens, als je switched op a, b en e, dan worden de switches op c en d er ook bij gegenereerd in de bytecode), maar als ik random letters uit het alfabet genereer en daar op switch met een 26-delige switch of ze opzoek in een Map<Integer, Character> met 26 entries, dan kom ik op minimale verschillen (orde 10% op ongeveer 30 seconden voor 100 miljoen switches/lookups).

In hoeverre kan je hoeveelheid bytecode in processortijd vertalen?

edit:
Ah, ik ben spuit 11

[ Voor 4% gewijzigd door Confusion op 18-10-2006 22:18 ]

[Verwijderd]

Confusion schreef op woensdag 18 oktober 2006 @ 22:02:
[...]

Maar de overhead van de put operatie heb je niet telkens, want je vult die HashMap maar één keer ;

Ik ben dus ook spuit 11, bedoelde natuurlijk de overhead van de Map.get . Die is dus:

Java:

public V get(Object key) {
    if (key == null)
        return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

Wat dus inderdaad nog steeds niet gering is.

Ik heb trouwens even getest met een NIO file channel:

fragment:

Java:

FileChannel fileChannel = fileInputStream.getChannel();
int fileSize = (int) fileChannel.size();
MappedByteBuffer byteBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileSize);

Voor de 22MB file (alleen lezen) is dat met een CharsetDecoder al >100% sneller dan de NoOp die ik hierboven gaf (met even de write weggecomment), namelijk 1.3 vs 3.2 seconde.

[.oisyn]

Verwijderd schreef op woensdag 18 oktober 2006 @ 21:29:
Onder het motto meten is weten en omdat ik (kuch) toch nix beters heb te doen

En nu nog mijn methode erbij?

Confusion schreef op woensdag 18 oktober 2006 @ 22:02:
In hoeverre kan je hoeveelheid bytecode in processortijd vertalen?

Niet

[DaCoTa]

Nu een test met NIO en de lookup array (NIET de Map dus), dan zitten we denk ik op de meest efficiente methode voor Java.

[Verwijderd]

DaCoTa schreef op donderdag 19 oktober 2006 @ 11:27:
Nu een test met NIO en de lookup array (NIET de Map dus), dan zitten we denk ik op de meest efficiente methode voor Java.

Dat zou best kunnen ja. Ik ben eigenlijk niet zo'n expert in de IO lib van Java (dat ding is uhmm... vrij groot...) dus ik weet eigenlijk niet of die memory mapped file nu echt de snelste methode is, en of er niet ergens in de lib gewoon een simpele filereader zit die intern NIO gebruikt. Mischien als ik vanavond tijd heb dat ik nog wat probeer inelkaar te flansen voor de fun

Slightly offtopic:

Het zou ook best kunnen dat de SUN JVM 6 ook alweer een stuk sneller is. Was de JVM in vroegere versies niet echt zo high performance (een triviaal geoptimaliseerd stukje C of C++ won bijna altijd van Java), maar met de laatste versies is dat enorm verbeterd. Vanaf JVM 6 schijnt het zelfs een dergelijk krachtige run-time optimizer te zijn, dat het ook voor wetenschappelijk gebruik mbt high performance computing interesant wordt. Sommige algorithmes performen er daadwerkelijk beter op dan wanneer ze statisch gecompiled zijn. Vandaar dat er dus ook een toegenome interesse is om de VM voor andere doeleinden dan Java te gebruiken.

[Soultaker]

Oeps, ik zie nu dat ik bij mijn eerdere tests geen BufferedReader had gebruikt. Doe ik dat wel, dan is de oorspronkelijke code (met de HashMap) ongeveer twee keer zo snel (~7.8 seconde).

Maar zo is 'ie toch het snelst:

Java:

import java.io.*;

public class CharacterReplacer
{
    char[] map;

    public CharacterReplacer()
    {
        String in  = "/|ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÑÒÓÕÖØÔÙÚÛÜÝàáâãäåæçèéêëìíîïñòóõöøôùúûüý~",
               out = "-,AAAAAAACEEEEIIIINOOOOOOUUUUYaaaaaaaceeeeiiiinoooooouuuuy\"";

        map = new char[65536];
        for(int n = 0; n < map.length; ++n)
            map[n] = (char)n;
        for(int n = 0; n < in.length(); ++n)
            map[(int)in.charAt(n)] = out.charAt(n);
    }

    public void processFile(String fileIn, String fileOut)
        throws FileNotFoundException, IOException
    {
        Reader in  = new InputStreamReader ( new FileInputStream(fileIn), "iso-8859-1" );
        Writer out = new OutputStreamWriter( new FileOutputStream(fileOut), "iso-8859-1" );
        char[] buffer = new char[1024];
        int length;

        while((length = in.read(buffer, 0, buffer.length)) > 0) {
            for(int n = 0; n < length; ++n)
                buffer[n] = map[buffer[n]];
            out.write(buffer, 0, length);
        }
        in.close();
        out.close();
    }

    public static void main(String[] args)
    {
        try {
            new CharacterReplacer().processFile("input.txt", "output.txt");
        } catch(Exception e) {
            e.printStackTrace();
        }
    }
}

Waarschijnlijk omdat het sneller is om hele buffers tegelijk heen en weer te schuiven. Dit duurt ~1,7 seconde voor 100MB. Een vergelijkbare C implementatie duurt ~0,7 seconde maar die doet geen karakterconversie; best netjes dus van Java (maar nog steeds trager dan tr!).

[.oisyn]

Euh ja, precies wat ik al zei dus (met als bijkomend voordeel dat er bij mij geen char-byte conversie plaats hoeft te vinden - alleen moet de table dan wel goed opgebouwd worden)

[ Voor 55% gewijzigd door .oisyn op 19-10-2006 13:09 ]

[Soultaker]

Inderdaad, maar ik vond het niet eerlijk jouw implementatie te vergelijken met eentje die wel byte/char-conversie doet.

(Leuk detail: de grootte van de gebruikte buffer maakt ook nog wel veel uit, met bijvoorbeeld 512 bytes of 16kb is de code merkbaar trager; dat heeft waarschijnlijk met caching te maken - en natuurlijk de sector size van het bestandssysteem.)

[ Voor 51% gewijzigd door Soultaker op 19-10-2006 13:22 ]

[Deddiekoel]

Soultaker, je hebt het steeds over tr/sed en dat standaardtools sneller zijn. Over welk OS heb je het dan? Momenteel moet deze java code draaien op een Windows machine. Is tr/sed dan nog een optie?
Ik ga toch ook even jouw laatste stukje code proberen, even kijken hoe snel die is.

Mijn collega is inmiddels helemaal blij met mijn implementatie. TCL deed er nl. uren over om 170 Mb te verwerken waar java in seconden klaar was.
Ik ben wel enigzins verbaasd dat de HashMap niet sneller is dan de switch. Ik had namelijk begrepen dat HashMaps juist vies snel waren.

[ Voor 14% gewijzigd door Deddiekoel op 19-10-2006 19:19 ]

[Coca-Cola]

Hashmaps zijn pas vanaf een bepaalde grote echt sneller. Als we het hier over een mapping van 1000 chars hadden dan zou je dat wel merken

[Verwijderd]

Soultaker schreef op donderdag 19 oktober 2006 @ 13:20:
(Leuk detail: de grootte van de gebruikte buffer maakt ook nog wel veel uit, met bijvoorbeeld 512 bytes of 16kb is de code merkbaar trager; dat heeft waarschijnlijk met caching te maken - en natuurlijk de sector size van het bestandssysteem.)

Ik zat hier zelf ook al een beetje mee te spelen. Bij de BufferedReader kun je namelijk de buffer grote bij een overloaded ctor opgeven (default is 8kb), boven de 16kb en onder de 2kb werd het er idd slechter op.

@ts
HashMaps zijn wel heel snel als je een geheel object als key gebruikt (in de praktijk is dat object meestal een String). In het geval van enkele chars kun je gebruik maken van de eigenschap dat chars (ook onder Java) direct een getal voorstellen. Zowel de native array methode als de switch maken hiervan gebruik. Je springt hiermee direct naar geheugen adressen waar je direct een waarde van terughaalt. Dit sluit heel nauw aan op hoe een CPU werkt (heel eenvoudig gezegt; adressen bestaan fysiek in je computer, hashmaps niet). Ik denk dat de native array methode van .oisyn en soultaker ook theoretisch de snelste methode is.

[Soultaker]

Deddiekoel schreef op donderdag 19 oktober 2006 @ 19:19:
Soultaker, je hebt het steeds over tr/sed en dat standaardtools sneller zijn. Over welk OS heb je het dan? Momenteel moet deze java code draaien op een Windows machine. Is tr/sed dan nog een optie?

Ik testte onder Linux, maar tr en sed zijn ook voor Windows beschikbaar (bijvoorbeeld als onderdeel van MSYS).

Mijn collega is inmiddels helemaal blij met mijn implementatie. TCL deed er nl. uren over om 170 Mb te verwerken waar java in seconden klaar was.

Mooi. Had je het vervangen van die character entities (&#180; en &#168;) ook geïmplementeerd?

[The - DDD]

Mijn god wat een nutteloze excercitie is dit topic.

Een simpele text pump in Java.

Is er echt een dwingende reden om Java te gebruiken anders dan "Ik vind Java gewoon wel lekker."?

Gewoon nieuwsgierig, verder geen gezeik ofzo. Men moet immers lekker zelf weten wat je met je tijd doet. En nee, TCL is niet de meest vlotte taal.

[ Voor 6% gewijzigd door The - DDD op 19-10-2006 21:26 ]

[den 150]

Ik vind dit best wel een grappig topic. Het is algemeen bekend als je pure number crunching wilt doen, dat java dan absoluut niet the way to go(tm) is. De hoofdreden om een platform te kiezen is kennis ervan. Je moet er gemakkelijk in kunnen ontwikkelen & onderhouden.

Als je performance wil, ga dan aan de slag in asm, C, of zoals reeds gedemonstreerd standaard gnu tools. Is performance wel zo belangrijk? Hoeveel x gebeurt het omzetten van die bestanden? Mag de hele file in geheugen worden geladen of is het geheugen gebruik beperkt?

Dit gezegd zijnde wil ik ook wel eens een poging ondernemen . Ik ga ook proberen (raar dat nog niemand daaraan had gedacht) om multithreaded te werken: 1 thread for processen, 1 thread voor IO.

Kleine tip nog: wees voorzichtig met NIO, de byte arrays/buffers/streams mappen rechtstreeks naar je OS virtual memory. Als je bvb op een grote file bezig bent met filechannels wordt eerst de totale grootte van die file gealloceerd in OS VM. In Windows 32bit is dat beperkt tot 2GB/proces. Aangezien deze code het enige is wat in je JVM draait heb je daar bijna volledige beschikking over, maar als je in een appserver draait dan heb je al wat minder. Ik heb hier ook eens 2 dagen achter gezocht (op een productieserver nota bene), maak niet diezelfde fout

[Verwijderd]

The - DDD schreef op donderdag 19 oktober 2006 @ 21:24:
Mijn god wat een nutteloze excercitie is dit topic.

Een simpele text pump in Java.

Is er echt een dwingende reden om Java te gebruiken anders dan "Ik vind Java gewoon wel lekker."?

Waarom vullen mensen kruiswoord puzzels in? Waarom probeerd men Linux op de meest exotische devices te laten draaien? It's all in the game

Om dan nog maar wat nutteloze toevoegingen te doen, ik heb een simpele nio reader en writer gemaakt (kon ze niet in de std lib vinden, mischien keek ik niet goed genoeg) en de tijden zijn zoals eerder vermeld voor alleen de reader een flink stuk beter. >300% winst voor de 22mb file en iets minder dan 100% voor de 719MB.

Als ik overigens de buffer grote wat hoger zet, van 32kb naar 2MB, 5MB of 10MB dan performed de 719MB file een stuk beter, namelijk +- 79 seconden ipv 120. Opmerkelijk genoeg wordt de 22mb file daar niet echt sneller van, zelfs langzamer. Onderstaande getallen suggeren dan ook dat je de buffer het beste zou kunnen nemen als functie van de file size (met natuurlijk een redelijk of instelbaar maximum).

code:

NIOSwitch
22mb - 2000, 2172, 2016 (32kb buffer)
22mb - 2594, 2671, 2563 (32kb buffer)
715mb - 122781 (32kb buffer)
715mb - 79453 (10mb buffer)

NoOp
22mb - 6439, 6453, 6469, etc
715mb - 216421

switch
22mb - 6604,6610, 6610, etc
715mb - 218047

map
22mb - 8203, 8172, 8172, etc
715mb - 266531

Voor de geintereseerde de source:

nioread/MappedInputFile.java

Java:

package nioread;


import java.io.*;
import java.nio.*;
import java.nio.channels.*;
import java.nio.charset.*;


public class MappedInputFile  {
    
    private File file;
    private FileInputStream fileInputStream;
    private FileChannel fileChannel;
    private MappedByteBuffer byteBuffer;
    private Charset charset = Charset.forName("ISO-8859-15");
    private CharsetDecoder charDecoder = charset.newDecoder();

    public void openFile(String fileName) throws IOException {      
        file = new File(fileName);      
        fileInputStream = new FileInputStream(file);
        fileChannel = fileInputStream.getChannel();     
        byteBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size());     
        charDecoder.reset();
    }
    
    public long getSize() throws IOException {
        return fileChannel.size();
    }
    
    public boolean fillBuffer(CharBuffer charBuffer) {      
        
        if (charDecoder.decode(byteBuffer, charBuffer, true) == CoderResult.UNDERFLOW) {            
            charDecoder.flush(charBuffer);          
            charBuffer.flip();
            return false; // file completely read
        } 
        else {          
            charBuffer.flip();
            return true; // more to be read
        }
    }   

    public void closeFile() throws IOException {
        if (fileChannel != null) {          
            fileChannel.close();
            fileChannel = null;
            file = null;
            fileInputStream = null;
            byteBuffer = null;          
        }
    }
} 

nioread/MappedOutputFile.java

Java:

package nioread;

import java.io.*;
import java.nio.*;
import java.nio.channels.*;
import java.nio.charset.*;


public class MappedOutputFile  {
    
    private File file;
    private FileOutputStream fileOutputStream;
    private FileChannel fileChannel;
    private ByteBuffer byteBuffer;
    private Charset charset = Charset.forName("ISO-8859-15");
    private CharsetEncoder charEncoder = charset.newEncoder();

    public void openFile(String fileName, int capacity) throws IOException {        
        file = new File(fileName);      
        fileOutputStream = new FileOutputStream(file);
        fileChannel = fileOutputStream.getChannel();        
        byteBuffer = ByteBuffer.allocate(capacity); 
        charEncoder.reset();
    }
    
    public void storeBuffer(CharBuffer charBuffer) throws IOException {         
        boolean done = false;
        while ( !done ) {
            done = charEncoder.encode(charBuffer, byteBuffer, false) == CoderResult.UNDERFLOW;
            byteBuffer.flip();
            fileChannel.write(byteBuffer);
            byteBuffer.rewind();
        }       
        charBuffer.rewind();    
    }   

    public void closeFile() throws IOException {
        if (fileChannel != null) {          
            fileChannel.close();
            fileChannel = null;
            file = null;
            fileOutputStream = null;
            byteBuffer = null;          
        }
    }
} 

En ten slote het filter weer. Omdat de switch en de array elkaar toch niet zoveel scheelde heb ik maar ff de switch er weer ingezet. Met de array van .oisyn zal ie mischien nog een fractie sneller zijn? Ook heb ik nog niet naar de grote van de buffer gekeken. Kan vast ook nog wel getuned worden, maar 'k vind het wel welletjes zo

testing/FilterNIOSwitch.java

Java:

package testing;

import java.nio.CharBuffer;

import nioread.MappedInputFile;
import nioread.MappedOutputFile;

public class FilterNIOSwitch {

    /**
     * @param args
     */
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis(); 
        
        CharBuffer charBuffer = CharBuffer.allocate( 32768 );       
        MappedInputFile inputFile = new MappedInputFile();
        MappedOutputFile outputFile = new MappedOutputFile();
        
        try {
            inputFile.openFile("C:\\input.txt");
            outputFile.openFile("C:\\output.txt", charBuffer.limit() );
            
            boolean proceed = true;
            while ( proceed ) {
                proceed = inputFile.fillBuffer(charBuffer);
                filterBuffer(charBuffer);
                outputFile.storeBuffer(charBuffer);
            }           
        } 
        catch (Exception e) {
            e.printStackTrace();
        }       
        
        long timeElapsed = System.currentTimeMillis() - startTime;
        System.out.print( "Filtering took: " + timeElapsed );

    }
    
    public static void filterBuffer( CharBuffer buffer ) {
        
        char[] src = buffer.array(); // slightly faster than using objects get/set methods
                
        for ( int i=0; i<src.length; i++) {
            
            switch ( src[i] ) {
                // Specific characters: ~|/
                case '~' :
                    src[i] = '"';
                    break;
    
                case '|' :
                    src[i] = ','; break;                    
               
                case '/': src[i] = '-'; break;        
                //ÀÁÂÃÄÅÆ range
                case 'À':
                case 'Á':
                case 'Â' :
                case 'Ä' :
                case 'Å' :
                case 'Æ' : src[i] = 'A'; break;
                
                //Ç range
                case 'Ç': src[i] = 'C'; break;
                //ÈÉÊË range
                case 'È':
                case 'É':
                case 'Ê':
                case 'Ë': src[i] = 'E'; break;
                
                //ÌÍÎÏ range
                case 'Ì':
                case 'Í':
                case 'Î':
                case 'Ï': src[i] = 'I'; break;
                //Ñ range
                case 'Ñ': src[i] = 'N'; break;
                //ÒÓÕÖØÔ range
                case 'Ò':
                case 'Ó':
                case 'Õ':
                case 'Ö':
                case 'Ø':
                case 'Ô': src[i] = 'O'; break;
                //ÙÚÛÜ range
                case 'Ù':
                case 'Ú':
                case 'Û':
                case 'Ü': src[i] = 'U'; break;
                //Ý range
                case 'Ý': src[i] = 'Y'; break;              
                //àáâãäåæ range
                case 'à':
                case 'á':
                case 'â':
                case 'ä':
                case 'å':
                case 'æ': src[i] = 'a'; break;
                //ç range
                case 'ç': src[i] = 'c'; break;
                //èéêë range
                case 'è':
                case 'é':
                case 'ê':
                case 'ë': src[i] = 'e'; break;
                //ìíîï range
                case 'ì':
                case 'í':
                case 'î':
                case 'ï': src[i] = 'i'; break;
                //ñ range
                case 'ñ': src[i] = 'n'; break;
                //òóõöøô range
                case 'ò':
                case 'ó':
                case 'õ':
                case 'ö':
                case 'ø':
                case 'ô': src[i] = 'o'; break;
                //ùúûü range
                case 'ù':
                case 'ú':
                case 'û':
                case 'ü': src[i] = 'u'; break;
                //ý range
                case 'ý': src[i] = 'y';           
            }       
        }

    }
}

[ Voor 3% gewijzigd door Verwijderd op 20-10-2006 00:29 ]

[Verwijderd]

den 150 schreef op donderdag 19 oktober 2006 @ 22:55:
Het is algemeen bekend als je pure number crunching wilt doen, dat java dan absoluut niet the way to go(tm) is. [ ...] Als je performance wil, ga dan aan de slag in asm, C, [...]

Absoluut is 'absoluut' te sterk uitgedrukt. Zie ook mijn comment een paar posts hierboven. Er zijn wel degelijk zware algortimes die pure number crunching doen die sneller lopen in Java. Niet voor niets is er al jaren lang onderzoek gaande naar zogenaamde native optimizers/dynamic recompilers. Dit is feitelijk wat de JVM doet vanaf versie 1.1, maar dan speciaal bedoeld om van native machine code naar native machine code te compilen at runtime. Het idee daarachter is dat je sommige optimalisaties veel beter kunt uitvoeren als je runtime informatie tot je beschikking hebt. Making the common case fast is soms moeilijk als je niet weet (als compiler) wat die common case dan wel niet is.

De kracht van Java zelf lag inderdaad nooit in haar snelheid, maar in de waanzinnige grote standaard library met tal van classes voor profesionele (business/enterprise) software development. Dat Java nooit voor de scientific wereld bedoeld was zie je ook wel terug in diezelfde library. Zo rijk als het aan classes voor enterprise development, zo arm is het aan scientific support libraries (vergeleken met bv C).

Ondertussen verstreken de jaren en bijna ongemerkt werd de JVM van een slome interpreter, via een matige dynamic recompiler tot een waarlijk high performance geheel. Een oud jaargenoot van me is nu AIO en voor zijn onderzoek waarbij de meest optimale implementatie van diverse algortimes heel belangrijk is, zijn ze nu heel serieus met de JVM bezig.

Een niet al te objectieve, maar toch zeer interesante performance meting kun je in deze blog nalezen (even naar beneden scrollen tot ongeveer in het midden)

http://blogs.sun.com/dagastine/

Kleine tip nog: wees voorzichtig met NIO, de byte arrays/buffers/streams mappen rechtstreeks naar je OS virtual memory.

Klopt, daarom is NIO ook nog sterker dan de gewone IO package OS afhankelijk.

Aangezien deze code het enige is wat in je JVM draait heb je daar bijna volledige beschikking over, maar als je in een appserver draait dan heb je al wat minder.

Toevallig zat ik een tijdje terug de source code van netbeans door te lezen en daar zag ik dat men ook op dit probleem lette. In een IDE zou je dit waarschijnlijk krijgen als verschillende editors dergelijke grote mappings proberen te doen (en/of crashen volgens de comment).

Even met Google code zoeken, en ik heb het fragment weer gevonden:

Java:

 public ByteBuffer getReadBuffer(int start, int byteCount) throws IOException {
        ByteBuffer cont;
        synchronized (this) {
            //XXX Some optimizations possible here:
            // - Don't map the entire file, just what is requested (perhaps if the mapped
            //    start - currentlyMappedStart > someThreshold
            // - Use RandomAccessFile and use one buffer for reading and writing (this may
            //    cause contention problems blocking repaints)
            cont = this.contents;
            if (cont == null || start + byteCount > mappedRange || start < mappedStart) {
                FileChannel ch = readChannel();
                long offset = start + byteCount;
                mappedStart = Math.max((long)0, (long)(start - (MAX_MAP_RANGE /2)));
                long prevMappedRange = mappedRange;
                mappedRange = Math.min(ch.size(), start + (MAX_MAP_RANGE / 2));
                try {
                    try {
                        cont = ch.map(FileChannel.MapMode.READ_ONLY,
                            mappedStart, mappedRange - mappedStart);
                        this.contents = cont;
                    } catch (IOException ioe) {
                        Logger.getAnonymousLogger().info("Failed to memory map output file for " + //NOI18N
                                "reading.  Trying to read it normally."); //NOI18N
                        Exceptions.printStackTrace(ioe);

                        //If a lot of processes have crashed with mapped files (generally when testing),
                        //this exception may simply be that the memory cannot be allocated for mapping.
                        //Try to do it non-mapped
                        cont = ByteBuffer.allocate((int) (mappedRange - mappedStart));
                        ch.position(mappedStart).read(cont);
                        this.contents = cont;
                    }

[.oisyn]

Waarom hou je nou steeeds de map en switch implementaties aan, maar laat je de array implementatie links liggen

[Verwijderd]

.oisyn schreef op vrijdag 20 oktober 2006 @ 00:39:
Waarom hou je nou steeeds de map en switch implementaties aan, maar laat je de array implementatie links liggen

Is geen reden voor... luiheid. Zat even op de NIO dingen te concentreren, omdat we eerder al zagen dat de bulk van de tijd in de I/O ging zitten. Het verschil tussen helemaal niks filteren en chars direct weg schrijven vs de switch filter was al minimaal. De map heb ik helemaal niet meer gebruikt, zijn gewoon de oude getallen die ik er als vergelijking bij heb gezet.

Ik zei trouwens al wel dat ik dacht dat die array implementatie nog iets sneller zou zijn Als het niet al zo laat was geworden had ik die er zeker nog wel even bijgezet (ben nu zelf toch ook wel benieuwd).

[Deddiekoel]

Ik heb nu de array oplossing .oisyn/Soultaker geimplementeerd en hij is inderdaad vies snel.
Een 170 Mb bestand wordt nu in iets van 3 seconden verwerkt (heb geen precieze metingen). Indrukwekkend hoe je van snel naar sneller kunt en blijkbaar nog steeds niet op snelst zit.

[MrBucket]

Ik heb dit topic even vluchtig doorgelezen, maar volgens mij mis ik een toch wel voor de hand liggende optimalisatie?

Waarom bepaal je niet eerst de unicode-range van potientieel gevaarlijke karakters, en doe je voor elke karakter uit je source-string een check of deze upberhaupt in de gevaarlijke range valt? Als dat niet het geval is kan je je hele switch / hasmap / etc.-stap overslaan, omdat dat karakter er gegarandeerd niet in voor komt.

Tenminste, ik ga er vanuit dat zo'n 95% van de karakters niet in de gevaarlijke range valt?

[ Voor 9% gewijzigd door MrBucket op 20-10-2006 10:25 ]

[.oisyn]

Verwijderd schreef op vrijdag 20 oktober 2006 @ 00:47:

Is geen reden voor... luiheid.

Ah ok, ik had je er ook niet op zien reageren dus wellicht had je er overheen gelezen

MrBucket schreef op vrijdag 20 oktober 2006 @ 10:21:
Ik heb dit topic even vluchtig doorgelezen, maar volgens mij mis ik een toch wel voor de hand liggende optimalisatie?

Waarom bepaal je niet eerst de unicode-range van potientieel gevaarlijke karakters, en doe je voor elke karakter uit je source-string een check of deze upberhaupt in de gevaarlijke range valt? Als dat niet het geval is kan je je hele switch / hasmap / etc.-stap overslaan, omdat dat karakter er gegarandeerd niet in voor komt.

Tenminste, ik ga er vanuit dat zo'n 95% van de karakters niet in de gevaarlijke range valt?

95%? Da's denk ik wel veel. Denk eraan dat je hier niets aan unicode hebt he, hij leest gewoon bytes (in vermoedelijk de standaard codepage voor dat systeem). Voor een switch wordt een dergelijke check er meestal wel ingecompileerd (ik heb compilers hele dicision trees zien genereren, in feite heb je dan een statisch gecompileerde binary search), en voor een table die klein genoeg is om volledig in de cache te staan is een extra branch allesbehalve voordeliger.

[Deddiekoel]

MrBucket schreef op vrijdag 20 oktober 2006 @ 10:21:
Ik heb dit topic even vluchtig doorgelezen, maar volgens mij mis ik een toch wel voor de hand liggende optimalisatie?

Waarom bepaal je niet eerst de unicode-range van potientieel gevaarlijke karakters, en doe je voor elke karakter uit je source-string een check of deze upberhaupt in de gevaarlijke range valt? Als dat niet het geval is kan je je hele switch / hasmap / etc.-stap overslaan, omdat dat karakter er gegarandeerd niet in voor komt.

Tenminste, ik ga er vanuit dat zo'n 95% van de karakters niet in de gevaarlijke range valt?

Ik heb ook eerst in deze richting zitten denken door gewoon een encoding transform te doen. En volgens mij hebben anderen hier ook naar gekeken.
Voor mij was het punt om dit niet te doen dat we nu de speciale tekens vertalen naar een leesbaar equivalent. Als we alleen de speciale tekens weg wilt halen (zoals bij een encoding switch) dan worden de speciale tekens door een blokje oid vervangen en verlies je leesbaarheid...

[DaCoTa]

Deddiekoel schreef op vrijdag 20 oktober 2006 @ 09:50:
Ik heb nu de array oplossing .oisyn/Soultaker geimplementeerd en hij is inderdaad vies snel.
Een 170 Mb bestand wordt nu in iets van 3 seconden verwerkt (heb geen precieze metingen). Indrukwekkend hoe je van snel naar sneller kunt en blijkbaar nog steeds niet op snelst zit.

*kuch* DaCoTa in "[Java] Zo efficient mogelijk speciale ka..." *kuch*

MrBucket schreef op vrijdag 20 oktober 2006 @ 10:21:
Waarom bepaal je niet eerst de unicode-range van potientieel gevaarlijke karakters, en doe je voor elke karakter uit je source-string een check of deze upberhaupt in de gevaarlijke range valt? Als dat niet het geval is kan je je hele switch / hasmap / etc.-stap overslaan, omdat dat karakter er gegarandeerd niet in voor komt.

Ik denk dat de echte snelheid gehaald word door juist geen enkele branching meer te doen. Een lookup array doet altijd hetzelfde, geen prediction nodig, alleen een tabel die zo klein is dat die volledig in de cache valt. Dat gecombineerd met efficient geheugen gebruikt (geen allocaties binnen de loop, alles hergebruiken), gebufferde IO met een bloksize die prettig voor het OS is, maakt dat het vlot gaat.

edit:
Ruilen? Een spuit 11 opmerking tegen credits voor de snelste oplossing roepen 69 minuten na de TS

[ Voor 49% gewijzigd door DaCoTa op 20-10-2006 16:38 ]

[.oisyn]

DaCoTa schreef op vrijdag 20 oktober 2006 @ 13:59:
Ik denk dat de echte snelheid gehaald word door juist geen enkele branching meer te doen. Een lookup array doet altijd hetzelfde, geen prediction nodig, alleen een tabel die zo klein is dat die volledig in de cache valt. Dat gecombineerd met efficient geheugen gebruikt (geen allocaties binnen de loop, alles hergebruiken), gebufferde IO met een bloksize die prettig voor het OS is, maakt dat het vlot gaat.

*kuch* .oisyn in "[Java] Zo efficient mogelijk speciale ka..." *kuch*

[flowerp]

Aangezien ik nog niemand the obvious thing heb zien doen en de snelle io van henk combineerde met de snelle lookup methode van soultaker/oisyn heb ik dat maar even geprobeerd. Een 2 seconden snelle cut & paste leverde het volgende op:

Java:

package testing;

import java.nio.CharBuffer; 

import nioread.MappedInputFile; 
import nioread.MappedOutputFile; 

public class FilterNIOArray { 

    static char[] map; 

    
    /** 
     * @param args 
     */ 
    public static void main(String[] args) { 
        long startTime = System.currentTimeMillis();  
        
        String in  = "/|ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÑÒÓÕÖØÔÙÚÛÜÝàáâãäåæçèéêëìíîïñòóõöøôùúûüý~", 
        out = "-,AAAAAAACEEEEIIIINOOOOOOUUUUYaaaaaaaceeeeiiiinoooooouuuuy\""; 

         map = new char[65536]; 
         for(int n = 0; n < map.length; ++n) 
             map[n] = (char)n; 
         for(int n = 0; n < in.length(); ++n) 
             map[(int)in.charAt(n)] = out.charAt(n); 
         
        CharBuffer charBuffer = CharBuffer.allocate( 32768 );         
        MappedInputFile inputFile = new MappedInputFile(); 
        MappedOutputFile outputFile = new MappedOutputFile(); 
         
        try { 
            inputFile.openFile("/tmp/input.txt"); 
            outputFile.openFile("/tmp/output.txt", charBuffer.limit() ); 
             
            boolean proceed = true; 
            while ( proceed ) { 
                proceed = inputFile.fillBuffer(charBuffer); 
                filterBuffer(charBuffer); 
                outputFile.storeBuffer(charBuffer); 
            }             
        }  
        catch (Exception e) { 
            e.printStackTrace(); 
        }         
         
        long timeElapsed = System.currentTimeMillis() - startTime; 
        System.out.print( "Filtering took: " + timeElapsed ); 

    } 
     
    public static void filterBuffer( CharBuffer buffer ) { 
         
        char[] src = buffer.array(); // slightly faster than using objects get/set methods 
                 
        for ( int i=0; i<src.length; i++) {             
                src[i] = map [ src[i]];
        } 

    } 
}

Hiernaast heb ik ook even de 'no filtering' getest voor de nio versie (gewoon de filterbuffer method call weggecomment). De test heb ik gedraait op een uber trage G3 450Mhz/320MB onder Mac OS X 10.4.8 met Java 5 en een test file van 23mb. Opvallend is dat de NIO vs de normale IO bij mij niet zo veel winst geeft als we bij henk op Windows XP zagen.

Dit waren de tijden:

code:

nionoop    10970, 11235, 10934
nioarray   12907, 12253, 12896, 12896, 12701
nioswitch  13965, 13897, 13535, 13524, 13812
switch     20187, 19560, 19785, 19259, 20131

Duidelijk is dus dat de array methode op een machine met een extreem trage CPU significant sneller is. Gemiddeld scheelt het op een kleine file al ongeveer een hele seconden.

Oh, en ik zag nog een bugje in de FilterSwitch versie van henk; bij de laatste switch mist een break en er is geen flush en close op de bufferedwriter toegepast (zo mis je mogelijk het laatste stukje van je file).

ps, een hele rare issue kwam ik tegen bij deze code: Eclipse 3.1 onder Mac OS X ziet Ý en ý als identieke characters en flagged het in de switch als een dubbele case (???)

[.oisyn]

Gebruik ook eens mijn code ipv die van Soultaker? Ik gok dat er nog wat optimalisatie is te halen door de byte-unicode conversie achterwege te laten. Om de table te bouwen heb je wel nog even die switchstatement nodig zoals voorgesteld.

[flowerp]

.oisyn schreef op zaterdag 21 oktober 2006 @ 23:45:
Gebruik ook eens mijn code ipv die van Soultaker?

Wilde ik in de eerste instantie ook doen, maar die van Soultaker kon ik zo copy-pasten en in die van jou stond nog "etc..."

Maar ik probeer het morgen wel even, en kijk dan ook even of ik een een JDK 6 makkelijk aan de praat kan krijgen onder OS X.

Ik gok dat er nog wat optimalisatie is te halen door de byte-unicode conversie achterwege te laten. Om de table te bouwen heb je wel nog even die switchstatement nodig zoals voorgesteld.

In het geval van de NIO implementatie moet ik dan ook even die hele chardecoder eruit halen en direct op de bytebuffer werken. Als je er even over nadenkt dan moet dat bijna wel -weer- een stuk sneller worden

[.oisyn]

Op zich kun je de de code op de plek van etc... achterwege laten, de contents van de array hebben namelijk weinig te maken met de daadwerkelijke performance

[farlane]

Mensen mensen ga toch een pilsje pakken ...

[flowerp]

@.oisyn
Ik was begonnen met het implementeren van jouw oplossing, maar toen ik hem runde bedacht ik me dat het met bytes helemaal niet kan werken omdat die in Java signed zijn!

Het moet dus een tikkeltje anders.

Als ik deze run, komt er al heel snel een exception omdat de lookup table[data[i]] natuurlijk fout gaat zodra data[i] > 127 wordt (uitkomst is dan negatief). Ik zal straks eens kijken op welke plekken ik de byte het beste door de integer kan vervangen.

Java:

package testing;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.nio.ByteBuffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;


public class FilterNIOByteArray {
    
    public static void main(String[] args) { 
        long startTime = System.currentTimeMillis();  
         
        try {
                convert();
        }
        catch ( Exception e ) {
                e.printStackTrace();
        }
        
        long timeElapsed = System.currentTimeMillis() - startTime; 
        System.out.print( "Filtering took: " + timeElapsed ); 

    } 
    

    static byte[] createConversionTable() { 
        byte[] table = new byte[256]; 
        for (int i = 0; i < 256; i++) { 
            switch(i) { 
                case 'è':  
                case 'é':  
                case 'ê': 
                    table[i] = (byte)'e';                   
                    break; 

                // etc 

                default: 
                    table[i] = (byte)i; 
                        System.out.println( "def value=" + table[i] );
            } 
        } 

        return table; 
    } 

    static void convert() throws Exception { 
        
        byte[] table = createConversionTable(); 
        
        // Single buffer for reading and writing.
        ByteBuffer buffer = ByteBuffer.allocate(65536);
        byte[] data = buffer.array();
        
        // Input file
        File file = new File("/tmp/input.txt");         
        FileInputStream   fileInputStream = new FileInputStream(file); 
        FileChannel   fileChannel = fileInputStream.getChannel();         
        MappedByteBuffer byteBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size());
        
        // Output file
        File fileOut = new File("/tmp/output.txt");         
        FileOutputStream fileOutputStream = new FileOutputStream(fileOut); 
        FileChannel fileChannelOut = fileOutputStream.getChannel();  
            
        
        int bytesRemaining = byteBuffer.remaining();        
        while ( bytesRemaining > 0 ) {
            
                // Check is we read a full block or the last bath of bytes
                int readBytes = bytesRemaining > data.length? data.length : bytesRemaining;
            
                // Fetch block of 'readBytes' bytes from the channel
                byteBuffer.get(data, 0, readBytes );
                
                // Convert in place
                for (int i=0; i< readBytes; i++ ) {                 
                    data[i] = table[data[i]];
                }               
                buffer.limit(readBytes);
                
                // Write bytes to file ('buffer' is directly backed by 'data')
                fileChannelOut.write(buffer);
                
                buffer.rewind();
                
                bytesRemaining = byteBuffer.remaining();
        }
            
    }
    
}

[.oisyn]

zal straks eens kijken op welke plekken ik de byte het beste door de integer kan vervangen.

Nergens, maak van regel 81:

Java:

data[i] = table[data[i] & 0xff]; 

Ik vraag me trouwens af of de JITer slim genoeg is om hier een movzx instructie te genereren, ipv een movsx en een and 0xff

[ Voor 69% gewijzigd door .oisyn op 22-10-2006 22:46 ]

[flowerp]

.oisyn schreef op zondag 22 oktober 2006 @ 22:44:
[...]

Nergens, maak van regel 81:

Java:

data[i] = table[data[i] & 0xff]; 

Nou, heb ik gedaan (stom, had ik zelf ook wel kunnen bedenken maar das achteraf praten ) en hij is nu onrealistisch snel.

Dit zijn de nieuwe getallen:

code:

niobarray    2559, 2536, 2708, 2485, 2506
nionoop    10970, 11235, 10934
nioarray   12907, 12253, 12896, 12896, 12701
nioswitch  13965, 13897, 13535, 13524, 13812
switch     20187, 19560, 19785, 19259, 20131

Alleen de eerste keer zag ik een tijd van 7997 maar die heb ik maar even weggelaten.

Ik vraag me overigens wel af hoe bruikbaar de byte methode is. Het zal dan alleen werken op unicode filed die in 8bit gecodeerd zijn, terwijl de standaard encoding toch 16bit is. Plus dat je op deze manier natuurlijk ook niet de encoding kunt bepalen. Ik heb hem even op een ASCII encoded file geprobeerd (met dus de è gecodeerd as 0x8f) en daar werkt het niet op.

Maar goed, snel is het dus wel Vooral de charencoder eruit halen scheelt enorm!

Ik vraag me trouwens af of de JITer slim genoeg is om hier een movzx instructie te genereren, ipv een movsx en een and 0xff

Inderdaad. Voor zover ik weet slaat Java nergens duidelijk de JITted code op in een cache. Sommige andere VMs doen dat wel, is namelijk ook makkelijk voor als je je applicatie een 2de keer draait.

btw, hier is nog de final code:

Java:

package testing; 

import java.io.File; 
import java.io.FileInputStream; 
import java.io.FileOutputStream; 
import java.nio.ByteBuffer; 
import java.nio.MappedByteBuffer; 
import java.nio.channels.FileChannel; 


public class FilterNIOByteArray { 
     
    public static void main(String[] args) {  
        long startTime = System.currentTimeMillis();   
          
        try { 
                 convert(); 
        } 
        catch ( Exception e ) { 
                e.printStackTrace(); 
        } 
         
        long timeElapsed = System.currentTimeMillis() - startTime;  
        System.out.print( "Filtering took: " + timeElapsed );  

    }  
     

    static byte[] createConversionTable() {  
        byte[] src = new byte[256];  
        for (int i = 0; i < 256; i++) {  
            switch(i) {  
            // Specific characters: ~|/ 
            case '~' : 
                src[i] = '"'; 
                break; 
 
            case '|' : 
                src[i] = ','; break;                     
            
            case '/': src[i] = '-'; break;         
            //ÀÁÂÃÄÅÆ range 
            case 'À': 
            case 'Á': 
            case 'Â' : 
            case 'Ä' : 
            case 'Å' : 
            case 'Æ' : src[i] = 'A'; break; 
             
            //Ç range 
            case 'Ç': src[i] = 'C'; break; 
            //ÈÉÊË range 
            case 'È': 
            case 'É': 
            case 'Ê': 
            case 'Ë': src[i] = 'E'; break; 
             
            //ÌÍÎÏ range 
            case 'Ì': 
            case 'Í': 
            case 'Î': 
            case 'Ï': src[i] = 'I'; break; 
            //Ñ range 
            case 'Ñ': src[i] = 'N'; break; 
            //ÒÓÕÖØÔ range 
            case 'Ò': 
            case 'Ó': 
            case 'Õ': 
            case 'Ö': 
            case 'Ø': 
            case 'Ô': src[i] = 'O'; break; 
            //ÙÚÛÜ range 
            case 'Ù': 
            case 'Ú': 
            case 'Û': 
            case 'Ü': src[i] = 'U'; break; 
            //? ? range 
            case 'Ý': src[i] = 'Y'; break;               
            //àáâãäåæ range 
            case 'à': 
            case 'á': 
            case 'â': 
            case 'ä': 
            case 'å': 
            case 'æ': src[i] = 'a'; break; 
            //ç range 
            case 'ç': src[i] = 'c'; break; 
            //èéêë range 
            case 'è': 
            case 'é': 
            case 'ê': 
            case 'ë': src[i] = 'e'; break; 
            //ìíîï range 
            case 'ì': 
            case 'í': 
            case 'î': 
            case 'ï': src[i] = 'i'; break; 
            //ñ range 
            case 'ñ': src[i] = 'n'; break; 
            //òóõöøô range 
            case 'ò': 
            case 'ó': 
            case 'õ': 
            case 'ö': 
            case 'ø': 
            case 'ô': src[i] = 'o'; break; 
            //ùúûü range 
            case 'ù': 
            case 'ú': 
            case 'û': 
            case 'ü': src[i] = 'u'; break; 
            //? range ??? 
            case 'ý': src[i] = 'y'; break;
            
            default: 
                    src[i] = (byte)i;
                        
            }  
        }  

        return src;  
    }  

    static void convert() throws Exception {  
         
        byte[] table = createConversionTable();  
            
        // Single buffer for reading and writing. 
        ByteBuffer buffer = ByteBuffer.allocate(65536); 
        byte[] data = buffer.array(); 
         
        // Input file 
        File file = new File("/tmp/input.txt");          
        FileInputStream   fileInputStream = new FileInputStream(file);  
        FileChannel   fileChannel = fileInputStream.getChannel();          
        MappedByteBuffer byteBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size()); 
         
        // Output file 
        File fileOut = new File("/tmp/output.txt");          
        FileOutputStream fileOutputStream = new FileOutputStream(fileOut);  
        FileChannel fileChannelOut = fileOutputStream.getChannel();   
             
         
        int bytesRemaining = byteBuffer.remaining();         
        while ( bytesRemaining > 0 ) { 
             
                // Check is we read a full block or the last bath of bytes 
                int readBytes = bytesRemaining > data.length? data.length : bytesRemaining; 
             
                // Fetch block of 'readBytes' bytes from the channel 
                byteBuffer.get(data, 0, readBytes ); 
                 
                // Convert in place 
                for (int i=0; i< readBytes; i++ ) {                     
                    data[i] = table[data[i] & 0xff ]; 
                }                 
                buffer.limit(readBytes); 
                 
                // Write bytes to file ('buffer' is directly backed by 'data') 
                fileChannelOut.write(buffer); 
                 
                buffer.rewind(); 
                 
                bytesRemaining = byteBuffer.remaining(); 
        } 
             
    } 
     
}

offtopic:
ps ik ben er nu ook half achter waarom de ý en Ý als dezelfde cases werden gezien. Op mijn platform (OS X dus) worden ze beiden niet herkend en maakt eclipse er in vraagteken van die je pas ziet als je de editor sluit en weer opend.

[ Voor 65% gewijzigd door flowerp op 23-10-2006 00:16 ]

[.oisyn]

flowerp schreef op zondag 22 oktober 2006 @ 23:44:
Ik vraag me overigens wel af hoe bruikbaar de byte methode is. Het zal dan alleen werken op unicode filed die in 8bit gecodeerd zijn, terwijl de standaard encoding toch 16bit is. Plus dat je op deze manier natuurlijk ook niet de encoding kunt bepalen. Ik heb hem even op een ASCII encoded file geprobeerd (met dus de è gecodeerd as 0x8f) en daar werkt het niet op.

Doorgaans zijn textfiles gewoon 8 bit encoded in de standaard codepage van het OS. De byte<->unicode conversie is dus niet nodig zolang je maar een correcte mapping table gebruikt. Ik denk dat de gegenereerde table hier niet juist is, omdat (byte)'é' in Java niet hetzelfde oplevert als de é in een tekstbestand. Ik heb net een é opgeslagen vanuit notepad, en die vertaalt dat blijkbaar naar 233.

.edit: Hmm, Java komt ook met 233

.edit2: De è wordt trouwens een 232 (0xe8), zowel met notepad als met (byte)'è'

[ Voor 5% gewijzigd door .oisyn op 23-10-2006 00:36 ]

[flowerp]

.oisyn schreef op maandag 23 oktober 2006 @ 00:28:
[...]

Doorgaans zijn textfiles gewoon 8 bit encoded in de standaard codepage van het OS. De byte<->unicode conversie is dus niet nodig zolang je maar een correcte mapping table gebruikt. Ik denk dat de gegenereerde table hier niet juist is, omdat (byte)'é' in Java niet hetzelfde oplevert als de é in een tekstbestand. Ik heb net een é opgeslagen vanuit notepad, en die vertaalt dat blijkbaar naar 233.

.edit: Hmm, Java komt ook met 233

.edit2: De è wordt trouwens een 232 (0xe8), zowel met notepad als met (byte)'è'

Tis meestal nogal een behoorlijk gedoe met die encodings. Op de Mac heb je in Calculator de 'programmer mode' waarmee je makkelijk de byte waardes kan opzoeken van characters. In Character Palete kun je dan bv de hele unicode reeks door browsen. Zo zag ik dat de è in de reeks valt die "Latin-1 Supplement" heet die loopt van 00000080 t/m 000000FF. De Unicode waarde is dan "0x00 0xE8". Als ik in Eclipse de encoding van een niet Java file (java files hebben vaste unicode encoding) op "iso-8859-1" zet en de è safe dan krijg ik als byte waarde 0xE8. De UTF-8 encoding is weer anders, die is dan 0xC3 0xA8, en zoals gezegd in US-ASCII is het dus weer 0x8F.

Kort gezegd, met de huidige methode kun je dus 8bit unicode/iso-8859-1 files filteren.

edit: Op mijn platform saved Eclipse java files default in MacRoman wat identiek lijkt te zijn aan US-ASCII. De è in de .java file wordt gesaved als een 0x8F

[ Voor 5% gewijzigd door flowerp op 23-10-2006 13:00 ]

[MSalters]

é is geen ASCII. ASCII is een Amerikaanse standaard, en loopt tot 0x7F. Alles boven de 0x7F is gedefinieerd door een andere standaard, vaak ISO-8859-*, MacRoman of CP1252. Maar het probleem is dat in domme tekstfiles de encoding niet wordt opgeslagen - er staat misschien een 0xE8 in, maar wat dat betekent staat er niet bij. Daarom moet je het bij in het inlezen opgeven, of de systeemstandaard gebruiken.

edit:
é is dus U+008E in unicode, en Unicode tot U+0100 loopt gelijk op met ISO-8859-1. é is niet 0x00 0x8E in Unicode. In UTF-32 BE is het bijvoorbeeld 0x8E 0x00 0x00 0x00

[ Voor 18% gewijzigd door MSalters op 23-10-2006 21:02 . Reden: [edit] afsluiten ]

[matthijsln]

Dit is denk wel een toepasselijke link

Joel on software: The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!)

[ Voor 23% gewijzigd door matthijsln op 23-10-2006 22:29 ]

[.oisyn]

[b][message=26710851,noline]MSalters schreef op maandag 23 oktober 2006 @ 20:59

edit:
é is dus U+008E in unicode, en Unicode tot U+0100 loopt gelijk op met ISO-8859-1. é is niet 0x00 0x8E in Unicode. In UTF-32 BE is het bijvoorbeeld 0x8E 0x00 0x00 0x00

Is dat niet juist de LE variant, aangezien bij BE de msb eerst staat?