Angepinnt [Sammelthread] Knobel-Aufgaben, knifflige Algorithmen, elegante Lösungen

    • VB.NET

    Es gibt 178 Antworten in diesem Thema. Der letzte Beitrag () ist von Thunderbolt.

      Ich hatte sowas mal gemacht, allerdings mit Klasse, ohne finde ich das auch etwas verrückt und vor allem nicht brauchbar.
      Ich hab meinen Code mal angehängt, irgendwo ist ein Fehler drin, sodass Removen nicht korrekt funktioniert, da der Baum aber langsam wie sonst was war hab ich dann nicht mehr weiter gemacht. Wenns jemanden interessiert kann er ja dran weiterarbeiten.
      Dateien

      habs mir mal angeguckt - sind paar grundlegende Fehler drin
      • in der eingeschachtelten Node-Klasse darf der <T> - Typ nicht redefiniert werden. Der Typ-Parameter überträgt sich von selbst auf die eingeschachtelte Klasse.
      • Jeder Node hat bei dir eine List<T>. Aber ein Node sollte nur einen einzigen Wert führen
        • deine Klassen sind sowas von verkapselt, dass man garkein Test-Projekt basteln konnte, mit einem Treeview, was die Baumstruktur ühaupt sichtbar macht.
          Zumindest während der Entwicklung des Algos kriegt man so dochn Vogel.
      Hab das also bisserl umgepfuscht und fund, dass die Rotiererei scheinbar garnet funzt. Oder meine Änderungen habens kaputt gemacht, aber ich war eiglich sehr behutsam. Oder meine Anzeige-Funktion stimmt nicht, aber ich glaub doch:

      C#-Quellcode

      1. private void BuildTreeView(TreeNodeCollection nodes, BinaryTree<int>.BinaryTreeNode itm) {
      2. if(itm == null) return;
      3. var nd = nodes.Add(itm.Items[0].ToString());
      4. BuildTreeView(nd.Nodes, itm.LessThan);
      5. BuildTreeView(nd.Nodes, itm.GreaterThan);
      6. }

      Dateien

      ErfinderDesRades schrieb:

      Jeder Node hat bei dir eine List<T>. Aber ein Node sollte nur einen einzigen Wert führen
      Ich habs so geregelt, dass zwei oder mehr nach dem Vergleichsverfahren als gleich eingestufte Objekte in die selbe Node kommen. Kann man auch anders machen, an der Laufzeit ändert sich dadurch aber nix.
      Ich hab ne Funktion geschrieben, die den Baum in der Console ausgibt, falls dir das ausreicht.
      Das Rotieren wird noch nirgends aufgerufen. Ich hab die Aufrufe wieder rausgemacht, nachdem ich gemerkt hab, das schon vorher was schief läuft. :P

      Ich glaube ihr habt mich falsch verstanden, es geht nicht darum, konkrete Objekte zu persistieren. Dazu würde auch ich dann ein Objekt erstellen :P

      Es geht darum, dass man zum Beispiel beliebige Objekte "hat", die erstmal in keiner logischen Beziehung zueinander stehen. Diese sollen nach einem bestimmten Muster (zb der Erstellungszeit) gespeichert werden.
      Doch das eben so, dass der Baum halt balanced ist, das ist prinzipiell die einzige Bedingung (und auch der Sinn). (Bedingung ist auch, dass unter einem Knoten höchstens 2 andere sein dürfen). So sollte Entartung vermieden werden.
      Persistierung in Bäumen macht natürlich eigentlich nur Sinn, wenn Parents und Childs irgendeine Beziehung zueinander haben.

      Der Algorithmus, nach dem ich gefragt hatte, diente nur dazu, den Baum zu balancieren. Welche Typen jetzt in eben dieser Reihenfolge gespeichert werden, ist ihm egal.
      Man soll der Funktion einfach einen Integer übergeben können: Anzahl der Knoten. Daraufhin soll eine Liste als "List(of Integer)" zurückgegeben werden, dessen .count - 1 mit der Anzahl der Knoten übereinstimmt.
      Die "List (of Integer)" beinhaltet die Reihenfolge der ID's, mit der alle neuen Objekte beliebigen Typs in diesem Baum gespeichert werden können, damit der Baum zu jedem Zeitpunkt balanciert ist, zu jedem Zeitpunkt.
      Das sollte das ganze wesentlich einfacher machen. Um diese Reihenfolge zu erstellen, braucht man keine Klasse vom Typ TreeNode, die Gegebenbeiten des .netframeworks reichen.
      Mein Code ist kaum länger als eine Laptop Bildschirm Seite.

      Das ist weniger ne Denkaufgabe, als ne Rechenaufgabe.
      code

      C#-Quellcode

      1. private static IEnumerable<int> lastLayer(int completeLayerCount)
      2. {
      3. int maxNodeCount = (1 << completeLayerCount);
      4. for (int step = maxNodeCount/2; step > 1; step /= 2)
      5. {
      6. int offset = maxNodeCount-1 + step/2;
      7. for (int i = offset; i < offset + maxNodeCount; i += step)
      8. {
      9. yield return i;
      10. }
      11. }
      12. }
      14. private static List<int> TreeIndices(int nodeCount)
      15. {
      16. int completeLayerCount = (int)(Math.Log(nodeCount + 1, 2));
      17. int someMagicNumber = 1 << completeLayerCount;
      18. int fullLayersNodeCount = someMagicNumber - 1;
      19. IEnumerable<int> fullLayers = Enumerable.Range(0, fullLayersNodeCount);
      20. List<int> lastLayerNodes = new int[] { fullLayersNodeCount, fullLayersNodeCount + someMagicNumber / 2 }.Concat(lastLayer(completeLayerCount)).Take(nodeCount - fullLayersNodeCount).ToList();
      21. lastLayerNodes.Sort();
      22. return fullLayers.Concat(lastLayerNodes).ToList();
      23. }


      test

      C#-Quellcode

      1. private void Test()
      2. {
      3. int nodeCount = 61;
      4. List<int> blub = TreeIndices(nodeCount);
      5. int checker = 2;
      6. for (int i = 1; i <= nodeCount; i++)
      7. {
      8. Debug.Write(blub[i-1].ToString() + " ");
      9. if (i == checker - 1)
      10. {
      11. Debug.WriteLine("");
      12. checker *= 2;
      13. }
      14. }
      15. Debug.WriteLine("");
      16. }

      nee,

      Direktfenster schrieb:


      0 1 2 3 5 4 6 7 11 9 13 8 12 10 14 15 23 19 27 17 25 21 29 16 24 20 28 18 26 22 30 31 47 39 55 35 51 43 59 33 49 41 57 37 53 45 61 32 48 40 56 36 52 44 60 34 50 42 58 38 54

      wäre die richtige Reihenfolge für anzahl = 61 gewesen.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „iCanNonIc“ ()

      Du hast Recht.
      Bei mir ist der Baum gar nicht balanced. Ich habe mir die Zahlenfolgen aufgeschrieben und einen Algorithmus entwickelt, der sie wiedergibt. Dabei habe ich vergessen, dass die Reihenfolge in der jeweiligen Ebene auch eine Rolle spielt. Statt 7 11 9 13 8 12 10 14 habe ich einfach 7 11 9 13 8 10 12 14 generiert.

      Ich habe mir mal ein paar Gedanken gemacht und bin auf eine ziemlich krasse Lösung gestoßen.
      Wenn man die einzelnen Bits der binäre Darstellung einer Zahl als Entscheidung an einer Abzweigung interpretiert, dann kann man jede Position in einer Ebene durch einen Integer repräsentieren.
      Edit: Ergänzung: Das niedrigste Bit enspricht der obersten Abzweigung. Wenn man den Baum so durch geht, dass er immer balanced ist, und dabei immer den am weitesten links befindlichen Ast nimmt, dann wechselt das 1.Bit bei jedem Schritt. Das 2.Bit oszilliert bei jedem 2.Schritt, das 3.Bit bei jedem 4.Schritt usw... Das entspricht einfach einem Hochzählen im Binärsystem.

      Wenn ich alle Positionen durchgehe, muss ich nur noch die Position in eine Zahl umrechnen.
      Edit: Ergänzung: Der oberste Ast entscheidet in welcher Hälfte die Position ist. Die Äste darunter in welchem Viertel. Man merkt hier, dass der Wert (z.B. 0-31 auf Ebene 5) binär durch die Position codiert ist. Leider entspricht das niedrigste Bit der Position dem höchsten Bit des Wertes.
      Deswegen muss man die Bits der Position spiegeln, um an den Wert zu kommen. Auf den Wert muss man dann nur noch die Zahl aller Knoten aus allen vorherigen Ebenen addieren.
      Umgesetzt habe ich das mit einer LookUpTable für Bytes. Die Bits eines Bytes werden gespiegelt und dann die Reihenfolge der Bytes umgedreht.
      Das ganze funzt unabhängig von der Endianess. Die Hälfte vom Code ist das Erstellen der LookUpTable.

      C#-Quellcode

      1. private static IEnumerable<int> TreeIndices()
      2. {
      3. for (int layerIndex = 0; true; layerIndex++)
      4. {
      5. int lastNode = (1 << layerIndex) - 1;
      6. for (uint i = 0; i <= lastNode; i++)
      7. {
      8. yield return lastNode + (int)(Reversed(i) >> (32 - layerIndex));
      9. }
      10. }
      11. }
      13. private void Test()
      14. {
      15. int nodeCount = 61;
      16. foreach (int i in TreeIndices().Take(nodeCount))
      17. Debug.Write(i + " ");
      18. Debug.WriteLine("");
      20. }
      21. static byte[] ReversedBitsLookUpTable = generateLookUpTable();
      23. private static byte[] generateLookUpTable()
      24. {
      25. byte[] LookUpTable = new byte[byte.MaxValue + 1];
      26. for (uint b = 0; b <= byte.MaxValue; b++)
      27. {
      28. byte value = Convert.ToByte(b);
      29. for (int i = 0; i < 8; ++i)
      30. {
      31. LookUpTable[b] <<= 1;
      32. byte bit = (byte)(value & 0x01);
      33. LookUpTable[b] |= bit;
      34. value >>= 1;
      35. }
      36. }
      37. return LookUpTable;
      38. }
      39. public static uint Reversed(uint value)
      40. {
      41. return BitConverter.ToUInt32(BitConverter.GetBytes(value).Reverse().Select(v => ReversedBitsLookUpTable[v]).ToArray(), 0);
      42. }


      Das schöne dabei ist, dass das Generieren von N Elementen nur N Schritte benötigt. Die Instruktionen pro Schritt sind auch relativ gering. Ein Random Access wäre in konstanter Zeit möglich.
      Andersherum: Sogar die komplette Berechnung der Entscheidungsverzweigungen eines speziellen Wertes wäre in konstanter Zeit möglich.

      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „markus.obi“ ()

      Damit hast du selber einen schönen "ahaaaa" effekt gegönnt. ;)

      Ich hatte den auch, wenn auch nicht so groß, denn es geht - Meiner Meinung nach - auch noch etwas einfacher.
      Mir ist nämlich bei folgender Betrachtung etwas aufgefallen.
      (Dort stehen die Positionen der Knoten des aktuellen Levels = 2 ^ x als x = 3) in der horizontalen, die Reihenfolge, damit der Baum balanced ist, in der vertikalen):
      Spoiler anzeigen


      Zieht man imaginäre Linien von 1 - 2, 3 - 4, 5 - 6, 7 - 8 fällt auf, dass sie parallel laufen. "Bricht" man die Liste auf 1 - 4 und halbiert entsprechend die Zahlen, würde die neue Tabelle für
      2 ^ (x - 1) gelten.

      Genau so sieht dann auch mein Algorithmus aus.
      Die Implementierung ist dann sogar noch einfacher.
      Idee

      Man nehme eine Liste. Man schreibe in die erste Zeile alle Zahlen von 1 bis 2 ^ x (als Liste). Noch sind die Zahlen numerisch geordnet.
      Bis jedes Listenelement der ursprünglichen Liste nur noch einen Eintrag hat halbiere man die Liste aus Zahlen, nehme den halben hinteren Teil weg und füge ihn als eine neue Liste aus Zahlen an die ursprünliche Liste an. Nicht ganz trivial? Siehe Beispiel:

      Spoiler anzeigen

      1. Schreibe alle Zahlen 1 2 3 4 5 6 7 8 als Liste in eine Liste.
      2. Halbiere die Liste in der Liste, bis du nicht mehr halbieren kannst. Schneide die hintere hälte aus und füge sie als neue Liste(of ID) in die Liste ein:
      1 2 3 4
      5 6 7 8

      1 2
      5 6
      3 4
      7 8

      1
      5
      3
      7
      2
      6
      4
      8

      Entnimm jeder Liste(of int) in der Liste(of Liste(of int)) den jeweils ersten Eintrag und schreibe ihn in eine Reihe:
      1 5 3 7 2 6 4 8



      Ich denke, eine Implementierung kann jeder selber vornehmen, zumahl meine recht schäbig ist :P

      Ist jetzt nur noch die Frage, welcher Algorithmus performanter ist ^^
      Mein Algorithmus liefert die Reihenfolge der zu balancierenden Knoten als ID-Liste zurück. Mein Laptop ist jetzt nicht der schnellste, aber auch bei meiner Methode steigt die Berechnugnszeit linear zur Anzahl. Für 100000 Knoten braucht er 300 ms, für 1 Million 3000 ms.

      iCanNonIc schrieb:

      denn es geht - Meiner Meinung nach - auch noch etwas einfacher.

      Irgendwie scheint mir deine Methode nicht wirklich einfacher. Meine Methode besteht halt nur aus
      1.) integer hochzählen
      2.) Bitmuster des integers spiegeln
      3.) die ehemals führenden Nullen wegshiften
      Von der Performance ist deine Methode ziemlich ungünstig, weil man ständig Listen bearbeitet. Was ich allerdings interessant finde ist, dass du nur eine Komplexität von N hast.
      Wäre gut, wenn du mal nen Code zu deiner Methode posten könntest, damit wir das nachvollziehen können.

      Hab mal die Geschwindigkeit getestet. Dabei habe ich ausprobiert, ob das IEnumerable mit dem yield return viel langsamer ist als das Schreiben in eine bestehende Liste fester Länge. Wie erwartet ist der IEnumerable nur etwas langsamer. Das beste Optimierungs potential bietet das Bit-Invertieren per Unsafe-Code. Damit ist das ganze nochmal um den Faktor 10 schneller. 1 Mio Einträge errechnet in 31ms.
      Prozessor ein Kern: 3,7GHz (Turbo-Boost)
      Erstellen einer Liste mit 1 Mio Einträge bei mind. 60 Durchgängen.

      Quellcode

      1. BufferList IEnumerable
      2. safe 320 ms 325 ms
      3. unsafe 31 ms 36 ms



      BufferedList

      C#-Quellcode

      1. private static List<int> TreeIndicesList(int nodeCount)
      2. {
      3. List<int> l = new List<int>(nodeCount);
      4. l.AddRange(Enumerable.Repeat(0, nodeCount));
      5. int nodeCounter = 0;
      6. for (int layerIndex = 0; true; layerIndex++)
      7. {
      8. int lastNode = (1 << layerIndex) - 1;
      9. for (uint i = 0; i <= lastNode; i++)
      10. {
      11. if (nodeCounter == nodeCount)
      12. return l;
      13. l[nodeCounter++] = lastNode + (int)(ReversedUnsafe(i) >> (32 - layerIndex));
      14. }
      15. }
      16. }


      Unsafe Reverse

      C#-Quellcode

      1. public static unsafe uint ReversedUnsafe(uint value)
      2. {
      3. byte* source = (byte*)&value;
      4. uint newvalue;
      5. byte* target = (byte*) &newvalue;
      6. target[0] = ReversedBitsLookUpTable[source[3]];
      7. target[1] = ReversedBitsLookUpTable[source[2]];
      8. target[2] = ReversedBitsLookUpTable[source[1]];
      9. target[3] = ReversedBitsLookUpTable[source[0]];
      10. return newvalue;
      11. }


      Random Access ist bei meiner Methode viel schneller. Man muss allerdings, um das höchste Bit finden, die Baumebene zu bestimmen. Für Bit-Größen, die der Prozessor handeln kann (64bit, 32bit) geht das in log(log(N)) Schritten. z.B. Für Integer.MaxValue in log(log(2^32)) = 5 Schritten. Ist also defakto konstante Zeit.

      Kleine Aufgabe an die Runde: Schreibe einen Algorithmus, der die Position des höchsten Bits eines Integers N findet und eine Zeit-Komplexität von log(log(N)) hat. Es gibt einen Algo (Binäre Suche), der das in konstanter Zeit macht und immer log(log(2^32)) = 5 Schritte braucht. Der hier gesuchte Algorithmus hat aber die Komplexität log(log(N)) und ist manchmal langsamer und manchmal schneller als der vorherig genannte.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „markus.obi“ ()

      Ist jetzt aber in basic.
      Im ersten Post hatte ich ja gesagt, das ich nur Listen aus Zahlen und Listen aus Objekten (in dem fall Listen) nehme und nur native Datentypen und deren Operationen nehme, so hab ichs auch gebaut.

      Spoiler anzeigen

      VB.NET-Quellcode

      1. Public Shared Function getReihenfolge(ByVal Knotenzahl As Integer) As List(Of Integer)
      2. Dim ListenListe As New List(Of List(Of Integer)), RückgabeListe As New List(Of Integer)
      3. Dim count, offset As Integer
      5. While Not 2 ^ count > Knotenzahl
      6. count += 1
      7. End While
      9. For i As Integer = 1 To count
      10. ListenListe.Add(aktuellesLevel(i))
      11. Next
      13. RückgabeListe.Add(0)
      14. Dim TempListe As New List(Of Integer)
      15. TempListe = ListenListe(0)
      16. For Each i As Integer In TempListe
      17. RückgabeListe.Add(CInt(i))
      18. Next
      19. For l As Integer = 1 To ListenListe.Count - 1
      20. offset = CInt(offset + (2 ^ l))
      21. Dim cList As New List(Of Integer)
      22. cList = ListenListe(l)
      23. For Each i As Integer In cList
      24. RückgabeListe.Add(CInt(i + offset))
      25. Next
      26. Next
      28. RückgabeListe = RückgabeListe.GetRange(0, Knotenzahl)
      29. Return RückgabeListe
      31. End Function
      32. Private Shared Function aktuellesLevel(ByVal count As Integer) As List(Of Integer)
      34. Dim ReturnListe As New List(Of List(Of Integer))
      35. For i As Integer = 1 To CInt(2 ^ count)
      36. Dim TempListe As New List(Of Integer)
      37. TempListe.Add(i)
      38. ReturnListe.Add(TempListe)
      39. Next
      41. For i As Integer = 1 To count
      42. For e As Integer = CInt(ReturnListe.Count / 2) To ReturnListe.Count - 1
      43. Dim TempListe As New List(Of Integer)
      44. TempListe.AddRange(ReturnListe(e - CInt(ReturnListe.Count / 2)).ToArray)
      45. TempListe.AddRange(ReturnListe(e).ToArray)
      46. ReturnListe(e - CInt(ReturnListe.Count / 2)) = TempListe
      47. Next e
      48. ReturnListe.RemoveRange(CInt(ReturnListe.Count / 2), CInt(ReturnListe.Count / 2))
      49. Next
      51. Return ReturnListe(0)
      53. End Function


      Darüber hinaus könnte man die Funktion so umbauen, dass nicht nur binäre Bäume, sondern dass auch Bäume balanciert werden, die mehr 3 oder mehr Knoten besitzen.

      markus.obi schrieb:

      Schreibe einen Algorithmus, der die Position des höchsten Bits eines Integers N findet und eine Zeit-Komplexität von log(log(N)) hat.
      Meinst du sowas?

      C#-Quellcode

      1. ​ public int GetHighestBit(uint value)
      2. {
      3. int[] powers = new[] { 0x8, 0x4, 0x2, 0x1, 0x1 };
      4. int currentPower = 0xF;
      6. for (int i = 0; i < powers.Length; i++)
      7. {
      8. if (value > ~(uint.MaxValue << currentPower + 1))
      9. currentPower += powers[i];
      10. else if (value < (1u << currentPower))
      11. currentPower -= powers[i];
      12. else
      13. break;
      14. }
      15. return currentPower;
      16. }

      iCanNonIc schrieb:


      Direktfenster schrieb:


      0 1 2 3 5 4 6 7 11 9 13 8 12 10 14 15 23 19 27 17 25 21 29 16 24 20 28 18 26 22 30 31 47 39 55 35 51 43 59 33 49 41 57 37 53 45 61 32 48 40 56 36 52 44 60 34 50 42 58 38 54
      hmm - ich versteh nur Bahnhof.
      Also ich ahne, dass die Farbwechsel verschiedene Level des Baums andeuten, aber warum innerhalb eines Levels die Zahlen in dieser Reihenfolge stehen verstehe ich nicht wirklich.
      Erinnert mich an die Heap-Bedingung, also dass die Kinder eines Knotens beide größer sein müssen als ihr Papa. Und scheint mir auch ein Heap zu sein, obige Zahlenreihe. Und ich könnte auch einen irre performanten Algo angeben, um sone Zahlenreihe zu creiern - aber wo ist da der Baum?

      Also wäre damit gedient, für diese Zahlenfolge einen Algo zu creiern?
      Die Systematik die ich sehe ist, dass jeder Level sich 2 mal hinter sich kopiert - das erste Mal in Verdopplung +1, und das 2. Mal die Verdopplung + 2

      Also mit dieser Reihenfolge ist folgendes gemeint:

      Mal angenommen du stehst aus irgendeinem Grund vor der Problematik, du musst viele Objekte speichern. Dabei ist wichtig, dass du sie in einem binären Baum speichern (musst). Nun muss dieser Baum in Balance gehalten werden. Balance bedeutet hier, dass, egal welchen Knoten du im gesamten Baum betrachtest, du an seinem LINKEN oder RECHTEN Knoten unter sich (INKLUSIVE dessen jeweiligen Unterknoten bis ganz "unten") höchstens eine Differenz von einem Knoten hast.

      Du hast zum Beispiel einen Binären Baum aus 3 Knoten. Einem Parent, und 2 Child Knoten.
      Angenommen, du musst einen weiteren Knoten hinzufügen. Wohin damit? Du hast ja 4 Möglichkeiten.
      Überträgt man das auf Dateisystem, würden die Ordnerpfade so aussehen:
      0/1 und 0/2. (Null, eins und zwei sind die am Anfang hinzugefügten Knoten).
      Deine 4 Möglichkeiten sind also 0/1/1, 0/1/2, 0/2/1 oder 0/2/2.
      Alles klar, viel kann ja nich falsch gehen^^, also nehmen wir mal 0/1/1.
      Doch jetzt musst du noch ein Objekt speichern. Welchen Knoten nimmst du nun? Klar, 0/1/2.
      Aber das geht nicht. Bedingung war ja, dass sowohl rechts als auch links eines JEDEN knoten im Baum, Gleichstand in der Anzahl der jeweiligen Knoten darunter war.
      Betrachten wir den Knoten 0, fällt auf, dass unter 0/1 insgesamt drei Knoten, unter 0/2 aber nur einer. Also musst du, anstatt 0/1/2 den Knoten 0/2/1. Bedingung wieder erfüllt.

      Die Zahlenreihe bedeutet nur, dass du jedem Knoten pro "Level" des Baumes von links nach rechts eine ID gibst, die immer weiter hoch zählt.
      Von außen betrachtet, kann man sehen, welche Knoten jetzt genommen werden müssen.

      Meine Knobelaufgabe war es, einen Algorithmus zu erstellen, der es schafft, diesen Baum zu balancieren. Ohne Objekte, die Knoten repräsentieren und über Eigenschaften ihre Parents, Childs oder Siblings kennen. Ledliglich Integer als ID beschreiben den Knoten als solchen.

      hey - ich hab eine Byte-Rotation mit Safe-Code, die fast ebenso schnell zu sein scheint wie der Unsave-Code:

      C#-Quellcode

      1. public static uint ReversedFastSafe(uint value) {
      2. var rt = new StructConverter() { UInt32 = value };
      3. var rt2 = new StructConverter();
      4. rt2.Byte0 = ReversedBitsLookUpTable[rt.Byte3];
      5. rt2.Byte1 = ReversedBitsLookUpTable[rt.Byte2];
      6. rt2.Byte2 = ReversedBitsLookUpTable[rt.Byte1];
      7. rt2.Byte3 = ReversedBitsLookUpTable[rt.Byte0];
      8. return rt2.UInt32;
      9. }
      11. }
      13. [StructLayout(LayoutKind.Explicit, Pack = 1)]
      14. public struct StructConverter {
      15. [FieldOffset(0)]
      16. public byte Byte0;
      17. [FieldOffset(1)]
      18. public byte Byte1;
      19. [FieldOffset(2)]
      20. public byte Byte2;
      21. [FieldOffset(3)]
      22. public byte Byte3;
      23. [FieldOffset(0)]
      24. public UInt32 UInt32;
      25. }
      Also wenn mein Benchmarking mich nicht täuscht - kann vlt. jmd gegenprüfen?

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

      @ErfinderDesRades
      Deine Methode braucht bei mir 30 ms und ist damit etwa 2 ms schneller, als meine unsafe Variante.
      Ich habe noch ne Möglichkeit gefunden, die ich mir vorher schon überlegt hatte aber aus Übersichtlichkeit nicht implementiert hatte.
      Es ist nämlich so, dass sich bei 255 von 256 Fällen nur das niedrigste Byte ändert. Deswegen braucht man in 255 von 256 Fällen nur ein Byte invertieren. Dadurch bekommt man in der Theorie nochmal einen Faktor 4 in der Geschwindigkeit.
      Bitshift scheint außerdem auch etwas schneller zu sein als einzelne Bytes anzusprechen. Pointer auf Bytes zu dereferenzieren ist teuer! Einzelne Bytes zuzuweisen wahrscheinlich auch (teurer als Int32 zuzuweisen).

      Ich habe auch mal meine "unsafe c#" Variante in C++ kopiert, und schwupps, braucht es statt 32 ms nur 8 ms. Durch den oben genannten Trick wäre nochmal eine Verringerung um maximal Faktor 4 möglich.

      Ein Implementationsversuch kam dann auch ziemlich nah dran. Ergebnis: 3,0 ms in C++. In C# braucht die identische Methode 21 ms! C# ist also arschlangsam. Das Schöne an der Methode ist, ist dass sie keinen unsafe Code enthält.

      C++ Variante (3 ms)

      C-Quellcode

      1. typedef uint32_t uint;
      2. typedef unsigned char byte;
      3. static vector<uint> TreeIndices(uint nodeCount)
      4. {
      5. vector<uint> l(nodeCount);
      6. uint nodeCounter = 0;
      7. for (uint layerIndex = 0; true; layerIndex++)
      8. {
      9. uint lastNode = (1 << layerIndex) - 1;
      10. uint reversed = 0;
      11. uint binPosCounter = 0;
      12. const uint leadingZeroCount = 32 - layerIndex;
      14. while (true)
      15. {
      16. reversed &= ~(0xff000000u >> 24);
      17. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 24) & 0xffu] << 0;
      18. for (uint i1 = 0; i1 < 256; i1++)
      19. {
      20. reversed &= ~(0xff000000u >> 16);
      21. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 16) & 0xffu] << 8;
      22. for (uint i2 = 0; i2 < 256; i2++)
      23. {
      24. reversed &= ~(0xff000000u >> 8);
      25. reversed |= ReversedBitsLookUpTable[ (binPosCounter >> 8) & 0xffu] << 16;
      26. for (uint i3 = 0; i3 < 256; i3++)
      27. {
      28. if (nodeCounter == nodeCount)
      29. return l;
      30. reversed &= ~(0xff000000u >> 0);
      31. reversed |= ReversedBitsLookUpTable[binPosCounter & 0xffu] << 24;
      32. l[nodeCounter] = lastNode + (reversed >> leadingZeroCount);
      33. nodeCounter++;
      34. if (binPosCounter == lastNode){
      35. goto nextLayer;
      36. }
      37. binPosCounter++;
      38. }
      39. }
      40. }
      41. }
      42. nextLayer:;
      43. }
      44. }


      Nach C# übersetzt 21 ms

      C#-Quellcode

      1. private static List<uint> TreeIndicesListSafe(int nodeCount)
      2. {
      3. List<uint> l = new List<uint>(nodeCount);
      4. l.AddRange(Enumerable.Repeat<uint>(0, nodeCount));
      5. int nodeCounter = 0;
      6. for (int layerIndex = 0; true; layerIndex++)
      7. {
      8. uint lastNode = (1u << layerIndex) - 1;
      9. uint reversed = 0;
      10. uint binPosCounter = 0;
      11. int leadingZeroCount = 32 - layerIndex;
      13. while (true)
      14. {
      15. reversed &= ~(0xff000000u >> 24);
      16. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 24) & 0xffu] << 0;
      17. for (uint i1 = 0; i1 < 256; i1++)
      18. {
      19. reversed &= ~(0xff000000u >> 16);
      20. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 16) & 0xffu] << 8;
      21. for (uint i2 = 0; i2 < 256; i2++)
      22. {
      23. reversed &= ~(0xff000000u >> 8);
      24. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 8) & 0xffu] << 16;
      25. for (uint i3 = 0; i3 < 256; i3++)
      26. {
      27. if (nodeCounter == nodeCount)
      28. return l;
      29. reversed &= ~(0xff000000u >> 0);
      30. reversed |= ReversedBitsLookUpTable[binPosCounter & 0xffu] << 24;
      31. l[nodeCounter] = lastNode + (reversed >> leadingZeroCount);
      32. nodeCounter++;
      33. if (binPosCounter == lastNode)
      34. {
      35. goto nextLayer;
      36. }
      37. binPosCounter++;
      38. }
      39. }
      40. }
      41. }
      42. nextLayer: ;
      43. }
      44. }
      (Die LookUpTable ist vom Typ uint[])
      Bevor sich jemand über das goto beschwert: Mehrere foor lops auf einmal zu brechen ist wohl einer der wenigen Daseinsberechtigungen von goto. Wenn man möchte, kann man es auch durch ein breakflag ersetzen.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „markus.obi“ ()

      @markus.obi
      Mich würde mal interessieren, womit du die Codes benchmarkst. Kannst du das irgendwo mal hochladen? Am Ende benchmarkst du noch im Debug-Mdoe, bei dem du in den stdout schreibst. ;)

      Zum C#-Code:
      Muss es eine List<uint> sein oder tut es nicht auch ein unit[]? Des Weiteren frage ich mich, warum du Enumerable benutzt, um die List auf 0 zu initialisieren. Wenn es hier auf Performance ankommt, wäre eine For-Schleife sicherlich schneller (mal davon abgesehen, dass eine List<T> hier irgendwie nicht hinpasst, weil die Länge fix ist und auch keine Methoden wie Remove oder Add gebraucht werden. uint[] wäre autiomatisch auf 0 initialisert und schneller).
      Von meinem iPhone gesendet

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nikeee13“ ()

      Weil ich fünffach verschachtelte Schleifen nicht gut finde: eine zweifach verschachtelte.

      C# Quellcode

      C#-Quellcode

      1. static uint[] ReversedBitsLookUpTable = generateLookUpTable();
      2. private static uint[] generateLookUpTable()
      3. {
      4. uint[] LookUpTable = new uint[byte.MaxValue + 1];
      5. for (uint b = 0; b <= byte.MaxValue; b++)
      6. {
      7. byte value = Convert.ToByte(b);
      8. for (int i = 0; i < 8; ++i)
      9. {
      10. LookUpTable[b] <<= 1;
      11. LookUpTable[b] |= (byte)(value & 0x01);
      12. value >>= 1;
      13. }
      14. }
      15. return LookUpTable;
      16. }
      18. static uint[] TreeIndicesListSafe(int nodeCount)
      19. {
      20. const uint ff = 255;
      21. const uint ffff = 65535;
      22. const uint max = 16777216;
      23. const uint flag = 4278190080;
      25. uint[] nodeArray = new uint[nodeCount];
      27. int nodeCounter = 0;
      29. for (int layerIndex = 0; layerIndex < 32; layerIndex++)
      30. {
      31. uint lastNode = (1u << layerIndex) - 1;
      32. uint reversed = 0;
      33. uint binPosCounter = 0;
      34. int leadingZeroCount = 32 - layerIndex;
      35. bool keeprunning = true;
      37. for (uint i = 0; keeprunning && i < max; i++)
      38. {
      39. if (i == 0)
      40. {
      41. reversed &= ~(flag >> 24);
      42. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 24) & ff] << 0;
      43. }
      44. if ((i & ffff) == 0)
      45. {
      46. reversed &= ~(flag >> 16);
      47. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 16) & ff] << 8;
      48. }
      49. if ((i & ff) == 0)
      50. {
      51. reversed &= ~(flag >> 8);
      52. reversed |= ReversedBitsLookUpTable[(binPosCounter >> 8) & ff] << 16;
      53. }
      54. if (nodeCounter == nodeCount)
      55. return nodeArray;
      57. reversed &= ~flag;
      58. reversed |= ReversedBitsLookUpTable[binPosCounter & ff] << 24;
      60. nodeArray[nodeCounter++] = lastNode + (reversed >> leadingZeroCount);
      62. if (binPosCounter++ == lastNode)
      63. {
      64. keeprunning = false;
      65. continue;
      66. }
      68. if ((i + 1) >= max)
      69. i = 0;
      70. }
      71. }
      73. return null;
      74. }

      Das Ding ist nicht getestet, weil ich die Methode zum erstellen der ReversedBitsLookUpTable nicht gefunden habe - son Scheiß aber auch.
      Sollte aber theoretisch so funktionieren.
      Getestet, funktioniert. Zeiten messe ich aber nicht.

      Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „AliveDevil“ ()

    Facebook
    Telefonspende