Jaki jest szybki i pythonic/czysty sposób usuwania posortowanej listy z innej posortowanej listy w pythonie?

Question

Tworzę szybką metodę generowania listy liczb pierwszych w zakresie (0, limit + 1). W funkcji kończę usuwanie wszystkich liczb całkowitych z listy wymienionej z listy o nazwie prime. Szukam szybkiego i pythonic sposób usuwania liczb całkowitych, wiedząc, że obie listy są zawsze sortowane.

Mogę się mylić, ale uważam, że list.remove (n) iteruje na liście porównując każdy element za pomocą n. co oznacza, że ​​poniższy kod działa w czasie O (n^2).

# removable and primes are both sorted lists of integers 
for composite in removable: 
    primes.remove(composite) 

Opierając się moje przypuszczenie (co może być nie tak i proszę o potwierdzenie, czy jest to poprawne) oraz fakt, że obie listy są zawsze sortowane, to myślę, że poniższy kod działa szybciej, ponieważ tylko pętle na liście raz dla czasu O (n). Jednak nie jest to wcale pythonic lub czyste.

i = 0 
j = 0 
while i < len(primes) and j < len(removable): 
    if primes[i] == removable[j]: 
     primes = primes[:i] + primes[i+1:] 
     j += 1 
    else: 
     i += 1 

Czy jest być może wbudowana funkcja lub prostszy sposób robienia tego? A jaki jest najszybszy sposób?

Noty boczne: Nie zmieniłem ustawień funkcji ani kodu powyżej. Nie ma również znaczenia, czy wymieniona lista jest zmieniana/niszczona w procesie.

Dla wszystkich zainteresowanych pełne funkcje jest poniżej:

import math 

# returns a list of primes in range(0, limit+1) 
def fastPrimeList(limit): 
    if limit < 2: 
     return list() 
    sqrtLimit = int(math.ceil(math.sqrt(limit))) 
    primes = [2] + range(3, limit+1, 2) 
    index = 1 
    while primes[index] <= sqrtLimit: 
     removable = list() 
     index2 = index 
     while primes[index] * primes[index2] <= limit: 
      composite = primes[index] * primes[index2] 
      removable.append(composite) 
      index2 += 1 
     for composite in removable: 
      primes.remove(composite) 
     index += 1 
    return primes 

Answer 1

ten jest dość szybki i czysty, to robi O(n) kontrole członkostwa zestaw, w zamortyzowanym czasie biegnie w O(n) (pierwszej linii jest O(n) amortyzowane, drugi linia jest O(n * 1) amortyzowane, ponieważ czek członkostwo jest O(1) zamortyzowany):

removable_set = set(removable) 
primes = [p for p in primes if p not in removable_set] 

Oto modyfikacja Twojej 2nd rozwiązania. Czyni O(n) podstawowe operacje (najgorszy przypadek):

tmp = [] 
i = j = 0 
while i < len(primes) and j < len(removable): 
    if primes[i] < removable[j]: 
     tmp.append(primes[i]) 
     i += 1 
    elif primes[i] == removable[j]: 
     i += 1 
    else: 
     j += 1 
primes[:i] = tmp 
del tmp 

Należy pamiętać, że stałe również znaczenia. Interpreter Pythona działa dość wolno (to znaczy z dużą stałą), aby wykonać kod Pythona. Drugie rozwiązanie ma dużo kodu Pythona i może być wolniejsze w przypadku małych praktycznych wartości n niż rozwiązanie z set s, ponieważ operacje set są zaimplementowane w C, zatem są one szybkie (to jest z małą stałą).

Jeśli masz wiele rozwiązań roboczych, uruchom je na typowych wejściach i zmierz czas. Możesz być zaskoczony ich względną prędkością, często nie jest to to, co byś przewidział.

Answer 2

Najważniejszą rzeczą jest usunięcie kwadratu. Masz to z dwóch powodów.

Najpierw wywołanie remove przeszukuje całą listę pod kątem wartości do usunięcia. Wykonanie tego zajmuje czas liniowy i robisz to raz dla każdego elementu w removable, więc twój całkowity czas to O(NM) (gdzie N to długość primes i M jest długością removable).

Po drugie, usunięcie elementów ze środka listy zmusza do przesunięcia całej reszty listy o jedno miejsce do góry. Więc każdy bierze liniowy czas i znowu robisz to razrazy, więc znowu to jest O(NM).

---

Jak można tego uniknąć?

Po pierwsze, musisz skorzystać z sortowania lub po prostu użyć czegoś, co pozwala ci na ciągłe sprawdzanie czasu zamiast liniowego, jak na przykład set.

Po drugie, należy utworzyć listę indeksów do usunięcia, a następnie wykonać drugie przejście, aby przenieść każdy element do odpowiedniej liczby indeksów naraz lub po prostu zbudować nową listę zamiast próbować mutacji oryginał w miejscu.

Jest tutaj wiele różnych opcji. Który jest najlepszy? Niemal na pewno nie ma to znaczenia; Zmiana czasu na O(NM) po prostu na O(N+M) będzie prawdopodobnie więcej niż wystarczającą optymalizacją, że jesteś zadowolony z wyników. Ale jeśli chcesz wycisnąć więcej wydajności, musisz wdrożyć je wszystkie i przetestować je na realistycznych danych.

Jedyne, co moim zdaniem nie jest oczywiste, to "jak używać sortowania". Chodzi o to, aby użyć tego samego rodzaju naprzemienne-zip iteracji, które chcesz używać w korespondencji seryjnej rodzaju, jak ten:

def sorted_subtract(seq1, seq2): 
    i1, i2 = 0, 0 
    while i1 < len(seq1): 
     if seq1[i1] != seq2[i2]: 
      i2 += 1 
      if i2 == len(seq2): 
       yield from seq1[i1:] 
       return 
     else: 
      yield seq1[i1] 
      i1 += 1