Elemente mehrdimensionaler Arrays summieren

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

Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von Haudruferzappeltnoch.

    Elemente mehrdimensionaler Arrays summieren

    Hallo,

    ich möchte aus einem großen Boolean(,) gerne wissen wieviele Trues drin sind.
    Nur dauert das so elendig lange:

    VB.NET-Quellcode

    1. Dim Count = 0
    2. For each b in DerGroßeBoolSpeicher
    3. If b Then Count += 1
    4. Next

    Und mit LINQ kann man an mehrdimensionale Arrays nicht dran.
    Wenn ich List(Of ) oder ähnliches verwende dann wird das hinzufügen der einzelnen Elemente zum Zeitfresser.
    Habt ihr da nen Tipp?
    Vielleicht ist die "Datenmenge" auch zu groß. Ca. 50.000.000 macht 10 Sekunden (Dadrin 15 Mio Bools zu setzen dauert dagegen nur 0,1 Sekunden)

    Viele Grüße

    Was mir spontan einfällt, ist bei so vielen Werten das in mehrere, kleinere Arrays aufzuteilen und dann in versch. Tasks oder Threads die Werte aufzuaddieren.

    Bspw. wenn du 50 Mio Werte hast, dann kannst du das Array in 50 Threads/Tasks verteilen und dann einfach nur entsprechend den Pivot mitgeben und ab dann N weiterzählen.

    Dann mit ​Task.FromResult(countedTrues); den Wert zurückgeben. Alle Tasks in einer Liste speichern und dann ​Task.WaitAll() anwenden.
    Quellcode lizensiert unter CC by SA 2.0 (Creative Commons Share-Alike)

    Meine Firma: Procyon Systems
    Meine Privatwebseite: SimonC.eu

    Bitte nicht wundern, wenn meine Aktivitäten im Forum etwas langsamer sind, ich baue gerade mein Nebengewerbe zum Vollgewerbe aus.
    Ich versuche auf euch zurückzukommen :)

    @siycah Wenn, dann mit Parallel.For, das ist einfacher und wird vom System optimiert.
    @Haudruferzappeltnoch Du brauchst zwei Schleifen.
    Die äußere Parallel.For über die Zeilen, die innere For über die Spalten.
    Die Spalten-Ergebnisse in ein Array mit den Zeilen-Indizes, diese am Ende summieren.
    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!

    Ich mache das leider gehörig falsch, ich kriege bei jedem mal ein anderes Endergebnis, wenn ich eine große (aber immer gleiche) Datenmenge versuche. Für kleine Mengen stimmts.

    VB.NET-Quellcode

    1. Dim Count = 0
    2. Dim arr(_Cells.GetLength(1)) As Integer
    3. For i = 0 To _Cells.GetLength(1) - 1
    4. Dim a = i
    5. Parallel.For(0, _Cells.GetLength(0), Sub(x)
    6. If _Cells(x, a) Then arr(a) += 1
    7. End Sub)
    8. Count += arr(i)
    9. Next

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

    Wer's nachspielen will, ich kann's nachstellen. Es wird immer mal wieder bei der Prüfung gestoppt, weil das Ergebnis nicht passt.

    VB.NET-Quellcode

    1. Imports System.Threading.Tasks
    3. Friend Class Form1
    4. Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
    5. Dim _Cells(99, 99) As Boolean
    6. Dim Foo = True
    7. For i = 0 To 99
    8. For j = 0 To 99
    9. _Cells(i, j) = Foo
    10. Next
    11. Foo = Not Foo
    12. Next
    14. Dim Count = 0
    15. Dim arr(_Cells.GetLength(1)) As Integer
    16. For i = 0 To _Cells.GetLength(1) - 1
    17. Dim a = i
    18. Parallel.For(0, _Cells.GetLength(0), Sub(x)
    19. If _Cells(x, a) Then arr(a) += 1
    20. End Sub)
    21. If arr(i) <> 50 Then Stop
    22. Count += arr(i)
    23. Next
    25. End Sub
    26. End Class

    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.

    Die Größe kann da ein wenig abweichen, bei 99 kriege ich noch keine Fehler, ab 150 ca.
    Ich denke man kann RFGs Vorschlag auf zwei Weisen verstehen, ich habe es nochmal umgebaut, was eine Performancesteigerung bringt und das Limit, ab dem Fehler auftreten, anhebt. Allerdings bleibt da das Problem generell bestehen.

    VB.NET-Quellcode

    1. Sub Main()
    2. Dim size = 3250
    3. Dim _Cells(size, size) As Boolean
    4. Dim Foo = True
    5. For i = 0 To size
    6. For j = 0 To size
    7. _Cells(i, j) = Foo
    8. Next
    9. Foo = Not Foo
    10. Next
    11. 'Kontrolle
    12. Dim CountReal = 0
    13. For i = 0 To size
    14. For j = 0 To size
    15. If _Cells(i, j) Then CountReal += 1
    16. Next
    17. Next
    18. '
    19. Dim Count = 0
    20. Parallel.For(0, _Cells.GetLength(0), Sub(x)
    21. Dim g = 0
    22. For j = 0 To _Cells.GetLength(1) - 1
    23. If _Cells(x, j) Then g += 1
    24. Next
    25. Count += g
    26. End Sub)
    27. If Count <> CountReal Then Throw New Exception
    28. Console.ReadKey()
    29. End Sub
    Hier scheiterts bei ca. 3250+, das wären ca. 10Mio. Aber was mir aufgefallen ist, da ich zur Kontrolle nochmal ohne Parallel nachrechne, ist, dass es deutlich besser läuft als bei meinem ersten Versuch.

    Der Unterschied ist das For each Versus normales For, damit wird es schon deutlich besser (50 Mio. 0,8 Sekunden):

    VB.NET-Quellcode

    1. Dim Count = 0
    2. For y = 0 To _Cells.GetLength(1) - 1
    3. For x = 0 To _Cells.GetLength(0) - 1
    4. If _Cells(x, y) Then Count += 1
    5. Next
    6. Next

    Ich schaue mal, ob ich noch ein bisschen basteln kann, aber so bin ich langsam in einem Bereich mit dem ich leben kann.

    @Haudruferzappeltnoch In Deinen letzten beiden Snippets wird _Cells.GetLength(a) mal _Cells.GetLength(b) aufgerufen, das kannst Du per Variable nach außen ziehen.
    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!

    Meinst du:

    VB.NET-Quellcode

    1. Dim Count = 0
    2. Dim xTop = _Cells.GetLength(0) - 1
    3. Dim yTop = _Cells.GetLength(1) - 1
    4. For y = 0 To yTop
    5. For x = 0 To xTop
    6. If _Cells(x, y) Then Count += 1
    7. Next
    8. Next

    Habe außerdem festgestellt, dass ein ArrayArray noch schneller ist (0,2 Sekunden). Das sollte jetzt so langsam maximiert sein, zumindest ists jetzt im Bereich des Bools setzen. Verrückt was die Schleife ausmacht

    VB.NET-Quellcode

    1. Dim Count = 0
    2. Dim xTop = _Cells.Length - 1
    3. Dim yTop = _Cells(0).Length - 1
    4. For y = 0 To yTop
    5. For x = 0 To xTop
    6. If _Cells(x)(y) Then Count += 1
    7. Next
    8. Next

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

    Haudruferzappeltnoch schrieb:

    Habe außerdem festgestellt, dass ein ArrayArray noch schneller ist
    Dann probiere mal ein ein-dimensionales Array aus, da brauchst Du keine Index-Rechnung:

    VB.NET-Quellcode

    1. Dim Count = 0
    2. Dim xTop = _Cells.Length - 1
    3. For x = 0 To xTop
    4. If _Cells(x) Then Count += 1
    5. Next
    Das habe ich in einem anderen Kontext mal optimiert:
    Die Index-Rechnung (Zeile * Breite + Spalte) seibst zu machen bringt auch was.
    =====
    Probier mal, _Cells()() mit Parallel.For zu bearbeiten, das dürfte besser laufen als _Cells(,).
    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!

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

    Erste Tests ergeben bei mir, dass eine eigene Zählvariable pro Parallel.For-Durchlauf das Problem tatsächlich beseitigt.
    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.

    Zum Beispiel funktioniert (vgl. Post 6, Code 1):

    VB.NET-Quellcode

    1. Sub Main()
    2. Dim size = 3250 '+++
    3. Dim _Cells(size, size) As Boolean
    4. Dim Foo = True
    5. For i = 0 To size
    6. For j = 0 To size
    7. _Cells(i, j) = Foo
    8. Next
    9. Foo = Not Foo
    10. Next
    11. 'Kontrolle
    12. Dim CountReal = 0
    13. For i = 0 To size
    14. For j = 0 To size
    15. If _Cells(i, j) Then CountReal += 1
    16. Next
    17. Next
    18. '
    19. Dim Count(_Cells.GetLength(0) - 1) as Long
    20. Parallel.For(0, _Cells.GetLength(0), Sub(x)
    21. For j = 0 To _Cells.GetLength(1) - 1
    22. If _Cells(x, j) Then Count(x) += 1
    23. Next
    24. End Sub)
    25. If Count.Sum <> CountReal Then Throw New Exception
    26. Console.ReadKey()
    27. End Sub
    Benchmarks hab ich leider nicht dafür. Aber size kann ich erhöhen bis ich andere Fehler provoziere, wie Speichermangel.

    Also das ist soweit was Parallel.For angeht. Ich habe da noch einen Faktor 3-4 rausgekriegt. Entscheidend war für mich jedoch das For each und der Arraytyp _Cells(,) vs _Cells()()

Facebook
Telefonspende