[Java] Datenstruktur - Array schon drin?

[secret_3des]

Hi!

Ich steh gerade etwas auf dem Schlauch.. Wie realisiere ich folgendes am effizientesten:

Also ich hab eine "Menge" von Kombinationen, z.B.
0 0 1
0 15 0
0 2 0
0 2 0
0 15 0
1 0 0
2 0 0
1 0 0
..

Jetzt will ich die verarbeiten und zwar so, dass ich jede Kombinationen nur einmal im Resultat habe. Ich muss also überprüfen ob ich die Kombination x y z schon mal "angefasst" habe.

Gibt es eine Datenstruktur / Möglichkeit dafür, die besonders gut geeignet ist?

Viele Grüße,
Tom

 

[TheNoxier]

HashMap<String, Integer[]>

Also Key den String
Zahl1 + "_" + Zahl2 + "_" + Zahl3

Und als Value die Zahlen in welcher form die du auch immer hast. z.b. eben Integer[]

Da jeder Key nur einmal vergeben werden kann, hast du nachher als values() nur noch jeden Kombi ein mal.


nox, dem das mal eben so eingefallen ist


edit, ich könnte morgen in der arbeit mal nachschauen ob es was schnellers/besser als die HashMap gibts, aber was bessere fählt mir gerade nicht ein.

 

[secret_3des]

Hi!

Danke für die schnelle Antwort - und das um die Zeit! ;-)

Ich hab das ganze jetzt implementiert.. und das mit dem hinzufügen klappt auch prima. Nur das auslesen funktioniert aus mir unerklärlichen Gründen nicht..

Also im Debug-Modus seh ich, dass in der HashMap folgende Werte sind:

{1, 0, 0, =[Ljava.lang.Long;@1cdfd19, 0, 15, 0, =[Ljava.lang.Long;@1cdfd19, 0, 0, 1, =[Ljava.lang.Long;@1cdfd19}

Also: 1,0,0 + 0,15,0 + 0,0,1

Wenn ich mit

for (Long[] levelK : levelKombis.values()) {..}

die HashMap durch gehe, bekomme ich aber dreimal 0,15,0.. Muss ich das verstehen? Wo könnte das Problem liegen?

Viele Grüße,
Tom

PS. Die String-Operationen kosten halt auch relativ viel Zeit.. Was besseres fällt mir aber auch nicht wirklich ein. Wenn dir noch eine andere Idee kommt, wäre ich froh, wenn du sie mir verrätst. ;-)

Gibt es eine Möglichkeit einen StringBuffer zu "leeren" ohne new StringBuffer() aufzurufen? Das kostet viel Speicher.. und die GC braucht wieder einiges an Zeit zum Aufräumen..

 

[1668mib]

Wenn du weißt, wie groß die Zahlen maximal werden können, kannst du auch mit Multiplikation arbeiten

HashMap<Integer, Integer[]>
Und der erste Int ist dann z.B. 10000 * Zahl1 + 100 * Zahl2 + Zahl3

die Faktoren 10000 und 100 musst du halt anpassen je nach Zahlengrößen...


Edit: Es bieten sich vielleicht auch Faktoren auf 2er Basis an, also z.B. 1024 und 1024*1024

 

[secret_3des]

Ich weiß nicht wie groß die Zahlen werden und ich weiß auch nicht wieviele es sind. Es können 2 aber auch 10 oder 10 sein. Das mit dem multiplizieren (speziell mit Zweier-Potenzen) ist an sich eine gute Idee, aber da würde ich wohl bald an die Zahlenbereichsgrenzen stoßen. Danke trotzdem für den Vorschlag!

Hat jemand irgendeine Idee wieso die HashMap nicht korrekt durchlaufen wird? Also obwohl drei unterschiedliche Arrays drin stehen, bekomme ich drei mal dieselben Werte.. (s.o.).

 

[TheNoxier]

wie heisst den dein code nachdem


for (Long[] levelK : levelKombis.values()) {


Sprich wie gibst du es aus?

 

[secret_3des]

Oh, hab gar nicht gesehen, dass nochmal geantwortet wurde. Sorry!

Also ich mache folgendes in der Schleife:

for (Long[] levelK : levelKombis.values()) {
				strBuff1.append("( ");
	
				for (int j = 0; j < prefCount; j++) {
	
					if (j == prefCount - 1)
						strBuff1.append(" lvl" + (j) + " = " + levelK[j]);
					else
						strBuff1.append(" lvl" + (j) + " = " + levelK[j]
								+ andString);
				}
	
				strBuff1.append(")" + orString);
				
			}

Die (große) Schleife sollte doch jedesmal ein neues levelK-Array "anfassen", oder?

 

[TheNoxier]

Der Code geht.
Hab die obigen Beispieldaten verwendet und den Rest sinnvoll befüllt.
Performance Hinweise, sofern du es nicht schon weisst:

Verwende StringBuilder anstatt StringBuffer, solange die nicht mit mehreren Thread gleichzeitig drauf zugreifst. (StringBuffer ist synchronized and StringBuilder nicht)
Verwende immer .append() und keine "+" damit nicht neue String's erstellt werden.

Ansonsten hier ist mein Code: (Java 1.5)

 @SuppressWarnings("boxing")
   public static void main(String[] args) {
      int prefCount = 3;
      String andString = " | ";
      String orString = "\n";
      HashMap<String, Long[]> levelKombis = new HashMap<String, Long[]>();
      levelKombis.put("1,0,0", new Long[] { 1l, 0l, 0l });
      levelKombis.put("0,15,0", new Long[] { 0l, 15l, 0l });
      levelKombis.put("0,0,1", new Long[] { 0l, 0l, 1l });
      levelKombis.put("0,15,0", new Long[] { 0l, 15l, 0l });
      levelKombis.put("0,0,1", new Long[] { 0l, 0l, 1l });
      levelKombis.put("0,15,0", new Long[] { 0l, 15l, 0l });
      levelKombis.put("0,0,1", new Long[] { 0l, 0l, 1l });
      levelKombis.put("0,15,0", new Long[] { 0l, 15l, 0l });
      levelKombis.put("0,0,1", new Long[] { 0l, 0l, 1l });
      levelKombis.put("0,15,0", new Long[] { 0l, 15l, 0l });
      levelKombis.put("0,0,1", new Long[] { 0l, 0l, 1l });

      StringBuilder strBuff1 = new StringBuilder();

      for (Long[] levelK : levelKombis.values()) {
         strBuff1.append("( ");

         for (int j = 0; j < prefCount; j++) {
            if (j == prefCount - 1) {
               strBuff1.append(" lvl").append(j).append(" = ").append(levelK[j]);
            } else {
               strBuff1.append(" lvl").append(j)
                  .append(" = ").append(levelK[j]).append(andString);
            }
         }
         strBuff1.append(")").append(orString);
      }
      System.out.println(strBuff1);
   }

Ausgabe:

(  lvl0 = 0 |  lvl1 = 0 |  lvl2 = 1)
(  lvl0 = 0 |  lvl1 = 15 |  lvl2 = 0)
(  lvl0 = 1 |  lvl1 = 0 |  lvl2 = 0)

Die (große) Schleife sollte doch jedesmal ein neues levelK-Array "anfassen", oder?

Ja macht sie auch

nox

 

[secret_3des]

Vielen Dank für's Testen!

Ich hab das Problem jetzt identifiziert.. das Problem war, dass ich für das Befüllen der HashMap immer das gleiche Long-Array verwendet habe. Dadurch hatten alle Einträge die gleich ID und es wurde immer nur das mittlere (der drei) ausgewählt..

Geht das nicht irgendwie ohne jedesmal ein neues Objekt zu erzeugen? Das sind auf diese Weise sonst über 5000 Objekte die erzeugt werden. Das braucht wieder (unnötig) Speicher..

Also meine Methode zum Befüllen sieht im Moment so aus:

HashMap<String, Long[]> levelKombis = new HashMap<String, Long[]>();
			Long[] currLvl = new Long[prefCount];
		
			for (ArrayTuple atLvlValues : results) {
	
				for (int i = startIndex, j = 0; i < prefCount + startIndex; i++, j++) {
					currLvl[j] = atLvlValues.getLong(i);
					levelId += currLvl[j] + ", ";
				}
					
				levelKombis.put(levelId, currLvl);
				[B]currLvl = new Long[prefCount];[/B]
				levelId = "";
			}

Viele Grüße,
Tom

PS. Danke auch für den Tipp mit dem StringBuilder und den append.

 

[TheNoxier]

Hab mich mal kurz umgesehen und folgendes gefunden:

Aus

 String itemList = "";

 itemList=itemList + items[i].description;

Macht der javac compiler ein:

itemList=new StringBuffer().append(itemList).
          append(items[i].description).toString();

Also am Besten bei String Aktionen wie "+=" oder "+", vor allem die, die in einer Schleife arbeiten immer per Hand StringBuffer, oder in single-thread umgebung, StringBuilder verwenden.

http://thought-bytes.blogspot.com/2007/03/java-string-performance.html

Aber zu deinem Code:

Wie wäre es mit: (Type long anstatt Class Long im gesamten code)

 for (ArrayTuple atLvlValues : results) {

         //starte mit groesse 10 um das auto-resizen am anfang zu verhindern.
         levelId = new StringBuilder(10);
         currLvl = new long[prefCount];
         
         for (int i = startIndex, j = 0; i < prefCount + startIndex; i++, j++) {
            currLvl[j] = atLvlValues.getLong(i);
            levelId.append(currLvl[j]).append(",");
         }
            
         levelKombis.put(levelId.toString(), currLvl);
         
      }

Sofern keine auto-boxing von long nach Long passiert, sollte das schneller sein. - denk ich


Gruß
nox

EDIT:

man könnte sogar den StringBuilder in der HashMap lassen. String oder StringBuilder macht da auch keine Unterschied mehr aus. Und wir sparen uns die zeit für den "toString" ...

 

[secret_3des]

Also am Besten bei String Aktionen wie "+=" oder "+", vor allem die, die in einer Schleife arbeiten immer per Hand StringBuffer, oder in single-thread umgebung, StringBuilder verwenden.

Schöner Programmierstil ist es wohl allemal. Von der Performance macht es aber wohl (in diesem Fall) keinen Unterschied, da ich den StringBuilder / StringBuffer ja immer wieder leeren bzw. neu erzeugen muss.
Auf jeden Fall danke, dass du dich da schlau gemacht hast. Ist interessant zu wissen.

Wie wäre es mit: (Type long anstatt Class Long im gesamten code)

Ja, gute Idee. :-)

man könnte sogar den StringBuilder in der HashMap lassen. String oder StringBuilder macht da auch keine Unterschied mehr aus. Und wir sparen uns die zeit für den "toString" ...

Das funktioniert denke ich nicht, da zwei StringBuilder-Objekte nicht gleich sind (auch nicht bei gleichem Inhalt). Wenn ich nur eines verwende, habe ich dasselbe Problem wie "früher", dass der HashWert immer gleich ist und deshalb nur ein einziges Element hinzugefügt wird.
Wenn du aber einen Vorschlag hast, wie man das ohne toString() realisieren kann, lasse ich mich gerne eines besseren belehren. ;-)

Ich werde demnächst mal ein paar Performanceuntersuchungen bei einigen 10.000 (100.000) solchen Kombinationen anstellen.

Viele Grüße,
Tom

 

[TheNoxier]

Man könnten den StringBuilder extenden zu einer neuen Klasse, und dort equals und hashCode überschreiben