Große Anzahl Objekte zufällig im Raster verteilen



  • Angenommen, ich hätte durchnummerierte Objekte und das wären ganz schön viele, sagen wir mal 10^40 und ich möchte die pseudozufällig auf ein Raster der Größe 10^20 x 10^20 verteilen.

    Im voraus kann ich das natürlich nicht berechnen. Also bräuchte ich einen Algorithmus, der on-demand für eine bestimme Position das zugehörige Objekt errechnen kann und natürlich darf dabei kein Objekt auf verschiedenen Positionen zu finden sein.

    Was für Ansätze gäbe es da? Mir fällt dazu irgendwie nichts vernünftiges ein.
    Man könnte die Bits der Position in eine neue, aber feste Reihenfolge bringen. Besonders gut ist das aber nicht: wenn sich ein Bit in der Position verändert, würde sich auch nur ein Bit im Ergebnis verändern.



  • Nimm 2 Arrays mit den Inhalten: 0...xmax und 0...ymax. Dann wendest du Random-Shuffle auf beide an und hast damit die Positionen für alle xmax*ymax-Objekte gemischt. Dabei sind Kollisionen ausgeschlossen und die Laufzeit ist linear. 🙂


  • Mod

    Andromeda schrieb:

    Nimm 2 Arrays mit den Inhalten: 0...xmax und 0...ymax. Dann wendest du Random-Shuffle auf beide an und hast damit die Positionen für alle xmax*ymax-Objekte gemischt. Dabei sind Kollisionen ausgeschlossen und die Laufzeit ist linear. 🙂

    Ich glaube, du hast die Problemstellung nicht verstanden. Es sind zu viele Objekte, um im Voraus alle Positionen zu berechnen.

    @Threadersteller: Je genauer du dein Problem beschreibst, desto besser kann man dir helfen. Sehr oft meinen Leute, dass ihr Problem auf eine bestimmte Art und Weise gelöst werden kann, und versteifen sich dann auf diesen Lösungsweg. Dabei übersehen sie oft sehr viel einfachere Lösungswege. Deine Beschreibung klingt ganz so, als wäre dein Rasterverteilungsproblem ein Teil eines Lösungsweges für ein ganz anderes Problem, welches es eigentlich zu lösen gilt.



  • SeppJ schrieb:

    Andromeda schrieb:

    Nimm 2 Arrays mit den Inhalten: 0...xmax und 0...ymax. Dann wendest du Random-Shuffle auf beide an und hast damit die Positionen für alle xmax*ymax-Objekte gemischt. Dabei sind Kollisionen ausgeschlossen und die Laufzeit ist linear. 🙂

    Ich glaube, du hast die Problemstellung nicht verstanden. Es sind zu viele Objekte, um im Voraus alle Positionen zu berechnen.

    Das ist mir später auch aufgefallen. Er sagte aber, dass die Objekte durchnumeriert sind. Folglich muss ja die Numerierung schon geklappt haben.

    Aber wie du schon sagst: er sollte mal genauer beschreiben, um was es geht.



  • Ist es wahrscheinlich, dass auf lange Sicht ein größerer Teil der Objekte (sprich mehr als 1%) bestimmt werden müssen? Darf auf einer Position immer nur ein Objekt sein? Stehen manche Objekte untereinander in einem Naheverhältnis und müssen deshalb auch in unmittelbarer Nähe erscheinen?

    Falls möglich: ich würde mir einmalig die Wahrscheinlichkeit "Position ist besetzt" berechnen und bei Input (x,y) einfach via Random feststellen ob die Stelle besetzt ist und dann das Objekt in hinsetzen.

    // pseudocode:
    
    const double p = 0.blabla1; // 1 dividiert durch (anzahl felder dividiert durch anzahl objekte)
    map<pos, obj> setObjects;
    int objectIndex = 1;
    
    obj getObjAt (pos)
    {
        if(setObjects.hasKey(pos)) return setObjects.get(pos);
    
        double random = getRandomDouble(0, 1);
        if(random > p)
            return null;
    
        var nextObj = myObjects.get(objectIndex)
        setObjects.put(pos, nextObj);
        return nextObj;
    }
    

    MfG SideWinder



  • Die eigentliche Aufgabe ist, alle möglichen Kombinationen mehrerer Attribute zufällig in einem Raster anzuordnen. Jedes Attribut hat einen Wertebereich, z.B.:
    A: 10-50, B: 10-50, C: 0-15.

    Auch wenn die "zufällige" Anordnung nicht perfekt zufällig ist, sollte vermieden werden, dass ähnliche Kombinationen nah zusammen stehen.

    Die Fläche ist in 3D interaktiv "begehbar", solche Muster würden also direkt ins Auge springen.

    @Andromeda
    Also, bei manchen der kleineren Problemstellungen würde diese Methode funktionieren. Z.B. bei 10^7 x 10x7, zwei Arrays der Größe 10^7 würden schon ins RAM passen.
    Ich hab ein bisschen mit solch zwei gemischten Indexarrays experimentiert. Es fällt auf, dass selbst wenn ich das noch beliebig mit Bitshuffles/xor auf die x,y-Indices und/oder das Endergebnis kombiniere, dass die Differenz zweier benachbarten Spalten und Reihen immer konstant ist. Ich bin mir nicht sicher, ob das in der Praxis ein Problem ist, aber es ist zumindest ein Muster, das sofort ins Auge springt.

    Beispiel:

    `0902 0415 0412 0908 ...

    0802 0315 0312 0808 ...

    0770 0283 0280 0776 ...

    0994 0507 0504 1000 ...

    ...`

    Das hat mich allerdings auf ein oder zwei weitere Ideen gebracht, die ich später ausprobieren werde.

    @ SideWinder
    Oha! Dabei zu schummeln, ist mir gar nicht in den Sinn gekommen. Tatsächlich wird die Zahl der untersuchten Positionen auf lange Sicht höchstens wenige Millionen betragen, das ist also tatsächlich eine pragmatische Lösung.



  • ;torstein schrieb:

    Ich hab ein bisschen mit solch zwei gemischten Indexarrays experimentiert. Es fällt auf, dass selbst wenn ich das noch beliebig mit Bitshuffles/xor auf die x,y-Indices und/oder das Endergebnis kombiniere, dass die Differenz zweier benachbarten Spalten und Reihen immer konstant ist. Ich bin mir nicht sicher, ob das in der Praxis ein Problem ist, aber es ist zumindest ein Muster, das sofort ins Auge springt.

    Das lag dann wohl am Zufallsgenerator. Bei einem guten (der z.B. kryptografischen Ansprüchen gerecht wird), dürften keine Muster entstehen.



  • Andromeda schrieb:

    Das lag dann wohl am Zufallsgenerator. Bei einem guten (der z.B. kryptografischen Ansprüchen gerecht wird), dürften keine Muster entstehen.

    Vielleicht hatte ich deine Idee auch nur falsch verstanden.
    Ich hatte das ungefähr so umgesetzt:

    const int noBits=5;
    const int dim=1<<noBits;
    std::vector<int> xiv,yiv;
    for (int i=0;i<dim;i++)xiv.push_back(i);
    for (int i=0;i<dim;i++)yiv.push_back(i);
    shuffle(xiv);
    shuffle(yiv);
    
    for (int y=0;y<dim;y++)
    {
      for (int x=0;x<dim;x++)
      {
        auto value=((xv[x])<<5)|yv[y];
      }
    }
    

    So entstehen solche Muster.



  • Ahh, der technische Begriff dazu fehlte mir bisher, aber wenn ich das richtig sehe, suche ich eine "minimale perfekte Hashfunktion". Dazu gibt es zum Glück einiges an Literatur.



  • ;torstein schrieb:

    Die eigentliche Aufgabe ist, alle möglichen Kombinationen mehrerer Attribute zufällig in einem Raster anzuordnen. Jedes Attribut hat einen Wertebereich, z.B.:
    A: 10-50, B: 10-50, C: 0-15.

    Das sind ja "nur" 40*40*15 Möglichkeiten. Jeweils eine bekommst du locker in ein "int".

    Mach dir ein Array aus 24000 ints, gebe jedem Element seinen Indexwert, also array[0]=0 ... array[23999]=23999. Als nächstes random-shuffle und fertig.

    Dekodiert wird dann so:
    A: 10+array[x]%40
    B: 10+array[x]/40%40
    C: array[x]/40/40%15

    Damit solltest du alle Kombinationen erwischt haben, schön vermischt und ohne Wiederholung oder sonstige Mehrdeutigkeiten. 🙂



  • Klar, war aber ja auch nur ein Beispiel. Tatsächlich können es viel mehr Attribute sein und damit gerät man sehr schnell in den Bereich der Fantastilliarden.



  • ;torstein schrieb:

    Klar, war aber ja auch nur ein Beispiel. Tatsächlich können es viel mehr Attribute sein und damit gerät man sehr schnell in den Bereich der Fantastilliarden.

    Wenn du auf das Mischen verzichten könntest: es gibt einen Algorithmus um die nächste Permutation einer fast beliebigen Anzahl von Elementen zu ermitteln. Dabei kommen auch keine Wiederholungen vor, aber das Ganze ist natürlich geordnet.

    Du könntest allerdings mit dem Output des Algorithmus ein kleines Array füllen und das dann mischen. Dann hättest du einen Ausschnitt der Gesamtmenge, vermischt, ohne Wiederholung, aber eben nur einen begrenzten Wertebereich.



  • Andromeda schrieb:

    Du könntest allerdings mit dem Output des Algorithmus ein kleines Array füllen und das dann mischen. Dann hättest du einen Ausschnitt der Gesamtmenge, vermischt, ohne Wiederholung, aber eben nur einen begrenzten Wertebereich.

    Die Idee ist gut und als ich das machen wollte, kam mir die Idee, das schon vorher zu machen. Ich mische 65536 Positionen und benutze dieses feste Array um jeweils 16 bit der Eingabe zu neuzuwürfeln.

    Beispielhaft für 64 bit bin ich jetzt bei sowas angelangt:

    template <class T,class Vec> T chunked_shuffle(T v,Vec&& vec)
    {
      auto chunkbits=log2i(vec.size());
      T sv=0;
      for (int i=0;i<sizeof(T)*8;i+=chunkbits)
      {
        T mask=(T(1)<<chunkbits)-1;
        T masked=(v&(mask<<i))>>i;
        sv|=T(vec[masked])<<i;
      }
      return sv;
    }
    
    template <class T,class Vec> T bit_shuffle(T v,Vec&& vec)
    {
      T sv=0;
      foreach_i(p,vec)
      {
        T b=(v&(T(1)<<i))>>i;
        sv|=b<<p;
      }
      return sv;
    }
    
    uint64_t perfect_hash(uint64_t v)
    {
      for (int i=0;i<20;i++)
      {
        v^=17484005144761633368;
        v=chunked_shuffle(v,pr65536);
        v=bit_shuffle(v,pr64);
        v^=3299664321131084580;
        v=bit_shuffle(v,pr64_2);
        v^=10966199739824101812;
        v=chunked_shuffle(v,pr65536_2);
        v^=13102024336882850561;
      }
      return v;
    }
    

    Keine Ahnung, ob all diese Operationen notwendig sind, bzw. zur Verbesserung des Ergebnisses beitragen, aber das Ergebnis sieht nun zumindest sehr zufällig aus:

    `90464c728875bb4f 1a487430db16d494 08466be3378cdb3b 5b39cf382a2003d5 b576347685b259fc ...

    011423c6961e6b49 ac5bd3cb7a957370 d480bce547bad5b6 16716e2ab0611a31 d3928407cf279cab ...

    36d4d3bda22b6bf4 8d744d30322bb4c4 40438849d67e327c 692a45c81c5462ae f429c04d7358c7d2 ...

    636df036638e11d7 a6c00616ca7c6f2b 079c97e4c43269a7 df88a7456d641ebe 93701c1a62602709 ...

    3502542b7a9b2a04 1066808fcd0e20c4 d9342c0d71726815 28eeb32f6f90ebad 42d2e4b5eb233efe ...

    ...`

    Damit wäre das Problem elegant gelöst.
    Danke an die Antworten 👍



  • in der graphic nutzen wir dafür die Hammsley Sequence die mittels eine radical inverse funktion erstellt wird. (GPUs haben dafuer sogar eine instruktion).

    auf CPU seite geht auch Halton, aber da gibt es, je nach anwendungsbereich, uU sichtbare haeufungen.

    https://en.wikipedia.org/wiki/Low-discrepancy_sequence
    http://http.developer.nvidia.com/GPUGems3/gpugems3_ch20.html

    theoretisch kannst du damit unendlich viele zufaellige positionen erstellen die immer dichter werden aber nie ueberlappen.


Anmelden zum Antworten