Überwachung von mehrfach auftretenden array einträgen

[schneitzmaster]

Hey Leute,

ich habe einen n x 3 dimensionalen integer array. In einer Schleife arbeite ich mich durch alle Zeilen. Die Zahlen in einer Zeile sind stets verschieden. Die Reihenfolge der Zahlen in einer Zeile spielt keine Rolle. In dem großen Array können gleiche Zeilen auftreten. Den integer-array kann ich nicht verändern.
Ich möchte nun jedes auftretende Zahlentripel nur einmal bearbeiten und suche nach eine effizienten Methode dies zu realisieren.

Momentan erstelle ich mir "dynamisch" ein dictionary und überprüfe in jedem schleifendruchgang, ob das aktuelle zahlentripel schon vorhanden ist oder nicht.
Hier der Beispiel Code:

Code: Alles auswählen

import numpy as np
import itertools
source =  np.arange(0, 5)
combos = itertools.combinations(source, 3)
big_arr = np.array( [e for e in combos] )
big_arr = np.vstack( (big_arr,big_arr[:,[1,2,0]],big_arr[:,[0,2,1]],big_arr) )
big_arr = big_arr[np.random.randint(len(big_arr),size=len(big_arr))]
# ROUTINE
b = {}
for a_i in big_arr:
    a_i = tuple(np.sort(a_i))
    if a_i not in b:        
        b.update( {a_i:True} )
        # DO STUFF
    else:
        print 'a_i processed already'

Gibt es eine schnellere Methode, da ja in jedem Schleifendruchgang das dictionary b durchsucht wird? Ich hatte vielleicht an einen 3-D sparse-array gedacht aber festgestelt, das numpy soetwas nicht anbietet.
Ich wäre dankebar für jegliche Idee.

[BlackJack]

@schneitzmaster: Wörterbücher nach einem Schlüssel ”durchsuchen” ist schnell denn genau dafür sind sie ja da. Wobei Du den *Wert* ja gar nicht brauchst, also ist das eigentlich nur ein `set` was Du da bräuchtest.

Und wie kommt man bitte auf ``b.update( {a_i:True} )``? Umständlicher kann man ``b[a_i] = True`` ja kaum schreiben. Aber wie gesagt, eigentlich bräuchte man da ein `set` und `b.add(a_i)`.

Dir ist klar das `np.sort()` „in place” arbeitet und Dir Dein `big_arr` zeilenweise sortiert‽

Code: Alles auswählen

In [31]: A
Out[31]: 
array([[3, 2, 1],
       [1, 2, 3]])

In [32]: A[0]
Out[32]: array([3, 2, 1])

In [33]: A[0].sort()

In [34]: A
Out[34]: 
array([[1, 2, 3],
       [1, 2, 3]])

Ansonsten könnte es vielleicht sinnvoll sein mehr mit Numpy-Mitteln zu arbeiten und sich `numpy.sort()`/die `sort()`-Methode und `numpy.unique()` mal genauer anzuschauen.

[EyDu]

Und einfach mal mit der Suchmaschine deiner Wahl nach "numpy unique rows" suchen und den ausführlichen Thread auf Strackoverflow dazu durchlesen...

[EyDu]

Da fällt mir auf: Du hattest doch vor einem Monat quasi die identische Frage.

[schneitzmaster]

@EyDu: Der Beitrag auf Stackoverflow ist mir bewusst. Leider kann ich den big_array nicht verändern weil ich die zahlen tripel quasi "on-the-fly" bekomme. Ich hatte auch schon gedacht erst einmal eine schleife durchlaufen zu lassen um den big_array zu erzeugen, dann unique_rows verwenden um schließlich noch mal über den reudzierten array zu laufen.

@BlackJack: Vielen Dank für den Hinweis mit set. Diese Funktion war mir bisher nicht Bekannt ist aber eigentlich Ideal dafür geeignet.
Die Zwuweisung bzgl. des dictionaries hatte ich irgendwo im Netz gefunden... bin halt noch kein waschechter Python Programmierer
Deinen Komentar mit sorted verstehe nicht so ganz schießlich will ich ja nur den 1-D array a_i sortieren. Das wird mit sort realisiert und macht von daher keine Probleme.

@EyDu: Welche Frage identische Frage meinst du?

[BlackJack]

@schneitzmaster: Du solltest Dir mein `sort()`-Beispiel noch einmal genau anschauen! Vielleicht wird es Dir etwas klarer wenn ich da noch ein `a_i` einführe:

Code: Alles auswählen

In [39]: A
Out[39]: 
array([[3, 2, 1],
       [1, 2, 3]])

In [40]: a_i = A[0]

In [41]: a_i
Out[41]: array([3, 2, 1])

In [42]: a_i.sort()

In [43]: a_i
Out[43]: array([1, 2, 3])

In [44]: A
Out[44]: 
array([[1, 2, 3],
       [1, 2, 3]])

Das sortiert die erste Zeile in `A` und da Du jede Zeile von `big_arr` sortierst ist am Ende das komplette `big_arr`-Array verändert (ausser die Zeilen die sowieso schon in der sortierten Reihenfolge vorlagen).

Deine Antwort an EyDu verstehe ich nicht. Was bedeutet hier „on the fly”? Soll das heissen Du bekommst die Werte für die Zeilen nach und nach und gehst für *jeden* neuen Zeilendatensatz immer wieder das ganze grosse Array durch‽

[EyDu]

@EyDu: Der Beitrag auf Stackoverflow ist mir bewusst. Leider kann ich den big_array nicht verändern weil ich die zahlen tripel quasi "on-the-fly" bekomme. Ich hatte auch schon gedacht erst einmal eine schleife durchlaufen zu lassen um den big_array zu erzeugen, dann unique_rows verwenden um schließlich noch mal über den reudzierten array zu laufen.

Wenn du die Daten live bekommst, warum verwendest du dann überhaupt ein NumPy-Array? Oder hast du hier einfach nur ein unglücklich gewähltes Beispiel gezeigt? Die sind nicht zum ständigen aktualisieren gedacht.

Deinen Komentar mit sorted verstehe nicht so ganz schießlich will ich ja nur den 1-D array a_i sortieren. Das wird mit sort realisiert und macht von daher keine Probleme.

Du schreibst in deinem ersten Beitrag, dass du das Array nicht verwenden darfst, verwendest dann aber np.sort, welches dein Array verändert

@EyDu: Welche Frage identische Frage meinst du?

Den hier.

[schneitzmaster]

@BlackJack: Jetzt verstehe ich deinen Einwand. Allerdings spielt das für mein Beispiel keine Rolle, da ich big_arr nur für das Minimalbeispiel erzeugt habe.

Vielleicht kann ich mein Problem noch einmal etwas genauer beschreiben. Ich produziere mir ein Zahlentripel a_i (im Minimalbeispiel die Zeilen aus big_arr). Dieses passiert "On-The-Fly" also während des schleifendurchlaufes. Bei den Zahlentripel spielt die Reihenfolge keine Rolle und es treten keine Zahlen in einem Triplet doppelt auf.
Nun muss mit dem Zahlentripel eine Operation durchgeführt werden.
Stoße ich im Verlauf des Schleifendurchlaufes wieder auf das Zahlentripel darf diese Operation nicht noch einmal durchgeführt werden.
Der big_arr wurde von mir in dem Minimalbeispiel lediglich zur zur Generierung des Beispiels an sich erstellt. Es ist mir also egal ob ich den während des Durchlaufs sortiere oder nicht (deswegen habe ich auch den Kommentar nicht ganz verstanden).

@EyDu: Numpy habe ich ja nur verwendet um den big_arr zu erstellen. Bei der eigentlichen for-schleife verwende ich ja dann ein dictionary zum updaten. np.sort habe ich nur verwendet um a_i zu sortieren. das war meine eigentliche intension. sorted() wäre wohl passender.
Bei Meiner Frage vor einem Monat habe ich von Anfang an vollen Zugriff auf array hier nicht. Das ist wohl in meinem Beispiel falsch rüber gekommen.

[EyDu]

Dann solltest du dringend mal über den Begriff "Minimalbeispiel" nachdenken. Eine einfache Liste mit vier oder fünf händisch erstellten Tupeln hätte vollkommen ausgereicht um dein Problem zu demonstrieren. Stattdessen bringst du NumPy mit ins Spiel, blähst das ganze Problem damit riesig auf und kommst dann noch mit Geschwindigkeitsproblemen. Natürlich gehen wir dann davon aus, dass das Problem mit NumPy gelöst werden soll.

Mit einem billigen Beispiel von 10 Zeilen hätte dann jeder das Problem gleich gesehen und die ganze Diskussion wäre mit dem ersten Beitrag erledigt gewesen, dass du das einfach mit Mengen lösen kannst. In einer handvoll unkomplizierter Zeilen. Ohne eine Vektorisierung des Problems, welche gar nicht benötigt wird.

[schneitzmaster]

Für mich hat die Größe von big_arr eine Rolle gespielt. Ohne den wäre mir selbst das nicht klar geworden und ich kann eben immer nur von mir ausgehen und nicht deine Denkweise erraten.
Sorry wenn mein Minimalbeispiel dir nicht gefallen hat. :K

Für mich heißt Minimalbeispiel ein Problem in sowenig wie möglich Code-Zeilen darstellen. Ich hab versucht in 7 Zeilen (code zeile 9 - 16) das Problem darzustellen. Deswegen auch die Unterteilung mit dem Kommentar #Routine. Der Rest war nur "vorgeplänkel". Gut das hätte ich noch schreiben können, dachte aber der Kommentar reicht aus.

[EyDu]

Du willst jetzt nicht ernsthaft behaupten, dass

Code: Alles auswählen

import numpy as np
import itertools
source =  np.arange(0, 5)
combos = itertools.combinations(source, 3)
big_arr = np.array( [e for e in combos] )
big_arr = np.vstack( (big_arr,big_arr[:,[1,2,0]],big_arr[:,[0,2,1]],big_arr) )
big_arr = big_arr[np.random.randint(len(big_arr),size=len(big_arr))]

leichter und übersichtlicher ist als

Code: Alles auswählen

big_arr = [
    (1, 2, 3),
    (4, 5, 6),
    (1, 3, 2),
    (7, 8, 9)]

? Das deckt das Problem ebenfalls ab.

Für mich hat die Größe von big_arr eine Rolle gespielt.

In deinem Problem gibt es aber gar kein großes Array. Du behandelst nur viele Elemente, das ist etwas ganz anderes.

[BlackJack]

@schneitzmaster: Also mich hat die *Überschrift* des Themas — „Überwachung von mehrfach auftretenden array einträgen” — nicht eine Sekunde daran zweifeln lassen dass Du tatsächlich ein grosses Array vorliegen hast und in dem Du etwas suchst. Ich wäre bei dem Betreff nicht im Traum darauf gekommen das es *kein* Array mit den ganzen Werten geben könnte. :K

[Sirius3]

@schneitzmaster: ich habe auch ein großes Numpy-Array als Ausgansdaten für das Problem gesehen.
Nochmal die Lösung für Dein neues Problem, inklusive Minimalbeispiel:

Code: Alles auswählen

def sorted_unique(iterable):
    seen = set()
    for item in iterable:
        item = tuple(sorted(item))
        if item not in seen:
            seen.add(item)
            yield item

# Beispiel
input_data = itertools.permutations(range(5),3)
for item in sorted_unique(input_data):
    # do something