Async: einfaches Visualisieren von Algorithmen

    • VB.NET
    • .NET (FX) 4.5–4.8

      Async: einfaches Visualisieren von Algorithmen

      Das Voranschreiten eines Algorithmus' zu visualisieren war bislang eigentlich unmöglich, denn der Computer kann ja nicht innehalten. Natürlich kann man ihn mit Thread.Sleep() anhalten, aber das hält auch die Oberfläche an - also visualisiert wird dabei auch nix :thumbdown:
      Man hat die Algos immer zur völligen Unkenntlichkeit umstrukturieren müssen, um bestimmte Zustände, die ganz normal im Algo auftreten, als konsistente Objekte verfügbar zu bekommen, die man einerseits im Gui präsentieren kann, von denen man andererseits aber auch den nächsten Schritt des Algos gehen kann. Eine einfache For-Schleife mutiert mindestens zu einem Button, einer Eventhandler-Methode und einer Klassen-Variable - von der Schleife bleibt nichts ;( .

      Aber dank Async kann der Computer nun innehalten, und diese entstellten Mutanten dürfen aussterben - mögen sie ruhen in Frieden :saint:
      Das einfachste Innehalten geht mit Await Task.Delay(500): ein Delay von 500ms einzuschieben.
      Das zweit-einfachste ist, auf ein AutoResetEvent zu warten, welches der User per Button-Click durchschaltet:

      VB.NET-Quellcode

      1. Private _Blocker As New AutoResetEvent(True)
      3. Private Function Wait() As Task
      4. Return Task.Run(Function() _Blocker.WaitOne())
      5. End Function
      7. Private Sub btStep_Click(sender As Object, e As EventArgs) Handles btStep.Click
      8. _Blocker.Set()
      9. End Sub
      Die Wait-Methode (#3) ist ebenso aufzurufen wie Task.Delay, und sie schiebt ebenso einen Delay ein, nur jetzt bestimmt der User, wanns weiter geht.

      Als praktisches Demo habe ich den BubbleSort-Algo hergenommen - hier the whole Story:

      VB.NET-Quellcode

      1. Imports System.ComponentModel
      2. Imports System.Threading
      3. Imports System.Runtime.CompilerServices
      5. Public Class frmSortVisualizerVb
      7. Private _List As New BindingList(Of Integer)()
      8. Private _Blocker As New AutoResetEvent(True)
      10. Public Sub New()
      11. InitializeComponent()
      12. ListBox1.DataSource = _List
      13. End Sub
      15. Private Sub Button_Click(sender As Object, e As EventArgs) Handles btBubbleSort.Click, btReset.Click, btStep.Click
      16. Select Case True
      17. Case sender Is btReset : Generate(30, 30)
      18. Case sender Is btBubbleSort : BubbleSort(_List)
      19. Case sender Is btStep : _Blocker.Set()
      20. End Select
      21. End Sub
      23. Private Sub ckStepwise_CheckedChanged(sender As Object, e As EventArgs) Handles ckStepwise.CheckedChanged
      24. btStep.Enabled = ckStepwise.Checked
      25. _Blocker.[Set]()
      26. End Sub
      28. Private Async Sub Generate(max As Integer, count As Integer)
      29. _List.Clear()
      30. Dim rnd = New Random(0)
      31. For i = 0 To count - 1
      32. If ckStepwise.Checked Then Await Wait()
      33. _List.Add(rnd.[Next](max))
      34. Next
      35. End Sub
      37. Private Async Sub BubbleSort(lst As IList(Of Integer))
      38. 'repeat: run up, compare each element with its successor - if greater: Swap
      39. 'topSwap/lastSwap consider, that the elements behind the last swap-Position of the previous Run-up already are sorted
      40. Dim topSwap = lst.Count - 2
      41. Dim lastSwap As Integer
      42. Do
      43. lastSwap = 0
      44. For i = 0 To topSwap
      45. If lst(i) > lst(i + 1) Then
      46. 'If ckStepwise.Checked Then Await Task.Delay(500)
      47. If ckStepwise.Checked Then Await Wait()
      48. lst.Swap(i, i + 1)
      49. lastSwap = i
      50. End If
      51. Next
      52. topSwap = lastSwap - 1
      53. Loop Until lastSwap = 0
      54. End Sub
      56. Private Function Wait() As Task
      57. Return Task.Run(Function() _Blocker.WaitOne())
      58. End Function
      60. End Class
      62. Friend Module Extensions
      63. <Extension> _
      64. Public Sub Swap(Of T)(Subj As IList(Of T), I1 As Integer, I2 As Integer)
      65. Dim Tmp = Subj(I1)
      66. Subj(I1) = Subj(I2)
      67. Subj(I2) = Tmp
      68. End Sub
      69. End Module
      Eine Listbox, gebunden an eine BindingList(Of Integer) (#7, 12).
      Es gibt die 3 Buttons btReset, btBubbleSort und btStep, eine Checkbox ckStepwise, sowie die beiden Algorithmen Generate und BubbleSort.
      Alles selbsterklärend, wie man sieht: Nomen est Omen!
      Innegehalten wird in Zeilen #32, sowie (#46), #47
      Einzig zu erklären vlt. das AutoResetEvent: Dessen Methode .WaitOne() blockiert den aktuellen Thread so lange, bis von einem anderen Thread aus mit .Set() freigeschaltet wird.
      Auf das erstaunlichste, nämlich den Async/Await-Pattern selbst gehe ich hier nicht ein, weil darauf bin ich hier schon eingehender drauf eingegangen: Async, Await und Task
      Naja - kurz: Am Await-Aufruf bricht eine Methode verfrüht ab, und der Aufrufer fährt fort, ohne blockiert worden zu sein.
      Währenddessen wird das Awaitete in einem Task abgearbeitet. Ist der Task fertig hopft die Methode auf einmal wieder rein, und setzt fort als sei nichts gewesen. 8|
      Klar soweit ?

      same in c#

      C#-Quellcode

      1. public partial class frmSortVisualizerCs : Form {
      2. private BindingList<int> _List = new BindingList<int>();
      3. private AutoResetEvent _Blocker = new AutoResetEvent(true);
      5. public frmSortVisualizerCs() {
      6. InitializeComponent();
      7. listBox1.DataSource = _List;
      8. btStep.Click += (s, e) => _Blocker.Set();
      9. btReset.Click += (s, e) => Generate(30, 30);
      10. btBubbleSort.Click += (s, e) => BubbleSort(_List);
      11. ckStepwise.CheckedChanged += ckStepwise_CheckedChanged;
      12. }
      13. void ckStepwise_CheckedChanged(object sender, EventArgs e) {
      14. btStep.Enabled = ckStepwise.Checked;
      15. _Blocker.Set();
      16. }
      17. private async void Generate(int max, int count) {
      18. _List.Clear();
      19. var rnd = new Random(0);
      20. for (var i = -1; ++i < count; ) {
      21. if (ckStepwise.Checked) await Wait();
      22. _List.Add(rnd.Next(max));
      23. }
      24. }
      25. private async void BubbleSort(IList<int> lst) {
      26. //repeat: run up, compare each element with its successor - if greater: Swap
      27. //topSwap/lastSwap consider, that the elements behind the last swap-Position of the previous Run-up already are sorted
      28. var topSwap = lst.Count - 2;
      29. int lastSwap;
      30. do {
      31. lastSwap = 0;
      32. for (var i = 0; i <= topSwap; ++i) {
      33. if (lst[i] > lst[i + 1]) {
      34. //if (ckStepwise.Checked) await Task.Delay(500);
      35. if (ckStepwise.Checked) await Wait();
      36. lst.Swap(i, i + 1);
      37. lastSwap = i;
      38. }
      39. }
      40. topSwap = lastSwap-1;
      41. } while (lastSwap != 0);
      42. }
      43. private Task Wait() {
      44. return Task.Run(() => _Blocker.WaitOne());
      45. }
      46. }
      47. public static class Extensions {
      48. public static void Swap<T>(this IList<T> Subj, int I1, int I2) {
      49. var Tmp = Subj[I1];
      50. Subj[I1] = Subj[I2];
      51. Subj[I2] = Tmp;
      52. }
      53. }


      Vielen Dank übrigens an @RodFromGermany, @NyuQz und @RushDen, weil die haben mich inspiriert, wie man so sagt, hier und hier :thumbsup:
      Dateien

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

    Facebook
    Telefonspende