Zwei ForSchleifen performanter/übersichtlicher machen ?

  • Allgemein

Es gibt 24 Antworten in diesem Thema. Der letzte Beitrag () ist von ~blaze~.

    ~blaze~ schrieb:

    für was für eine Problemstellung verwendest du denn den Code?
    Um die Stellen zu finden, in der Text in einem Bild ist.
    Hier mal Pseudocode.

    Quellcode

    1. Für jede Zeile
    2. Für jede Spalte
    3. Wenn Farben[Zeile,Spalte] nicht weiß dann
    4. Merke Position()
    6. Für jede gefundenePosition
    7. Wenn nichtDirektUntereinander (Position[i - 1].Y != Position[i].Y)
    8. Für jede Zeile
    9. Für jede Spalte
    10. Wenn Farben[Zeile, Spalten] nicht weiß dann
    11. merkeStartPosition()
    12. Wenn Farben[Zeile, Spaltenlänge - GesamtLänge] nicht weiß dann
    13. merkeEndPosition()
    15. Füge gefundenen Textbereichen hinzu


    Nach etwa dem selben Prinzip mache ich es bei den einzelnen Buchstaben.
    Ich hatte mal überlegt das alles in eine Schleife zu machen, aber das war etwas zu wirr.

    Da würde ich ehrlich gesagt sogar ein eindimensionales Array nehmen:

    VB.NET-Quellcode

    1. For i As Integer = 0 To _entries.Length -1
    2. 'nur berechnen, wenn nötig
    3. 'Dim x As Integer = i Mod width
    4. 'Dim y As Integer = i \ width
    6. Next

    Damit holst du die "maximale" Performanz raus und über die eher intuitive Benennung x und y hast du halt auch die Übersichtlichkeit. Ich würde für die Findung dann ein BitArray anlegen, das die gleiche Länge hat, wie das Array. Für den i-ten Wert setzt du das Bit auf True, wenn es bereits besucht wurde, ansonsten bleibt es bei False, die Suche selbst erfolgt ausgehend von nicht-weißen Pixeln nach links, rechts, oben, unten, links oben, rechts oben, links unten und rechts unten und zwar über ein rekursives Verfahren (oder iterativ, das ist aber unübersichtlicher und weniger elegant). Jeder abgesuchte Pixel wird dann eben im Bit-Array markiert und auf einer zusätzlichen "Maske" markiert - die erkläre ich gleich noch. Wenn der Pixel weiß ist, wird er nicht der Maske hinzugefügt, aber dennoch als besucht markiert. Die Rekursion endet an den weißen Punkten, in der Bitmaske gesetzte Punkte werden beim Durchlaufen aller Pixel weggelassen.
    Die Maske kannst du dir einfach als ein Feld darstellen, welches für einen Ausschnitt angibt, ob der Pixel weiß oder nicht-weiß ist. Da für den rekursiven Algorithmus die Maske nach links, rechts, unten und oben wachsen kann, müsste man dafür eine geeignete Datenstruktur finden, die
    - die Enumeration möglichst effizient ermöglicht
    - die Erweiterung in eine Richtung möglichst effizient ermöglicht
    - Zusammenhängende "Kanten" möglichst schnell findet und in ein Muster einbringen kann
    - Zwei Kanten, die in einem Knoten zusammenkommen, dem gleichen Knoten zuordnet

    Ich denke daher, dass es am besten ist, wenn du die Maske einfach zusammen mit dem Bitarray kombinierst, da das ja bereits alle obigen Anforderungen unterstützt. Wähle daher einfach einen beliebigen Ausgangspunkt (bspw. den zuerst gefundenen Punkt oder für Parallelisierung den, der in der "Mitte" liegt, also den, von dem aus in den meisten Richtungen möglichst gleich viele Punkte liegen. Damit kannst du die Berechnungen pro Buchstaben möglichst ausgeglichen auf mehrere Threads verteilen), von dem aus der Buchstabe aufgespannt wird.

    Ich hoff' mal, ich habe deine Problemstellung richtig verstanden und es nicht komplett wirr erklärt :P.

    Gruß
    ~blaze~

    Das ganze, wie @~blaze~: sagt, in unsave C#, da bist Du voll performant.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Danke @~blaze~: aber so ganz verstanden hab ich es noch nicht.
    So viel habe ich bisher. (Nur der Ansatz und das was ich verstanden habe)

    C-Quellcode

    1. unsafe
    2. {
    3. bool[] map = new bool[this.colors.Length];
    4. int width = this.bitmapData.Width;
    5. for (int i = 0; i < this.colors.Length - 1; i++)
    6. {
    7. // Positionen (optional)
    8. int x = i / width;
    9. int y = i % width;
    11. // Wenn die aktuelle Farbe nicht weiß ist
    12. if ((uint)colors[i].Argb != UINTWHITE)
    13. {
    15. }
    17. // Feld als besucht markieren
    18. map[i] = true;
    19. }
    20. }

    Ich hab noch nicht ganz durchgeblickt, was genau die Taktik sein soll.
    Ich gehe nur einmal durch mein ColorArray, ist das richtig ?
    Dabei gucke ich wenn ich einen "nicht-weißen" Pixel finde. Von diesem aus suche ich (mit noch einer Schleife ?) die umliegenden Felder ab ?
    Und das was ich finde und innerhalb des Bereichs finde, markeire ich auf einer Maske.
    Wenn es so ist, dann verstehe ich nicht wieso ich das ganze auf einer Maske markieren soll und nicht direkt die gefundenen Buchstabenfarbwerte/Koordinaten auflisten soll.
    Wäre nett wenn du das vielleicht nochmal erklären könntest bitte ;)

    Also es gibt eine direkte BitArray-Klasse, da bools in .Net 4 Bytes groß sind (außer es gibt da eine Regelung, die sie beim boxing auf 1 Byte Reduziert), aber man kann dennoch einiges an Platz einsparen.

    x und y solltest du nur dann berechnen, wenn sie benötigt werden.

    C-Quellcode

    1. unsafe
    2. {
    3. fixed(uint* cb = _buffer) //Array anpinnen
    4. for(uint* cbp = cb, cbdest = cb + _buffer.Length; cbp < cbdest; cbp++)
    5. //Code
    6. }

    *c gibt dir den uint an, der am Zeiger steht
    c->[Member] führt eine indirekte Operation auf dem Wert aus
    c[Index] gibt den Wert am Index an (funktioniert ähnlich, wie der Array-Zugriff)
    usw. Das dürften die wichtigsten Operationen sein. uint* ist eine Zahl. Additionen, etc. werden in sizeof(uint)-Schritten (also 4 Byte) durchgeführt, wodurch eben cbp++ dem Wert von cbp + 4 entspricht. Den Zeiger kannst du auch casten, z.B. zu byte* und dann auf diesem byte* operieren.

    Du suchst die um einen nicht-weißen Pixel liegenden Pixel ab, aber mit einem rekursiven Algorithmus, also eine Methode, die sich selbst für den Pixel darüber, darunter, links, rechts und eben das gleiche in die Diagonale ausführt, sofern die Diagonale eine Rolle spielen soll.
    Die Auflistung ist nicht optimal, da sie keine wirkliche Region darstellt, sondern nur eine Liste und die kannst du nicht so schön verarbeiten, wie das BitArray (wenn du es kapselst, natürlich). Außerdem holst du etwas Performance raus.
    Stell dir mal vor, du nimmst ein Farbeimerwerkzeug einer Bildbearbeitungssoftware. Das füllt ebenfalls eine Art Matrix aus, wobei vom gewählten Pixel aus alle benachbarten Pixel, sofern die Farben der des anfangs gewählten Pixels entsprechen, eingefärbt werden und in diesem Fall für alle benachbarten Pixel wieder. Hier funktioniert es mehr oder weniger analog. Der Informationsgehalt ist im Array höher und die von mir angesprochenen Anforderungen an die Darstellung werden alle erfüllt, somit ist es wohl mehr oder weniger optimal.
    Das Matching der Buchstaben kann dadurch auch sehr stark optimiert werden, da du die Basislinie durch einen Algorithmus sehr leicht herausfinden kannst. Eine Toleranz in der Weißabweichung (siehe HSB-Farbraum, Brightness/Intensity) kannst du auch noch zurate ziehen, oder das Umfeld einbeziehen. Da geht einiges ;). Bei einer Liste hast du da größere Schwierigkeiten.

    Gruß
    ~blaze~

Facebook