Doppelte Zahlen in array finden

  • VB.NET

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

    Du sortierst das Array und vergleichst jeden Wert mit seinem Nachbarn.

    VB.NET-Quellcode

    1. Array.Sort(WERTE)
    Und sieh Dir auch mal dies an:

    VB.NET-Quellcode

    1. Array.Sort(WERTE, Werte2)
    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!

    TG22997 schrieb:

    ob es sich in der selben line wiederholen kann

    Ja, kann es, aber NUR BEI STRINGS. Andere Werte haben keine Leerzeichen und können somit nicht öfter vorkommen.

    456 456
    => klappt nicht


    Die Items werden also nur "Reihenweise" vergleicht.
    /nicht getestet

    wo ist dann das problem jedes item zu vergleichen... mit distinct kenn ich mich nicht aus weil ich schon lange
    nicht mehr intensiv programmiert habe. Aber hier mein Lösungsversuch mittels zwei schleifen:

    VB.NET-Quellcode

    1. Dim aList As New ArrayList
    2. For Each item As String In aList
    3. For Each nitem As String In aList
    4. If item = nitem Then
    5. 'Doppelte Elemente vorhanden
    6. End If
    7. Next
    8. Next

    Ist natürlich unsauber ich weiß... Aber habe ich noch nie gebraucht und wie gesagt muss ich mich
    mal mit Distinct auseinandersetzen ;D
    Würde mich auch darüber freuen wenn mir jemand Distinct erklärt.
    MfG Tim

    Enumerable.Distinct(Of TSource)

    Gibt mithilfe des Standardgleichheitsvergleichs zum Vergleichen von Werten unterschiedliche Elemente aus einer Sequenz zurück.

    msdn.microsoft.com/de-de/library/vstudio/bb348436.aspx

    Mit Distinct (Englisch für "eindeutig") werden doppelte Elemente in einer "Liste" über Board geschmissen.
    Mein Code ruft die Länge des eindeutigen Arrays ab (also dem von Distinct()) & die des regulären Arrays.
    Dann werden beide Längen verglichen: Wenn das eindeutige Array weniger Elemente als das Reguläre hat, dann sind folglich Doppelte Elemente vorhanden,
    /nicht getestet

    Vielen Dank für eure Hilfe.

    @RodFromGermany: mit array.sort ist das array bereits sortiert.
    Was ist denn der Unterschied zwischen deinen beiden Varianten?

    @rotherford:ich habe den Code ein bisschen gekürzt und angepasst; funktioniert:

    VB.NET-Quellcode

    1. Dim arr(0 To 6) As Long
    2. {Wertezuweisung des Arrays}
    3. If arr.Length > arr.Distinct().Count() Then
    4. MsgBox("doppelte")
    5. Else
    6. MsgBox("keine doppelte")
    7. End If


    @TG22997: meine Auflistung sieht so aus: 1; 2; 3; 3; 4; 5; 6


    Gruß Ludwig

    Hi
    performant sind beide genannten Methoden nicht. Sortierung ist immer so ein Thema, aber beide Methoden führen eine Menge unnötiger Operationen aus. Wie wär's mit folgendem?

    VB.NET-Quellcode

    1. Public Module CustomExtensions
    2. <Runtime.CompilerServices.Extension()> _
    3. Public Function IsDistinct(Of T)(ByVal enumeration As IEnumerable(Of T)) As Boolean
    4. Dim previous As ICollection(Of T) = New LinkedList(Of T)()
    5. For Each v As T In enumeration
    6. If previous.Contains(v) Then Return False
    7. previous.Add(v)
    8. Next
    9. Return True
    10. End Function
    12. <Runtime.CompilerServices.Extension()> _
    13. Public Function IsDistinct(Of T)(ByVal enumeration As IEnumerable(Of T), ByVal comparer As IEqualityComparer(Of T)) As Boolean
    14. Dim previous As ICollection(Of T) = New LinkedList(Of T)()
    15. For Each v As T In enumeration
    16. For Each c As T In previous
    17. If comparer.Equals(v, c) Then Return False
    18. Next
    19. previous.Add(v)
    20. Next
    21. Return True
    22. End Function
    23. End Module

    VB.NET-Quellcode

    1. Dim arr() As String = {"a", "b", "a", "c"}
    2. MessageBox.Show(arr.IsDistinct().ToString())

    Bisschen Hintergrundwissen: Bei einer geringen Anzahl von Elementen fällt der Performanceschub zwar nicht ins Gewicht, aber für große dafür ggf. sehr stark, da wirklich nur die nötigsten Operationen ausgeführt werden. Man könnte es theoretisch auch ohne Pufferung rein auf der übergebenen Enumeration machen. Ist halt nicht sichergestellt, dass der Enumerator performant implementiert ist.
    Wenn man die Performance noch weiter steigern möchte, kann man auch noch den Hashcode verwenden, um die Menge der zu vergleichenden Elemente weiter einzuschränken. Das erfordert allerdings, dass die Elemente ihren Hashcode während dem Aufruf nicht ändern.

    Hab's noch mal mit dem Dictionary ergänzt. Hat mich jetzt grad' mal interessiert:
    Spoiler anzeigen

    VB.NET-Quellcode

    1. Public Module CustomExtensions
    2. <Runtime.CompilerServices.Extension()> _
    3. Public Function IsDistinct(Of T)(ByVal enumeration As IEnumerable(Of T)) As Boolean
    4. Dim previous As ICollection(Of T) = New LinkedList(Of T)()
    5. For Each v As T In enumeration
    6. If previous.Contains(v) Then Return False
    7. previous.Add(v)
    8. Next
    9. Return True
    10. End Function
    12. <Runtime.CompilerServices.Extension()> _
    13. Public Function IsDistinct(Of T)(ByVal enumeration As IEnumerable(Of T), ByVal comparer As IEqualityComparer(Of T)) As Boolean
    14. Dim previous As ICollection(Of T) = New LinkedList(Of T)()
    15. For Each v As T In enumeration
    16. For Each c As T In previous
    17. If comparer.Equals(v, c) Then Return False
    18. Next
    19. previous.Add(v)
    20. Next
    21. Return True
    22. End Function
    24. <Runtime.CompilerServices.Extension()> _
    25. Public Function IsDistinctQuick(Of T)(ByVal enumeration As IEnumerable(Of T)) As Boolean
    26. Dim clist As ICollection(Of T) = Nothing
    27. Dim previous As Dictionary(Of Integer, ICollection(Of T)) = New Dictionary(Of Integer, ICollection(Of T))
    28. Dim hashcode As Integer
    29. For Each v As T In enumeration
    30. hashcode = v.GetHashCode()
    31. If previous.TryGetValue(hashcode, clist) Then
    32. If clist.Contains(v) Then Return False
    33. Else
    34. clist = New LinkedList(Of T)()
    35. previous.Add(hashcode, clist)
    36. End If
    37. clist.Add(v)
    38. Next
    39. Return True
    40. End Function
    42. <Runtime.CompilerServices.Extension()> _
    43. Public Function IsDistinctQuick(Of T)(ByVal enumeration As IEnumerable(Of T), ByVal comparer As IEqualityComparer(Of T)) As Boolean
    44. Dim clist As ICollection(Of T) = Nothing
    45. Dim previous As Dictionary(Of Integer, ICollection(Of T)) = New Dictionary(Of Integer, ICollection(Of T))
    46. Dim hashcode As Integer
    47. For Each v As T In enumeration
    48. hashcode = comparer.GetHashCode(v)
    49. If previous.TryGetValue(hashcode, clist) Then
    50. For Each p As T In clist
    51. If comparer.Equals(v, p) Then Return False
    52. Next
    53. Else
    54. clist = New LinkedList(Of T)()
    55. previous.Add(hashcode, clist)
    56. End If
    57. clist.Add(v)
    58. Next
    59. Return True
    60. End Function
    61. End Module


    Gruß
    ~blaze~

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

    Ich verstehe heute noch nicht was du für Kenntnisse über vb.net hast...
    Habe schon lange nicht mehr programmiert. Ich glaube mit dir hatte ich
    mich damals über vb.net manchmal ausgetauscht... muss den code auch mal probieren.

    MfG Tim

    LudwigM schrieb:

    Was ist denn der Unterschied zwischen deinen beiden Varianten?
    Klick drauf und drück auf F1 (Hilfe).
    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!

    Zwischen dem IsDistinct und IsDistinctQuick ist übrigens ein echt großer Unterschied in der Performance. Hab' ein paar einfache Tests mit Random durchlaufen lassen und die Unterschiede sind echt gravierend. Der 1. Code hat bei 100000 Strings knapp 26 Sekunden gebraucht, der 2. nur 0,12. Das Dictionary selber liegt halt (fast) in O(1), während LinkedList.Contains in O(n) liegt. Da bei der 2. Methode nur die Elemente mit gleichem Hashcode in eine gemeinsame Liste gespeichert werden, müssen entsprechend nur sehr wenige Elemente verglichen werden. Nachteil am Dictionary ist halt der erhöhte Speicherbedarf und der Overhead bei großen Eingaben.

    Gruß
    ~blaze~

    Jep, wobei man häufig auch ein "Workaround" finden kann. Häufig hilft's zum Beispiel wenn man die Hashcodes "umorganisiert" (zumindest bei meinem eigenen theoretischen Dictionary :P, weiß nicht, wie das Framework-Dictionary intern arbeitet). Also zum Beispiel eine bijektive Abbildung für den Hashcode finden, sodass die Aufteilung in 4 Bytes zur Indizierung in den Hashcode-Tabellen so ausfällt, dass die Anzahl der Elemente in der Tiefe möglichst hoch ist, aber in der Breite eher gering.
    Bei dem großen Unterschied muss ich allerdings sagen, dass ich die quick-Methode bei großen Listen bevorzuge.

    Gruß
    ~blaze~