Summe der Ziffern einer Zahl EFFIZIENT berechnen?

  • Themenstarter Themenstarter Guest
  • Beginndatum Beginndatum
Status
Nicht offen für weitere Antworten.
G

Guest

Gast
Hi,

Java bietet im Gegensatz zu anderen Sprachen ja keinen Zugriff auf die Ziffern eines Integers.
Das Umwandeln in String kostet IMHO aber sehr viel Zeit.

Hier ein Demo Programm:
Code: 
public class Demo {
	public static void main(String[] args) {
		new Demo().run();
	}
	
	public void run(){
		long start = System.currentTimeMillis();
		
		for(int i=1;i<20000000;i++){
			getSum(i);
		}		
		System.out.println((System.currentTimeMillis()-start)/1000+" Sekunden");
	}
	
	
	public int getSum(int zahl){
		int sum = 0;
		String s = String.valueOf(zahl);
		for(int i=0;i<s.length();i++){
			sum = sum + Integer.parseInt(s.substring(i, i+1));
		}
		return sum;
	}
}
Das dauert bei mir ca. 15 Sekunden.

Kann man das anders machen und geht das schneller?
 
Nach Datum sortieren Nach Zustimmungen sortieren
du kannst aus dem String die Zeichen mit charAt() rausholen,
dann noch minus '0' und nach int umwandeln oder direkt mit dem char rechnen,

schonmal schneller als das parseInt()

---------

wenn du direkt mit der Zahl rechnen willst, dann verwende % 10 und / 10, um per Rechnung an die einzelnen Ziffern zu kommen
 
Zustimmen 0
Ok,

das bringt schon mal einiges:
Code: 
public class Demo {
	public static void main(String[] args) {
		new Demo().run();
	}
	
	public void run(){
		long start = System.currentTimeMillis();

		
		for(int i=1;i<20000000;i++){
			getSum(i);
		}		
		System.out.println((System.currentTimeMillis()-start)/1000+" Sekunden"); 
	}
	
	
	public int getSum(int zahl){
		int sum = 0;
		String s = String.valueOf(zahl);
		for(int i=0;i<s.length();i++){
			sum = sum + s.charAt(i)-48;
		}
		return sum;
	}
}

Das dauert nur noch ca. 3 Sekunden. Gehts noch schneller?
 
Zustimmen 0
ist allerdings bisschen langsamer, bei mir recht genau 6 Sekunden

gehts eigentlich um die reine Zählleistung oder reicht dir auch ne Formel?

max * 17/ x2 = fertig

-------


eine Zwischenlösung wäre wohl, statt jedes mal einen neuen String zu erzeugen, ein char-Array anzulegen und da nur die passenden chars auszutauschen,

['0','0','3']

->

['0','0','4']

->
['0','0','5']



der Übergang zur Formelrechnung ist dann langsam fließend
 
Zustimmen 0
Code: 
public int getSum(int zahl){
      int sum = 0;
      for(;zahl > 0; zahl/=10)
      {
    	  sum += zahl%10;
      }
      return sum;
   }
 
Zustimmen 0
Code: 
public class Quersumme {

  private final static int[] SUM = new int[] {
      0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
      2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
      2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
      8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
      17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
      9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
      12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
      13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
      17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
      18, 19, 20, 21, 22, 23, 24, 25, 26, 27
  };

  public static int quersumme(int zahl) {
    int sum = 0;
    while (zahl > 0) {
      sum += SUM[zahl % 1000];
      zahl /= 1000;
    }
    return sum;
  }

  public static void main(String ...args) {
    System.out.println(quersumme(1234567));
  }
}
 
Zustimmen 0
ob wohl ein switch schneller ist als ein Array-Zugriff?
bitte ausprobieren 😉

das müsste man tatsächlich programmieren, das Array hätte man auch dynamisch füllen lassen können
(ok, den Quellcode für das switch kann auch ein Programm schreiben)
 
Zustimmen 0
Eine andere Idee wäre, die letzte Ziffer ohne % zu ermitteln:
Code: 
 private static int lastDigit(int zahl) {
     int hex = zahl & 0xF;
     switch(hex) {
     case 10 : return 0;
     case 11 : return 1;
     case 12 : return 2;
     case 13 : return 3;
     case 14 : return 4;
     case 15 : return 5;
     default: return hex;
     }
 }
 
Zustimmen 0
>Eine andere Idee wäre, die letzte Ziffer ohne % zu ermitteln:

Code: 
		int sum = 0;
		int temp;
		while (zahl > 0) {
			temp = zahl / 10; //div 10
			sum += (zahl - (temp << 3) - (temp << 1)); //orig - (temp * 10)
			zahl = temp;
		}

recht schnell..auf der idee von Marco13 bzw aus Long (hingegen ohne Tabelle)
 
Zustimmen 0
Hab auch gerade gemerkt, dass mein Code nicht ging...

Aber man könnte beides kombinieren... Also so eine Formel für %1000, und dann in meinem Array nachgucken.
 
Zustimmen 0
Funktioniert:
Code: 
  public static int quersumme(int zahl) {
    int sum = 0;
    while (zahl > 0) {
      int temp = zahl / 1000;
      sum += SUM[zahl - (temp << 10) + (temp << 4) + (temp << 3)];
      zahl = temp;
    }
    return sum;
  }
 
Zustimmen 0
Status
Nicht offen für weitere Antworten.

Aktuelle Jobs

Neue Themen

Ähnliche Themen

(Integer) Liste nach aufsteigender Summe der Ziffern sortieren (mit Bedingung)
Antworten: 8
die Summe der (Dezimal-) Ziffern von n3 gleich n ist.
Antworten: 9
Arabische Ziffern in römische Ziffern
Antworten: 1
Anzahl der Ziffern der kürzesten Zahl aus einem zurückliefern
Antworten: 1
Anzahl der Ziffern einer Zahl
Antworten: 10

Zurück
Oben