[Java] code optimalisatie

[mbravenboer]

Op zich waarschijnlijk interessant werk, maar niet zo verstandig naar mijn mening: de JDBC driver zal doorgroeien omdat hij onderhouden zal worden: jij kan je driver niet blijven onderhouden omdat het waarschijnlijk niet je 'core-business' zal worden. Je komt dus gegarandeerd op een moment dat je driver niet meer werkt op nieuwere MySQL versies en de JDBC driver je in performance voorbij streeft.

Kan je niet beter kijken waar de problemen in de MySQL driver zitten, die fixen en de verbeteringen insturen?

Een andere optie is natuurlijk om een beschaafd DBMS te gaan gebruiken. Naast de voordelen in het DBMS zelf is het ook zeer waarschijnlijk dat er een kwalitatievere JDBC driver is. Qua open oplossingen wordt de PostgreSQL driver zeer aktief onderhouden en is erg goed bij wat betreft de nieuwste Java goodies.

[mbravenboer]

In het algemeen werken "de bestaande oplossing passen me niet helemaal, dus dan doe ik het zelf wel" oplossingen dus niet echt (echt niet). Wat zelf voor de lol prutsen met zaken die eigenlijk al geimplementeerd zijn (zoals bijvoorbeeld een XML parser, een HTTP server of een template engine) is heel aardig, maar uiteindelijk kan je nooit op tegen mensen die van dergelijke zaken hun kern bezigheid hebben gemaakt. Alleen als jij het project zelf ook tot je kern bezigheid maakt, kan je wat zinvols bereiken.

[B-Man]

lange reactie

De Connector/J JDBC driver cached veel te veel. Ik kan vervolgens kiezen: Connector/J aanpassen of zelf een veel simpelere nieuwe driver schrijven.

Mijn keuze gaat uit naar een simpele driver, aangezien deze gemakkelijker te onderhouden is. Daarnaast is het protocol, en mijn driver, erg klein. Mijn driver omvat een viertal classes van enkele honderden regels code.

Wat ook meespeelt is het feit dat Connector/J (bijna) alle JDBC specs implementeert, waarvan ik 99% niet nodig heb. Zaken zoals encodings enz.

Maar goed, ik heb de basis van de driver can cauco gebruikt als leerobject, en deze is van zichzelf al 40-50% sneller dan connector/J. Van de nieuwste versie is echter geen source beschikbaar, en daarnaast werkt de driver alleen i.c.m. Resin.

[B-Man]

hobbit_be schreef op 05 March 2003 @ 04:38:
nou - effe een late niter - tis nu 4:22am

maar ik me nu effe een replace die enorm veel sneller is... hoe enorm ben ik zelf
verrast van. euh de verschillen op grote text waarvan er een hoop echte replacen hangt is het verschil wel erg groot.

(per 72x zijn er 3 replaces)

72000 characters / test:100 (zijn dus 100x1000x3 replaces = 3.000.000)
ooString :2.578s 2 seconden
mBravenBoer :136.297s 2 minuten

toegegeven een replace op een document met 72000 zul je niet
vaak tegenkomen... door de enorme memory copies valt
stringbuffer uit de boot.

maar ook op kleinere is er een groot verschil. In neem aan
dat enkel bij een single replace er weinig verschil zal zijn.
edit: effe getest met een sample van 1.000.000 maar ook hier
is het verschil ongeveer x2.5... (niet dat je daar iets van zou merken)


720 characters / test:10000
0.985s - per keer is dat dus 0.09ms
3.453s x3 - per keer 0.35ms

7200 characters / test:1000
0.969s - per keer is dat dus 1ms
8.078s x8 - 8ms

ooh en dit is wanneer de de nieuwe tekst > oude tekst...

voor dezelfde monster replace maar dan nieuwe tekst < oude tekst:

ooString :1.296s //relatief dus ook een pak sneller...
mBravenBoer :110.391s

en ja ik test de correctheid v/d results ...

code release ik morgen wel omdat ie nog niet snel genoeg is

Hobbit_be: je hebt je code geloof ik nog niet gepost, ik wacht nog steeds met spanning ;-) op je supersnelle replace functie, dan kan ik vergelijken of het blok-append-algoritme of een replace sneller is. Wil je je functie ajb posten, dan kan ik er eens naar kijken.

[hobbit_be]

B-Man idd - werk had even (nu nog) voorrang. Hier is de link naar de file die ik gebruik
om te testen. Het includes mBravenBoer/Zynt/Onno implementaties alsook de code for al het timen enzo. alleen de package name zul je moeten veranderen (?). Normaal gebruik ik log4j maar heb er uit gehaald for ease of use. Het gebruikt nu alleen standaard java. Laat me weten wat ie zegt: je zult vast de tests kunnen verhogen voor een snellere PC... (ik had geen goesting om een 5 minuten te wachten per test)

http://www.onnos.com/dkitTest.java

[B-Man]

hobbit_be: ga er nu even naar kijken. Heb zojuist zelf ook nog een replace functie gemaakt die twee keer zo snel is als mijn eerste functie (zie eerste pagina van dit topic).

Java:

public static String replace2(String orig, String from, String to) {
        
        int fromLength = from.length();

        if (fromLength == 0)
            throw new IllegalArgumentException("String to be replaced must not be empty");

        int start = orig.indexOf(from);
        if (start == -1) return orig;
        if (from.equals(to)) return orig;
        
        // Start replace
        
        int diff = to.length() - from.length();
        int tMax = orig.length()-from.length()+1;

        StrBuffer buffer;
        char[] origC = orig.toCharArray();
        char[] fromC = from.toCharArray();
        buffer = new StrBuffer(origC);
        int hits = 0, cp; // cp = Corrected Position
                
        first:for(int i=0;i<tMax;i++) {
            if(origC[i]!=fromC[0]) continue;
            
            for(int j=0;j<fromLength;j++)
                if(origC[i+j]!=fromC[j]) continue first;
                
            // hit!
            cp = i+(hits*diff); // Corrected position
            buffer.replace(cp, cp+fromLength, to);
            hits++;
        }

        return buffer.toString();
    }

In een String van 600 chars 11 maal een code vervangen door een string die langer is, 1000x achter elkaar, duurt met mijn eerste functie zo'n 120ms, en met deze functie zo'n 60ms.

[hobbit_be]

euh is nog 1 line teveel in mijn source

// String.valueOf(tSource); line: 369 - ik denk wel dat java hem wegcompileerd

[B-Man]

Wat denk je van mijn functie?

[hobbit_be]

kun je wel even StrBuffer meegeven? anders kan ik het niet testen

[B-Man]

Java:

public class StrBuffer {
    /** 
     * This variable 'numchar' is the number of characters in the buffer.
     */
    int numchar;

    /**
     * The variable 'mybuf' is used for character storage.
     */
    char mybuf[];

    /**
     * Make an empty string buffer with 80 characters of storage.
     */
    public StrBuffer() {
        this(80);
    }

    /**
     * Make an empty string buffer with 'len' characters of storage.
     *
     * @param      len   the initial storage capacity.
     * @exception  NegativeArraySizeException  if the 'len' less than 0.
     */
    public StrBuffer(int len) {
        this.mybuf = new char[len];
    }
    
    public StrBuffer(char[] data) {
        this.mybuf = data;
        this.numchar = data.length;
    }

    /**
     * Calling this method has same effect as setLength(0)
     * Clears the contents of the string buffer.
     */
    public void resetLength() {
        this.numchar = 0;
    }
    
    public int getLength() {
        return numchar;
    }

    public void setCapacity(int len) {
        if (len <= mybuf.length)
            return;
        mybuf = new char[len];
        numchar = 0;
    }
    
    public char[] getBuffer() {
        if(numchar==0) return new char[0];
        
        char []ret = new char[numchar];
        System.arraycopy(mybuf, 0, ret, 0, numchar);
        return ret;
    }
    
    public void setBuffer(char []buffer) {
        mybuf = buffer;
        numchar = buffer.length;
    }
    
    void ensureStorage(int size) {
        if(size > numchar)
            moreStorage(size);
    }

    /**
     * Expand the storage size to at least 'minStorage' number of characters.
     */
    void moreStorage(int minStorage) {
        int newStorage = (this.mybuf.length * 2) + 5;
        if (newStorage < minStorage)
            newStorage = minStorage;
        char newBuf[] = new char[newStorage];
        System.arraycopy(this.mybuf, 0, newBuf, 0, this.numchar);
        this.mybuf = newBuf;
    }

    /**
     * Appends the argument string to this string buffer. 
     *
     * @param   str   a string.
     * @return  this string buffer
     */
    public StrBuffer append(String str) {
        int oldlen = str.length();
        int newlen = this.numchar + oldlen;
        if (newlen > this.mybuf.length)
            moreStorage(newlen);
        str.getChars(0, oldlen, this.mybuf, this.numchar);
        this.numchar = newlen;
        return this;
    }

    public StrBuffer append(int i) {
        return append(String.valueOf(i));
    }

    public StrBuffer append(char[] ch) {
        int len = ch.length;
        int newcount = numchar + len;
        if (newcount > mybuf.length)
            moreStorage(newcount);

        System.arraycopy(ch, 0, mybuf, numchar, len);
        numchar = newcount;
        return this;
    }

    //public StrBuffer append(Object o) {
    //  return append(o.toString());
    //}

    public StrBuffer append(char[] text, int start, int len) {
        int newcount = numchar + len;
        if (newcount > mybuf.length)
            moreStorage(newcount);
        System.arraycopy(text, start, mybuf, numchar, len);
        numchar = newcount;
        return this;
    }

    public StrBuffer replace(int start, int end, String str) {
        if (start < 0) throw new StringIndexOutOfBoundsException(start);
        if (end > numchar) end = numchar;
        if (start > end) throw new StringIndexOutOfBoundsException();

        int len = str.length();
        int newCount = numchar + len - (end - start);
        if (newCount > mybuf.length)
            moreStorage(newCount);
            
        // Copy everything after our str to a new position
        if((end-start) != len) // Only when the length is different
            System.arraycopy(mybuf, end, mybuf, start + len, numchar - end);
        str.getChars(0, len, mybuf, start);
        numchar = newCount;
        return this;
    }

    /**
     * Returns a new string based on contents of string buffer.
     *
     * @return  a string
     */
    public String toString() {
        return new String(this.mybuf, 0, this.numchar);
    }
}

[B-Man]

Mijn testcode:

Java:

public static void main(String[] args) {
        // Now test the new tag splitter
        Stopwatch s = new Stopwatch();
        s.start();
        String myText = "Dit is een [test] met een [test2] en nog [test] 2etcetera\n" +
            "dsiafuhdfnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn\n" +
            "fddsfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff\n" +
            "fjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj\n" +
            "[test][test][test2]reahfhhhhhhhhhhhhhhhhhhhhhhhh [test] hhhhhhhhhhh\n" +
            "fasaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaajjjjjjj [test] jjjjjjjjjjjjjjjjj\n" +
            "[test]nvnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn\n" +
            "[test]nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn[test]nnnnnnnnnnnnnnnnnn\n" +
            "[test2]hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh\n";
        String myText2 = "abc[test] __ [test] 123 [test] xyz\ntweede [test] text [test] etceter";
        int cnt = 10000;
        for(int i=0;i<cnt;i++) {
            Utility.replaceOld(myText, "[test]", "haha");
            Utility.replaceOld(myText, "[test2]", "haha2");
        }
        System.out.println(s.elapsed());
        s.start();
        StrBuffer test = new StrBuffer(myText.toCharArray());
        for(int i=0;i<cnt;i++) {
            Utility.replace(test, "[test]", "haha");
            Utility.replace(test, "[test2]", "haha2");
            test.setBuffer(myText.toCharArray());
        }
        System.out.println(s.elapsed());
    }

Resultaat:

1401
656

Dat is dus 0,0656ms per keer

[edit]
Mijn Stopwatch class is simpelweg een wrapper om m.b.v. System.currentTimeMillis() te rekenen.

[ Voor 12% gewijzigd door B-Man op 09-03-2003 17:07 ]

[hobbit_be]

thx heb em effie getest

dkit.admin.dkitTest
validating replace:

ooString Result:
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
mBravenBoer Result:
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
Zynt Result:
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
B-Man Result:
OOPS.in thOOPSple, a loop nestedunderneath in anotherOOPSxample

> !!!! INCORRECT REPLACE !!!

//-------------------------------------------------------------------
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4
testing with 72 characters and repeating test:1

testing with 720 characters and repeating test:10000
ooString :1.125 /ms
mBravenBoer :3.484 /ms
mZynt :1.422 /ms
B-Man :1.672 /ms

testing with 7200 characters and repeating test:1000
ooString :1.094 /ms
mBravenBoer :8.172 /ms
mZynt :1.359 /ms
B-Man :6.937 /ms

//-------------------------------------------------------------------
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12

testing with 720 characters and repeating test:10000
ooString :1.156 /ms
mBravenBoer :3.735 /ms
mZynt :1.656 /ms
B-Man :1.937 /ms

testing with 7200 characters and repeating test:1000
ooString :1.203 /ms
mBravenBoer :8.688 /ms
mZynt :1.765 /ms
B-Man :6.953 /ms

//-----------------------------------------------------------------------
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 7

testing with 720 characters and repeating test:10000
ooString :1.094 /ms
mBravenBoer :3.218 /ms
mZynt :1.453 /ms
B-Man :0.922 /ms

testing with 7200 characters and repeating test:1000
ooString :1.047 /ms
mBravenBoer :3.141 /ms
mZynt :1.39 /ms
B-Man :0.922 /ms

The verdict:

a) je replace werkt niet (heb je oude code gegeven?)
b) hij is trager in alle gevallen behalve de laatste (trager dan zynt/onno)
c) het laatste geval geeft geen verschil in tijd door wat be dunkt
dat hij iets geks doet: maar wil best checken. Aangezien mijn code
is optimised for same-size replaces vindt ik het dus heel gek.

[B-Man]

Hmm, ging hier ook net wat mis. Ik denk dat het in mijn StrBuffer class zit. Ik denk dat ik die hele class niet gebruik (komt van het net, geen eigen code), en de code die ik nodig heb direct in mijn eigen functie zet. Back in 15 mins.

[B-Man]

Hobbit: ik heb zojuist je ooString klasse opgenomen in mijn eigen test (hierin zit nu ook mijn aangepaste replace, werkt nu volgens mij wel goed), en dit zijn de resultaten:

664 // die van mij
1023 // ooString.replaceUltraSnel met een string als input
1402 // ooString.replace

Testcode:

Java:

public static void main(String[] args) {
        // Now test the new tag splitter
        Stopwatch s = new Stopwatch();
        s.start();
        String myText = "Dit is een [test] met een [test2] en nog [test] 2etcetera\n" +
            "dsiafuhdfnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn\n" +
            "fddsfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff\n" +
            "fjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj\n" +
            "[test][test][test2]reahfhhhhhhhhhhhhhhhhhhhhhhhh [test] hhhhhhhhhhh\n" +
            "fasaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaajjjjjjj [test] jjjjjjjjjjjjjjjjj\n" +
            "[test]nvnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn\n" +
            "[test]nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn[test]nnnnnnnnnnnnnnnnnn\n" +
            "[test2]hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh\n";
        String myText2 = "abc[test] __ [test] 123 [test] xyz\ntweede [test] text [test] etceter";
        int cnt = 10000;
        for(int i=0;i<cnt;i++) {
            Utility.replaceOld(myText, "[test]", "haha");
            Utility.replaceOld(myText, "[test2]", "haha2");
        }
        System.out.println(s.elapsed());
        s.start();
        //StrBuffer test = new StrBuffer(myText.toCharArray());
        char [] ha = new char[0];
        for(int i=0;i<cnt;i++) {
            ha = myText.toCharArray();
            Utility.replace(ha, "[test]", "haha");
            Utility.replace(ha, "[test2]", "haha2");
        }
        System.out.println(s.elapsed());
        s.start();
        for(int i=0;i<cnt;i++) {
            ooString.replaceUltrasnel(myText, "[test]", "haha");
            ooString.replaceUltrasnel(myText, "[test2]", "haha2");
        }
        System.out.println(s.elapsed());
        s.start();
        for(int i=0;i<cnt;i++) {
            ooString.replace(myText, "[test]", "haha");
            ooString.replace(myText, "[test2]", "haha2");
        }
        System.out.println(s.elapsed());
        ha = myText.toCharArray();
        ha = Utility.replace(ha, "[test]", "haha");
        ha = Utility.replace(ha, "[test2]", "haha2");
        System.out.println(new String(ha));
    }

Zoals je kunt zien, is mijn code een stuk sneller. Graag je reactie ;-)
Voor de volledigheid hier mijn huidige replace code:

Java:

public static char[] replace(char []orig, String from, String to) {
        
        int fromLength = from.length();

        if (fromLength == 0)
            throw new IllegalArgumentException("String to be replaced must not be empty");

        if (from.equals(to)) return orig;
        
        // Start replace
        
        int diff = to.length() - from.length();
        //int tMax = buffer.getLength()-from.length()+1;
        int tMax = orig.length-from.length()+1;
        int toLength = to.length();

        char[] fromC = from.toCharArray();
        char[] toC = to.toCharArray();
        int hits = 0, cp; // cp = Corrected Position
        int cl = orig.length;   // current length
        
        //System.out.println("before hits");
        int h = 0;
        
        if(diff > 0) {
            first:for(int i=0;i<tMax;i++) {
                if(orig[i]!=fromC[0]) continue;
                
                for(int j=0;j<fromLength;j++)
                    if(orig[i+j]!=fromC[j]) continue first;
                    
                // hit!
                //cp = i+(hits*diff); // Corrected position
                
                h++;
            }
            
            if(h==0) {
                System.out.println("no hits");
                return orig;
            }       
            
            //System.out.println("after hits: "+h);
            
            // Create new array if necessary
            if(h>0 && diff>0) {
                char []tmp = new char[cl+(h*diff)];
                cl = tmp.length;
                System.out.println(orig.length+", "+tmp.length);
                System.arraycopy(orig, 0, tmp, 0, orig.length);
                orig = tmp;
            }
        }
                
        first:for(int i=0;i<tMax;i++) {
            if(orig[i]!=fromC[0]) continue;
            
            for(int j=0;j<fromLength;j++)
                if(orig[i+j]!=fromC[j]) continue first;
                
            // hit!
            
            if(diff != 0) {
                int size = orig.length-i-fromLength;
                System.arraycopy(orig, i+fromLength, orig, i+toLength, size);
                if(diff < 0) cl += diff;
            }
            // Now replace
            to.getChars(0, toLength, orig, i);
            hits++;
            
            i += toLength-1;
        }
        
        if(diff<0) {
            // Copy to a smaller array
            char []c = new char[cl];
            System.arraycopy(orig, 0, c, 0, cl);
            orig = c;
        }
        
        return orig;
    }

[B-Man]

Nog wat testinfo: als ik mijn myText var 10x achter elkaar plak, en dezelfde serie tests er 10.000x op loslaat:

code:

// myText
Old: 1401
New: 708
ooString mb: 1023
ooString fast: 1393

// myText x 10
Old: 14352
New: 9908
ooString mb: 12770
ooString fast: 14551

Waarin old mijn oude replace is, new mijn nieuwe, ooString mb mbravenboer, en ooString fast de replace() in ooString.

Wederom is mijn replace de snelste, ik kom er niet uit... vermoeidheid denk ik.

[update]
vervangende string korter:

code:

Old: 1933
New: 720
ooString mb: 1035
ooString fast: 1388

Old: 14074
New: 11812
ooString mb: 14358
ooString fast: 13898

[ Voor 17% gewijzigd door B-Man op 09-03-2003 19:48 ]

[hobbit_be]

effe checken - maar als je char[] gaat doorgeven kan het ook een pak sneller he dat is een hele hoop gecopy weg, dus geen appelen met peren vergelijken maar ga effe checken want die toChars die jij gebruikt ken ik niet en die ziet er interessant uit wel leuk zo'n sessie..

[hobbit_be]

hmm toch niet zo net:

java.lang.ArrayIndexOutOfBoundsException72, 99

als de nieuwe string > oude string dus er zit nog ergens een fout in bij je...

edit:
en ook nog een foute bij mezelf ontdekt gelukkig niet ernstig:

maar mijn berekening van tMax index moet niet

final int tMaxIndex = tSourceLength - tNewStringLength + 1;

maar:

final int tMaxIndex = tSourceLength - tOldStringLength + 1;

doh!!!

[ Voor 53% gewijzigd door hobbit_be op 09-03-2003 20:22 ]

[B-Man]

Er zit nog steeds een bug in mijn replace... als de vervangende string langer is dan het origineel, dan krijg ik een error. Zometeen even naar kijken.

[B-Man]

Oke, ik ben met de bug bezig... Maarre, wat denk je van mijn snelheidstest? Zoals je kunt zien is mijn functie sneller? Althans, voorzover ik het nu al heb kunnen testen (newstring even lang als oldstring en newstring < oldstring)...

[ Voor 33% gewijzigd door B-Man op 09-03-2003 20:33 ]

[hobbit_be]

euh ik ondek net nog wel een grove logica fout bij jouw - die ik eerst ook maakte trouwens:

jij modified in sommige gevallen de orig[] parameter: dwz dat SOMS de char[] die jij doorgeeft ook modified wordt teruggegeven EN de origenele veranderd:

in dat geval is het een ander soort replace die inderdaad een pak sneller is.

voorbeeld:

Java:

String tOrig = "this is an example";
char[] tFast = tOrig.toArray();

char[] tResult = BManReplace(tFast, "this", "test") 
//zoals eerder vermeld als jouw als ik "test met groter" zou pakken crashed jouw replace

//dan is tResult = "test is an example";

//MAAR:

//tFast = "test is an example";  //???? 

did kan natuurlijk het gebruik zijn als je wil want het het is idd sneller (2x full mem copy)

maar dan moet je de functie wel zo vermelden. als ik mijn functie ook zo maak gaat het bij mij ook een pak sneller. jouw replace is dus meer een :

someStringClass.replace("fast", "hello"); //zonder een return...

stel dat je met je template 3 keer die gebruikt dan vind die in alle volgende gevallen de tag
niet meer -

laat iets weten mocht je de New > Old probleem heb opgelost dan kunnen we nog eens comparen...

[B-Man]

Om toch fatsoenlijk te kunnen vergelijken init ik mijn char array opnieuw per iteratie:

Java:

char [] ha = new char[0];
        for(int i=0;i<cnt;i++) {
            ha = myText.toCharArray();
            Utility.replace(ha, in1, out1);
            Utility.replace(ha, in2, out2);
        }

Ik heb de bug ook gevonden, zometeen even eruit halen.

Overigens is dit gedrag me bekend. Het is sneller, en daarom acceptabel.

[hobbit_be]

heb effe dezelfde logica gestoken in een 'snelle' versie van m'n replace (ook met char[] en
may modify original)

//New < Old
testing with 720 characters and repeating test:10000
ooString :1.204 /ms
B-Man 2: 1.609 /ms
Onno Faster 2: 0.828 /ms

testing with 7200 characters and repeating test:1000
ooString :1.078 /ms
B-Man 2: 6.782 /ms
Onno Faster 2: 0.782 /ms

//New == Old
testing with 720 characters and repeating test:10000
ooString :0.969 /ms
B-Man 2: 0.656 /ms
Onno Faster 2: 0.688 /ms

testing with 7200 characters and repeating test:1000
ooString :0.984 /ms
B-Man 2: 0.657 /ms
Onno Faster 2: 0.687 /ms

in mijn test gevallen is mijn search sneller bij NEW < OLD maar de jouwe is dan weer sneller als ze gelijk zijn... het zou dus kunnen dat jouw search voor een 'match' sneller is dan die van mij want jouw copy is trager - maw ze zijn wellicht te combineren.. ook jouw fast return als eerste character niet klopt is interessant...

[B-Man]

bug is eruit, moest corrigeren op basis van de originele input als de vervangende string langer is:

Java:

// hit!
            
            if(diff != 0) {
                if(diff<0) size = orig.length-i-fromLength;
                else        size = ol-i-fromLength;
                System.arraycopy(orig, i+fromLength, orig, i+toLength, size);
                if(diff < 0) cl += diff;
            }

output met een vervangende string die langer is:

code:

Old: 1949
New: 853
ooString mb: 1320
ooString fast: 1431

Old: 14962
New: 11619
ooString mb: 19320
ooString fast: 14877

[B-Man]

hobbit: alweer winst, we stoten het vorige string-replace topic van de troon

Post je ajb je code?

[hobbit_be]

ik denk het vast wel: zowel synth code als mbravenboer heb ik al uit de benchmark gehaalt die zijn minstens 2x (mbravenboer x8) trager...

ik had nog in mijn nieuwe fast een foutje (ik gaf bij een kleiner result de grotere door) dus nu is mijn 'fast' replaces iets trager.

gek genoeg is is nog altijd sneller bij kleinere gevallen en de jouwe nog steeds troon voor als ze gelijk zijn

[B-Man]

Zoals ik al aangaf wil ik graag een blik werpen op je meest recente functie, dan kan ik kijken wat er te combineren valt.

[hobbit_be]

euh wat is "ol" bij jouw? en waar heb je 'size' nu gedefinieerd?

ik zie nog een snellere loop voor jouw in deel 2 van je search begin je opnieuw
van 0 maar je kunt al ineens naar 1 skippen

[ Voor 58% gewijzigd door hobbit_be op 09-03-2003 21:28 ]

[hobbit_be]

here is mijn versie alla different rules

Java:

    public static char[] replace(char[] aSource, String aOld, String aNew)
    {
       final int tSourceLength = aSource.length;
        if (tSourceLength == 0)
        {
            return aSource;
        }
        final int tOldStringLength = aOld.length();
        if (tOldStringLength == 0)
        {
            return aSource;
        }
        if (aOld.equals(aNew)) // :) you NEVER know penatly should be light
        {
            return aSource;
        }
         final int tNewStringLength = aNew.length(); 
         final char[] tOld = aOld.toCharArray();
         final char[] tNew = aNew.toCharArray();

        final int tMaxIndex = tSourceLength - tOldStringLength + 1;
        int tIndex = 0;
        int tSearchIndex; //to prevent reinit of int var in case java doesn't see it..

        if (tNewStringLength == tOldStringLength)
        {
             nextChar:while (tIndex < tMaxIndex) //ugly ? yes but nice :)
            {
                tSearchIndex = 0; //restart search
                while (tSearchIndex < tNewStringLength)
                {
                    if (aSource[tIndex++] != tOld[tSearchIndex++]) //is ++Int faster???
                    {
                        continue nextChar; //restart search
                    }
                }
                System.arraycopy(tNew, 0, aSource,
                                 tIndex - tNewStringLength,
                                 tNewStringLength);
            }
            return aSource;
        }
        
        int tWriteToIndex = 0;
        int tReadFromIndex = 0;
        int tOriginalCopySize;
        int tReplaceCount = 0; 
        
        if (tNewStringLength < tOldStringLength)
        {
             nextChar3:while (tIndex < tMaxIndex)
            {
                tSearchIndex = 0; //restart search
                while (tSearchIndex < tOldStringLength)
                {
                    if (aSource[tIndex++] != tOld[tSearchIndex++])
                    {
                        continue nextChar3; //restart search
                    }
                } 
                tOriginalCopySize = tIndex - tReadFromIndex - tOldStringLength;
                if (tOriginalCopySize > 0) 
                { 
                    System.arraycopy(aSource, tReadFromIndex, aSource,
                                     tWriteToIndex, tOriginalCopySize);
                    tWriteToIndex += tOriginalCopySize; //offset write position
                }
                System.arraycopy(tNew, 0, aSource, tWriteToIndex,
                                 tNewStringLength);
                tWriteToIndex += tNewStringLength;
                tReadFromIndex = tIndex;
                tReplaceCount++; 
            }
            if (tReplaceCount == 0)
            {
                return aSource; 
            }
            tOriginalCopySize = tSourceLength - tReadFromIndex;
            if (tOriginalCopySize > 0)
            {
                System.arraycopy(aSource, tReadFromIndex, aSource,
                                 tWriteToIndex, tOriginalCopySize);
                tWriteToIndex += tOriginalCopySize; //this is length
            }
            int tSize = tSourceLength +
                        ( (tNewStringLength - tOldStringLength) * tReplaceCount);

            char[] tBuffer = new char[tSize]; 
            System.arraycopy(aSource, 0, tBuffer, 0, tSize);

            return tBuffer; 

        }

        int tMaxReplaceCount = mReplaceIndex.length; //cache this
        nextChar2:while (tIndex < tMaxIndex)
        {
            tSearchIndex = 0; //restart search
            while (tSearchIndex < tOldStringLength)
            {
                if (aSource[tIndex++] != tOld[tSearchIndex++])
                {
                    continue nextChar2; //restart search
                }
            }
            mReplaceIndex[tReplaceCount++] = tIndex - tOldStringLength;
            if (tReplaceCount >= tMaxReplaceCount) //painful but unlikely
            {
                int[] tReplaceIndex = new int[tMaxReplaceCount +
                                      mReplaceIndexGrowth];
                System.arraycopy(mReplaceIndex, 0, tReplaceIndex, 0,
                                 tMaxReplaceCount);
                tMaxReplaceCount = mReplaceIndex.length;
            }
        }
        if (tReplaceCount == 0)
        {
            return aSource; //no matches...
        }
        int tSize = tSourceLength +
                    ( (tNewStringLength - tOldStringLength) * tReplaceCount);

        char[] tBuffer = new char[tSize]; //ugly but required unless
        for (int tReplaceIndex = 0; tReplaceIndex < tReplaceCount;
                                 tReplaceIndex++)
        {
            tIndex = mReplaceIndex[tReplaceIndex];
            tOriginalCopySize = tIndex - tReadFromIndex;
            if (tOriginalCopySize > 0) //copy original text piece
            {
                System.arraycopy(aSource, tReadFromIndex, tBuffer,
                                 tWriteToIndex, tOriginalCopySize);
                tWriteToIndex += tOriginalCopySize; //offset write position
            }
            System.arraycopy(tNew, 0, tBuffer, tWriteToIndex,
                             tNewStringLength);
            tWriteToIndex += tNewStringLength;
            tReadFromIndex = tIndex + tOldStringLength; //offset read 'jump' over the replace..
        }
        if (tReadFromIndex < tSourceLength)
        {
            System.arraycopy(aSource, tReadFromIndex, tBuffer,
                             tWriteToIndex, tSourceLength - tReadFromIndex);
        }
        return tBuffer; //the only usefull String Copy...
    }

[B-Man]

hobbit_be schreef op 09 March 2003 @ 21:26:
euh wat is "ol" bij jouw? en waar heb je 'size' nu gedefinieerd?

ik zie nog een snellere loop voor jouw in deel 2 van je search begin je opnieuw
van 0 maar je kunt al ineens naar 1 skippen

ol = old length, een int die de oorspronkelijke lengte van mijn input char[] bevat. size is een int die alleen betekenis in de tweede lus heeft.

[B-Man]

Oh, en pffffff, wat een lap code zeg, daar stelt die van mij niet veel bij voor

[hobbit_be]

yow!

ik heb effe jouw 'match' in mijn code gepropt en idd hij is sneller ik heb hem NOG wat geoptimaliseerd en het is idd die eerste check die het em doet

dwz: dat je bijvoorbeeld voor elke lengte van old string een nieuwe search kunt doen voor extra speed... zonder die toChars (maar pure System) is die dus nog sneller... als new==old dan is de nieuwe al 2x zo snel als de oude (maar die moet natuurlijk copying enzo)...

ik ga effe < > ook doen:

de search is nu:

Java:

final char tFirst = tOld[0]; //:) simpel maar genoeg voor 100ms :)
first:for (tIndex = 0; tIndex < tMaxIndex; tIndex++)
{
    if (aSource[tIndex] != tFirst)
    {
        continue;
    }

    for (tSearchIndex = 1; tSearchIndex < tOldStringLength; tSearchIndex++)
    {
        if (aSource[tIndex + tSearchIndex] != tOld[tSearchIndex])
        {
            continue first;
        }
    }

[hobbit_be]

dit is mijn laatste post vandaag

a) ik krijg met ol = orig.length nog steeds ArrayIndexOutOfBound. ik snap
ook niet veel v/j code daaromtrent...

b) laatste post is al achterhaalt - doen ik die 'trick' om eerste (indexOf) te doen
op mijn while loop loslaat ging ie nog sneller (dus alvast bedankt!!!)

c) mijn originele (dus propere ooString) is nu ook weer een stuk sneller:

d) final rsesult:

Old > New

testing with 720 characters and repeating test:10000
BMan - Onno: 0.781 /ms
ooString : 0.984 /ms
B-Man 2: 1.547 /ms

testing with 7200 characters and repeating test:1000
BMan - Onno: 0.782 /ms
ooString : 0.938 /ms
B-Man 2: 6.812 /ms

Old = New

testing with 720 characters and repeating test:10000
BMan - Onno: 0.563 /ms
B-Man 2: 0.625 /ms
ooString : 0.844 /ms

testing with 7200 characters and repeating test:1000
BMan - Onno: 0.562 /ms
B-Man 2: 0.641 /ms
ooString : 0.89 /ms

Kan het sneller ? - yep door x-aantal speciale gevallen los te laten
maar deze is universeel en misschien kan deze nog sneller afhankelijk
van JVM implementatie: qua algorithme zitten we goed

edit:
NEW > OLD werkt ook waanzinnig snel nu...

[ Voor 3% gewijzigd door hobbit_be op 09-03-2003 22:56 ]

[B-Man]

Goed nieuws hobbit! Ben nu mijn MySQL driver aan het afronden, die is ook erg snel vergeleken met de MM.MySQL driver.

Om duidelijk te maken wat ol en size zijn hierbij de gehele (werkende! ook indien newLen > oldLen) functie:

Java:

public static char[] replace(char []orig, String from, String to) {
        
        int fromLength = from.length();

        if (fromLength == 0)
            throw new IllegalArgumentException("String to be replaced must not be empty");

        if (from.equals(to)) return orig;
        
        // Start replace
        
        int diff = to.length() - from.length();
        //int tMax = buffer.getLength()-from.length()+1;
        int tMax = orig.length-from.length()+1;
        int toLength = to.length();

        char[] fromC = from.toCharArray();
        char[] toC = to.toCharArray();
        int hits = 0, cp; // cp = Corrected Position
        int cl = orig.length;   // current length
        int ol = cl,size;           // original length
        
        //System.out.println("before hits");
        int h = 0;
        
        if(diff > 0) {
            first:for(int i=0;i<tMax;i++) {
                if(orig[i]!=fromC[0]) continue;
                
                for(int j=0;j<fromLength;j++)
                    if(orig[i+j]!=fromC[j]) continue first;
                    
                // hit!
                //cp = i+(hits*diff); // Corrected position
                
                h++;
            }
            
            if(h==0) {
                System.out.println("no hits");
                return orig;
            }       
            
            //System.out.println("after hits: "+h);
            
            // Create new array if necessary
            if(h>0 && diff>0) {
                char []tmp = new char[cl+(h*diff)];
                cl = tmp.length;
                //System.out.println("add "+(h*diff));
                //System.out.println(orig.length+", "+tmp.length);
                System.arraycopy(orig, 0, tmp, 0, orig.length);
                orig = tmp;
            }
        }
                
        first:for(int i=0;i<tMax;i++) {
            if(orig[i]!=fromC[0]) continue;
            
            for(int j=0;j<fromLength;j++)
                if(orig[i+j]!=fromC[j]) continue first;
                
            // hit!
            
            if(diff != 0) {
                if(diff<0) size = orig.length-i-fromLength;
                else        size = ol-i-fromLength;
                System.arraycopy(orig, i+fromLength, orig, i+toLength, size);
                if(diff < 0) cl += diff;
            }
            // Now replace
            to.getChars(0, toLength, orig, i);
            hits++;
            
            i += toLength-1;
        }
        
        if(diff<0) {
            // Copy to a smaller array
            char []c = new char[cl];
            System.arraycopy(orig, 0, c, 0, cl);
            orig = c;
        }
        
        return orig;
    }

[Soultaker]

Mag ik die replace ook in C implementeren met de JNI? Dan zullen we nog wel eens zien wat snel is.

[B-Man]

Soultaker: ik las laast dat sommige zaken m.b.v. JNI juist trager zijn dan m.b.v. JIT in de JVM... Zal eens kijken of ik de nieuwsgroep-post terug kan vinden. Het ging in ieder geval zo'n 33% trager m.b.v. JNI.

Maarre, feel free om het te proberen. Als het sneller gaat, dan heb ik er wel oren naar Werk overigens wel op linux...

[ Voor 24% gewijzigd door B-Man op 10-03-2003 00:14 ]

[Soultaker]

B-Man schreef op 10 March 2003 @ 00:13:
Soultaker: ik las laast dat sommige zaken m.b.v. JNI juist trager zijn dan m.b.v. JIT in de JVM... Zal eens kijken of ik de nieuwsgroep-post terug kan vinden. Het ging in ieder geval zo'n 33% trager m.b.v. JNI.

Maarre, feel free om het te proberen. Als het sneller gaat, dan heb ik er wel oren naar Werk overigens wel op linux...

Ik ben de afgelopen nachten niet voor drie uur naar bed geweest omdat ik projectdocumentatie af moet maken, dus ik heb daar echt geen tijd voor (wel GoT checken tussendoor natuurlijk ). Maar ik ben benieuwd waar die tijd in gaat zitten. Als je met behulp van reflectie allerlei methoden bij objecten moet gaan zoeken, is de JNI waarschijnlijk erg traag, maar als je gewoon drie strings binnenkrijgt (die je als character arrays kunt benaderen) en een enkele string moet construeren, zoals in dit geval, dan kan ik me moeilijk voorstellen dat er nog verdere overhead optreedt (misschien zijn native method calls iets kostbaarders maar dan nog).

[B-Man]

Soultaker: overigens is System.arraycopy() al een native functie.

[hobbit_be]

B-Man: (sorry dat ik dit moet laten zien)

Original: example.in this example, a loop nestedunderneath in another loop.example

[example gets replaced]

validating replace:

ooString:
very big replace.in this very big replace, a loop nestedunderneath in another loop.very big replace

mBravenBoer:
very big replace.in this very big replace, a loop nestedunderneath in another loop.very big replace

B-Man Final Result:
very big replace.in this very big replace, a loop nestedunderneath in another loo ... (some weird characters)

B-Man - Onno
very big replace.in this very big replace, a loop nestedunderneath in another loop.very big replace

maar hij geeft geen geheugen fouten meer... dus alleen een copy op het laatste gaat er fout...

times:

Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4

testing with 720 characters and repeating test:10000
ooString : 0.985 /ms
B-Man Final: 1.625 /ms
BMan - Onno: 0.765 /ms

testing with 7200 characters and repeating test:1000
ooString : 0.921 /ms
B-Man Final: 6.813 /ms
BMan - Onno: 0.75 /ms

Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 7


testing with 720 characters and repeating test:10000
ooString : 0.875 /ms
B-Man Final: 0.641 /ms
BMan - Onno:0.562 /ms

testing with 7200 characters and repeating test:1000
ooString : 0.922 /ms
B-Man Final: 0.656 /ms
BMan - Onno: 0.563 /ms

Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12

testing with 720 characters and repeating test:10000
ooString : 1.032 /ms
B-Man Final: 1.734 /ms
BMan - Onno: 0.797 /ms

testing with 7200 characters and repeating test:1000
ooString :1.047 /ms
B-Man Final: 6.39 /ms
BMan - Onno: 0.828 /ms

ik heb effe je code ontleed en als je echt speed nodig hebt (dus als diff <> 0) dan is je code echt niet optimaal: heel veel memory copy dat niet nodig is. Als ik grotere tests draai moet ik zolang wachten dat ik de app afbreek (heapsize maar ook veel te veel reshuffle)

ik zal morgen de final geven , want een deel van de code is van jouw en jij hebt hem vast meer nodig dan ik... (vandaag HAD ik aan een invocation engine moeten werken - java is daarin toch niet zo mooi als ik dacht)

BTW als je naar de results kijkt is iedere result per deel eigenlijk gelijk aan het aantal replaces. (720x10000 = 7200x1000).

Mocht je die MM.MySQL driver klaarkrijgen ben ik daar ook zeer in geinteresseerd BTW. ook ik heb alleen standaard spul nodig...

Soultaker: tja als je me effe alleen laten met masm zal ik het vast ook nog een pak sneller kunnen krijgen. Ik zou zeggen dat de code gemiddeled 10x 100x sneller zou zijn met een native (misschien meer met SSE)

[hobbit_be]

toch maar effe posten:

Java:

  //make these private if syncronised is required
  //otherwise these get reused
    static private int[] mReplaceIndex = new int[10000];
    static private int mReplaceIndexGrowth = 10000;

 //the replace. returns a result, but may change aSource object as well
      public static char[] BManOnnoReplace(char[] aSource, String aOld,
                                         String aNew)
    {
        final int tSourceLength = aSource.length;
        if (tSourceLength == 0)
        {
            return aSource;
        }
        final int tOldStringLength = aOld.length();
        if (tOldStringLength == 0)
        {
            return aSource;
        }
//probably remove this since why would anyone replace the same?
//        if (aOld.equals(aNew)) // :) you NEVER know penatly should be light
//        {
//            return aSource;
//        }

        final int tNewStringLength = aNew.length();
        final char[] tOld = aOld.toCharArray();
        final char[] tNew = aNew.toCharArray();

        final int tMaxIndex = tSourceLength - tOldStringLength + 1;
        int tIndex = 0;
        int tSearchIndex; 
        final char tFirst = tOld[0]; 
//we cache first of old - quite a speed difference
        if (tNewStringLength == tOldStringLength)
        {
            nextChar:while (tIndex < tMaxIndex) 
            {
                if (aSource[tIndex++] != tFirst)
                {
                    continue;
                }
             //if we are here then 1st character is already same so skip
                tSearchIndex = 1; 
                while (tSearchIndex < tNewStringLength)
                {

                    if (aSource[tIndex++] != tOld[tSearchIndex++]) //is ++Int faster???
                    {
                        continue nextChar; //restart search
                    }
                }
                System.arraycopy(tNew, 0, aSource,
                                 tIndex - tNewStringLength,
                                 tNewStringLength);
            }
            return aSource; //BAIL! -> modifies aSource
        }

        int tWriteToIndex = 0;
        int tReadFromIndex = 0;
        int tOriginalCopySize;
        int tReplaceCount = 0;

        if (tNewStringLength < tOldStringLength)
        {
            nextChar3:while (tIndex < tMaxIndex)
            {
                if (aSource[tIndex++] != tFirst)
                {
                    continue;
                }

                tSearchIndex = 1; //restart search
                while (tSearchIndex < tOldStringLength)
                {
                    if (aSource[tIndex++] != tOld[tSearchIndex++])
                    {
                        continue nextChar3; //restart search
                    }
                }
                tOriginalCopySize = tIndex - tReadFromIndex -
                                    tOldStringLength;
 //copy piece missed from last - minimum copy - no duplicate copying
 //what so ever!!!
                if (tOriginalCopySize > 0)
                {
                    System.arraycopy(aSource, tReadFromIndex, aSource,
                                     tWriteToIndex, tOriginalCopySize);
                    tWriteToIndex += tOriginalCopySize; //offset write position
                }
                System.arraycopy(tNew, 0, aSource, tWriteToIndex,
                                 tNewStringLength);
                tWriteToIndex += tNewStringLength;
                tReadFromIndex = tIndex;
                tReplaceCount++;
            }
            if (tReplaceCount == 0)
            {
                return aSource;
            }
//we still need to copy last bit
            tOriginalCopySize = tSourceLength - tReadFromIndex;
            if (tOriginalCopySize > 0)
            {
                System.arraycopy(aSource, tReadFromIndex, aSource,
                                 tWriteToIndex, tOriginalCopySize);
                tWriteToIndex += tOriginalCopySize; //this is length
            }
//we need to return correct array not aSource coz lengths are different
            int tSize = tSourceLength +
                        ( (tNewStringLength - tOldStringLength) *
                         tReplaceCount);
//when doing a STring return -> no penalty!
            char[] tBuffer = new char[tSize];
            System.arraycopy(aSource, 0, tBuffer, 0, tSize);

            return tBuffer;

        }

//case NEW > OLD
        int tMaxReplaceCount = mReplaceIndex.length; //cache this
        nextChar2:while (tIndex < tMaxIndex)
        {
            if (aSource[tIndex++] != tFirst)
            {
                continue;
            }

            tSearchIndex = 1; //restart search
            while (tSearchIndex < tOldStringLength)
            {
                if (aSource[tIndex++] != tOld[tSearchIndex++])
                {
                    continue nextChar2; //restart search
                }
            }
            mReplaceIndex[tReplaceCount++] = tIndex - tOldStringLength;
            if (tReplaceCount >= tMaxReplaceCount) //painful but unlikely
            {
                int[] tReplaceIndex = new int[tMaxReplaceCount +
                                      mReplaceIndexGrowth];
                System.arraycopy(mReplaceIndex, 0, tReplaceIndex, 0,
                                 tMaxReplaceCount);
                mReplaceIndex = tReplaceIndex;
                tMaxReplaceCount = mReplaceIndex.length;
            }
        }
        if (tReplaceCount == 0)
        {
            return aSource; //no matches...
        }
        int tSize = tSourceLength +
                    ( (tNewStringLength - tOldStringLength) * tReplaceCount);

        char[] tBuffer = new char[tSize]; //ugly but required unless
//do the actual replacing - again no duplicate copies... 
        for (int tReplaceIndex = 0; tReplaceIndex < tReplaceCount;
                                 tReplaceIndex++)
        {
            tIndex = mReplaceIndex[tReplaceIndex];
            tOriginalCopySize = tIndex - tReadFromIndex;
            if (tOriginalCopySize > 0) //copy original text piece
            {
                System.arraycopy(aSource, tReadFromIndex, tBuffer,
                                 tWriteToIndex, tOriginalCopySize);
                tWriteToIndex += tOriginalCopySize; //offset write position
            }
            System.arraycopy(tNew, 0, tBuffer, tWriteToIndex,
                             tNewStringLength);
            tWriteToIndex += tNewStringLength;
            tReadFromIndex = tIndex + tOldStringLength; //offset read 'jump' over the replace..
        }
        if (tReadFromIndex < tSourceLength)
        {
            System.arraycopy(aSource, tReadFromIndex, tBuffer,
                             tWriteToIndex, tSourceLength - tReadFromIndex);
        }
        return tBuffer; //the only usefull String Copy...
    }

iemand nog ideetjes?

[Marcj]

Hmm.. ik denk ik probeer ik eens wat. Ff een algoritme geschreven en getest mbv die dkitTest.java

result:

code:

OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4
testing with 72 characters and repeating test:1
ooString :0.0 /ms
mBravenBoer :0.0 /ms
mZynt :0.0 /ms
MarcJ : 0.01 /ms
testing with 720 characters and repeating test:10000
ooString :0.571 /ms
mBravenBoer :0.791 /ms
mZynt :0.581 /ms
MarcJ : 0.631 /ms
testing with 7200 characters and repeating test:1000
ooString :0.521 /ms
mBravenBoer :1.782 /ms
mZynt :0.501 /ms
MarcJ : 0.461 /ms
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12
testing with 72 characters and repeating test:1
ooString :0.0 /ms
mZynt :0.0 /ms
MarcJ : 0.0 /ms
testing with 720 characters and repeating test:10000
ooString :0.561 /ms
mBravenBoer :0.891 /ms
mZynt :0.731 /ms
MarcJ : 0.651 /ms
testing with 7200 characters and repeating test:1000
ooString :0.551 /ms
mBravenBoer :1.892 /ms
mZynt :0.731 /ms
MarcJ : 0.481 /ms

Efficiënter bij hele grote reeksen dus, maar minder bij de wat kortere. Ik denk dat ik nu ff wat ga fine-tunen

edit2:

code:

validating replace:
ooString Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
mBravenBoer Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
Zynt Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
MarcJ Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4
testing with 72 characters and repeating test:1
ooString :0.0 /ms
mZynt :0.0 /ms
MarcJ : 0.0 /ms
testing with 720 characters and repeating test:10000
ooString :0.581 /ms
mZynt :0.6 /ms
MarcJ : 0.491 /ms
testing with 7200 characters and repeating test:1000
ooString :0.541 /ms
mZynt :0.521 /ms
MarcJ : 0.5 /ms
testing with 72000 characters and repeating test:100
ooString :1.192 /ms
mZynt :0.701 /ms
MarcJ : 0.611 /ms
testing with 720000 characters and repeating test:10
ooString :1.242 /ms
mZynt :1.632 /ms
MarcJ : 0.711 /ms
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12
testing with 72 characters and repeating test:1
ooString :0.0 /ms
mZynt :0.0 /ms
MarcJ : 0.0 /ms
testing with 720 characters and repeating test:10000
ooString :0.551 /ms
mZynt :0.681 /ms
MarcJ : 0.521 /ms
testing with 7200 characters and repeating test:1000
ooString :0.541 /ms
mZynt :0.64 /ms
MarcJ : 0.471 /ms
testing with 72000 characters and repeating test:100
ooString :0.871 /ms
mZynt :1.262 /ms
MarcJ : 0.551 /ms
testing with 720000 characters and repeating test:10
ooString :1.242 /ms
mZynt :1.322 /ms
MarcJ : 0.881 /ms

sorry mBravenBoer, maar jouw code wat echt te traag voor 72000 characters...

[ Voor 51% gewijzigd door Marcj op 10-03-2003 11:32 ]

[Marcj]

Java:

public class Algoritm {
    public static char[] replace(char[] aSource, String aOld, String aNew)
    {
        final int tSourceLength = aSource.length;
        if(tSourceLength == 0)  //Zonder source doen we niks natuurlijk...
            return aSource;
            
        final int tOldStringLength = aOld.length();
        if(tOldStringLength == 0)   //En ook niet als er niks te vervangen is
            return aSource;
            
        final int tNewStringLength = aNew.length();
        final char[] tOld = aOld.toCharArray();
        final char[] tNew = aNew.toCharArray();
        
        final int[] tFound = find(aSource, tOld);   //Vind alle plaatsen waar je de string moet vervangen
        final int tFoundLength = tFound.length;
        
        int index = 0;
        int sourcePos = 0;
        int resultPos = 0;
        int length;
        char[] result = new char[(tSourceLength + (tFoundLength * (tNewStringLength - tOldStringLength)))]; //Dit is het resultaat met de juiste grootte
        while(index < tFoundLength) //Loop door alle plaatsen heen waar je wat moet vervangen
        {
            length = tFound[index]-sourcePos;   //Lengte van het stukje dat uit het origineel moet gekopiëerd worden
            System.arraycopy(aSource, sourcePos, result, resultPos, length);    //En kopiëer dat
            resultPos += length;    //De positie in de resultaatstring gaat met die lengte omhoog
            sourcePos += length + tOldStringLength; //En de positie in de sourcestring gaat met de lengthe plus het te vervangen omhoog
            System.arraycopy(tNew, 0, result, resultPos, tNewStringLength); //Plaats daarna op de juiste plaat de nieuwe string
            resultPos += tNewStringLength;  //En verhoog de positie van de resultaatstring weer.
            index++;
        }
        System.arraycopy(aSource, sourcePos, result, resultPos, result.length-resultPos);   //Voeg de rest aan het eind toe
        
        return result;
    }
    
    public static int[] find(char[] aSource, char[] aFind)
    {
        final int tSourceLength = aSource.length;
        if(tSourceLength == 0)
            return new int[0];
            
        final int tFindLength = aFind.length;
        if(tFindLength == 0)
            return new int[0];
        
        int index = 0;
        int[] temp = new int[(tSourceLength/tFindLength)];  //Het maximaal aantal te vinden keer is 
                                                                //de lengte van de source gedeelt door de lengte van het te vinden
        int nrFound = 0;
        
        while(index < tSourceLength)        //Doorzoek de hele sourceString
        {
            if((aSource[index] == aFind[0]) && (isFound(aSource, index+1, aFind, 1)) )  //Als het eerste teken overeenkomt, en de rest ook
            {
                temp[nrFound++] = index;    //Dan hebben we hier eentje gevonden
                index += tFindLength;
            }
            else
                index++;        //Anders zoeken we de volgende
        }
        
        int[] result = new int[nrFound];    //Het resultaat is kleiner dan temp, tenminste meestal ;)
        System.arraycopy(temp, 0, result, 0, nrFound);
        
        return result;
    }

    private static boolean isFound(char[] aSource, int index, char[] aFind, int findIndex)
    {
        if(findIndex >= aFind.length)   //Als de index als gelijk of groter is dan de lengte, dan zitten we erdoorheen
            return true;                //Dus kunnen we true terug geven.
        
        if(index >= aSource.length) //Als we door de source heen zijn, dan geven we false
            return false;
        
        if(aSource[index] == aFind[findIndex])  //Als het huidige teken van de source gelijk is aan die van de zoekstring
            return isFound(aSource, index+1, aFind, findIndex+1);   //Dan vragen we recursief de volgende aan. Tot het eind...
        else
            return false;       //Is die niet gelijk, dan returnen we false.
    }
}
            
        

veel beter krijg ik hem niet...

[B-Man]

Mijn bottleneck zit in ieder geval niet meer in de content, maar nu (weer) in de database driver.

Soms duurt het wel 14-20 ms voordat ik een reactie heb van mijn db. Ik heb de indruk dat het in de socket implementatie zit... Ik lees m.b.v. een BufferedInputStream gehele MySQL packets uit... Soms gaat het in 2ms, maar soms duurt het dus veel te lang...

Per e-mail moet ik drie keer de database in (gegevens uitlezen, en vervolgens wachtrij aanpassen en datatraffic wegschrijven).

Wie tijd heeft kan er naar kijken: http://www.iswd.nl/got/db.zip (Dit is mijn MySQL driver, werkt enkel met ResultSets die Int en String teruggeven, leest alle data in een keer in een byte array. Ondersteund ook al automatische reconnect).

Eerst mijn socket snelheid omhoog, dan ga ik verder met de replace.

Voorbeeld uit log file:

code:

10 Mrz 2003 12:57:45,397 [W1  ] INFO  - Processing job 4 / 5
10 Mrz 2003 12:57:45,397 [W1  ] DEBUG - Getting batch from DataStore
10 Mrz 2003 12:57:45,397 [W1  ] DEBUG - Getting additional job data
10 Mrz 2003 12:57:45,400 [W1  ] DEBUG - Generate e-mail
10 Mrz 2003 12:57:45,401 [W1  ] DEBUG - texts appended
10 Mrz 2003 12:57:45,401 [W1  ] DEBUG - fields replaced
10 Mrz 2003 12:57:45,401 [W1  ] DEBUG - Dispatching e-mail
10 Mrz 2003 12:57:45,402 [W1  ] DEBUG - Dispatch start
10 Mrz 2003 12:57:45,402 [W1  ] DEBUG - Message generated
10 Mrz 2003 12:57:45,403 [W1  ] DEBUG - Dispatched e-mail
10 Mrz 2003 12:57:45,403 [W1  ] DEBUG - in JobServer.job_done
10 Mrz 2003 12:57:45,405 [W1  ] DEBUG - bandwidth updated
10 Mrz 2003 12:57:45,406 [W1  ] DEBUG - removeJobByField
10 Mrz 2003 12:57:45,418 [W1  ] DEBUG - query done
10 Mrz 2003 12:57:45,418 [W1  ] DEBUG - removed job from the queue
10 Mrz 2003 12:57:45,421 [W1  ] DEBUG - updated subscription
10 Mrz 2003 12:57:45,421 [W1  ] INFO  - Job done, time: 24 ms
10 Mrz 2003 12:57:45,421 [W1  ] INFO  - Processing job 5 / 5
10 Mrz 2003 12:57:45,421 [W1  ] DEBUG - Getting batch from DataStore
10 Mrz 2003 12:57:45,422 [W1  ] DEBUG - Getting additional job data
10 Mrz 2003 12:57:45,425 [W1  ] DEBUG - Generate e-mail
10 Mrz 2003 12:57:45,425 [W1  ] DEBUG - texts appended
10 Mrz 2003 12:57:45,425 [W1  ] DEBUG - fields replaced
10 Mrz 2003 12:57:45,463 [W1  ] DEBUG - Dispatching e-mail
10 Mrz 2003 12:57:45,463 [W1  ] DEBUG - Dispatch start
10 Mrz 2003 12:57:45,465 [W1  ] DEBUG - Message generated
10 Mrz 2003 12:57:45,465 [W1  ] DEBUG - Dispatched e-mail
10 Mrz 2003 12:57:45,465 [W1  ] DEBUG - in JobServer.job_done
10 Mrz 2003 12:57:45,485 [W1  ] DEBUG - bandwidth updated
10 Mrz 2003 12:57:45,485 [W1  ] DEBUG - removeJobByField
10 Mrz 2003 12:57:45,499 [W1  ] DEBUG - query done
10 Mrz 2003 12:57:45,499 [W1  ] DEBUG - removed job from the queue
10 Mrz 2003 12:57:45,501 [W1  ] DEBUG - updated subscription
10 Mrz 2003 12:57:45,501 [W1  ] INFO  - Job done, time: 80 ms

[.oisyn]

Marcj: je kunt je find routine nog zwaar optimalizeren door steeds de achterste char van find te vergelijken. Als die char niet in source voorkomt, kun je gelijk met find.length () stappen vooruit springen.

Komt ie er wel in voor, dan moet je kijken hoeveel plaatsen je terug moet springen naar een mogelijk begin van find. Hiervoor kun je natuurlijk van tevoren een opzoektabelletje maken.

Dit algoritme heeft ook een naam, maar ik weet bij god niet hoe die luidt


.edit: voorbeeld erbij
find = "blaat"
source = "hallo hier staat blaat en blaat en nog een blaat"

find.length () = 5
tabel:
'b' -> 0
'l' -> 1
'a' -> 2, 3
't' -> 4

je begint dus te controleren bij de 5e char (positie 4 dus). Dat is een 'o'. Een o staat niet in de tabel, dus je kunt er zeker van zijn dat in de eerste 5 chars geen "blaat" voorkomt. Je schuift dus 5 plaatsen op (naar positie 9). Hier staat een 'r', die ook niet in de tabel staat, dus weer 5 plaatsen opschuiven (naar 14). Hier staat een 'a'. Heej, die staat in de tabel, met een waarde van 2 en 3. Mogelijkerwijs begint find dus op 2 of 3 plaatsen terug. Op positie 11 (3 plaatsen terug) staat een 't'. Deze is niet gelijk aan de 'b', dus hier kan find niet beginnen. Op positie 12 staat wederom geen 'b'. Er kan dus weer 5 plaatsen vooruit worden geschoven, naar plaats 19.

Wederom staat daar een 'a'. 3 Plaatsen terug staat geen 'b', maar 2 plaatsen terug wel. Je controleert vanaf die 'b' de rest van de string, en als die overeen komt heb je een blaat gevonden. Je gaat dan weer verder bij 1 positie na "blaat", op plaats 22 dus. En dit herhaal je tot je voorbij het eind van search bent.

Hier ga je in het best-case geval steeds met 5 stappen vooruit, terwijl je in jouw algoritme slechts 1 stap vooruit gaat. Het levert dan ook een behoorlijke snelheidswinst op

.edit2: dit algoritme is trouwens nog meer te optimalizeren (jaja ) door een kleine aanpassing te maken. In mijn vorige voorbeeld bewoog ik steeds terug als er een char werd gevonden die in find stond. Je kunt natuurlijk ook vooruit bewegen en dan gewoon weer die char controleren als elke andere. Dit scheelt een stuk code, en ook hoeft er maar 1 waarde per char in de tabel te staan.

De tabel wordt dan zoiets:
'b' -> CHECK^*
'l' -> 3
'a' -> 1
't' -> -4

* CHECK is een special case (in principe gewoon een waarde die je nooit gaat gebruiken, zoals 0x80000000 ofzo), als deze wordt gevonden dan moet vanaf hier het hele woord worden vergeleken. Het algoritme wordt dan vrij simpel. Je begint wederom bij de laatste char van find. Staat deze char niet in de tabel, dan gewoon find.length () chars vooruit gaan. Staat ie wel in de tabel, dan de waarde die daarbij hoort optellen bij de vorige positie en verder gaan. Is deze waarde echter CHECK, dan gewoon het hele stuk vergelijken met find. Komt ie niet overeen, dan weer find.length () plaatsen vooruit bewegen

in pseudo-code:

Java:

int[] find (String source, String find)
{
    int[65536] tabel;
    int[] result;
    int len = find.length ();
    int total = source.length ();

    tabel[find[0]] = CHECK;
    tabel[find[len - 1]] = -len + 1;
    for (int i = 1; i < len - 1; i++)
        tabel[find[i]] = len - i - 1;

    int index = len - 1;

    while (index < total)
    {
        int p = tabel[search[index]];
        if (p == 0)
            index += len;
        else if (p != CHECK)
            index += p;
        else
        {
            if (match (search, find, index, len))
                result.add (index);
            index += len;
        }
    }

    return result;
}

boolean match (String search, String find, int index, int len)
{
    for (int i = 0; i < len; i++)
        if (search[index + i] != find[i])
            return false;
    return true;
}

vrij simpel algo, maar erg effectief

[ Voor 102% gewijzigd door .oisyn op 10-03-2003 14:32 ]

[hobbit_be]

.oisyn : dat klinkt heel interessant! als mijn huidig project af is ga ik dat zekere implementeren . qua geheugen copy can het niet sneller dan bMan-Onno. (aangezien daar geen enkele byte teveel wordt gebruikt). Maar door B-man's post met firstChar quick bail bleek dat de search idd nog sneller kon. Jouw algorithme zal op een bepaald punt (voor een bepaalde search lengte) meer efficient zijn. Maar 1 nadeel per last char is dat je steeds moet zoeken in je LUT: je kan natuurlijk alles in een bucketsoort gooien per character type maar als je dan met Unicode begint (een 64000 clear in het begin van search? of een addmax zdepth trick zelfs . Alles hangt af van hoe de search eruit ziet en je origineel. Dat is alleen uit te maken uit een heel hoop tests met 'standaard' data-sets.

Marcj: ook mooi maar je search (find) is een heel pak minder effeicient dan BManOnnoReplace en ook niet altijd nodig. Mocht je gelukkig de tijd hebben zou ik .oisyns methode is proberen te implementeren. Als die sneller blijkt te zijn (best-case) dan stoppen we hem ook in de dan BManOnnoMarcjOisynZynt.Replace

[Dezjay]

Ach ja, ik probeerde gewoon een simpeler algoritme dan die ik hier allemaal zag staan. En het werkte al sneller dat de huidige. Maar optimalisaties zijn altijd welkom natuurlijk! Kunnen we ze combineren

edit: shit, arnold is hier nog ingelogd...

[ Voor 11% gewijzigd door Dezjay op 10-03-2003 15:03 ]

[B-Man]

hobbit: heb mijn functie wederom aangepast, nu gaan lange strings ook snel omdat ik nu enkel de data tussen tags "verschuif".

dkitTest output:

code:

Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 7
testing with 72 characters and repeating test:1
ooString  :0.0070 /ms
mZynt     :0.0010 /ms
B-Man     :0.0 /ms
B-Man New :0.0050 /ms
testing with 720 characters and repeating test:10000
ooString  :0.744 /ms
mZynt     :0.946 /ms
B-Man     :0.362 /ms
B-Man New :0.36 /ms
testing with 7200 characters and repeating test:1000
ooString  :0.758 /ms
mZynt     :0.942 /ms
B-Man     :0.352 /ms
B-Man New :0.352 /ms
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4
testing with 72 characters and repeating test:1
ooString  :0.0 /ms
mZynt     :0.0010 /ms
B-Man     :0.0 /ms
B-Man New :0.0 /ms
testing with 720 characters and repeating test:10000
ooString  :0.912 /ms
mZynt     :0.841 /ms
B-Man     :0.752 /ms
B-Man New :0.666 /ms
testing with 7200 characters and repeating test:1000
ooString  :0.923 /ms
mZynt     :0.874 /ms
B-Man     :2.344 /ms
B-Man New :0.688 /ms
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12
testing with 72 characters and repeating test:1
ooString  :0.0 /ms
mZynt     :0.0 /ms
B-Man     :0.0 /ms
B-Man New :0.0 /ms
testing with 720 characters and repeating test:10000
ooString  :0.983 /ms
mZynt     :1.253 /ms
B-Man     :0.86 /ms
B-Man New :0.722 /ms
testing with 7200 characters and repeating test:1000
ooString  :1.047 /ms
mZynt     :1.354 /ms
B-Man     :1.987 /ms
B-Man New :0.758 /ms

Waarin B-Man New mijn nieuwe functie is.

[B-Man]

De functie:

Java:

public static char[] replace(char []orig_in, String from, String to) {
        
        int fromLength = from.length();

        if (fromLength == 0)
            throw new IllegalArgumentException("String to be replaced must not be empty");

        if (from.equals(to)) return orig_in;
        
        // Start replace
        
        int diff = to.length() - from.length();
        //int tMax = buffer.getLength()-from.length()+1;
        int tMax = orig_in.length-from.length()+1;
        int toLength = to.length();

        char []out;
        char[] fromC = from.toCharArray();
        char[] toC = to.toCharArray();
        int hits = 0, cp; // cp = Corrected Position
        int cl = orig_in.length;    // current length
        int ol = cl,size=0,h=0;     // original length
        
        if(diff != 0) {
            first:for(int i=0;i<tMax;i++) {
                if(orig_in[i]!=fromC[0]) continue;
                
                for(int j=0;j<fromLength;j++)
                    if(orig_in[i+j]!=fromC[j]) continue first;
                h++;
            }
            
            if(h<=0) {
                return orig_in;
            } else {
                out = new char[cl+(h*diff)];
                cl = out.length;
            }
        } else {
            // Create array of same size, simply copy
            //out = new char[orig_in.length];
            //System.arraycopy(orig_in, 0, out, 0, orig_in.length);
            out = orig_in;
        }
        
        int lhe = 0; // last hit end
        int po = 0, poTag = 0; // pos out
                
        first:for(int i=0;i<tMax;i++) {
            if(orig_in[i]!=fromC[0]) continue;
            
            for(int j=0;j<fromLength;j++)
                if(orig_in[i+j]!=fromC[j]) continue first;
                
            // hit!
            
            if(diff != 0 && hits==0 && i > 0) {// before first
                System.arraycopy(orig_in, 0, out, 0, i);
                poTag = i; po = i;
            }
            
            if(diff!=0 && lhe > 0) { // Between this one and prev
                size = i-lhe-1;
                System.arraycopy(orig_in, lhe+1, out, po, size);
                poTag += size;
                po += size;
            }
            
            // Now replace tag
            to.getChars(0, toLength, out, poTag);
            po += toLength;
            poTag += toLength;
            
            lhe = i + fromLength-1;
            i += fromLength-1;
            
            hits++;         
        }
        
        if(diff!=0) // Copy all after last tag          
            System.arraycopy(orig_in, lhe+1, out, po, orig_in.length-lhe-1);
        
        return out;
    }

Ik zit overigens ook nog met het socket-verhaal dat ik eerder meldde, heeft iemand tijd om eens naar mijn MySQL driver code te kijken? Heb een link wat eerder op pagina 5 gepost.

[.oisyn]

kun je de java-code van het algo dat ik voordroeg eens posten? Iets zegt me namelijk dat je het niet zo handig geimplementeerd hebt

[hobbit_be]

B-Man: las New = Old dan werkt de laatste replace van jouw niet meer... sorry...

edit:

New > Old
testing with 72000 characters and repeating test:100
ooString : 1.36 /ms
B-Man Final: 2.062 /ms
BMan - Onno: 1.578 /ms //???strange

maar eindelijk wel een 'level 4' pass < 3 minuten

.oisyn:
jouw algorithme heeft me wel op een ideetje gebracht zonder de Table. gewoon van achter naar voor scannen zou idd nog een pak snaller kunnen zijn door de extra jumps die kunnen.

ook de table implementatie zou ik graag testen: alles draait em nu enkel en alleen voor de 'indexOf' deel, de rest kan echt niet sneller.

arggh geen tijd en er kunnen nog ms af!!! . BTW ook de indexof van String zelf is een while loop...

[ Voor 81% gewijzigd door hobbit_be op 10-03-2003 16:30 ]

[B-Man]

hobbit: met onderstaande functie kan ik al je tests (je dkitTest class) in alle gevallen succesvol doorlopen (old=new, old>new, old<new).

Nu overigens nog wat geoptimaliseerd, en ik doorloop de buffer nu maar eenmaal (snel!). Tevens iets van .oisyn toegevoegd.

Java:

private static int []locs = new int[16000];
    
    public static char[] replace(char []orig_in, String from, String to) {
        
        int fromLength = from.length();

        if (fromLength == 0)
            throw new IllegalArgumentException("String to be replaced must not be empty");

        if (from.equals(to)) return orig_in;
        
        // Start replace
        
        int diff = to.length() - from.length();
        int tMax = orig_in.length-from.length()+1;
        int toLength = to.length();

        char []out;
        char[] fromC = from.toCharArray();
        int hits = 0, cp; // cp = Corrected Position
        int size=0,h=0;     // original length
        int end = fromLength-1;
        
        if(diff != 0) {
            first:for(int i=0;i<tMax;i++) {
                if(orig_in[i]!=fromC[0]) continue;
                if(orig_in[i+end]!=fromC[end]) continue;
                
                for(int j=0;j<fromLength;j++)
                    if(orig_in[i+j]!=fromC[j]) continue first;
                locs[h++]=i;
                i+=fromLength-1;
            }
            
            if(h<=0) {
                return orig_in;
            } else {
                out = new char[orig_in.length+(h*diff)];
            }
        } else {
            // Create array of same size, simply copy
            //out = new char[orig_in.length];
            //System.arraycopy(orig_in, 0, out, 0, orig_in.length);
            out = orig_in;
        }
        
        int lhe = 0; // last hit end
        int po = 0; // pos out
                
        /*
        first:for(int i=0;i<tMax;i++) {
            if(orig_in[i]!=fromC[0]) continue;
            if(orig_in[i+end]!=fromC[end]) continue;
            
            for(int j=0;j<fromLength;j++)
                if(orig_in[i+j]!=fromC[j]) continue first;
                
            // hit!
            
            if(diff!=0 && i > 0) {
                if(hits==0) { // before first
                    System.arraycopy(orig_in, 0, out, 0, i);
                    po = i;
                } else if(lhe > 0 && (i-lhe>1)) { // Between this one and prev
                    size = i-lhe-1;
                    System.arraycopy(orig_in, lhe+1, out, po, size);
                    po += size;
                }
            }
            
            // Now replace tag
            to.getChars(0, toLength, out, po);
            po += toLength;
            
            i += fromLength-1;
            lhe = i;
            
            hits++;
        }
        */
        for(int i=0;i<h;i++) {
            if(diff!=0 && locs[i] > 0) {
                if(i==0) { // before first
                    System.arraycopy(orig_in, 0, out, 0, locs[i]);
                    po = locs[i];
                } else if(locs[i]-(locs[i-1]+fromLength)>0) { // Between this one and prev
                    size = locs[i]-lhe-1;
                    System.arraycopy(orig_in, lhe+1, out, po, size);
                    po += size;
                }
            }
            
            // Now replace tag
            to.getChars(0, toLength, out, po);
            po += toLength;
            
            //i += fromLength-1;
            lhe = locs[i]+fromLength-1;
        }
        
        if(diff!=0) // Copy all after last tag          
            System.arraycopy(orig_in, lhe+1, out, po, orig_in.length-lhe-1);
        
        return out;
    }

[B-Man]

Output met bovenstaande functie:

oldlen = newlen:

code:

Size Of Old: 7
Size Of New: 7
testing with 72 characters and repeating test:1
ooString  :0.0 /ms
mZynt     :0.0 /ms
B-Man     :0.0 /ms
B-Man New :0.0010 /ms
testing with 720 characters and repeating test:10000
ooString  :1.256 /ms
mZynt     :1.271 /ms
B-Man     :0.548 /ms
B-Man New :0.245 /ms
testing with 7200 characters and repeating test:1000
ooString  :0.581 /ms
mZynt     :0.636 /ms
B-Man     :0.304 /ms
B-Man New :0.137 /ms

oldlen < newlen:

code:

Size Of Old: 7
Size Of New: 4
testing with 72 characters and repeating test:1
ooString  :0.0020 /ms
mZynt     :0.0 /ms
B-Man     :0.0 /ms
B-Man New :0.0010 /ms
testing with 720 characters and repeating test:10000
ooString  :0.772 /ms
mZynt     :0.584 /ms
B-Man     :0.607 /ms
B-Man New :0.502 /ms
testing with 7200 characters and repeating test:1000
ooString  :0.686 /ms
mZynt     :0.642 /ms
B-Man     :2.209 /ms
B-Man New :0.391 /ms

oldlen < newlen:

code:

Size Of Old: 7
Size Of New: 12
testing with 72 characters and repeating test:1
ooString  :0.0010 /ms
mZynt     :0.0 /ms
B-Man     :0.0 /ms
B-Man New :0.0 /ms
testing with 720 characters and repeating test:10000
ooString  :0.663 /ms
mZynt     :1.078 /ms
B-Man     :0.704 /ms
B-Man New :0.395 /ms
testing with 7200 characters and repeating test:1000
ooString  :0.712 /ms
mZynt     :0.948 /ms
B-Man     :2.178 /ms
B-Man New :0.445 /ms

Ik snap niet waarom het bij jou niet goed gaat, en bij mij wel?

[.oisyn]

hobbit_be schreef op 10 March 2003 @ 16:25:
.oisyn:
jouw algorithme heeft me wel op een ideetje gebracht zonder de Table. gewoon van achter naar voor scannen zou idd nog een pak snaller kunnen zijn door de extra jumps die kunnen.

let wel dat van achteren naar voren lopen een negatief effect heeft ivm cache-misses

[hobbit_be]

yo B-Man je kan dkitTest wel doorlopen idd maar als new=old dan moet je effe VISUEEL controleren of het result correct is en dat is in dat geval niet (weet niet met jouw nieuwe code).

Maar goed zoals vermeld is het dus niet meer een questie van copy's maar van zoeken waar een match zit. heb dus effe een nieuwe test geschreven en die kijkt ALLEEN naar find hits methode.

Results:
----------------------------------------------
Size Of Old: 7 / Size Of New: 4
testing with 720 characters and repeating test:10000
BMan 0.36 /ms, Found 300000 Matches
Onno 0.25 /ms, Found 300000 Matches
testing with 7200 characters and repeating test:1000
BMan 0.359 /ms, Found 300000 Matches
Onno 0.204 /ms, Found 300000 Matches
testing with 72000 characters and repeating test:100
BMan 0.406 /ms, Found 300000 Matches
Onno 0.25 /ms, Found 300000 Matches
----------------------------------------------
Size Of Old: 7 / Size Of New: 7
testing with 720 characters and repeating test:10000
BMan 0.328 /ms, Found 300000 Matches
Onno 0.219 /ms, Found 300000 Matches
testing with 7200 characters and repeating test:1000
BMan 0.343 /ms, Found 300000 Matches
Onno 0.219 /ms, Found 300000 Matches
testing with 72000 characters and repeating test:100
BMan 0.406 /ms, Found 300000 Matches
Onno 0.282 /ms, Found 300000 Matches
----------------------------------------------
Size Of Old: 7 / Size Of New: 12
testing with 720 characters and repeating test:10000
BMan 0.343 /ms, Found 300000 Matches
Onno 0.203 /ms, Found 300000 Matches
testing with 7200 characters and repeating test:1000
BMan 0.36 /ms, Found 300000 Matches
Onno 0.234 /ms, Found 300000 Matches
testing with 72000 characters and repeating test:100
BMan 0.422 /ms, Found 300000 Matches
Onno 0.281 /ms, Found 300000 Matches

edit:
[effe oisyn's syntaxer beproeven ;]

bovenstaand met volgende code...

Java:

 public int findMatchesBMan(char[] aOriginal, char[] aFrom, char[] aTo)
    {
        final int tFromLength = aFrom.length;
        final int tToLength = aTo.length;
        final int tMaxIndex = aOriginal.length - tFromLength + 1;
        int tHits = 0;

        final char tFirst = aFrom[0];
        int i = 0;
        int j;
        final int end = tFromLength - 1;
        final char tLast = aFrom[end];
        first:for (; i < tMaxIndex; i++)
        {

            if (aOriginal[i] != tFirst)
            {
                continue;
            }

            if (aOriginal[i + end] != tLast)
            {
                continue;
            }

            for (j = 0; j < tFromLength; j++)
            {
                if (aOriginal[i + j] != aFrom[j])
                {
                    continue first;
                }
            }
            tHits++;
        }
        return tHits;
    }

    public int findMatchesOnno(char[] aOriginal, char[] aFrom, char[] aTo)
    {
        final int tFromLength = aFrom.length;
        final int tToLength = aTo.length;
        final int tMaxIndex = aOriginal.length - tFromLength + 1;
        int tHits = 0;

        final char tFirst = aFrom[0];
        int tIndex = 0;
        int tSearchIndex;

        nextChar:while (tIndex < tMaxIndex) //ugly ? yes but nice :)
        {
            if (aOriginal[tIndex++] != tFirst)
            {
                continue;
            }
            tSearchIndex = 1; //restart search
            while (tSearchIndex < tFromLength)
            {
                if (aOriginal[tIndex++] != aFrom[tSearchIndex++]) //is ++Int faster???
                {
                    continue nextChar; //restart search
                }
            }
            tHits++;
        }
        return tHits;
    }

dus hier heb ik de gewoon de search loops uitgehaald de string wordt NIET veranderd en is dus een find hits's. (met jouw laatste versie die ik trouwens ook nog wat heb geoptimaliseerd ivm temp vars etc...)

[ Voor 35% gewijzigd door hobbit_be op 10-03-2003 17:29 ]

[B-Man]

hobbit: pfff. de vermoeidheid slaat toe Al een paar nachten kort geslapen, en dan begin in over dingen heen te lezen. Als newlen=oldlen werd er niets vervangen... Gaat nu wel goed ;-)

[hobbit_be]

ken het wel dude... ik had eigenlijk een simple .equals moeten doen

.oisyn: ik wou effe jouw code implementeren maar ik heb al direct een probleem:

stel replace "bob" met iets... jouw code geeft dan als tabel

"b" : -2
"o" : 1

maw hij zou never stoppen... of zie ik iets over het hoofd?

[B-Man]

hobbit: heb je toevallig al een blik geworpen op mijn db driver?

[hobbit_be]

B-Man: nope en ga ik eerlijk gezegd ook niet doen tenzij ik mijn deadline voor vrijdag vroeger af heb (unlikely ... daarna wil ik zeker is naar pluizen. ALs mijn baas wist dat ik vandaag bijna alleen wat benchmarks en replaces zit te maken...

[B-Man]

haha... dan heb ik een groot voordeel: ben eigen baas (daarnaast overigens ook student, en had nu eigenlijk tentamen-voorbereid-tijd gepland, maar ja, sommige dingen kan ik gewoon niet laten )

Ik heb mijn MySQL IO driver overigens weer iets sneller door alleen een ResultSet te creeeren indien er een select query wordt uitgevoerd, en dat scheelt weer wat tijd. Het duurt me nog steeds te lang...

Het lijkt erop dat de socket implementatie van Java bepaalde instellingen nodig heeft of zo, aangezien de celeron waarop ik test (een 1200MHz met 256 MB ram) bij een bulk test maar voor < 20% belast wordt, maar dat ik soms toch 20ms op socket input moet wachten...

PS lachen man, we hebben toch een aardig snelle string replace in elkaar gedraaid

[Marcj]

.oisyn schreef op 10 March 2003 @ 13:30:
Marcj: je kunt je find routine nog zwaar optimalizeren door steeds de achterste char van find te vergelijken. Als die char niet in source voorkomt, kun je gelijk met find.length () stappen vooruit springen.

Komt ie er wel in voor, dan moet je kijken hoeveel plaatsen je terug moet springen naar een mogelijk begin van find. Hiervoor kun je natuurlijk van tevoren een opzoektabelletje maken.

Dit algoritme heeft ook een naam, maar ik weet bij god niet hoe die luidt

Ik ben nu ff bezig geweest met jouw implementatie, maar ik krijg hem niet sneller dan die van mij. Ik snap wel wat je bedoelt, maar die tabel vertraagt de boel weer zodanig dat je je hele snelheidswinst kwijt bent. Uiteindelijk is hij zelfs nog trager.

Je tweede oplossing zou in principe een stuk sneller moeten zijn, maar het gaat niet altijd even goed. Als de eerste en laatste letter gelijk zijn, wat dan?
Ander voorbeeld:
aFind = "lepel"

l -> CHECK of toch -4?
e -> 1 of 2?
p -> 2!

Het gaat gewoon niet altijd werken...

edit: zit ff te denken, kan het niet beter zo??
l -> CHECK
e -> -1 (laagste getal die naar CHECK wijst)
p -> -2

Maar nu zit ik nog te denken hoe ik die laatste letter ga oplossen...

[ Voor 9% gewijzigd door Marcj op 11-03-2003 11:29 ]

[Marcj]

YES! Het werkt.. en nog verdomte snel ook

code:

validating replace:
ooString Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
mBravenBoer Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
Zynt Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
MarcJ Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
B-Man Result: 
OOPS.in this OOPS, a loop nestedunderneath in another loop.OOPS
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4
testing with 72 characters and repeating test:1
MarcJ : 0.0 /ms
MarcJ Oud: 0.0 /ms
B-Man : 0.0 /ms
testing with 720 characters and repeating test:10000
MarcJ : 0.431 /ms
MarcJ Oud: 0.461 /ms
B-Man : 0.41 /ms
testing with 7200 characters and repeating test:1000
MarcJ : 0.351 /ms
MarcJ Oud: 0.43 /ms
B-Man : 0.391 /ms
testing with 72000 characters and repeating test:100
MarcJ : 0.521 /ms
MarcJ Oud: 0.57 /ms
B-Man : 0.661 /ms
testing with 720000 characters and repeating test:10
MarcJ : 0.782 /ms
MarcJ Oud: 0.851 /ms
B-Man : 0.811 /ms
Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12
testing with 72 characters and repeating test:1
MarcJ : 0.0 /ms
MarcJ Oud: 0.0 /ms
B-Man : 0.0 /ms
testing with 720 characters and repeating test:10000
MarcJ : 0.421 /ms
MarcJ Oud: 0.49 /ms
B-Man : 0.421 /ms
testing with 7200 characters and repeating test:1000
MarcJ : 0.37 /ms
MarcJ Oud: 0.451 /ms
B-Man : 0.411 /ms
testing with 72000 characters and repeating test:100
MarcJ : 0.591 /ms
MarcJ Oud: 0.661 /ms
B-Man : 0.63 /ms
testing with 720000 characters and repeating test:10
MarcJ : 0.931 /ms
MarcJ Oud: 0.991 /ms
B-Man : 0.942 /ms

B-Man is zijn laatste algoritme.

de code:

Java:

public class Algoritm {
    public static char[] replace(char[] aSource, String aOld, String aNew)
    {
        final int tSourceLength = aSource.length;
        if(tSourceLength == 0)  //Zonder source doen we niks natuurlijk...
            return aSource;
            
        final int tOldStringLength = aOld.length();
        if(tOldStringLength == 0)   //En ook niet als er niks te vervangen is
            return aSource;
            
        final int tNewStringLength = aNew.length();
        final char[] tOld = aOld.toCharArray();
        final char[] tNew = aNew.toCharArray();
        
        final int[] tFound = findFast(aSource, tOld);
            //Vind alle plaatsen waar je de string moet vervangen
        final int tFoundLength = tFound.length;
        
        int index = 0;
        int sourcePos = 0;
        int resultPos = 0;
        int length;
        char[] result = new char[(tSourceLength + (tFoundLength * (tNewStringLength - tOldStringLength)))];
            //Dit is het resultaat met de juiste grootte
        while(index < tFoundLength) //Loop door alle plaatsen heen waar je wat moet vervangen
        {
            length = tFound[index]-sourcePos;
                //Lengte van het stukje dat uit het origineel moet gekopiëerd worden
            System.arraycopy(aSource, sourcePos, result, resultPos, length);
                //En kopiëer dat
            resultPos += length;
                //De positie in de resultaatstring gaat met die lengte omhoog
            sourcePos += length + tOldStringLength;
                //En de positie in de sourcestring gaat met de lengthe plus het te vervangen omhoog
            System.arraycopy(tNew, 0, result, resultPos, tNewStringLength); 
                //Plaats daarna op de juiste plaat de nieuwe string
            resultPos += tNewStringLength;
                //En verhoog de positie van de resultaatstring weer.
            index++;
        }
        System.arraycopy(aSource, sourcePos, result, resultPos, result.length-resultPos);
            //Voeg de rest aan het eind toe
        
        return result;
    }
    
    private static int CHECK = 65535;
    
    public static int[] findFast(char[] aSource, char[] aFind)
    {
        final int tSourceLength = aSource.length;
        if(tSourceLength == 0)
            return new int[0];
            
        final int tFindLength = aFind.length;
        if(tFindLength == 0)
            return new int[0];
            
        //Maak een tabel
        int[] table = new int[256];
        table[(int)aFind[0]] = CHECK;
        for(int i = 1; i < tFindLength; i++)
        {
            if(table[(int)aFind[i]] == 0)
                table[(int)aFind[i]] = -i;
        }
                
        int index = tFindLength - 1;
        int[] temp = new int[(tSourceLength/tFindLength)];
            //Het maximaal aantal te vinden keer is 
            //de lengte van de source gedeelt door de lengte van het te vinden
        int nrFound = 0;
        
        while(index < tSourceLength)
        {
            int n = table[(int)aSource[index]];
            if(n == 0)
                index += tFindLength;
            else if(n == CHECK)
            {
                if(isFound(aSource, index+1, aFind, 1))
                {
                    temp[nrFound++] = index;
                    index += tFindLength;
                }
                else
                {
                    if(index != 0)
                        index--;
                    else
                        index += tFindLength;
                }
            }
            else
                index += n;
        }
        
        int[] result = new int[nrFound];    //Het resultaat is kleiner dan temp, tenminste meestal ;)
        System.arraycopy(temp, 0, result, 0, nrFound);
        
        return result;
    }       

    private static boolean isFound(char[] aSource, int index, char[] aFind, int findIndex)
    {
        int i = 0;
        while(i+findIndex < aFind.length)
        {
            if(index+i >= aSource.length)
                return false;
            if(aSource[index+i] != aFind[findIndex+i])
                return false;
            i++;
        }
        return true;
    }
}

[ Voor 2% gewijzigd door Marcj op 11-03-2003 12:19 . Reden: kleine verbetering, die nog geen milliseconde opleverd ;) ]

[B-Man]

Marcj: dit vind ik nou een van de mooie dingen aan Java. Het programmeert lekker, en er is veel ruimte voor optimalisatie! Ik zal zometeen eens in detail kijken naar je functies.

Wat overigens aan de testresultaten af te lezen is, is dat de verschillende nog marginaal zijn vergeleken met eerdere tests. Dit betekent vermoedelijk dat we het theoretische maximum van java aan het bereiken zijn

Ik zat gisteren een artikel te lezen over de nieuwe ByteBuffer en CharBuffer classes die in het nieuwe java.nio package zitten, native array, buiten de GC om. Ik las dat ze erg snel zijn, alleen de functie om een java array naar een nio buffer over te hevelen was volgens het artikel tergend traag.
Heeft een van jullie hier zelf al eens mee gewerkt?

[Verwijderd]

Misschien zie ik iets compleet over het hoofd, of test ik verkeerd, maar in deze test opstelling lijkt mijn implementatie 2 keer zo snel...

Java:

public class Test {
  private static final int ITERATIONS = 100000;

  public static final Comparator CMPR_DATE = new Comparator() {
    public int compare(Object o1, Object o2){
      return 0;
    }
  };



  public static void main(String[] args) {
    long start =  System.currentTimeMillis();
    for(int i = 0; i < ITERATIONS; ++i)
      replace("Een test String", "test", "nieuwe");

    double totalTime = (double)(System.currentTimeMillis() - start);
    System.out.println( "Average replace time: " + totalTime / (double) ITERATIONS);

    start =  System.currentTimeMillis();
    for(int i = 0; i < ITERATIONS; ++i)
      replace("Een test String".toCharArray(), "test", "nieuwe");

    totalTime = (double)(System.currentTimeMillis() - start);
    System.out.println( "Average replace time: " + totalTime / (double) ITERATIONS);



  }

  public static String replace(String source, String sequence, String replace){
    char[] sourceChars = source.toCharArray();
    char[] sequenceChars = sequence.toCharArray();
    char[] replaceChars = replace.toCharArray();
    int sequenceLength = sequenceChars.length;
    if(sourceChars.length == 0 || sequenceChars.length == 0 ||
       replaceChars.length == 0) return source;
    int[] replacePoints = new int[sourceChars.length / sequenceChars.length];

    int index = 0;
    for(int i = 0; i < sourceChars.length; ++i){
      if (equalsSequence(sourceChars, i, sequenceChars, 0, sequenceLength)) {
        replacePoints[index] = i;
        ++index;
        i += sequenceLength;
      }
    }

    if(index == 0)return source;


    int length = sourceChars.length +
        ((replaceChars.length - sequenceLength) * index);

    char[] outputChars = new char[length];



    int sourceCharPtr = 0;
    int outputCharPtr = 0;
    for(int i = 0; i < index; ++i){
      while(sourceCharPtr < replacePoints[i]){
        outputChars[outputCharPtr] = sourceChars[sourceCharPtr];
        ++outputCharPtr;
        ++sourceCharPtr;
      }

      for(int j = 0; j < replaceChars.length; ++j){
        outputChars[outputCharPtr] = replaceChars[j];
        ++outputCharPtr;
      }
      sourceCharPtr += sequenceLength;
    }

    while (sourceCharPtr < sourceChars.length) {
      outputChars[outputCharPtr] = sourceChars[sourceCharPtr];
      ++outputCharPtr;
      ++sourceCharPtr;
    }
    return new String(outputChars);
  }
/*
  public static void replace(char[] source, int offsetFirst, char[] replace,
                             int offsetSecond, int length){
    for( int i = 0; i < length; ++i)
      source[i + offsetFirst] = replace[i + offsetSecond];
  }
*/



  public static boolean equalsSequence(char[] first, int offsetFirst,
                                       char[] second, int offsetSecond,
                                       int length){    
    if(first.length - offsetFirst < length ||
       second.length - offsetSecond < length) return false;

    for( int i = 0; i < length; ++i ){
      if( first[i + offsetFirst] != second[i + offsetSecond])
        return false;
    }
    return true;
  }



  public static char[] replace(char[] aSource, String aOld, String aNew)
    {
        //implementatie even voor leesbaarheid verwijderd
    }

    private static int CHECK = 65535;

    public static int[] findFast(char[] aSource, char[] aFind)
    {
        //implementatie even voor leesbaarheid verwijderd
    }

    private static boolean isFound(char[] aSource, int index, char[] aFind, int findIndex)
    {
         //implementatie even voor leesbaarheid verwijderd
     }
}

[Verwijderd]

Ha ik merk nu dat als de String groter wordt, dat jullie implementatie snel terrein wint, en al heel snel sneller is...

[B-Man]

Onze functies schalen inderdaad door, zoals je in de laatste dkitTest uitvoer ziet, zelf gemakkelijk tot 720.000 chars.

[Marcj]

B-Man schreef op 11 March 2003 @ 12:47:
Marcj: dit vind ik nou een van de mooie dingen aan Java. Het programmeert lekker, en er is veel ruimte voor optimalisatie! Ik zal zometeen eens in detail kijken naar je functies.

Wat overigens aan de testresultaten af te lezen is, is dat de verschillende nog marginaal zijn vergeleken met eerdere tests. Dit betekent vermoedelijk dat we het theoretische maximum van java aan het bereiken zijn

Ik zat gisteren een artikel te lezen over de nieuwe ByteBuffer en CharBuffer classes die in het nieuwe java.nio package zitten, native array, buiten de GC om. Ik las dat ze erg snel zijn, alleen de functie om een java array naar een nio buffer over te hevelen was volgens het artikel tergend traag.
Heeft een van jullie hier zelf al eens mee gewerkt?

Geen ervaring mee, maar ik ben in mijn snelle find wel een fout tegengekomen. Je kunt hem vast laten lopen door bijvoorbeeld deze string te nemen:
"eeeeeeeeeeeeeee[test]"
Als ik nu [test] wil vervangen, ziet hij een 'e'. Dan denkt hij, ik moet 2 terug. Tot het begin, en dan gaat hij weer 6 vooruit, maar daarna direct weer 2 terug. Tot het begin.... snap je waar ik heen wil?
Hier kan ik zo 123 geen oplossing voor verzinnen..

edit:
Oplossing gevonden, maar deze check maakt hem zodanig trager dat m'n winst weer verloren is

[ Voor 5% gewijzigd door Marcj op 11-03-2003 13:06 ]

[Marcj]

Verwijderd schreef op 11 March 2003 @ 12:55:
Ha ik merk nu dat als de String groter wordt, dat jullie implementatie snel terrein wint, en al heel snel sneller is...

Klopt, jouw implementatie is een stuk sneller, omdat bij die van mij eerst een tabel aangemaakt wordt. Hier gaat een milliseconde verloren, maar die kan heel snel terug gewonnen worden als de string wat langer wordt. Ik bedoel, een string van 720.000 tekens doorlopen in 0,0891 seconden vindt ik vrij snel (heb nog een optimalisatie gevonden net...). Hoe snel doet die van jouw dat?

edit:
Zeg B-Man, ik zat al te kijken waarom jouw code zoveel sneller is dan die van mij als de lengte gelijk blijft, maar dan doet jouw code helemaal niets

[ Voor 12% gewijzigd door Marcj op 11-03-2003 13:09 ]

[B-Man]

marj: is inmiddels aangepast hoor Alleen heb ik de code nog niet gepost. Werd hier eerder al door hobbit op gewezen.

[B-Man]

Final version (voorlopig haha):

Java:

private static int []locs = new int[16000];
    
    public static char[] replace(char []orig_in, String from, String to) {
        
        int fromLength = from.length();

        if (fromLength == 0)
            throw new IllegalArgumentException("String to be replaced must not be empty");

        if (from.equals(to)) return orig_in;
        
        // Start replace
        
        int diff = to.length() - from.length();
        int tMax = orig_in.length-from.length()+1;
        int toLength = to.length();

        char []out;
        char[] fromC = from.toCharArray();
        int hits = 0, cp; // cp = Corrected Position
        int size=0,h=0;     // original length
        int end = fromLength-1, i;
        char fromCs = fromC[0];
        char fromCe = fromC[fromLength-1];
        
        first:for(i=0;i<tMax;i++) {
            if(orig_in[i]!=fromCs) continue;
            if(orig_in[i+end]!=fromCe) continue;
            
            for(int j=0;j<fromLength;j++)
                if(orig_in[i+j]!=fromC[j]) continue first;
            locs[h++]=i;
            i+=fromLength-1;
        }
        
        if(h<=0) {
            return orig_in;
        } else {
            if(diff==0) out = orig_in;
            else out = new char[orig_in.length+(h*diff)];
        }
        
        int lhe = 0; // last hit end
        int po = 0; // pos out
                
        for(i=0;i<h;i++) {
            if(diff!=0 && locs[i] > 0) {
                if(i==0) { // before first
                    System.arraycopy(orig_in, 0, out, 0, locs[i]);
                    po = locs[i];
                } else if(locs[i]-(locs[i-1]+fromLength)>0) { // Between this one and prev
                    size = locs[i]-lhe-1;
                    System.arraycopy(orig_in, lhe+1, out, po, size);
                    po += size;
                }
            }
            if(diff==0) po = locs[i];
            
            // Now replace tag
            to.getChars(0, toLength, out, po);
            po += toLength;
            
            //i += fromLength-1;
            lhe = locs[i]+fromLength-1;
        }
        
        if(diff!=0) // Copy all after last tag          
            System.arraycopy(orig_in, lhe+1, out, po, orig_in.length-lhe-1);
        
        return out;
    }

[Verwijderd]

Deze is bij kleine strings in ieder geval sneller, en bij grote strings lijkt hij ook iets sneller te zijn, hoewel ik niet de test met 720000 characters heb uitgevoerd.

maar er kunnen nog bugs in zitten, want daar heb ik nog niet op getest...
(ohja, en kijk even niet naar de functie naam, maar met zoveel replace functies moet je nou eenmaal ambiguiteit tegen gaan)

Java:

private static int match = 0;

  public static int[] findFaster(char[] source, char[] sequence){
    match = 0;

    int sequenceLength = sequence.length;
    int sourceLength = source.length;
    int sequenceLast = sequenceLength -1;
    int evalLength = source.length - sequenceLength + 1;
    if( sequenceLength > sourceLength ) return null;
    int[] replacePoints = new int[sourceLength/sequenceLength];
    int sourcePtr = sequenceLast;
    int sequencePtr = sequenceLast;

    while(sourcePtr < evalLength ){

      if( source[sourcePtr] == sequence[sequencePtr] ){
        if( sequencePtr > 0 ){
           --sourcePtr;
           --sequencePtr;
           continue;
        }
        else {
          replacePoints[match] = sourcePtr;
          ++match;
          sourcePtr += sequenceLength + sequenceLast;          
        }
      }
      else {
        while( sequencePtr > 0 ){
          if(source[sourcePtr] == sequence[sequencePtr]){
            sourcePtr -= sequencePtr;
            break;
          }
          --sequencePtr;
        }
      }
      sequencePtr = sequenceLast;
      sourcePtr += sequenceLast;
    }


    return replacePoints;
  }


  public static String replaceFaster(String source, String sequence, String replace){
      char[] sourceChars = source.toCharArray();
      char[] sequenceChars = sequence.toCharArray();
      char[] replaceChars = replace.toCharArray();
      int sequenceLength = sequenceChars.length;
      if(sourceChars.length == 0 || sequenceChars.length == 0 ||
         replaceChars.length == 0) return source;
      int[] replacePoints = findFaster(sourceChars, sequenceChars);


      if(match == 0 )return source;


      int length = sourceChars.length +
          ((replaceChars.length - sequenceLength) * match);

      char[] outputChars = new char[length];



      int sourceCharPtr = 0;
      int outputCharPtr = 0;
      for(int i = 0; i < match; ++i){
        while(sourceCharPtr < replacePoints[i]){
          outputChars[outputCharPtr] = sourceChars[sourceCharPtr];
          ++outputCharPtr;
          ++sourceCharPtr;
        }

        for(int j = 0; j < replaceChars.length; ++j){
          outputChars[outputCharPtr] = replaceChars[j];
          ++outputCharPtr;
        }
        sourceCharPtr += sequenceLength;
      }

      while (sourceCharPtr < sourceChars.length) {
        outputChars[outputCharPtr] = sourceChars[sourceCharPtr];
        ++outputCharPtr;
        ++sourceCharPtr;
      }
      return new String(outputChars);
    }

[hobbit_be]

yow nog even een paar laatste comments:

Ik had in de Final BManOnno implementatie nog 1 foutje die in sommige gevallen plaats had (per toeval ondekt toen ik Oisyn indexOf (of een derivant ervan) had geimplementeerd. Gelukkig deed het niet aan snelheid.

B-Man:Ik heb die versie van jouw deftig gecontroleerd en jouw check if last character != maakt het trager aangezien ie in feite gewoon een extra check is: je moet dus kiezen tussen een fisrt of last check maar niet beiden het verschil is niet fantastisch maar als we over ms spreken:). Ik zie nog steeds in jouw code een hoop dingen die ik al had verbeterd
(j mag beginnen van 1) en in jouw geval lopene tot (length -1) aangezieen je die al hebt vergeleken EN veel belangrijker is dat je de variable J buiten de loop moet zetten. Ook die toChar moet weg aangezien dat een dubbele method call is. Verder zou ik echt nog de drie gevallen scheiden vanwege een hoop extra overhead. Ook BManOnno search loop is nog altijd een pak sneller dan een For-loop. Ook jouw Locs resized niet wat tot ArrayOutOfIndex can leiden. Waarom is een from met 0 length een Illegal Argument? Nou goed. Je kiest waarschijnlijk voor compactere code iets wat ik begrijp.

MarcJ: het grote probleem van jouw code is de memory overhead in alle snelle oplossing wordt er geen byte teveel gecopiert en zeker geen dubbele. Dit verschil wordt vooral bij grote gevallen erg duidelijk (exponentieel terwijl Onno-Bman-Zynt linear zijn).

Oisyn: Ik heb een hybrid van jouw functie gemaakt aangezien de laatste (optimised approach simpelweg niet logisch is) de andere functie werkt wel maar is trager dan mijn oplossing waar voor elke eind character wordt gezien of ie wel of niet in zit met als gevolg dat ie soms idd ineens +len verder springt. Nu zoals te verwachten is in sommige gevallen die code sneller maar meestal alleen als de letters die in de from zitten weinig voorkomen in de rest van de string. Het is dus echt een mixed bag geval die volledig afhangt van het type van search etc etc. Het tijds verschil bij idealle omstandigheden is soms 200% sneller maar in de slechtse gevallen ( replace "aaa" in "aaaaaaaaaa" is is een heel pak trager. Om te zien of die dus echt sneller is zou er gewoon met 'echte' gevallen moeten gewerkt worden.

De laatste benchmarks aldus: alleen tussen B-mAn (final version (voorlopig haha)) en BmanOnno. Ik heb deze test nog x10 gedaan voor extra preciese.

de results zijn dus na 3.000.000 replaces

New < Old

testing with 720 characters and repeating test:100000
BMan: 7.953 /ms
Onno: 7.235 /ms

testing with 7200 characters and repeating test:10000
BMan: 8.032 /ms
Onno: 7.25 /ms

testing with 72000 characters and repeating test:1000
BMan: 15.875 /ms
Onno: 15.11 /ms

-----------------------------------------------------------------------------
NEW = OLD

testing with 720 characters and repeating test:100000
BMan: 5.766 /ms
Onno: 5.39 /ms

testing with 7200 characters and repeating test:10000
BMan: 5.813 /ms
Onno: 5.344 /ms

testing with 72000 characters and repeating test:1000
BMan: 7.797 /ms
Onno: 7.063 /ms

-----------------------------------------------------------------------------
NEW > OLD

testing with 720 characters and repeating test:100000
BMan: 8.375 /ms
Onno: 7.625 /ms

testing with 7200 characters and repeating test:10000
BMan: 8.719 /ms
Onno: 7.891 /ms

testing with 72000 characters and repeating test:1000
BMan: 17.219 /ms
Onno: 16.328 /ms

maw het enige verschil is in feite met het zoeken naar een 'match'. Oisyn's by deze dataset zit ertussen qua times.

Onno versie is als eerder gepost met 1 verschil (maar wel 3x)

Java:

if (aSource[tIndex] != tOld[tSearchIndex++])
{
    continue nextChar2; //restart search
}
++tIndex; 

het verschil met de vorige posts is aanzienlijk.

edit:
Marcj: ik wou ook die van jouw controleren maar deze is een String (String, String) replace die nooit sneller kan zijn dan een char[] (char[], char[])...

edit2:
heb effe de java.nio gaan zien maar die wrapt gewoon weer System.arraycopy en een char[] -> CharBuffer gebeurt maar lieft character per character...

[ Voor 7% gewijzigd door hobbit_be op 11-03-2003 15:12 ]

[Marcj]

hobbit_be schreef op 11 March 2003 @ 14:57:
MarcJ: het grote probleem van jouw code is de memory overhead in alle snelle oplossing wordt er geen byte teveel gecopiert en zeker geen dubbele. Dit verschil wordt vooral bij grote gevallen erg duidelijk (exponentieel terwijl Onno-Bman-Zynt linear zijn).

Euhmm.. ik snap je niet echt. Mijn code lijkt juist bij hele grote strings sneller te zijn. En kun je niet mijn code er ook ff bij testen? (of werkt hij niet goed?)

edit:
Je kunt er heen snel een String van maken hoor
String = String.valueOf(replace(String.toCharArray(), String, String));

[ Voor 12% gewijzigd door Marcj op 11-03-2003 15:16 ]

[hobbit_be]

Marcj: omdat je het request. ik heb je code aangepast om met char[] te werken

oh en je past de Validates NIET maw als er een replace op het einde staat vindt jouw code hem niet. de volgende results dus onder die voorwaarde. (per
test komt zo'n end-of 1x keer voor)


Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 4

testing with 720 characters and repeating test:10000
B-Man Final: 0.859 /ms
BMan - Onno: 0.766 /ms
MarkJ 0.843 /ms

testing with 7200 characters and repeating test:1000
B-Man Final: 0.828 /ms
BMan - Onno 0.734 /ms
MarkJ 0.859 /ms

testing with 72000 characters and repeating test:100
B-Man Final: 1.75 /ms
BMan - Onno 1.704 /ms
MarkJ 1.687 /ms !!

testing with 720000 characters and repeating test:10
B-Man Final: 1.516 /ms
BMan - Onno 1.406 /ms
MarkJ 1.656 /ms

Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 7

testing with 720 characters and repeating test:10000
B-Man Final: 0.578 /ms
BMan - Onno 0.547 /ms
MarkJ 0.875 /ms

testing with 7200 characters and repeating test:1000
B-Man Final: 0.594 /ms
BMan - Onno 0.531 /ms
MarkJ 0.953 /ms

testing with 72000 characters and repeating test:100
B-Man Final: 0.813 /ms
BMan - Onno 0.719 /ms
MarkJ 1.187 /ms

testing with 720000 characters and repeating test:10
B-Man Final: 1.0 /ms
BMan - Onno 0.922 /ms
MarkJ 1.531 /ms

Performing A Set Of Tests Depending On Search Size:
Size Of Old: 7
Size Of New: 12


testing with 720 characters and repeating test:10000
B-Man Final: 0.828 /ms
BMan - Onno 0.765 /ms
MarkJ 0.922 /ms

testing with 7200 characters and repeating test:1000
B-Man Final: 0.891 /ms
BMan - Onno 0.797 /ms
MarkJ 0.953 /ms

testing with 72000 characters and repeating test:100
B-Man Final: 1.515 /ms
BMan - Onno 1.485 /ms
MarkJ 1.625 /ms

testing with 720000 characters and repeating test:10
B-Man Final: 1.609 /ms
BMan - Onno 1.485 /ms
MarkJ 1.593 /ms

[Marcj]

Weet ik, er zitten nog wat bugs in ben ik achter gekomen. Ik heb al met wat andere testzinnen gewerkt waar mijn code helemaal op vast liep
Back to the drawing board..

edit: m'n eerste code is volgens mij nog steeds mijn snelste altijdwerkende code

[ Voor 21% gewijzigd door Marcj op 11-03-2003 15:39 ]

[B-Man]

Toch lachen 720.000 karakters, 10x, in ~1.5sec

[hobbit_be]

Marcj: ik vond het wel interessant dat jouw code zo dicht kwam eerlijk gezegd ik heb dus je indexOf (findFaster) effe in mijn indexOf benchmark gepropt en het resultaat is interssant

testing with 550 characters and repeating test:100000
BMan 1.937 /ms, Found 3000000 Matches
Onno 1.36 /ms, Found 3000000 Matches
Hybrid 1.375 /ms, Found 3000000 Matches
Marc-J 3.266 /ms, Found 2000000 Matches

testing with 5500 characters and repeating test:10000
BMan 1.86 /ms, Found 3000000 Matches
Onno 1.343 /ms, Found 3000000 Matches
Hybrid 1.313 /ms, Found 3000000 Matches
Marc-J 3.328 /ms, Found 2000000 Matches

testing with 55000 characters and repeating test:1000
BMan 1.937 /ms, Found 3000000 Matches
Onno 1.422 /ms, Found 3000000 Matches
Hybrid 1.406 /ms, Found 3000000 Matches
Marc-J 3.5 /ms, Found 2000000 Matches

testing with 550000 characters and repeating test:100
BMan 2.453 /ms, Found 3000000 Matches
Onno 1.953 /ms, Found 3000000 Matches
Hybrid 1.938 /ms, Found 3000000 Matches
Marc-J 3.984 /ms, Found 2000000 Matches

zo is ineens duidelijk waarom jouw code zo dicht komt hiij doet
een paar miljoen replaces minder... mocht je je FindFaster toch laten
werken... maar ik heb jouw strategie ook al toegepast en die was net iets
trager gek genoeg.

btw die Hybrid is dus the Oisyn-Hybrid implementatie

[hobbit_be]

wat voor PC's hebben jullie eigenlijk? ik vermoed dat de resultaten op andere type processoren wel es anders zouken kunnen zijn...

[Marcj]

Je hoeft niet verder in te wrijven dat m'n code brak is . Kijk eens naar mijn eerste code als je wilt. Voordat ik die manier van Oisyn probeerde te implementeren. Die is maar net iets trager dan die van B-Man..

[.oisyn]

Marcj: over mijn implementatie.
Je gebruikt een tabel van 256 chars, maar een java character is unicode, en dus 16 bits (65536 mogelijkheden).
Ook is het niet handig om voor elke find een nieuwe tabel aan te maken, een thread local tabel zou handiger zijn, hoewel je die dan wel steeds moet leegmaken

Ik zie ook dat je (p == CHECK) nogal raar geimplementeerd hebt, waarschijnlijk om het geval af te handelen dat de begin en eindletter hetzelfde is. Het is natuurlijk beter als je daar een boolean van maakt, en dan alleen die extra afhandeling te doen als de beginletter idd ook gelijk is aan de eindletter.

Je hebt ook (p == CHECK) en (p != CHECK) omgedraaid. Aangezien het vaker zal voorkomen dat p ongelijk is aan CHECK moet dat geval eerst, voor extra optimalisatie

[hobbit_be]

ik deed die test niet om 'in te wrijven'. omdat hij in mijn originele test ALLEEN de laatste replace niet deed dacht ik dat jouw indexOf wel eens sneller zou kunnen zijn. (ook while / loop etc etc). Vandaar dat ik die effe testte en hoopte ik dat hij idd sneller was, we werken hier allemaal samen hoor. die BManOnno code is een samenraapsel van 4 mensen .

Toen je results terugkwamen zag ik dat je index trager was wat me deed concluderen dat jouw character/character copy wel eens sneller zou kunnen zijn dan een SystemArrayCopy wat heel goed nieuws zou zijn. Maar toen merkte ik dat de matches veel te veel verschilde om alleen een replace op het eind te zijn. Dus ik was alleen ontgoocheld

.oisyn: ik heb dus een gedeelte van jouw code geimplementeerd (die Hybrid in lower posts) daar stond ook al dat de 'optimised' niet logisch is:

"hollapalooza" - wat zou in je tabel voor "o" staan?. Mijn tabel is een 65526 unicode static tabel met een UsedIndex extra tabellen voor reuse zonder hem te moeten heraanmaken nog helemaal te clearen .

Die hybrid: kijk of het character voorkomt,

1) y -> doe een gewoone front search (aangezien je onmogelijk kan weten waar het != gelijk is maakt het dus niet uit) als die failed dan herdoe de test voor de volgende index , als ie wel juist is (match) en jump +len.

2)n -> jump +len..

het gebruik van die opzoek tabel is dus eigenlijk niet nodig.

Java:

 nextChar:while (tIndex < tMaxIndex)
            {
                //first check if previous bunch CAN contain something
                if (mIndexOffset[aOriginal[tIndex++]] == 0) //NO so we can jump
                {
                    tIndex += tFromEndOffset; //tFromLength - 1; jump                   continue;
                }
                // System.err.println("possible hit:"+(tIndex-1));
                //now check if it is a hit
                tSingleIndex = tIndex - tFromLength; //tIndex - tFromEndOffset - 1;
                //yes it can contain so do a normal check
                //check first
                if (aOriginal[tSingleIndex++] != tFirst) //check first
                {
                      continue;
                }
                // System.err.println("first passed:"+(tSingleIndex-1));

                tSearchIndex = 1; //restart search
                while (tSearchIndex < tFromLength)
                {
                    if (aOriginal[tSingleIndex++] != aFrom[tSearchIndex++]) 
                    {
                          continue nextChar; //restart search
                    }
                }
                ////hit!!!
                //System.err.println("hit: "+(tIndex-tFromEndOffset-1));
                tIndex += tFromEndOffset; //tFromLength - 1; //jump
                tHits++;

            }

[ Voor 61% gewijzigd door hobbit_be op 11-03-2003 16:16 ]

[Marcj]

.oisyn schreef op 11 March 2003 @ 16:08:
Marcj: over mijn implementatie.
Je gebruikt een tabel van 256 chars, maar een java character is unicode, en dus 16 bits (65536 mogelijkheden).
Ook is het niet handig om voor elke find een nieuwe tabel aan te maken, een thread local tabel zou handiger zijn, hoewel je die dan wel steeds moet leegmaken

Ik zie ook dat je (p == CHECK) nogal raar geimplementeerd hebt, waarschijnlijk om het geval af te handelen dat de begin en eindletter hetzelfde is. Het is natuurlijk beter als je daar een boolean van maakt, en dan alleen die extra afhandeling te doen als de beginletter idd ook gelijk is aan de eindletter.

Je hebt ook (p == CHECK) en (p != CHECK) omgedraaid. Aangezien het vaker zal voorkomen dat p ongelijk is aan CHECK moet dat geval eerst, voor extra optimalisatie

Dit is het probleem niet. Het probleem is dat jouw implementatie makkelijk in een oneindige loop komt. En om dit te ontwijken moet ik een zodanig omslachtige check doen dat ik beter gewoon alle lettertjes kan gaan bekijken.
Of ik doe nog meer goed fout:

Java:

    private static int CHECK = 65535;
    
    public static int[] findFast(char[] aSource, char[] aFind)
    {
        final int tSourceLength = aSource.length;
        if(tSourceLength == 0)
            return new int[0];
            
        final int tFindLength = aFind.length;
        if(tFindLength == 0)
            return new int[0];
            
        //Maak een tabel
        int[] table = new int[65535];
        table[(int)aFind[0]] = CHECK;
        int n;
        for(int i = 1; i < tFindLength; i++)
        {
            n = (int)aFind[i];
            if(table[n] == 0)
                table[n] = -i;
        }
                
        int index = tFindLength - 1;
        int[] temp = new int[(tSourceLength/tFindLength)];
            //Het maximaal aantal te vinden keer is 
            //de lengte van de source gedeelt door de lengte van het te vinden
        int nrFound = 0;
        int highest = -1;
        
        boolean[] checked = new boolean[tSourceLength];
        
        while(index < tSourceLength)
        {
            n = table[(int)aSource[index]];
            if(checked[index])
                index = highest + 1;
            else if(n == 0)
            {
                checked[index] = true;
                index += tFindLength + 1;
            }
            else if(n != CHECK)
            {
                checked[index] = true;
                index += n;
            }
            else
            {
                checked[index] = true;
                if(isFound(aSource, index+1, aFind, 1))
                {
                    temp[nrFound++] = index;
                    index += tFindLength + 1;
                }
                else
                {
                    if(index != 0)
                        index--;
                    else
                        index += tFindLength;
                }
            }
                        
            if(index > highest)
                highest = index;
            //System.out.println(index);
        }
        
        int[] result = new int[nrFound];
            //Het resultaat is kleiner dan temp, tenminste meestal ;)
        System.arraycopy(temp, 0, result, 0, nrFound);
        
        return result;
    }

[Verwijderd]

..nevermmind...

[ Voor 94% gewijzigd door Verwijderd op 11-03-2003 16:21 ]

[Verwijderd]

Verwijderd schreef op 11 maart 2003 @ 14:52:
Deze is bij kleine strings in ieder geval sneller, en bij grote strings lijkt hij ook iets sneller te zijn, hoewel ik niet de test met 720000 characters heb uitgevoerd.

maar er kunnen nog bugs in zitten, want daar heb ik nog niet op getest...
(ohja, en kijk even niet naar de functie naam, maar met zoveel replace functies moet je nou eenmaal ambiguiteit tegen gaan)

Java:

private static int match = 0;

  public static int[] findFaster(char[] source, char[] sequence){
    match = 0;
    ...

Ik heb even naar deze code gekeken, maar als ik deze functie gebruik met een string die eindigd met data die gereplaced moet worden, dan wordt de laatste entry over geslagen...

bv: findFaster("<b>test1</b><br>test2<br>test1","test1","nieuwetekst")

dan is de output "<b>nieuwetekst</b><br>test2<br>test1"

[.oisyn]

Marcj schreef op 11 maart 2003 @ 16:15:
[...]


Dit is het probleem niet. Het probleem is dat jouw implementatie makkelijk in een oneindige loop komt.

oh wacht, ik heb idd wat over het hoofd gezien. Het is namelijk niet alleen zo als het begint en eindigt met dezelfde letter, maar simpelweg als de beginletter meerdere keren voorkomt. Ik zat al te denken dat je dan gewoon altijd terug moet bewegen als je een letter vind, en in het geval de huidige letter gelijk is aan de beginletter van find, dat je dan dat gedeelte controleert. Maar dan kun je woorden die verder in de string staan eerder vinden, dus dat klopt niet helemaal

Ik zal er nog eens naar kijken als ik er tijd voor heb

[Verwijderd]

Verwijderd schreef op 11 maart 2003 @ 18:26:
[...]


Ik heb even naar deze code gekeken, maar als ik deze functie gebruik met een string die eindigd met data die gereplaced moet worden, dan wordt de laatste entry over geslagen...

bv: findFaster("<b>test1</b><br>test2<br>test1","test1","nieuwetekst")

dan is de output "<b>nieuwetekst</b><br>test2<br>test1"

klopt. die bug heb ik ook gevonden, en door nog even een controle op het laatste stuk opgelost...
Blijft volgens mij sneller...

[Marcj]

.oisyn schreef op 12 maart 2003 @ 10:33:

[...]


oh wacht, ik heb idd wat over het hoofd gezien. Het is namelijk niet alleen zo als het begint en eindigt met dezelfde letter, maar simpelweg als de beginletter meerdere keren voorkomt. Ik zat al te denken dat je dan gewoon altijd terug moet bewegen als je een letter vind, en in het geval de huidige letter gelijk is aan de beginletter van find, dat je dan dat gedeelte controleert. Maar dan kun je woorden die verder in de string staan eerder vinden, dus dat klopt niet helemaal

Ik zal er nog eens naar kijken als ik er tijd voor heb

Ik heb er wel een oplossing voor bedacht, maar die vertraagd de boel enorm.
Nu zat ik aan zoiets te denken:
char CHECK = 'eerste letter'
int[] table = 'kleinste aantal letters terug naar de eerste letter'

Als je dan een letter controleert kijk je eerst of die gelijk is aan CHECK. Zo ja, dan kijk je of het woord daar staat. Zo niet, dan ga je in de tabel opzoeken of je een aantal letters terug kan springen. Zo niet, dan kun je een sprong maken.

[.oisyn]

Marcj: ja zo dacht ik ook, maar dan zit je dus met dit probleem:

find = "test";
source = "testestest";

dan geeft ie als resultaat [3] en dat klopt niet (dat moet [0, 6] zijn)

[Marcj]

.oisyn schreef op 12 maart 2003 @ 11:09:
Marcj: ja zo dacht ik ook, maar dan zit je dus met dit probleem:

find = "test";
source = "testestest";

dan geeft ie als resultaat [3] en dat klopt niet (dat moet [0, 6] zijn)

Waarom klopt het niet? Het is wel een geldig resultaat eigenlijk. Hij heeft alle test vervangen zodat er nergens meer test als een heel woord staat. Dit algoritme pakt alleen niet altijd de meeste.

Ik heb dit nu als code, en het werkt gewoon (al is het niet super-snel)

Java:

    public static int[] findFaster(char[] aSource, char[] aFind)
    {
        final int tSourceLength = aSource.length;
        if(tSourceLength == 0)
            return new int[0];
            
        final int tFindLength = aFind.length;
        if(tFindLength == 0)
            return new int[0];
            
        //Maak een tabel
        int[] table = new int[65535];
        char check = aFind[0];
        int n;
        for(int i = 1; i < tFindLength; i++)
        {
            n = (int)aFind[i];
            if(table[n] == 0)
                table[n] = -i;
        }
                
        int index = tFindLength - 1;
        int[] temp = new int[(tSourceLength/tFindLength)];
            //Het maximaal aantal te vinden keer is 
            //de lengte van de source gedeelt door de lengte van het te vinden
        int nrFound = 0;
        int highest = -1;
        
        boolean[] checked = new boolean[tSourceLength];
        
        while(index < tSourceLength)
        {
            if(aSource[index] != check)
            {
                n = table[(int)aSource[index]];
                if(n == 0)
                {
                    index += tFindLength;
                }
                else
                {
                    index += n;
                }
            }
            else
            {
                if(isFound(aSource, index+1, aFind, 1))
                {
                    temp[nrFound++] = index;
                    index += tFindLength;
                }
                else
                {
                    n = table[(int)aSource[index]];
                    if(n == 0)
                    {
                        index += tFindLength;
                    }
                    else
                    {
                        index += n;
                    }
                }
            }
            //System.out.println(index);
        }

edit:
resultaten zijn toch wel een beetje positief:

code:

testing with 71 characters and repeating test:1
MarcJ FindFast: 0.0 /ms
MarcJ FindFaster: 0.0 /ms
testing with 710 characters and repeating test:10000
MarcJ FindFast: 1.129 /ms
MarcJ FindFaster: 1.134 /ms
testing with 7100 characters and repeating test:1000
MarcJ FindFast: 1.663 /ms
MarcJ FindFaster: 1.612 /ms
testing with 71000 characters and repeating test:100
MarcJ FindFast: 7.51 /ms
MarcJ FindFaster: 7.41 /ms
testing with 710000 characters and repeating test:10
MarcJ FindFast: 58.1 /ms
MarcJ FindFaster: 50.1 /ms

Ik heb dus puur de zoek-functie getest. En met deze code:

Java:

//------------------------------------------------------------------------------
        //System.out.println("MarcJ :");
        tTimer.restart();
        for(a = 0; a < avgtime; a++)
        {
            Algoritm.findFast(tTest.toCharArray(), tOld.toCharArray());
        }
        System.out.println("MarcJ FindFast: " + 
        ((int)((tTimer.get() / (double)avgtime) * 1000000))/1000.0 +
        " /ms");
//------------------------------------------------------------------------------
        //System.out.println("MarcJ :");
        tTimer.restart();
        for(a = 0; a < avgtime; a++)
        {
            Algoritm.findFaster(tTest.toCharArray(), tOld.toCharArray());
        }
        System.out.println("MarcJ FindFast: " + 
        ((int)((tTimer.get() / (double)avgtime) * 1000000))/1000.0 +
        " /ms");

Hiermee kun je dus echt zien hoeveel milliseconden hij er per keer over doet. En het valt me op dat 7100 chars nauwelijks trager is dan 710 chars... Zal die tabel maken toch zoveel tijd kosten? Lijkt me toch niet?

[ Voor 31% gewijzigd door Marcj op 12-03-2003 11:34 ]

[.oisyn]

de algemene werking van een replace functie zoekt alle woorden van begin tot eind, en vervangt deze

replace ('test' -> 'bla' in 'testtesttest') zou dus 'blaesbla' moeten geven, en niet 'tesblaest'

[Marcj]

.oisyn schreef op 12 March 2003 @ 11:30:
de algemene werking van een replace functie zoekt alle woorden van begin tot eind, en vervangt deze

replace ('test' -> 'bla' in 'testtesttest') zou dus 'blaesbla' moeten geven, en niet 'tesblaest'

Toch vind ik dat nog niet echt fout. Maar zie dit: Herriner je mijn originele Find nog? Die gewoonweg alle lettertjes nagaat?

code:

testing with 71 characters and repeating test:1
MarcJ Find: 0.0 /ms
MarcJ FindFast: 0.0 /ms
MarcJ FindFaster: 0.0 /ms
testing with 710 characters and repeating test:10000
MarcJ Find: 0.028 /ms
MarcJ FindFast: 1.137 /ms
MarcJ FindFaster: 1.141 /ms
testing with 7100 characters and repeating test:1000
MarcJ Find: 0.239 /ms
MarcJ FindFast: 1.632 /ms
MarcJ FindFaster: 1.593 /ms
testing with 71000 characters and repeating test:100
MarcJ Find: 3.499 /ms
MarcJ FindFast: 7.91 /ms
MarcJ FindFaster: 7.11 /ms
testing with 710000 characters and repeating test:10
MarcJ Find: 49.1 /ms
MarcJ FindFast: 53.1 /ms
MarcJ FindFaster: 46.0 /ms

Sorry oisyn, maar volgens mij gaat het niet werken. Ik kan beter m'n originele code gebruiken...

[Marcj]

Oké .oisyn, nu hou ik maar op met jou code. Ik kan nog steeds in een loop komen..
testString = "In this [test] we [test] the [test]er....[other].. with ofcourse [test]"
Nu wil ik [other] gaan vervangen.
Dan komen we in een loop. Even voor de duidelijkheid
tabel:
o -> -1
t -> -2
h -> -3
e -> -4
r -> -5
] -> -6

Lengte = 7, dus we starten op index = 6;
6 -> 's' -> +8 -> 14
14 -> ' ' -> +8 -> 22
22 -> 't' -> -2 -> 20
20 -> 'e' -> -4 -> 16
16 -> 'e' -> -4 -> 12
12 -> 't' -> -2 -> 10
10 -> 'e' -> -4 -> 6
En nu zijn we terug bij af...

[.oisyn]

mja, imho teer je teveel op mijn uitleg enzo. Het is een bekend algoritme waarvan bewezen is dat ie sneller is (mits goed geimplementeerd ). Misschien moet je er eens wat info over gaan zoeken... ik weet alleen de echte naam van het algo niet

[Marcj]

.oisyn schreef op 12 March 2003 @ 12:49:
mja, imho teer je teveel op mijn uitleg enzo. Het is een bekend algoritme waarvan bewezen is dat ie sneller is (mits goed geimplementeerd ). Misschien moet je er eens wat info over gaan zoeken... ik weet alleen de echte naam van het algo niet

Ik kan ook niet echt wat vinden over een algoritme over opzoeken... Maar wat voor varianten ik ook bedenk, het wordt er niet sneller op en ik loop steeds tegen nieuwe problemen aan.

[Verwijderd]

.oisyn schreef op 12 March 2003 @ 12:49:
Misschien moet je er eens wat info over gaan zoeken... ik weet alleen de echte naam van het algo niet

Boyer-Moore algoritme. Eerste hit van google geeft duidelijke uitleg.

[.oisyn]

[Marcj]

http://www-igm.univ-mlv.fr/~lecroq/string/node1.html
Oef.. tnx! We gaan weer eens wat zoekfuncties proberen te maken

[hobbit_be]

nou effe opnieuw beginnen dan?

Daar beginnen we in ieder geval volgende week eens aan. Alhoewel op het eerste gezicht de meeste sneller kunnen zijn (zullen ze ook denk ik) maar dat ze in sommige gevallen ook een heel pak trager kunnen zijn. Mijn Hybrid doet hun test geval (maar wel een pokke voorbeeld) net even snel als Boyer-Moore, maar die doet wel een hoop precalc. Ik denk dat de meeste in C++/Asm wel sneller kunnen zijn (met Memory Pools enzo) maar in Java is de overhead van al dat memory new in de meeste gevallen 'dodelijk' imho.

Tuned-Boyer-Moyer moet je alvast niet gaan implementeren want die verwacht dat je de text die onderzocht moet worden effe gaat uitbreiden met de pattern lenght. oh en dat je hele Alphabet lookup (65536 in Java) effe op de pattern length gaat zetten (valt te omzeilen aangezien 0 niet in zijn look-up kan voorkomen).

Goed we weten weer wat doen volgende week, maar als ik een gokje mag doen: ik betwijfel de speed increases vanwege de recursie factor. Zoals ik al zei eerder met zo'n pattern - lookups ze zijn zalig als je zoiets doet:

zoek "***" in "------------------------------------------------***--"; //effe heel extreem
dit vind ik zeker 5x keer sneller

maar
zoek "---" in "------------------------------------------------***--";
doet ie minstens 5x...

(check result met Hybrid die net onder de complexiteit van Boer-Moore zit en die
dus soms sneller, soms trager is depending on pattern/text)

mischien even heuristics op je search string loslaten en distibutie spectra? Mochten we hier mee verder gaan stel ik voor dat we een gemeenschappelijke Search Text gebruiken die een echte normale Nederlandse tekst is. (en ik vermoed uit onderzoek dat per taal de resulaten gaan verschillen zodat je gewoon aan de snelheid kunt zien welke taal het is - net zoals onderzoekers dat kunnen met compressie methode)...

edit:
voorlopige conclusie: er bestaat gewoon geen beste replace er bestaat wel een beste replace voor elk geval. Net zoals programmeer talen dus.

[ Voor 6% gewijzigd door hobbit_be op 12-03-2003 15:09 ]

[Marcj]

Hmm, het enige waarmee ik nog een beetje resultaat mee heb kunnen behalen is het Quick Search Algoritm. De rest is gewoonweg te lang aan het initializeren van tabellen ed. Dit wil nog. Dit is net een 10% sneller met opzoeken dan mijn Brute-Force algoritme

code:

testing with 710 characters and repeating test:10000
MarcJ Brute Force: 0.027 /ms
MarcJ QuickSearch: 0.031 /ms
testing with 7100 characters and repeating test:1000
MarcJ Brute Force: 0.25 /ms
MarcJ QuickSearch: 0.239 /ms
testing with 71000 characters and repeating test:100
MarcJ Brute Force: 3.31 /ms
MarcJ QuickSearch: 2.8 /ms
testing with 710000 characters and repeating test:10
MarcJ Brute Force: 50.1 /ms
MarcJ QuickSearch: 44.1 /ms

Alleen met een hele kleine string is hij wel nog langzamer

edit: Ik ga voor de kortste replace

Java:

private static final int ASIZE = 256;
public static char[] QSreplace(char[] aSource, char[] aOld, char[] aNew)
{
    int[] table = new int[ASIZE];
    int i, j, k, iy, ir;
    j = k = iy = ir = 0;
    int tSourceLength = aSource.length - 1;
    int tOldLength = aOld.length - 1;
    int tNewLength = aNew.length - 1;
    for (i = 0; i < ASIZE; ++i) table[i] = aOld.length;
    for (i = 0; i < tOldLength; ++i) table[aOld[i]] = tOldLength - i;
        
    char[] temp;
    if(tNewLength > tOldLength)
        temp = new char[(tSourceLength + 1) + (tNewLength - tOldLength) * (tOldLength/tSourceLength)];
    else
        temp = new char[tSourceLength + 1];
            
    while (j <= tSourceLength - tOldLength)
    {
        if (isFound(aSource, j, aOld, 0))
        {
            k = j - iy;
            arraycopy(aSource, iy, temp, ir, k);
            iy += k;
            ir += k;
            arraycopy(aNew, 0, temp, ir, tNewLength + 1);
            iy += tOldLength + 1;
            ir += tNewLength + 1;
        }           
        j += table[aSource[j + tOldLength]];
    }
    k = tSourceLength - iy + 1;
    arraycopy(aSource, iy, temp, ir, k);
    ir += k;
        
    char[] result = new char[ir];
    arraycopy(temp, 0, result, 0, ir);
    return result;
}

Ik denk trouwens dat hij nog een heel stuk sneller te krijgen is als ik in een complete array in één keer een waarde kan invoeren. Die eerste for-loop lijkt me nou niet echt efficient...

[ Voor 45% gewijzigd door Marcj op 12-03-2003 16:54 ]

[Marcj]

M'n laatste poging is weer op een ramp uitgelopen. Nou ja een ramp... Hij is trager dan m'n Brute Force. Die Tuned-Boyer-Moore is idd niet snel te krijgen in java, alleen omdat je geen efficiente vervanger hebt voor wat in C memset() en memcmp() is. TBMreplace() zal in C dus wel heel snel kunnen werken, maar in Java gaat het gewoon niet lukken. Hij is trouwens wel goed werkend met heel weinig compares tussen characters. Alleen de initializatie doet hem weer de nek om.
(code laat ik maar achterwege...)

[ Voor 2% gewijzigd door Marcj op 12-03-2003 17:36 . Reden: typo.. ]

[hobbit_be]

Marcj: je kunt die hele affaire van op null zetten verwijderen door een index of used indeces bij te houden. dan moet je slechts per keer de oude effe resetten. zoals in mijn post kun je die tabel ook verandren door ipv overal te resetten naar de patternlenght (m) die dus
per search kan veranderen kun je die op 0 zetten aangezien dit nooit in de LUT kan voorkomen dan moet je dus if (... =0) = m; zodoende heb je die overhead niet. zo'n truuk gebruikte ik al in Hybrid.

memcpy is er trouwens wel: System.arraycopy Het enige echte probleem met Tuned is het feit dat je de search text al direct moet gaan extenden. In het geval van een String (String, STring) replaces moet je zowieso dat doen (toch copieren) en kun je die ook wegkrijgen. hmm maw het zou dus wel eens sneller kunnen gaan en daarmee is mijn oude post weer ongeldig

Java:

 static int[] mIndexOffset = new int[65536];  //alphabet gedoe bsBC 
 static int[] mUsedIndex = new int[65536]; //welke worden er gebruikt 
 static int mUsedCount = 0; //echte size van used index

//per replace effe de oude used op 'nul' zetten
 while (mUsedCount > 0)
        {
            // --mUsedCount; //decrease before to get index
            mIndexOffset[mUsedIndex[--mUsedCount]] = 0;
        }
        mUsedCount = 0;

//en dan voor elke keer dat je een 'nieuwe' used char vind:
if (mIndexOffset[tCharIndex] == 0) //zero is special char
{
    mUsedIndex[mUsedCount++] = tCharIndex
}

aldus bijna geen tabellen kost

oh en die check hoeft niet als je de values in te tabel value = m-value (dus omdraait) en dan weer heromdraait in je loop

[ Voor 9% gewijzigd door hobbit_be op 12-03-2003 17:44 ]

[Marcj]

Hmm, volgens mij moet het dan ergens anders aan liggen, want met die oplossing wordt het nog geen milliseconde sneller. Wat ik ook vreemd vind is dat m'n functie nu langzamer is geworden, terwijl ik nu juist replace() en find() in één functie heb gestopt. Dit scheelt die array met getallen. Soms snap ik er echt niets meer van

Ow, en die System.arraycopy is nauwelijks sneller dan mijn eigengeschreven arraycopy. Dat vind ik helemaal vreemd. Kan Java geen complete blokken kopiëren ofzo??
Mijn arraycopy:

Java:

public static void arraycopy(char[] x, int ix, char[] y, int iy, int length)
{
    while(length > 0)
    {
        y[iy++] = x[ix++];
        length--;
    }
}

Het maakt volgens mij geen ene zak uit, en dat terwijl de arraycopy bijna 35% van de tijd in beslag neemt