Simplen Algorithmus optimieren

[0001001]

Hi,

ich habe folgenden Algorithmus, der das Tanimoto Ähnlichkeitsmaß berechnet:

    private double calculateTanimoto(List<String> valuesA, List<String> valuesB) {
    	// create set union of all values
    	Set<String> set = new HashSet<String>();
    	set.addAll(valuesA);
    	set.addAll(valuesB);

    	// calc tanimoto parameters
  	
    	double nA = 0;
    	double nB = 0;
    	double nAB = 0;
    	
    	for(String s: set){
    		if(valuesA.contains(s)){
    			nA++;
    		}
    		if(valuesB.contains(s)){
    			nB++;
    		}
    		if(valuesA.contains(s) && valuesB.contains(s)){
    			nAB++;
    		}
    	}    	
    	
    	// calc tanimoto    	
    	return ((nAB/(nA+nB-nAB)));
    }

Problem sind IMHO die contains() Aufrufe. D.h. es wird für jeden Wert in der Gesamtliste (set) geprüft, ob der Wert in der ListeA (valuesA) oder der ListeB (valuesB) oder in beiden Listen vorkommt.

Ich vermute, dass die Suche mit contains sehr langsam ist. Könnte man das effizienter umsetzen?

Hier mein erster Verbesserungsvorschlag:

private double calculateTanimoto(List<String> valuesA, List<String> valuesB) {
    	// create set union of all values
    	Set<String> set = new HashSet<String>();
    	set.addAll(valuesA);
    	set.addAll(valuesB);
    	
    	Set<String> setA = new HashSet<String>(); // set is faster than hashmap
    	setA.addAll(valuesA);
    	Set<String> setB = new HashSet<String>();
    	setB.addAll(valuesB);
    	
    	// calc tanimoto parameters
    	int i=0;    	
    	double nA = 0;
    	double nB = 0;
    	double nAB = 0;
    	
    	
    	for(String s: set){
    		boolean inA = false;
    		boolean inB = false;
    		if(setA.contains(s)){
    			nA++;
    			inA = true;
    		}
    		if(setB.contains(s)){
    			nB++;
    			inB = true;
    		}
    		if(inA && inB){
    			nAB++;
    		}
    		i++;
    	}
    	
    	
    	// calc tanimoto    	
    	return ((nAB/(nA+nB-nAB)));
    }

Könnte man das noch weiter optimieren?

 

[Gonzo17]

Für was brauchst du da jetzt das "i"?

 

[maki]

nimm einen Profiler, alles andere ist geraten und führt nur durch Zufall zum Erfolg.

 

[SlaterB]

setA und setB sind schon ziemlich gut,
aber wozu danach noch nA/ nb zählen? dürfte doch genau setA.size() usw. sein,
für die Schnittmenge gibts sicher vorgegebene Methoden setA.retain(setB) oder so, und dann wieder size(),
Set<String> set ist dann überflüssig


Zählvariablen allgemein schon gar nicht als double

-----

aber mit Set ist alles geschafft, danach kann es eigentlich gar nicht mehr langsam sein,
wenn der ganze Arbeitsspeicher in wenigen sec durchgezählt werden könnte, braucht man da nicht viel mehr machen

 

[Marco13]

    private static double calculateTanimotoB(List<String> valuesA, List<String> valuesB)
    {
        Set<String> union = new HashSet<String>(valuesA);
        union.addAll(valuesB);
        Set<String> intersection = new HashSet<String>(valuesA);
        intersection.retainAll(new HashSet<String>(valuesB));
        return (double)intersection.size() / union.size();
    }

 

[Marco13]

Vielleicht noch der passende Microbenchmark dazu

import java.util.*;


class Tanimoto
{
    private static Random random = new Random(0);

    public static void main(String args[])
    {
        //verify();
        benchmark();
    }

    private static String createRandomString(int len)
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<len; i++)
        {
            sb.append('A'+(char)(random.nextFloat()*('Z'-'A')));
        }
        return sb.toString();
    }

    private static void verify()
    {
        int n = 3000;
        int len = 2;
        List<String> a = new ArrayList<String>();
        List<String> b = new ArrayList<String>();

        for (int i=0; i<n; i++)
        {
            a.add(createRandomString(len));
            b.add(createRandomString(len));
        }

        testA(n, len, 1, a, b);
        testB(n, len, 1, a, b);
    }

    private static void benchmark()
    {
        int len = 3;
        for (int n=1000; n<=2000; n+=250)
        {
            List<String> a = new ArrayList<String>();
            List<String> b = new ArrayList<String>();

            for (int i=0; i<n; i++)
            {
                a.add(createRandomString(len));
                b.add(createRandomString(len));
            }

            for (int runs=5; runs<=25; runs+=5)
            {
                testA(n, len, runs, a, b);
                testB(n, len, runs, a, b);
            }
        }
    }


    private static void testA(int n, int len, int runs, List<String> a, List<String> b)
    {
        double result = 0;
        long before = System.nanoTime();
        for (int r=0; r<runs; r++)
        {
            result += calculateTanimoto(a, b);
        }
        long after = System.nanoTime();
        double ms = (after-before) / 1000000.0;
        System.out.println("testA n="+n+" len="+len+" runs="+runs+" result "+result+" ms: "+ms);
    }


    private static double calculateTanimoto(List<String> valuesA, List<String> valuesB)
    {
        // create set union of all values
        Set<String> set = new HashSet<String>();
        set.addAll(valuesA);
        set.addAll(valuesB);

        // calc tanimoto parameters

        double nA = 0;
        double nB = 0;
        double nAB = 0;

        for(String s: set)
        {
            if(valuesA.contains(s))
            {
                nA++;
            }
            if(valuesB.contains(s))
            {
                nB++;
            }
            if(valuesA.contains(s) && valuesB.contains(s))
            {
                nAB++;
            }
        }

        // calc tanimoto
        return ((nAB/(nA+nB-nAB)));
    }






    private static void testB(int n, int len, int runs, List<String> a, List<String> b)
    {
        double result = 0;
        long before = System.nanoTime();
        for (int r=0; r<runs; r++)
        {
            result += calculateTanimotoB(a, b);
        }
        long after = System.nanoTime();
        double ms = (after-before) / 1000000.0;
        System.out.println("testB n="+n+" len="+len+" runs="+runs+" result "+result+" ms: "+ms);
    }


    private static double calculateTanimotoB(List<String> valuesA, List<String> valuesB)
    {
        Set<String> union = new HashSet<String>(valuesA);
        union.addAll(valuesB);
        Set<String> intersection = new HashSet<String>(valuesA);
        intersection.retainAll(new HashSet<String>(valuesB));
        return (double)intersection.size() / union.size();
    }


}

Die Ausgaben gehen so in die Richtung von

testA n=1250 len=3 runs=25 result 1.0276936391172657 ms: 4191.643598
testB n=1250 len=3 runs=25 result 1.0276936391172657 ms: 10.984808

nimm einen Profiler, alles andere ist geraten und führt nur durch Zufall zum Erfolg.

Nachdenken und das Problem analysieren hilft aber auch manchmal 😉


EDIT: Ach, das bezog sich noch auf die "unoptimierte" version - bei der Optimierten ist's nicht meht sooo deutlich

testA n=25000 len=3 runs=25 result 16.538897406839542 ms: 321.682439
testB n=25000 len=3 runs=25 result 16.538897406839542 ms: 269.092776

Aber zumindest einfacher, übersichtlicher, und zumindest noch einen Tick schneller....

 

[0001001]

Wow,

vielen Dank, besonders an Marco13 für den Benchmark!

 

[SlaterB]

    private static double calculateTanimotoC(List<String> valuesA, List<String> valuesB)
    {
        Set<String> setA = new HashSet<String>(valuesA);
        Set<String> setB = new HashSet<String>(valuesB);
        int a = setA.size();
        int b = setB.size();

        setA.retainAll(setB);
        double inter = setA.size();
        return inter / (a + b - inter);
    }

testB n=3000 len=2 runs=1 result 0.9888 ms: 20.532498
testC n=3000 len=2 runs=1 result 0.9888 ms: 2.372927
testB n=1000 len=3 runs=5 result 0.16782099094299413 ms: 12.829563
testC n=1000 len=3 runs=5 result 0.16782099094299413 ms: 2.282692
testB n=1000 len=3 runs=10 result 0.3356419818859883 ms: 11.040789
testC n=1000 len=3 runs=10 result 0.3356419818859883 ms: 4.52767
testB n=1000 len=3 runs=15 result 0.5034629728289826 ms: 15.864866
testC n=1000 len=3 runs=15 result 0.5034629728289826 ms: 8.104661
testB n=1000 len=3 runs=20 result 0.6712839637719765 ms: 20.201171
testC n=1000 len=3 runs=20 result 0.6712839637719765 ms: 10.646605
testB n=1000 len=3 runs=25 result 0.8391049547149705 ms: 24.886403
testC n=1000 len=3 runs=25 result 0.8391049547149705 ms: 13.072332

😉

 

[SlaterB]

und weil ja jede ms zählt:

 private static double calculateTanimotoD(List<String> valuesA, List<String> valuesB)
    {
        Set<String> setA = new HashSet<String>(valuesA);
        Set<String> setB = new HashSet<String>(valuesB);
        int a = setA.size();
        int b = setB.size();

        int inter = 0;
        for (String stB : setB)
        {
            if (setA.contains(stB))
            {
                inter++;
            }
        }
        return (double) inter / (a + b - inter);
    }

testB n=3000 len=2 runs=1 result 0.9888 ms: 9.317664
testC n=3000 len=2 runs=1 result 0.9888 ms: 2.11675
testD n=3000 len=2 runs=1 result 0.9888 ms: 1.767822
testB n=1000 len=3 runs=5 result 0.16782099094299413 ms: 10.514465
testC n=1000 len=3 runs=5 result 0.16782099094299413 ms: 2.235201
testD n=1000 len=3 runs=5 result 0.16782099094299413 ms: 3.781206
testB n=1000 len=3 runs=10 result 0.3356419818859883 ms: 9.703188
testC n=1000 len=3 runs=10 result 0.3356419818859883 ms: 5.191442
testD n=1000 len=3 runs=10 result 0.3356419818859883 ms: 4.336585
testB n=1000 len=3 runs=15 result 0.5034629728289826 ms: 14.794059
testC n=1000 len=3 runs=15 result 0.5034629728289826 ms: 7.285562
testD n=1000 len=3 runs=15 result 0.5034629728289826 ms: 5.799899
testB n=1000 len=3 runs=20 result 0.6712839637719765 ms: 18.52945
testC n=1000 len=3 runs=20 result 0.6712839637719765 ms: 9.555125
testD n=1000 len=3 runs=20 result 0.6712839637719765 ms: 8.67708
testB n=1000 len=3 runs=25 result 0.8391049547149705 ms: 24.19721
testC n=1000 len=3 runs=25 result 0.8391049547149705 ms: 12.983773
testD n=1000 len=3 runs=25 result 0.8391049547149705 ms: 10.62677

 

[maki]

nimm einen Profiler, alles andere ist geraten und führt nur durch Zufall zum Erfolg.

Nachdenken und das Problem analysieren hilft aber auch manchmal 😉

Aber ob das Ergebnis schneller, langsamer oder genau gleich ist, merkt man erst, wenn man misst, und das habt ihr ja 😉
Optimierungen jedoch ohne Überprüfung enden meist nicht als Optimierungen...

 

[Marco13]

    private static double calculateTanimotoE(List<String> valuesA, List<String> valuesB)
    {
        Set<String> setA = new HashSet<String>(valuesA);
        int inter = 0;
        for (String stB : valuesB)
        {
            if (setA.contains(stB))
            {
                inter++;
            }
        }
        return (double) inter / (setA.size() + valuesB.size() - inter);
    }

-->

testD n=70000 len=3 runs=70 result 68.3913711432595 ms: 1122.14439
testE n=70000 len=3 runs=70 result 68.3913711432595 ms: 1110.968867

:joke: (Nicht so ernst zu nehmen - die Zeiten pendeln da im Rahmen der Messungenauigkeit umeinander - aber schon "aus Prinzip" sollte man sich das überflüssige new HashSet sparen 😉 )