Python: najszybsze wyszukiwanie elementu jednej listy(krotki) w drugiej.

Ostatnio w jednym skrypcie musiałem sprawdzać czy co najmniej jeden z elementów krotki znajduje się na liście, lista była dość spora więc zainteresowało mnie jaki jest najszybszy sposób na zrobienie tego.

Podobno najszybszym sposobem na to są set'y, więc postanowiłem sprawdzić o ile szybszy jest ten sposób od przeglądania listy pętlą for i sprawdzania za pomocą in czy dany element z listy znajduje się w naszej krotce(lub odwrotnie). Napisałem więc prosty skrypt, tworzący trzystu elementową listę losowych ciągów znaków, a następnie porównałem użyciu modułu timeit czas wyszukiwania za pomocą podanego przeze mnie powyżej sposobu z czasem wyszukiwania przy użyciu metody intersection, sprawdziłem też czy najpierw opłaci się przeszukiwać większą listę a potem mniejszą, czy na odwrót, żeby wyniki były bardziej wiarygodne pomiary były dokonywane dla 10 różnych list po czym obliczona została średnia, wyniki znajdują się poniżej:

  • Pętla for(iterujemy po dłuższej, krotka-krotka): 89.661784
  • Pętla for(iterujemy po krótszej, krotka-krotka): 34.044677
  • Pętla for(iterujemy po krótszym, krotka-lista): 32.959450
  • Set'y (krotka-krotka): 0.688639
  • Set'y (krotka-lista): 0.708086

Przydałoby się chyba małe wyjaśnienie mojego zapisu. Pisząc iterujemy po większym miałem na myśli że większy że obiekt zawierający więcej wartości jest iterowany w pętli for natomiast obecność aktualnego elementu w mniejszym sprawdzamy przy pomocy in. Ten zapis z myślnikiem występujący po przecinku oznacza: czym_jest_krótsza_lista-czym_jest_dłuższa_lista.

Jak widać korzystanie z set'ów jest najszybszą formą wyszukiwania w takim przypadku, jeśli mimo wszystko chcemy używać pętli for a jedna z naszych list jest dłuższa od drugiej powinniśmy najpierw iterować po tej dłuższej liście. Zaskoczyło mnie to ze są różnice w szybkości w przypadku set'u tworzonego z listy i set'u tworzonego z krotki, wydawało mi, że takie sety są identyczne. Ok, a co w sytuacji gdy będziemy przeszukiwać nasze listy tylko raz? czy czas potrzebny na tworzenie z niej set'a, nie będzie na tyle duży ze używanie set'ów w takiej sytuacji przestanie być opłacalne? Oto wyniki:

  • Tworzenie set'u z krotki: 23.792158
  • Tworzenie set'u z listy: 23.832875

Jak widać nawet jak do czasu potrzebnego na wyszukanie dodalibyśmy czas tworzenia set'u, nadal jest to najszybsza metoda. Mam nadzieje ze komuś przydadzą się moje testy, jak by ktoś chciał po testować u siebie udostępniam swój skrypt.

Ta notka została wysłanana 02 marca 2009 o 22:41:32.
Możesz przejść na koniec i zostawić komentarz lub powrócić do strony głównej.

MegiTeam - mówimy Twoim językiem

Komentarze do notki Python: najszybsze wyszukiwanie elementu jednej listy(krotki) w drugiej.

  1. radmen powiedział(a):
    02 marca 2009 o 23:11:35

    Dzięki, mnie się przyda jako ciekawostka :)

  2. mrk powiedział(a):
    02 marca 2009 o 23:19:19

    A nie szybciej przypadkiem będzie przypadkiem zbudować słownik:
    dict={}
    for item in haystack: dict[item]=True

    i testować tak:
    for item in neddle:
    if item in dict: return True
    return False

    ?

  3. mrk powiedział(a):
    02 marca 2009 o 23:32:51

    Sprawdziłem, jednak nie, ale chyba tylko dlatego, że w przypadku setów zarówno zbudowanie słownika, jak i późniejsze wyliczanie przecięcia to pojedyncza instrukcja (zaimplementowana niskopoziomowo w C), mój sposób to jednak trochę pythona...

W górę » Strona główna

Dodaj komentarz: