Datentypen Speicheroptimierung

[Nico_G]

Hi,

ich hab mal wieder was ;-)

Zu meinem Problem. Den folgenden Java-Code habe ich geschrieben, um sämtliche Permutationen einer Zahlenfolge zu bestimmen.

Aus 123 wird also: 1,2,3,12,21,13,31,23,32,123,132,213,231,312,321

Bis neun Ziffern klappt das ganze ganz gut, aber bei allem darüber hinaus bricht das System zusammen. Also die Laufzeit wird astronomisch, bzw. Eclipse schmiert komplett ab.

Ich vermute mal das es an der verketteten ArrayListe liegt. Habt ihr da Ideen welcher Speichertyp empfehlenswert wäre? Ich hatte es schon überlegt Mengen, also java.util.Set zu nehmen. Aber dann habe ich das Problem das keine Duplikate vorkommen dürfen. Also 21 würde im obrigen Beispiel z.B. rausfallen.

Naja, vielleicht habt ihr ja ne Idee zur optimierung.

Lg.

Nico

Edit: Der interessante Teil beginnt ab Zeile 40

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;

public class Permutation {

	private static int endIndex;

	private static ArrayList<ArrayList> list = new ArrayList<ArrayList>();

	

        public static ArrayList<ArrayList> permutation(int count) {
		Set<Set<Integer>> subSets = SubSets.createSubSets(count);
		list = new ArrayList<ArrayList>();

		String s = new String();
		Iterator it1 = subSets.iterator();

		while (it1.hasNext()) {
			s = new String();
			Set localSet = (Set) it1.next();
			Iterator it2 = localSet.iterator();
			while (it2.hasNext()) {
				s = s + it2.next().toString();
			}
			endIndex = s.length() - 1;
			permut(s.toCharArray(), endIndex);
		}
		return list;
	}

	private static void swap(char[] a, int i, int j) {
		char local = a[i];
		a[i] = a[j];
		a[j] = local;
	}

	private static void permut(char[] a, int endIndex) {
		if (endIndex == 0) {
			ArrayList<Integer> set = new ArrayList<Integer>();
			for (char c : a) {
				set.add(Integer.parseInt(String.valueOf(c)));
			}
			list.add(set);
			
		} else {
			permut(a, endIndex - 1);
			for (int i = 0; i <= endIndex - 1; i++) {
				swap(a, i, endIndex);
				permut(a, endIndex - 1);
				swap(a, i, endIndex);
			}
		}
	}
}

 

[SlaterB]

ohne SubSets.createSubSets() ist nicht komplett klar, was hier passiert,
aber sieht für mich danach aus als werden count Sets erstellt mit Zahl 1, dann 1,2, dann 1,2,3 usw., richtig?

ein Fehler und auch etwas Performance-Bremse ist dein char[],
gerade ab 10 werden die Werte zweistellig, im char[] zwei Stellen,
beim Vertauschen betrachest du aber jede Stelle einzeln, statt 10 also '1' und '0' doppelt im Array

das Parsen der Ziffern ist dann auch unnötig langsam,
statt char[] nimm lieber ein Integer[], da kannst du genauso vertauchen und die Integer einfach übernehmen

---

ein Set wird nicht schneller als eine Liste sein,
wobei ich nicht verstehe was du mit Doppelten meinst, '21' ist nicht doppelt,

in jedem Teilergebnis sollten die Zahlen nicht doppelt sein und in der Ergebnisliste auch kein doppeltes Teilergebnis, das wäre ja falsch

-------

bei
> for (int i = 0; i <= endIndex - 1; i++) {
geht i wohl einen zu hoch

-----
eine wirkliche Lösung sehe ich nicht, egal ob Geschwindigkeit verdoppelt usw, mit höheren n steigt der Aufwand mit Fakultät,
schlimmer als exponentiell,
4 Mio. oder 40 Mio. oder 400 Mio. Kombinationen schreiben sich nicht von selbst in eine Liste,
das dauert seine Zeit

 

[Spacerat]

Ich würde mir um die ArrayList keine Gedanken machen, der Performaceeinbruch bzw. die Speicherexplosion wird bei steigender Anzahl an Stellen und Ziffern eh' irgendwann astronomisch und nahezu unberechenbar. Dann auch noch per Bruteforce alle möglichen Permutationen herausfinden wollen... mach' 'nen Haken dran. Verschlüsselungssysteme bauen nicht ohne Grund auf solch' bitteren Tatsachen auf.
Evtl. hilfst dir ja 'ne Permutationsmatrix -> Permutation ? Wikipedia

 

[Nico_G]

Vielen Dank für die Antworten.

@SlaterB
Guter Tip mit dem Char. Jetzt funktoniert es auch für Werte ab 10 =)

Ich dachte halt das es da echt noch ne gute Optimierung gäbe, ist aber auch nicht so schlimm.

Gruß

Nico