Dlaczego wyszukiwanie w posortowanej liście w python trwa dłużej?

Question

Zrobiłem eksperyment, w którym próbowałem znaleźć czas potrzebny na przeszukanie listy Pythona. Mam listę arr z losowymi liczbami całkowitymi. arr_s ma te same elementy tylko posortowane.

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

Teraz tworzę losową tablicę liczb całkowitych find który posiada elementy, które chcę, aby szukać w arr i arr_s.

>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr: 
...:  continue 

[OUT]:100 loops, best of 3: 2.18 ms per loop 


>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr_s: 
...:  continue 

[OUT]:100 loops, best of 3: 5.15 ms per loop 

Teraz rozumiem, że nie użyłem żadnej konkretnej metody wyszukiwania w posortowanej tablicy (np. Wyszukiwanie binarne). Czyli może to być standardowe wyszukiwanie liniowe, ale dlaczego wyszukiwanie w posortowanej tablicy w nieposortowanej tablicy zajmuje znacznie więcej czasu? Sądzę, że powinno to potrwać niemal w tym samym czasie. Próbowałem wszystkich rodzajów tablicy find. Tablice, które mają liczby całkowite od (0, 1000), (-1000, -100) i (-10000, 10000), pętle zawsze zajmują więcej czasu w posortowanej tablicy.

Answer 1

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

arr to tablica. arr_s to lista. Wyszukiwanie w tablicy może być efektywnie obsługiwane przez numpy, ale przeszukiwanie listy wymaga następujących wskaźników i sprawdzania typów. Nie ma nic wspólnego z sortowaniem.

Uwaga: in does weird things in numpy. Używanie in z numpy ndarrays może być złym pomysłem.

Answer 2

Listy w języku Python nie przypominają tablic C. Nie są one prostym blokiem pamięci, w którym element 1 zawsze pojawia się po elemencie 0 i tak dalej. Zamiast tego pod maską Python zapisuje rzeczy w elastyczny sposób, dzięki czemu można dodawać i usuwać elementy arbitralnych typów i dowolnie przenosić elementy.

W tym przypadku domyślam się, że czynność sortowania listy zmienia organizację leżącą u jej podstaw, co sprawia, że ​​dostęp do elementów jest nieco mniej wydajny.

Answer 3

Nie mam dokładnej odpowiedzi, ale możliwym punktem wyjścia jest sprawdzenie w iteratorach używanych przez każdy obiekt.

    In [9]: it = arr.__iter__() 
    In [10]: its = arr_s.__iter__() 
    In [11]: type(it) 
    Out[11]: iterator 
    In [12]: type(its) 
    Out[12]: listiterator 

Najwyraźniej używają dwóch różnych iteratorów, które mogłyby wyjaśnić różnicę w prędkości.