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

    • VB.NET

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

      Gegeben sei die Funktion:

      g (n) = g(n - g(n -1)) + g (n - g(n -2)) gilt , sofern n > 2

      1 als Rückgabe für n = 1 oder n = 2

      Gesucht wird die bestmögliche Optimierung für dieses Verfahren,
      da die Rekursion extrem ineffizient ist, wenn man die Funktion so benutzt.

      Es lag tatsächlich an der Initialisierung via Enumerable.Reapeat(). Mea Culpa!
      Die ganzen for-Schleifen sind tatsächlich sehr unschön und völlig unnötig, da man ja nur die innerste for-Schleife (0-255) gesondert behandeln will.
      Die Version vom EDR ist ziemlich elegant und war bei meinen Tests genauso schnell wie die Unsafe-Variante mit den Byte-Pointern (beide etwa 14,5 ms) .
      Die beiden Methoden machen ja im Prinzip das Gleiche - nur mit dem großen Unterschied, dass die EDR-Variante safe ist.

      @nikeee13
      Nene, kein Debug natürlich im Release. Natürlich ist auch zwischen der Zeitmessung kein stdout geschreibe - nur die Methode + Zuweisung des Rückgabewertes. Benchmarkcode ist im Anhang.
      Ohne Enumerable.Repeat() kommt c# ziemlich nahe an c++ ran. Wobei am Ende dann ein Faktor zwei Unterschied bleibt.

      Die beste Methode zum Invertieren ist damit die vom EDR (ReversedViaLayout).
      Der schnellste Algo in C# ist wohl die Methode TreeIndicesFast() mit ~5,5 ms.
      In C++ war sie nochmal doppelt so schnell mit ~2,7ms.
      Beidesmal in Kombination mit ReversedViaLayout(). Wobei die Laufzeit dieser Methode keine so große Rolle spielt, da sie nur alle 256 Durchgänge mal aufgerufen wird.

      Wer mag kann al ein bisschen mit ein paar Kombinationen rumspielen.

      imo ist die Benchmarkerei jetzt aber wirklich ausgelutscht. War eh niemals wirklich von belang, zumal für ein Problem von glaub ohne praktische Bedeutung: Rules Of Optimization
      Ich find die Zahlenfolge an sich faszinierend, weil das ist die Ausgabe eines binären balancierten Baumes bei Breath-First-Traversion.
      Breath-First-Traversion ist das Gegenstück zum Depth-First-Durchgang, welcher ja üblicherweise rekursiv erfolgt. Bei BT geht man nicht in die Tiefe - von einem Node in seine ChildNodes, sondern man arbeitet Ebene für Ebene des Trees durch, und packt die gefundenen Children erstmal ans Ende einer Queue.

      Also ich werd mich mal dran machen, einen Algo zu suchen, der aus dieser Zahlenfolge tatsächlich einen Treeview befüllt. Edit: nee - kommt grad nix zündendes in mein hirn...

      Annere Frage: Wie kommt man eiglich auf diese kranke Idee, die Zahlenfolge mit Bit-Inversionen zu generieren? - in meinen Augen klarer Fall von Hexerei :thumbsup:
      Also ich peile da ühaupt keinen Zusammenhang.

      @Daniel Baumert : sry - bin mit diesem Thema noch nicht durch :whistling:

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

      Daniel Baumert schrieb:

      Gegeben sei die Funktion:

      g (n) = g(n - g(n -1)) + g (n - g(n -2)) gilt , sofern n > 2

      1 als Rückgabe für n = 1 oder n = 2

      Gesucht wird die bestmögliche Optimierung für dieses Verfahren,
      da die Rekursion extrem ineffizient ist, wenn man die Funktion so benutzt.


      Man muss am verfahren gar nix optimieren. Nur an der Implementierung.

      C#-Quellcode

      1. using System;
      2. using System.Collections.Generic;
      4. public class Test
      5. {
      6. private static Dictionary<int, int> list;
      7. private static int g(int n)
      8. {
      9. if (!list.ContainsKey(n))
      10. {
      11. if (n > 2)
      12. list[n] = g(n-g(n-1)) + g(n-g(n-2));
      13. else
      14. list[n] = 1;
      15. }
      16. return list[n];
      17. }
      19. public static void Main(String[] args)
      20. {
      21. Test.list = new Dictionary<int, int>();
      22. for (int i = 1; i < 100; i++)
      23. Console.WriteLine("g({0}) = {1}", i, g(i));
      24. }
      25. }

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Quadsoft“ ()

      Um dem Thread mal wieder etwas leben zu verleihen:

      @Quadsoft

      Die Implementierung ist aber nicht effizient
      und nebenbei auch sinnlos, hat zwar den Ansatz der dynamischen Programmierung aber du rechnest alle Zwischenergebnisse ja erneut anstatt Sie aus dem dictionary zu nehmen (was die dictionary quasi sinnlos macht)
      Damit hast du also geschätzt eine Laufzeit von n*n/2*log2(n)^2 quasi O(n^2) bei den vielen rekursiven Aufrufen.
      Bei einer Problemstellung dessen optimale Werte sich aus dem Optimum der Teilwerte zusammensetzen ist die dynamische Programmierung immer der effizienteste Weg:

      C#-Quellcode

      1. private int g(int n)
      2. {
      3. if (n == 0 || n == 1)
      4. return 1;
      5. int[] a = new int[n];
      6. a[0] = 1;
      7. a[1] = 1;
      8. for (int i = 2; i < n; i++)
      9. {
      10. a[i] = a[i - a[i - 1]] + a[i - a[i - 2]];
      11. }
      12. return a[n - 1];
      13. }


      Das ist stets lineare Laufzeit O(n)

      RushDen schrieb:


      und nebenbei auch sinnlos, hat zwar den Ansatz der dynamischen Programmierung aber du rechnest alle Zwischenergebnisse ja erneut anstatt Sie aus dem dictionary zu nehmen (was die dictionary quasi sinnlos macht)


      Ich glaube, du liegst da etwas falsch. Natürlich lese ich aus dem Dictionary aus, und zwar wenn der Key (n) nicht im Dictionary vorhanden ist. Die Aufrufe sind daher auch nicht in O(n^2), sondern auch O(n). Bei z.b. n=98 habe ich genau 385 Aufrufe. Dein Code hat 1 Aufruf + 385 Array zugriffe. Du tust also exakt dasselbe. Man kann jetzt argumentieren, dass der Arrayzugriff performanter (d.h. um einen konstenten Faktor schneller) als mein Fuktionsaufruf + Dictionary-Lookup ist, aber laufzeittechnisch ist das dasselbe. Außerdem speichere ich das Dictionary über die Lebenszeit des aktuellen Funktionsaufrufs hinaus, was bei höheren n dazu führt, dass nur 5 Zugriffe pro n benötigt werden (zumindest wenn man aufsteigende n berechnet, wie in der schleife in meinem Code).

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Quadsoft“ ()

      Übungsaufgabe Stringmanipulation

      Hallo zusammen,
      dies ist für jeden, der Spaß am programmieren hat und auch gern noch etwas neues lernen möchte :).
      Um was gehts?
      Ziel des Ganzen ist es, eine Funktion zu schreiben, die eine IBAN verschleiert. Aus DE27100777770209299700 soll *******************700 werden. Dabei geht es in erster Linie nicht um den kürzesten oder den "schönsten" Algorithmus, sondern einzig um den vom Algorithmus allokierten Speicher.
      Im Anhang findet ihr eine bereits vorbereitete Solution - einmal als VB- und einmal als C#-Projekt - welches ihr nur erweitern müsst. In beiden Projekten ist bereits das Nuget-Paket BenchmarkDotNet referenziert. Dieses Paket wird verwendet, um den Speicherverbrauch der Funktion zu ermitteln.
      Außerdem habe ich in beiden Benchmark-Klassen ein Beispiel implementiert, wie sie ein Programmieranfänger erstellen würde.
      Um die Benchmarks auszuführen, müsst ihr das jeweilige Projekt im Release-Modus ausführen (Strg+F5, ohne debuggen Starten). Vergesst nicht, ggf. das Startprojekt zu ändern.
      Wie gesagt, Ziel ist es, eine (oder auch gern mehrere) Funktion(en)/Benchmark(s) zu schreiben, die weniger Speicher verbraucht, als das Beispiel von mir.

      Das Ergebnis eines solchen Benchmarks seht ihr in diesem Bild.
      Ihr könnt dann gerne hier eure Funktion und das Ergebnis des Benchmarks posten. Je nachdem wie die Resonanz ist und ich noch keinen sehr niedrigen Speicherverbrauch sehe, werde ich noch weitere optimierte Beispiele posten.
      Habt Spaß dabei und versucht erstmal eigene Lösungen zu finden, bevor die Suchmaschine der Wahl befragt wird. ;)
      Dateien

      @ISliceUrPanties wird dafür Studio 22 benötigt? Arbeite mit der 19er-Version und bekomme es nicht zum Laufen.
      Mein Ansatz:

      VB.NET-Quellcode

      1. <Benchmark>
      2. Public Function ObfuscateStringUser() As String
      3. Dim obf = IBAN_TO_OBFUSCATE
      4. For i = 1 To IBAN_TO_OBFUSCATE.Length - 3
      5. obf.Replace(obf(i), "*")
      6. Next
      7. Return obf
      8. End Function
      "Na, wie ist das Wetter bei dir?"
      "Caps Lock."
      "Hä?"
      "Shift ohne Ende!" :thumbsup:

      Ja. Ist ein .NET6 Projekt und benötigt VS 2022. Das Projekt ließe sich natürlich auch mit VS Code öffnen und per Kommandozeile ausführen. Es wird einfach nur das .Net 6 SDK benötigt.
      Einfach dotnet run -c Release im Projektverzeichnis ausführen.

      @tragl
      Klar kann ich das laufen lassen. :)

      Aber: Dein Code funktioniert nicht. Es wird immer die komplette IBAN zurückgegeben. Es wird zwar viel gemacht, aber Strings sind nicht veränderbar, auch wenn sie ein Referenzdatentyp sind.

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

      ISliceUrPanties schrieb:

      und benötigt VS 2022


      ok, möchte ich aktuell nicht draufmachen. Hatte ich in der Preview getestet und lief nicht alles sauber. Mache ich aber bestimmt im Laufe des Jahres nochmal. Trotzdem würde mich interessieren, was bei der Messung raus kommt,
      könntest du die einmal bei dir laufen lassen? ;)
      "Na, wie ist das Wetter bei dir?"
      "Caps Lock."
      "Hä?"
      "Shift ohne Ende!" :thumbsup:

      Jou, gutes Ergebnis, @ErfinderDesRades. Zumindest auf meinem PC:

      Die EdR1-Methode ist Deine, nur von IntelliSense optimiert zu:

      C#-Quellcode

      1. public string ObfuscateStringEdR1()
      2. {
      3. return string.Concat(new string('*', IBAN_TO_OBFUSCATE.Length - 3), IBAN_TO_OBFUSCATE.AsSpan(IBAN_TO_OBFUSCATE.Length - 3));
      4. }


      Meine Versuche hingegen k***en ab:

      C#-Quellcode

      1. public string ObfuscateStringVaporiZed()
      2. {
      3. int Length = IBAN_TO_OBFUSCATE.Length;
      4. char[] CharArray = IBAN_TO_OBFUSCATE.ToCharArray();
      5. return new string('*', Length - 3) + CharArray[Length - 3] + CharArray[Length - 2] + CharArray[Length - 1];
      6. }
      8. public string ObfuscateStringVaporiZedInterpolated()
      9. {
      10. int Length = IBAN_TO_OBFUSCATE.Length;
      11. char[] CharArray = IBAN_TO_OBFUSCATE.ToCharArray();
      12. return $"{new string('*', Length - 3)}{CharArray[Length - 3]}{CharArray[Length - 2]}{CharArray[Length - 1]}";
      13. }

      Der Hintergedanke war, weniger externe Funktionen aufzurufen - naja, geht nach hinten los.

      ##########

      und mit Cheat wird EdRs Code noch schneller :P

      VB.NET-Quellcode

      1. Public Function ObfuscateStringVaporiZed2() As String '= EdR-Code + VS-Optimierung + Cheat
      2. Return String.Concat("*******************", IBAN_TO_OBFUSCATE.AsSpan(IBAN_TO_OBFUSCATE.Length - 3))
      3. End Function


      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „VaporiZed“, mal wieder aus Grammatikgründen.

      Aufgrund spontaner Selbsteintrübung sind all meine Glaskugeln beim Hersteller. Lasst mich daher bitte nicht den Spekulatiusbackmodus wechseln.

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „VaporiZed“ ()

      jo, danke.
      Und dann kann ich nochmal mein Sprüchlein loswerden:
      Nichts ist unwichtiger, als die Geschwindigkeit einer Methode von 0,2ms auf 0,02ms zu optimieren.
      Boah! 10 mal schneller!
      Aber tatsächlich hat man 190Nano(!)Sekunden gewonnen - mit anderen Worten: nichts.

      Solche Threads wie diese sind fast gefährlich, weil sie verleiten Anfänger + auch Profis, ihre Hirne mit derlei Überlegungen zu verstopfen - und es gibt ganz sicher wichtigere Probleme.
      Gerne kommt bei diesen Versuchen noch komplizierter Code raus, der schlechter zu warten ist als die einfachste Lösung.
      Daher nie auf Geschwindigkeit optimieren - immer nur auf Wartbarkeit.
      Ausnahme: Wenn das Proggi - durch Messungen bestätigt - zu langsam ist.

      Noch ein weiteres zeigt sich:
      meiner oder VPZs Code sind ja durchaus ganz fabelhaft wartbar.
      Und deshalb sind sie die beste Lösung - nicht weil sie nebenbei auch schnell sind.
      Jdfs. was sich zeigt: gut wartbarer Code hat eine sehr sehr starke Tendenz, gleichzeitig auch sehr schnell zu sein (nicht dass das soo wichtig wäre, aber fast jeder schielt halt doch bisserl danach)


      Edit: Zum nachfolgenden "Rant": Ich wollte den Gesichtspunkt "(so gut wie) nie auf Geschwindigkeit optimieren" nur gesagt haben, weil ich finde, der muss immer gesagt werden, wenn auf Benchmarks geguckt wird.
      Weil das ist numal zu verführerisch, da komplizierte Kunstwerke zu verfassen, die tatsächlich aber die Code-Qualität herabsetzen.
      Ansonsten habich das Spielchen ja mitgespielt, also Spass machen tut mir sowas auch.
      Ich "antworte" hier auch nur im Edit, weil ich die Debatte nicht in die Länge ziehen will - es ist inhaltlich ja nix neues.

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

      ErfinderDesRades schrieb:

      Daher nie auf Geschwindigkeit optimieren - immer nur auf Wartbarkeit.
      Ausnahme: Wenn das Proggi - durch Messungen bestätigt - zu langsam ist.
      Full Ack. Ich arbeite in einem seit ~30 Jahre gewachsenen C-Projekt und der Code ist... gruselig. Funktionen mit um die 10.000 Zeilen sind keine Seltenheit, weil immer wieder für komische Edge-Cases Optimierungen eingefügt worden sind. Da neue Anforderungen zu implementieren, ist ein Graus.

      In diesem Sinne, Donald Knuth und Michael Jackson (nein, nicht der Musiker, der andere Michael Jackson) haben mal was zur Optimierung gesagt:

      Donald Knuth schrieb:

      Premature Optimization is the root of all evil

      Michael A. Jackson schrieb:

      Rules of Optimization:
      1. Don't.
      2. For experts only: Don't yet.

      Mit freundlichen Grüßen,
      Thunderbolt

      Ich komm bei den 2 Vorposts nicht mit. Klar sollte man Optimierungen welcherArtAuchImmer grundsätzlich in Arbeitscode nur mit guten Grund durchführen. Aber ich dächt, dass es hier um eine Art Rätsellösung geht. Ein Spiel. Eine Knobelaufgabe. Eine Herausforderung.
      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „VaporiZed“, mal wieder aus Grammatikgründen.

      Aufgrund spontaner Selbsteintrübung sind all meine Glaskugeln beim Hersteller. Lasst mich daher bitte nicht den Spekulatiusbackmodus wechseln.

      Ich verstehe diesen rant auch nicht. Mir gings nie um "Optimierung" oder Geschwindigkeit,

      ISliceUrPanties schrieb:

      sondern einzig um den vom Algorithmus allokierten Speicher

      Meine Intention war es, verschiede Möglichkeiten im Framework aufzuzeigen, wie man Strings erstellen/verarbeiten kann und welche Auswirkungen dies auf den Speicherverbrauch hat. Wie schlägt sich z.B. der StringBuilder in diesem Zusammenhang? Und gibt es noch andere Methoden?

      Mir hat dein "Cheat" gut gefallen @VaporiZed :D. Es werden nur die 72B verwendet, die die Iban verbraucht. Leider ist dieser Weg recht unflexibel. Aber es gibt dafür auch eine Lösung.

      VB.NET-Quellcode

      1. ​Public Function ObfuscateStringStringCreate() As String
      2. Return String.Create(IBAN_TO_OBFUSCATE.Length, IBAN_TO_OBFUSCATE, Sub(ret, val)
      3. val.AsSpan().CopyTo(ret)
      4. ret.Slice(0, val.Length - 3).Fill("*"c)
      5. End Sub)
      6. End Function

      Och schade, wäre cool gewesen wenn es die Aufgabe auch für C++ gegeben hätte; dann hätt' ich mal wieder was spaßiges zu tun gehabt. (Nicht das ich keinen Spaß im Leben hätte... Obwohl eigentlich :denk_emoji_aber_wir_sind_hier_nicht_auf_discord:)

      Ich weiß so gut wie gar nichts mehr über C#, VB und .NET im großen und ganzen.
      ----------------------------------------------------------------------------------------------------------------------

      Hier könnte meine Signatur stehen, aber die ist mir abfußen gekommen.

      ----------------------------------------------------------------------------------------------------------------------

      Okay, ich glaube, mein (und wahrscheinlich auch EdRs) Post werden anders verstanden als gemeint.

      Sicher ist es interessant, mal auszuprobieren, wie klein/schnell/effizient man eine Idee umsetzen kann. Das ist hier natürlich der Fall. Jedoch möchte ich – insbesondere bei aufstrebenden Mitlesern, die möglicherweise erst neu in der Programmierung unterwegs sind – nicht den Eindruck aufkommen lassen, dass ein bis zum letzten Quant optimiertes Programm ist das Ziel sein soll.
      Mit freundlichen Grüßen,
      Thunderbolt