najszybszy sposób na znalezienie 2 numery z obu list, że suma równa x

Question

mojego kodu:

n = 3 
a1 = 0 
b1 = 10 
a2 = 2 
b2 = 2 

if b1>n: 
    b1=n 
if b2>n: 
    b2=n 

diap1 = [x for x in range(a1, b1+1)] 
diap2 = [x for x in range(a2, b2+1)] 

def pairs(d1, d2, n): 
    res = 0 
    same = 0 
    sl1 = sorted(d1) 
    sl2 = sorted(d2) 
    for i in sl1: 
     for j in sl2: 
      if i+j==n and i!=j: 
       res+=1 
      elif i+j==n and i==j: 
       same+=1 
    return(res+same) 

result = pairs(diap1, diap2, n) 
print(result) 

UWAGA: n, A1, B1, A2, B2 może zmienić. Kod powinien znaleźć 2 cyfry z 2 list (po 1 z każdej), które są równe n. Na przykład: pary (a, b) i (b, a) są różne, ale (a, a) i (a, a) to ta sama para. Tak więc, wynik mojego kodu jest poprawny, a dla kodu powyżej jest 1 (1, 2), ale dla dużych wejść zajmuje to zbyt dużo czasu. Jak mogę ją zoptymalizować, aby działała szybciej?

Answer 1

Zastosowanie set() do szybkiego odnośnika ...

setd2 = set(d2) 

Nie próbuj wszystkich możliwych par liczb. Po ustaleniu numeru z pierwszej listy powiedz "i", po prostu sprawdź, czy (n-i) znajduje się w drugim zestawie.

for i in sl1: 
    if (n-i) in setd2: 
     # found match 
    else: 
     # no match in setd2 for i 

Answer 2

Następujący sposób możesz pracować najszybciej i znaleźć dwie liczby, których suma równa jest n, i zapisać je również na liście krotek.

s1 = set(list1) 
s2 = set(list2) 
nums = [] 
for item in s1: 
    if n-item in s2: 
     nums.append((item, n-item)) 

Answer 3

Przyjęta odpowiedź jest łatwa do zrozumienia i wdrożenia, ale musiałem po prostu udostępnić tę metodę. Możesz zobaczyć swoje pytanie jest takie samo jak to one.
Szczególnie interesująca jest ta answer, ponieważ nie trzeba więcej miejsca, wstawiając do zestawów. Załączam tutaj algorytm w mojej odpowiedzi.

Jeśli tablice są posortowane, możesz to zrobić w liniowym czasie i stałej pamięci.

• start z dwoma wskaźnikami, jeden wskazując na najmniejszy element, drugi skierowanymi do największego elementu B.
• Oblicz sumę wskazał elementów.
• Jeśli jest mniejszy niż k przyrost, wskaźnik do A, tak aby wskazywał na następny największy element.
• Jeśli jest większy niż k, zmniejsz wskaźnik do B, tak aby wskazywał na następny najmniejszy element.
• Jeśli to dokładnie k, znalazłeś parę. Przesuń jeden ze wskaźników i idź dalej, aby znaleźć następną parę.

Jeśli tablice są początkowo nieposortowane, można je najpierw posortować, a następnie zastosować powyższy algorytm.

Answer 4

Jeśli naciśniesz wartość n z pierwszej listy, a następnie wyszukasz wartość m na drugiej liście, aby suma odpowiadała szukanej wartości, możesz wykonać kilka skrótów. Na przykład, jeśli suma jest mniejsza, wszystkie wartości z drugiej listy, które są mniejsze lub równe m, również nie dadzą właściwej sumy. Podobnie, jeśli suma jest większa.

Używając tej informacji, chciałbym użyć następujących czynności:

• Skonfiguruj dwa stosy, jeden minimalny kupa, jeden maksymalny sterty.
• Spójrz na najlepszych elementów każdego sterty:
  • Jeżeli suma odpowiada szukane wartości, gotowe.
  • Jeśli suma przekracza szukaną wartość, usuń wartość z maksymalnej sterty.
  • Jeśli suma jest mniejsza od szukanej wartości, usuń wartość z minimalnej sterty.
• Jeśli jedna sterta jest pusta, nie ma rozwiązania.

Należy pamiętać, że używanie sterty to optymalizacja po prawej stronie sortowania dwóch sekwencji. Jeśli jednak często zdarza się, że nie ma zgodności, sortowanie liczb przed algorytmem może być szybsze. Powodem tego jest to, że dobry algorytm sortowania przewyższa niejawne sortowanie przez hałdy, a nie przez asymptotyczną złożoność, ale raczej przez pewne stałe czynniki.

Answer 5

Dziękujemy za wyraźne zdefiniowanie pytania i podanie kodu przykład, który próbujesz zoptymalizować.

Wykorzystując dwa podstawowe definicje z pytaniem i notacji ty przewidzianym, ja ogranicza moje optymalizacji próbę użycia list i dodał zdolność losowo zmienić wartości kojarzonych do n, A1, B1, A2 i b2.

W celu pokazania wyników optymalizacji, stworzyłem moduł, który zawiera korzystanie z funkcji random.randit do tworzenia różnych rozmiarach i lista funkcji timeit.Timer uchwycić czas oryginalne pary Funkcja() działa podobnie jak sugerowana optymalizacja w funkcji pairs2().

W funkcji pairs2(), zauważysz, że każda pętla iteracji zawiera instrukcję przerwania . Eliminują one niepotrzebną iterację po każdej liście po spełnieniu wymaganych kryteriów. Powinieneś zauważyć, że w miarę wzrostu wielkości list , poprawia się czas pairs() vs. pairs().

testowy kod modułu:

import random 
from timeit import Timer 

max_value = 10000 
n = random.randint(1, max_value) 
a1 = random.randint(0, max_value) 
b1 = random.randint(1, max_value+1) 
a2 = random.randint(0, max_value) 
b2 = random.randint(1, max_value+1) 

if b1>n: 
    b1=n 
if b2>n: 
    b2=n 

if a1>=b1: 
    a1 = random.randint(0, b1-1) 
if a2>=b2: 
    a2 = random.randint(0, b2-1) 

diap1 = [x for x in range(a1, b1)] 
diap2 = [x for x in range(a2, b2)] 
print("Length diap1 =", len(diap1)) 
print("Length diap2 =", len(diap2)) 

def pairs(d1, d2, n): 
    res = 0 
    same = 0  
    sl1 = sorted(d1) 
    sl2 = sorted(d2) 
    for i in sl1: 
     for j in sl2: 
      if i+j==n and i!=j:     
       res+=1           
      elif i+j==n and i==j: 
       same+=1 
    return(res+same) 

def pairs2(d1, d2, n): 
    res = 0 
    same = 0  
    sl1 = sorted(d1) 
    sl2 = sorted(d2) 
    for i in sl1: 
     for j in sl2: 
      if i+j==n and i!=j:     
       res+=1 
       break          
      elif i+j==n and i==j: 
       same+=1 
       break 
     if res+same>0: 
      break 
    return(res+same) 

if __name__ == "__main__": 
    result=0 
    timer = Timer("result = pairs(diap1, diap2, n)", 
        "from __main__ import diap1, diap2, n, pairs") 
    print("pairs_time = ", timer.timeit(number=1), "result =", result) 

    result=0 
    timer = Timer("result = pairs2(diap1, diap2, n)", 
       "from __main__ import diap1, diap2, n, pairs2") 
    print("pairs2_time = ", timer.timeit(number=1), "result =", result)