Wer kanns schneller?

[chrs]

    @org.junit.Test
    public void charArray() {
        for (int i = 0; i < 10000000; i++) {
            Quersumme.quersummeCharArray(354210);
        }
    }

    static long quersummeCharArray(long zahl) {
        long summe = 0;
        char[] arr = String.valueOf(zahl).toCharArray();

        for (char element : arr) {
            summe += element - '0';
        }

        return summe;
    }

Wer schreibt eine schnellere Methode? Die 6stellige Zahl sollte bleiben.

 

[Murray]

Was wären die Randbedingungen? Soll das gleiche rauskommen wie bei Deiner Methode? Oder doch lieber die Quersumme der Zahl?

 

[tfa]

Wenn das die Quersumme einer Zahl berechnen soll ist die Methode falsch.

 

[chrs]

Entschuldigt, ich habe ihn verbessert, es geht um die schnellste Quersummenberechnung von einer long

 

[Marco13]

It's a kind of magic - maa-gic - maaaa-giiic.... *sing*

import java.util.*;

class Quersumme
{

    static List<Long> list = new ArrayList<Long>();

    public static void main(String args[])
    {
        initValues();

        for (int i=0; i<list.size(); i++)
        {
            int n=10000000;
            test1(n, list.get(i));
            test2(n, list.get(i));
        }
    }


    private static void initValues()
    {
        String s = "12";
        int n = 3;
        do
        {
            long value = Long.parseLong(s);
            if (value > Long.MAX_VALUE / 10 - 1)
            {
                break;
            }
            list.add(value);
            s += n;
            n = (n+1) % 10;
        } while (true);
    }

    public static void test1(int n, long value)
    {
        long before = System.currentTimeMillis();
        long sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += Quersumme.quersummeCharArray(value);
        }
        long after = System.currentTimeMillis();
        System.out.println("test1 value "+value+" sum "+sum+" time "+(after-before));
    }

    static long quersummeCharArray(long zahl)
    {
        long summe = 0;
        char[] arr = String.valueOf(zahl).toCharArray();

        for (char element : arr) {
            summe += element - '0';
        }

        return summe;
    }

    public static void test2(int n, long value)
    {
        long before = System.currentTimeMillis();
        long sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += Quersumme.checksum(value);
        }
        long after = System.currentTimeMillis();
        System.out.println("test2 value "+value+" sum "+sum+" time "+(after-before));
    }

    static long checksum(long value)
    {
        long sum = 0;
        while (value > Integer.MAX_VALUE)
        {
            long q = value / 100;
            int r = (int)(value - ((q << 6) + (q << 5) + (q << 2)));
            value = q;
            sum += r;
        }
        int value2 = (int)value;
        while (value2 >= 65536)
        {
            int q2 = value2 / 100;
            int r = value2 - ((q2 << 6) + (q2 << 5) + (q2 << 2));
            value2 = q2;
            sum += r;
        }
        while (true)
        {
            int q2 = (value2 * 52429) >>> (16+3);
            int r = value2 - ((q2 << 3) + (q2 << 1));
            sum += r;;
            value2 = q2;
            if (value2 == 0)
            {
                break;
            }
        }
        return sum;
    }

}

Der ... "Kern" stammt aber nicht von mir .... :roll: (52429?! :bahnhof: )

 

[chrs]

Heilige Scheiße, das ist nicht nur viel viel schneller als meine Variante, man versteht es auch überhaupt nicht mehr, wie kommt man denn auf soetwas? Diese ganzen bitweisen Verschiebungen, ... respekt.

Gehts noch besser?

 

[Murray]

Leider liefert die zweite Methode teilweise andere Ergebnisse als die erste...

 

[tfa]

Gehts noch besser?

Mach dir ne Lookup-Table. Ist nur ein bisschen speicherintensiv.

 

[thE_29]

Jau, das ist auch schneller!

  static long quersummeCharArray(long zahl) {
    long summe = 0;
    String str = Long.toString(zahl);
    int size = str.length();
    for(int x = 0; x != size; x++)
      summe += str.charAt(x) - 48;
return summe;

Hingegen ist das lansamer

 static long quersummeCharArray(long zahl) {
    long summe = 0;
    for(; zahl > 0; zahl /= 10)
    {
      summe += zahl %10;
    }
return summe;

 

[chrs]

tHE_29: Ja genau die Modulo Lösung hatte ich auch schon..

 

[Marco13]

Ja, da war noch ein Fehler drin. So müßt's stimmen

import java.util.*;

class Quersumme
{

    static List<Long> list = new ArrayList<Long>();

    public static void main(String args[])
    {
        initValues();

        for (int i=0; i<list.size(); i++)
        {
            int n=1000000;
            test1(n, list.get(i));
            test2(n, list.get(i));
        }
    }


    private static void initValues()
    {
        String s = "12";
        int n = 3;
        do
        {
            long value = Long.parseLong(s);
            if (value > Long.MAX_VALUE / 10 - 1)
            {
                break;
            }
            list.add(value);
            s += n;
            n = (n+1) % 10;
        } while (true);
    }

    public static void test1(int n, long value)
    {
        long before = System.currentTimeMillis();
        long sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += Quersumme.quersummeCharArray(value);
        }
        long after = System.currentTimeMillis();
        System.out.println("test1 value "+value+" sum "+sum+" time "+(after-before));
    }

    static long quersummeCharArray(long zahl)
    {
        long summe = 0;
        char[] arr = String.valueOf(zahl).toCharArray();

        for (char element : arr) {
            summe += element - '0';
        }

        return summe;
    }

    public static void test2(int n, long value)
    {
        long before = System.currentTimeMillis();
        long sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += Quersumme.checksum(value);
        }
        long after = System.currentTimeMillis();
        System.out.println("test2 value "+value+" sum "+sum+" time "+(after-before));
    }


    private static int d[];
    private static void init()
    {
        d = new int[100];
        for (int i=0; i<100; i++)
        {
            d[i] = i/10+i%10;
        }
    }

    static long checksum(long value)
    {
        if (d==null) init();
        long q, sum = 0;
        int q2, r;
        while (value > Integer.MAX_VALUE)
        {
            q = value / 100;
            r = (int)(value - ((q << 6) + (q << 5) + (q << 2)));
            value = q;
            sum += d[r];
        }
        int value2 = (int)value;
        while (value2 >= 65536)
        {
            q2 = value2 / 100;
            r = value2 - ((q2 << 6) + (q2 << 5) + (q2 << 2));
            value2 = q2;
            sum += d[r];
        }
        while (true)
        {
            q2 = (value2 * 52429) >>> (16+3);
            r = value2 - ((q2 << 3) + (q2 << 1));
            sum += d[r];
            value2 = q2;
            if (value2 == 0)
            {
                break;
            }
        }
        return sum;
    }
}

Das stammt effektiv aus der java.lang.Long - das ist "genau" das, was bei "Long.toString" implizit auch gemacht wird. Die ganzen bitshifts sind eben trickreiche modulo100-Rechnungen ... bis auf den letzten, der sich mir auch nicht sofort erschließt :roll:

 

[Gast]

Ein Versuch das ganze anhand eines "Wissensbasierten"-Systems aufzubauen. Wenn es um das 1000000 fache Berechnen der Long 354210 geht.

static Map<Long, Long> map = new HashMap<Long, Long>(); 
    
    static long myquersumme(long zahl){
    	Long zahlAusMap = map.get(zahl);
    	if(zahlAusMap !=null){
    		return zahlAusMap;
    	}
    	long key = zahl;
    	long summe=0;
    	
    	while(zahl >0){
    		 
    		summe += zahl %10;
    		zahl = zahl/10;
    	}
    	map.put(key, summe);
    	return summe;
    }

 

[Gast]

@Marco13 warum wird bei dir in Zeile 108

q2 = (value2 * 52429) >>> (16+3);

verwendet anstatt

q2 = (value2 * 52429) >>> (19);

 

[Marco13]

Erstens, weil das - wie ich auch geschrieben hatte - aus java.lang.Long stammt, und zweitens, weil es egal ist: DAS optimiert schon der dümmste Compiler weg.