49-bit-zahl mit genau 6 Einsen bauen?

[berndoa]

Hallo, ich hadere immer noch mit meinem kleinen Lottoproblem.
Dort hatte ich ursprünglich eine Lottokombi mit 6 Zahlen erst als int[6] definiert und später dann zum Berechnen in eine long umgewandelt, deren bits relevant waren.

Jetzt will ich mein Programm mal überarbeiten dahingehend dassich von Anfang an mit einer 49 bit langen Zahl arbeite, die genau 6 Einsen enthält.
Nur die Frage, wie genau gehe ich da systematisch alle möglichen Zahlen durch?
Natürlich möglichst effizient und "performant" weils ja um ca. 13 Millionen zu generierende Zahlen geht.

Klar könnte ich mit 6 forschleifen da irgendwa sfabrizieren, aber ist das die beste Lösung?
Da gibts doch bestimmt ein paar Tricksereien, wie das besser geht

 

[Neumi5694]

Parallelisierung.

Wenn du das Ganze auf mehrere Teilaufgaben aufteilst, sparst du einiges an Zeit, wobei 13 Millionen Kombinationen jetzt nicht all zu viel sind. Wenn du dann auch noch die Grenzen mit berücksichtigst (das 5. Bit kann nicht an der 49. Stelle liegen, die Stelle ist zwingend höher als die des 4. Bits und garantiert max. 48), dann sollte das schon passen.
Du kannst z.B. 8 Threads erstellen, jeweils mit einem verschiedenen Bereich für das 1. Bit, den sie abdecken sollen.
Dabei relevant: Der Thread, der den obersten Bereich abdeckt, wird pro Stelle viel weniger lang brauchen, als der Thread, der den untersten Bereich abdeckt. Du solltest also für den "letzten" Thread einen deutlich größeren Bereich verwenden als für den ersten.
(Ist das erste Bit markiert, so handelt es sich beim Rest um "5 aus 48". Ist das 30. markiert, so handelt es sich um "5 aus 19", was natürlich deutlich weniger Zeit in Anspruch nimmt, kannst dir das Verhältnis zwischen den Stellen ja mal ausrechnen).

Um Schleifen wirst du woihl kaum rumkommen. Anstatt mehrerer gleicher Schleifen hintereinander zu erstellen mit wenig Inhalt ist es besser, eine zu verwenden, in der mehr passiert.


ps: Wenn du mal alles fertig hast, kannst du dich ja mal an "unser" System wagen, beim Superenalotto gibt's nicht 49, sondern 90 Zahlen.
Unter Programmierern bekannt als das fröhliche Hash-Raten.

 

[berndoa]

Ich bin mir nicht sicher ob wir über dasselbe sprechen:
Wenn wir stattdessen die 7er kombis mit genau 4 einsen suchen, dann suche ich die zahlen
0011110, 0011101,0011011,0010111,0001111, usw.
halt alle arten wie die 4 einsen verteilt sein können an den 7 stellen.

So das prinzip, nur mit eben 49 stellen und 6 einsen.

Später bzw. in einem anderen thrad habe ich übrigens auch das problem, nur mit 13millionen stellen und hunderttausenden einsen.
vermutlich ist das dort aber schlicht gar nicht machbar ohne Supercomputer vom Cern :-/

 

[Neumi5694]

Edit: Sorry, hab gerade mit 6 aus 7 gedacht anstatt 4 aus 7. Aber das Prinzip ist das Gleiche

Doch, ich mein schon das.
0000000
Zuerste wird mal 1 Bit gesetzt
1000000
Für das nächste bleiben dir also noch 2 Möglichkeiten.
a) 1100000
b) 1010000
Mehr sind es nicht, da du ja noch 4 Einsen setzen willst.
In Fall a) geht's also weiter mit 4 aus 5.
Fall b) wäre 4 aus 4 mit nur einer möglichen Belegung.

Das erste Bit kann natürlich auch an zweiter Stelle stehen
0100000
Hier gibt es, dann ebenfalls nur noch eine Möglichkeit (5 aus 5)
0111111

Das erste Bit kann NICHT an einer höheren Stelle als der ersten oder zweiten stehen, dann bleibt kein Platz mehr für die anderen Bits.

 

[Neumi5694]

Also:
Index des ersten Bits [0 .. 48-5]
Index des zweiten Bits[IndexBit1+1 .. 48-4]
Index des dritten Bits[IndexBit2+1 .. 48-3]
Index des vierten Bits[IndexBit3+1 .. 48-2]
Index des fünften Bits[IndexBit4+1 .. 48-1]
Index des sechsten Bits[IndexBit5+1 .. 48]

Du kannst also problemlos die Schleife des ersten Bits auf mehrere Threads aufteilen.

 

[berndoa]

Parallelisierung.

Wenn du das Ganze auf mehrere Teilaufgaben aufteilst, sparst du einiges an Zeit, wobei 13 Millionen Kombinationen jetzt nicht all zu viel sind. Wenn du dann auch noch die Grenzen mit berücksichtigst (das 5. Bit kann nicht an der 49. Stelle liegen, die Stelle ist zwingend höher als die des 4. Bits und garantiert max. 48), dann sollte das schon passen.
Du kannst z.B. 8 Threads erstellen, jeweils mit einem verschiedenen Bereich für das 1. Bit, den sie abdecken sollen.
Dabei relevant: Der Thread, der den obersten Bereich abdeckt, wird pro Stelle viel weniger lang brauchen, als der Thread, der den untersten Bereich abdeckt. Du solltest also für den "letzten" Thread einen deutlich größeren Bereich verwenden als für den ersten.
(Ist das erste Bit markiert, so handelt es sich beim Rest um "5 aus 48". Ist das 30. markiert, so handelt es sich um "5 aus 19", was natürlich deutlich weniger Zeit in Anspruch nimmt, kannst dir das Verhältnis zwischen den Stellen ja mal ausrechnen).

Um Schleifen wirst du woihl kaum rumkommen. Anstatt mehrerer gleicher Schleifen hintereinander zu erstellen mit wenig Inhalt ist es besser, eine zu verwenden, in der mehr passiert.


ps: Wenn du mal alles fertig hast, kannst du dich ja mal an "unser" System wagen, beim Superenalotto gibt's nicht 49, sondern 90 Zahlen.
Unter Programmierern bekannt als das fröhliche Hash-Raten.

Ich weiß nicht, schleifentechnisch hätte ich in etwa sowas gemacht:

for(int a=1;a<=(49-5);a++){
  for(int b=a+1;b<=(49-4);b++){
    for(int c=b+1;c<=(49-3);c++){
      for(int d=c+1;d<=(49-2);d++){
        for(int e=d+1;e<=(49-1);e++){
          for(int f=e+1;f<=(49-0);f++){
              long p=1L<<(49-a)
                       +1L<<(49-b)
                       +1L<<(49-c)
                       +1L<<(49-d)
                       +1L<<(49-e)
                       +1L<<(49-f);
          }
        }
      }
    }
  }
}

bzw. um compilerfehler zu vermeiden eben long p; vor den Schleifen definiert und in den Schleifen ganz innen nur immer wieder geändert.

Könnte ich 44 threads starten wobei sich jeder um einen anderen Fall der äussersten for schleife kümmert

 

[berndoa]

Vielleicht könnte ich eine 13 mille große zahl als long array handeln?

Anderer Gedanken:
Anstelle davon, mit 13Millionen bit langen Zahlen zu arbeiten, wäre es ggbfls. vielleicht sinnvoller, diese als Folge von Nullstreaks zu speichern?


Also bspw. die zahl 1000010 stattdessen zu speichern mittels der Info
"ab index=6 4 nullen, ab index=2 1 null" oder so?

Weil zumindest anfangs, solange ich noch nicht vielle longs geodert habe, bestehen die ja zu 90% aus nullen.
Oder halt umgekehrt die position und länge der 1er-streaks zu speichern.
Lässt sich ja auch vom einen ins andere umrechnen bei bedarf.

Wäre das irgendwie sinnvoll und auch praktisch umzusetzen?

Halt so ähnlich wie es auch bei kommazahlen mit mantisse, potenz und co. gemacht wird wenn man seeeehr lange zahlen nicht ausschreiben will

 

[Neumi5694]

1. Gefühlt würde ich von rechts nach links auffüllen, anstatt ständig 49-x, aber das ist Geschmackssache. Am Ende ändert sich dadurch nichts.

Deine Vorgehensweise mit den Bitmasken passt schon. Nur verschiebst du aktuell jedesmal alle 6 Bits um den jeweiligen Wert und addierst dann.
Besser:
2. Für jede Schleife nur eine Verschiebung.
3. Verknüpfen der Bitmasken mit ODER (sinnvoller als eine Addition)

for(int a=1;a<=(49-5);a++){
    long bitmaskeA = 1L << (49-a);//Nur einmal pro A anstatt jedes einzelne Mal
    for(int b=a+1;b<=(49-4);b++){
        long bitmaskeB = bitmaskeA | (1L << (49-b));
        for(int c=b+1;c<=(49-3);c++){
            long bitmaskeC = bitmaskeB | (1L<<(49-c));
...

Damit hast du viel weniger Verschiebeoperationen und anstatt der vergleichsweise rechenaufwendigen Addition eine billige bitweise Oder-Verknüpfung.
4. Du berechnest für jeden Schleifendurchgang 49-irgendwas.
Diese Berechnung wird jedesmal durchgeführt. Ersetze den Oberwert durch eine Variable.

int maxD=49-2
for(int d=c+1;d<=maxD;d++){

Kann natürlich sein, dass der Compiler das erkennt und automatisch optimiert, aber ich würde mich nicht darauf verlassen
Auch kann das alles völlig für den Allerwertesten sein, da die CPU-Pipeline sämtliche Optimierungsversuche zunichte macht. Früher auf den Pre-Pentium CPUs hätte das auf jeden Fall was gebracht. Einen Versuch ist es aber allemal wert.

5. Deine Idee mit den x Nullen bringt nichts, damit blähst du das Ganze nur auf. Jeder deiner Werte belegt nur 8 Byte. Diese zu beschreiben ("die nächsten 15 Bits sind '0', dann folgen 2 x '1', dann wieder '0', dann ...") braucht viel mehr Platz als die Zahl selbst.
Diese Art Kompression würde nur funktionieren, wenn du die Bits in Textform als "0" und "1" abspeichern würdest. Da würde jede Zahl 64 Byte belegen, da könnte es sich lohnen.
An verlustfreier Kompression wurde schon lange getüftelt, bevor es Computer gab, Ende der 70er wurde das Ganze salonfähig.

Und was die Parallelisierung angeht, kannst du das so machen, das ein Thread a von 1 bis 3 behandelt, der nächste von 4 bis 10, denn 11 bis 30, 31 bis 50 oder so ähnlich. Rechne am besten mal die di versen "(49-a) über 5" aus um auf eine gleichmäßige Auslastung der Threads zu kommen.

 

[Neumi5694]

ps: Mir ist gerade eingefallen, dass du deinen Speicherbedarf auf der Platte um ein Achtel reduzieren kannst.
Wie du bereits gesagt hast, sind die ersten 15 Stellen ja immer 0. Du kannst beim Speichern also jedesmal ein Byte einsparen (also 7 Byte anstatt 8).

Es geht auch noch heftiger:
Wenn du jeweils 8 Zahlen miteinander speicherst, kannst du das so machen, dass du bei allen Zahlen nur 48 Bit speicherst und das jeweils einzelne Bit aller 8 Zahlen in einem Zusatzbyte. Entweder so, oder die 49 relevanten Bits der Zahlen gleich direkt aneinanderhängen. So oder so belegen 8 Zahlen dann 49 Byte anstatt 64.

Beim Auslesen musst du das Ganze dann entsprechend auseinanderfiseln.

Wenn du Kompression ausprobieren willst, versuch mal, ein paar Millionen Werte nicht direkt auf die Platte zu schreiben, sondern in einen Zip-Stream.

 

[mihe7]

Zum Thema "Parallelisieren": mein Rechner braucht für die sequentielle Variante 50 bis 60 ms, um ein long Array mit allen ~ 14 Mio. Zügen zu berechnen. 14 Mio. longs sind etwa 112 MB. Ob sich da Parallelverarbeitung/Speichern lohnt?

 

[Neumi5694]

Wohl nicht, wenn man's nur einmal braucht.

 

[MarvinsDepression]

Zum Thema "Parallelisieren": mein Rechner braucht für die sequentielle Variante 50 bis 60 ms, um ein long Array mit allen ~ 14 Mio. Zügen zu berechnen. 14 Mio. longs sind etwa 112 MB. Ob sich da Parallelverarbeitung/Speichern lohnt?

Ne, dafür ist ein Thread ausreichend. Aber jede Permutation mit allen anderen zu vergleichen (incl. bitCount)... das könnte sich lohnen.

P.S.: Wie erstellst Du die möglichen Permutationen. Ich mach das zufuß und halte den Code für für zu unübersichtlich/umständlich. Es fällt mir aber nichts anderes ein.

private static final int PERM_49_OVER_6 = 13_983_816;
private static final int MAX = 49;
public static final int NUMBER_OF_VALUES = 6;

    public static long[] getPermutatioms() {
        final long[] perm = new long[PERM_49_OVER_6];
       
        perm[0] = (1L << NUMBER_OF_VALUES) - 1; // 00..0111111;
       
        for (int i = 1; i < perm.length; i++) {
            perm[i] = getNextPerm(perm[i - 1]);
        }
        return perm;
    }
   
    private static long getNextPerm(long bitPattern) {
        for (int bit = 1; bit < MAX; bit++) {
            if (bitIsSet(bitPattern, bit-1) && !bitIsSet(bitPattern, bit)) {
                bitPattern = shiftOnlyOneBit(bitPattern, bit-1);
                return resetLSB_Part(bitPattern, bit);
            }
        }
        return 0L; // sollte nicht vorkommen
    }
   
    private static boolean bitIsSet(long bitPattern, int bit) {
        return (bitPattern & (1L << bit)) != 0;
    }
   
    private static long eraseBit(long bitPattern, int bit) {
        long bitmask = ~(1L << bit);
        return bitPattern & bitmask;
    }
   
    private static long setBit(long bitPattern, int bit) {
        long bitmask = 1L << bit;
        return bitPattern | bitmask;
    }
   
    // bit = 3; 01001001 -> 01010001
    private static long shiftOnlyOneBit(long bitPattern, int bit) {
        bitPattern = eraseBit(bitPattern, bit);
        return setBit(bitPattern, bit + 1);
    }
   
    // bit = 5; 11111010 -> 11100111
    private static long resetLSB_Part(long bitPattern, int bit) {
        long bitmask = (1L << bit) - 1;
        int count = Long.bitCount(bitPattern & bitmask);
        bitPattern &= ~bitmask;
        return bitPattern | ((1L << count) - 1);
    }

 

[mihe7]

P.S.: Wie erstellst Du die möglichen Permutationen. Ich mach das zufuß und halte den Code für für zu unübersichtlich/umständlich. Es fällt mir aber nichts anderes ein.

So wie es @berndoa und @Neumi5694 beschrieben haben:

public long[] allDraws() {
  long time = System.currentTimeMillis();
  long[] numbers = new long[13983816];
  int count = 0;
  for(int a=1;a<=(49-5);a++){
    long aValue = 1L << (a-1);
    for(int b=a+1;b<=(49-4);b++){
      long bValue = 1L << (b-1);
      for(int c=b+1;c<=(49-3);c++){
        long cValue = 1L << (c-1);
        for(int d=c+1;d<=(49-2);d++){
          long dValue = 1L << (d-1);
          for(int e=d+1;e<=(49-1);e++){
            long eValue = 1L << (e-1);
            for(int f=e+1;f<=(49-0);f++){
                long fValue = 1L << (f-1);
                numbers[count] = aValue | bValue | cValue | dValue | eValue | fValue;
                count++;
            }
          }
        }
      }
    }
  }
  System.out.println(count + " draws in " + (System.currentTimeMillis() - time) + "ms");
  return numbers;
}

 

[MarvinsDepression]

Was für ein Glück, dass es nicht 23 aus 49 heißt 😂
Das ist dochl mal eine schöne Aufgabe zum thema Rekursion. Wer traut sich?

 

[mihe7]

Was für ein Glück, dass es nicht 23 aus 49 heißt 😂

Dann hätte ich es umgeschrieben Wäre allerdings nicht so "schön" gewesen.

Das ist dochl mal eine schöne Aufgabe zum thema Rekursion. Wer traut sich?

Das geht auch ohne: mal mit Arrays: mit 6,5,4,3,2,1 anfangen. In jeder Iteration wird erstmal die erste Stelle bis 49 hochgezählt, so dass die Stelle am Ende 50 ist. Dann zählt man so lange die nächste Stelle weiter wie
a) es noch eine nächste Stelle gibt
b) die atuelle Stelle > 49 - stelle ist.
Anschließend setzt man von hinten nach vorne jeden Wert, der größer als der maximal zulässige ist, auf den Wert der Folgestelle + 1

Beispiel:
49,48,4,3,2,1
50,48,4,3,2,1 (innere Schleife terminiert, weil 50 > 49)

an der aktuellen Stelle steht eine 50 > 49 - 0 und es gibt eine weitere Stelle, also nächste Stelle hochzählen (48 -> 49)
an der aktuellen Stelle steht eine 49 > 49 - 1 und es gibt eine weitere Stelle, also nächste Stelle hochzählen (4 -> 5)
an der aktuellen Stelle steht eine 5 < 49 - 2 -> Ende

Daraus ergibt sich erstmal
50, 49, 5, 3, 2, 1

Und jetzt von hinten nach vorne durchgehen:
1 <= 49 - 5 -> bleibt
2 <= 49 - 4 -> bleibt
3 <= 49 - 3 -> bleibt
5 <= 49 - 2 -> bleibt
49 > 49 - 1 -> 49 -> Wert der Folgestelle (5) + 1 = 6
50 > 49 - 0 -> 50 -> Wert der Folgestelle (6) + 1 = 7

Ergebnis:
7, 6, 5, 3, 2, 1

 

[berndoa]

Wie viele Threads kann man eigentlich gleichzeitig laufen lassen?

Was für ein Glück, dass es nicht 23 aus 49 heißt 😂
Das ist dochl mal eine schöne Aufgabe zum thema Rekursion. Wer traut sich?

Rekursion würde ich da erst gar nicht anfangen.
Die maximale Rekursionstiefe ist doch lächerlich niedrig, da kriegt man ruckzuck einen Error

 

[mihe7]

Die maximale Rekursionstiefe ist doch lächerlich niedrig, da kriegt man ruckzuck einen Error

Es sind hier ja nur 6 Stellen.

 

[MarvinsDepression]

Wie viele Threads kann man eigentlich gleichzeitig laufen lassen?

Hier im Forum sind auf jeden Fall mehr Threads möglich, als auf meinem Computer
Nein, im ernst. Theoretisch kannst Du nahezu beliebig viele Threads gleichzeitig laufen lassen. Das ist aber nicht sinnvoll. Wenn es darum geht, deinen Prozessor möglichst gut auszulasten, dann reichen auf alle Fälle soviele parallele Threads, wie Du Rechenkerne hast. Eher einer weniger, damit das System noch etwas Luft hat und freezingeffekte vermieden werden. Kommt aber auch noch darauf an, was sonst noch gleichzeitig auf deinem Computer läuft.

 

[berndoa]

Hier im Forum sind auf jeden Fall mehr Threads möglich, als auf meinem Computer
Nein, im ernst. Theoretisch kannst Du nahezu beliebig viele Threads gleichzeitig laufen lassen. Das ist aber nicht sinnvoll. Wenn es darum geht, deinen Prozessor möglichst gut auszulasten, dann reichen auf alle Fälle soviele parallele Threads, wie Du Rechenkerne hast. Eher einer weniger, damit das System noch etwas Luft hat und freezingeffekte vermieden werden. Kommt aber auch noch darauf an, was sonst noch gleichzeitig auf deinem Computer läuft.

Macht es eigentlich sinn, wenn ich sagen wir mal 5 Threads nutze und alle Zahlen (1,....)(2,....) bis (44,...) dass ich hingehe und lasse jeden thread die zahlen bearbeiten die mit einer zahlmod5=threadnummer beginnen?
übertrieben ausgedrückt aber im prinzip:
thread1 macht 1, thread2 2,...thread5 5, thread6 1, thread 7 2, usw.
halt relativ perfekt verteilt.
Dann werden in etwa 5 zahlenreihen gleichzeitig abgearbeitet.

 

[Neumi5694]

Hier wäre die Rekursionstiefe 5, kein Error.
An Rekursion hatte ich auch schon gedacht, aber da hier eh alles fix vorgegeben ist, war es die Mühe nicht wert. Die Schleifen reichen.

@berndoa Das mit dem Mod vergiss lieber, nutze als Offset die Anzahl der verschiedenen Werte, die es vorher geben konnte.
Perfekt verteilt ist es eben nicht, da 1 viel länger dauert als 2, für 1 gibt es mehr 5 aus x Werte.

Wennn das Ganze aber wirklich nur eine Minute dauert, dann lohnt sich das wirklich nicht. Die Zahlen speicherst du dann in eine Datei (14 Millionen Werte á 4 Byte = 56 MB), von mir aus noch gezippt. Lies das Ganze dann bei Programmstart ein und das war's.

Die Minute Laufzeit kommt mir im Nachhinein ziemlich lang vor.
Kann mir irgendwie nicht vorstellen, dass das Auslesen aus einer Datei weniger lange brauchen sollte (56 MB gehen ja in NullKommaNix) als das Berechnen.
edit: nvm, hab gerade oben den Code gesehen, Frage beantwortet.

 

[mihe7]

Wennn das Ganze aber wirklich nur eine Minute dauert

Eine Minute?!? Ich habe von Millisekunden geschrieben

 

[Neumi5694]

Eine Minute?!? Ich habe von Millisekunden geschrieben

Argh .... ich brauch mehr Schlaf.