Wie prüft man effizient, ob ein Wert mehrfach in einer Liste vorkommt?

[Erepaing54]

ich arbeite gerade an einem kleinen Projekt, bei dem ich überprüfen muss, ob bestimmte Werte mehrmals in einer Liste vorkommen. Dabei geht es nicht nur darum zu wissen, ob ein Wert doppelt ist, sondern auch wie oft.

Aktuell mache ich das so:

Code: Alles auswählen

werte = [1, 2, 3, 2, 4, 1, 5]
for w in set(werte):
    if werte.count(w) > 1:
        print(f"Wert {w} kommt {werte.count(w)}-mal vor.")

Das funktioniert, aber ich frage mich, ob es eine performantere oder "pythonic" Art gibt, das zu machen – besonders bei großen Listen.

Hat jemand Tipps oder Best Practices?

[pillmuncher]

@Erepaing54: Du suchst collections.Counter.

[Pedroski55]

Ich mag gerne so etwas möglichst ohne Zugriff auf builtins oder Module.

Code: Alles auswählen

import sys

werte = [1, 2, 3, 2, 4, 1, 5, 6, 7, 8, 7, 9 , 10, 11, 3,
         1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2,
         1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2,
         1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2,
         1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2,
         1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2,
         1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2,
         2, 3, 2, 2, 3, 2, 2, 3, 2, 2, 3, 2, 2, 3, 2,]

sys.getsizeof(werte) # 1064

schon_gesehen = []
tuples = []
# finde alle unique Nummern
# da die Zahlen sich wiederholen viel, kontrolliere erst, ob wir die Zahl schon haben
for i in range(len(werte)):
    # das erste Mal immer falsch
    if werte[i] in schon_gesehen:
        continue
    else:
        # immer nur vorwärts von werte[i] gucken
        rest = werte[i:]
        schon_gesehen.append(werte[i])        
        zahl = 0
        for r in rest:
            if r == werte[i]:
                zahl +=1
        tup = (werte[i], count)
        tuples.append(tup)    

Das kann man verkleinern:

Code: Alles auswählen

# list comprehension    
res = [(w, werte.count(w)) for w in set(werte)]

Oder mit generator wenn werte enorm ist:

Code: Alles auswählen

# generator, gut wenn werte sehr sehr gross ist
# ein generator ist sehr klein im Speicher, etwa 216 bytes egal wie gross werte sei
res = ((w, werte.count(w)) for w in set(werte))
sys.getsizeof(res) # 216

for r in res:
    print(r)

Oder:

Code: Alles auswählen

# filtrieren Resultat mit werte.count(w)
res = ((w, werte.count(w)) for w in set(werte) if werte.count(w) > 1)
sys.getsizeof(res) # 216

for r in res:
    print(r)

Finde set(werte) ohne Zugriff auf set()

Code: Alles auswählen

# leere Liste
schon_gesehen = []

# finde set(werte) ohne Zugriff auf set()
for w in werte:
    if w in schon_gesehen:
        continue
    else:
        schon_gesehen.append(w)

Viel Spass!

[Pedroski55]

Weiß nicht wie man etwas abändert, also schreibe ich hier:

Dies:

Code: Alles auswählen

tup = (werte[i], count)

hätte so sein müssen:

Code: Alles auswählen

tup = (werte[i], zahl)

[kbr]

Ich mag gerne so etwas möglichst ohne Zugriff auf builtins oder Module.

Ich nutze gerne builtins oder die stdlib. Dort sind die Bugs, die ich einführen würde, üblicherweise gefixt und bei laufzeitkritischen Aktionen besteht die Chance, das auch dies bereits optimiert ist.

[DeaD_EyE]

Es ist gut, zu wissen, wie man etwas selbst implementiert. Man sollte aber die builtins und stdlib nutzen, da dort vieles in C programmiert worden ist und optimiert ist.

[snafu]

Da stellen sich die typischen Fragen:

- Was sind für dich große Listen? Also wie viele Elemente haben die?
- Hast du mal probiert, ob der Ansatz mit collections.Counter() tatsächlich zu langsam ist?

[__blackjack__]

@snafu: Wer hat denn behauptet das `collections.Counter()` zu langsam sei?

@Pedroski55: Du benutzt Listen, also ein `builtin`. Du benutzt `range()`. Ebenfalls `builtin`. `len()` — rate mal wo das her kommt. Und Tupel und ganze Zahlen ebenfalls.

`collections.Counter()` könnte man auch leicht selbst schreiben, und das wäre dann effizienter *und einfacher* als das was Du da im ersten Beispiel verbrochen hast. Ernsthaft ``# immer nur vorwärts von werte[ i ] gucken`` ist an sich eine nette Idee wenn das tatsächlich nur die Werte ab Index i anschauen würde *ohne* eine Kopie der Werte von `i` ab zu machen.

Die Lösung wo zweimal `count()` mit dem gleichen Argument aufgerufen wird, ist offensichtlich völlig unnötig doppelt so langsam wie sie sein müsste.

[snafu]

@snafu: Wer hat denn behauptet das `collections.Counter()` zu langsam sei?

Wurde nicht direkt behauptet, aber ich habe das als Vermutung des OP so herausgelesen. Das trifft aber natürlich nicht zu. Der Counter selbst ist zwar größtenteils in Python geschrieben, aber sein zeitkritischer Teil wurde in die Hilfsfunktion _count_elements() ausgelagert, die ein Mapping erwartet. Und die ist in vielen Fällen in C geschrieben und dementsprechend optimiert. Via ``timeit`` lässt sich auch leicht herausfinden, dass der Counter aus dem collections-Modul deutlich schneller beim Zählen ist als die Python-Schleife mit ``get(item, 0) + 1``.

[Pedroski55]

Alles gute Punkte! Bedankt.

Nur, ich habe keine Ahnung wie alle diese wunderbaren Module und builtins ihre Wunder wirken, drum mag ich gerne sehen, wie ich Ähnliches zustande bringen kann, möglichst, nur möglichst, ohne Zugriff drauf.

Ganz klar, kannst nicht Python ganz und gar ohne Python machen! Und für die kleine Skripte die ich versuche, Schnelligkeit ist das Letzte worüber ich nachgrübele!

[snafu]

Sofern man zumindest die Grundfunktionen eines Wörterbuchs benutzen "darf", wäre dann dies hier eine Möglichkeit:

Code: Alles auswählen

def count(items):
    counter = {}
    for item in items:
        if item not in counter:
            counter[item] = 1
        else:
            counter[item] += 1
    return counter

[nezzcarth]

Nur, ich habe keine Ahnung wie alle diese wunderbaren Module und builtins ihre Wunder wirken, drum mag ich gerne sehen, wie ich Ähnliches zustande bringen kann, möglichst, nur möglichst, ohne Zugriff drauf.

Das kann aus meiner Sicht auch ein legitimer und sinnvoller Ansatz sein, wenn man Code zu Lernzwecken schreibt. In der praktischen Anwendungen – für Code, bei dem das Lösen tatsächlicher Probleme im Vordergrund steht – sind Pythons "included batteries" nach meiner Ansicht aber einer der Vorteile dieser Sprache und haben, denke ich, einen nicht geringen Anteil an ihrer Popularität. Wenn man diese Sachen nicht benutzen möchte, fällt einer der Gründe, die für Python sprechen und einige der Nachteile aufweigen,, weg und dann wird man vielleicht mit einer anderen Sprache glücklicher.

[__blackjack__]

@snafu: `_count_elements()`? Wo? Und der OP hat genau einen Beitrag geschrieben um einen Spamlink in der Signatur unterzubringen. Der Text ist damit eh nicht so wirklich ernstnehmbar.

[snafu]

@snafu: `_count_elements()`? Wo?

https://github.com/python/cpython/blob/ ... __.py#L533