Jak szybko znaleźć pierwszą wielokrotność 2 elementu listy na liście dużych liczb całkowitych?

Question

Mam listę około 100 000 posortowanych parzystych liczb całkowitych w zakresie 10^12 do 10^14. Moim celem jest znalezienie pierwszej liczby całkowitej x na liście tak, aby x*2 był również członkiem tej listy. Ponieważ moja lista jest dość długa, szybkość jest bardzo ważna.

Moją pierwszą myślą było po prostu przejrzenie listy i sprawdzenie, czy każdy element pomnożony przez 2 był również na liście, ale po wdrożeniu tego jest jasne, że jest to zbyt wolne dla moich celów.

Moja następna myśl polegała na rozkładaniu każdego elementu na liście na jego rozkład główny z Sympy's factorint, a następnie przeszukiwanie mojej rozłożonej listy dla tego samego rozkładu z wyjątkiem dodatkowym 2. To nie okazało się być szybsze oczywiście , ale wydaje mi się, że musi istnieć sposób użycia rozkładu pierwotnego, jeśli nie czegoś innego.

Answer 1

Możesz iterować na liście z dwoma iteratorami: jeden wskazuje na bieżący element, a drugi na pierwszy większy lub równy podwójnemu. To będzie O (N).

Oto szkic pomysłu:

l = [1, 3, 5, 7, 10, 12, 15] 

# ... 
j = 0 
for i in range(0, len(l)): 
    while l[j] < 2*l[i]: 
     j += 1 
     if j == len(l): 
      return -1 
    if l[j] == 2*l[i]: 
     return i 

Edit: Poniższe komentarze w innej odpowiedzi, kilka spektakli testy pokazują, że ta wersja będzie znacznie szybciej (3 razy w moich testów) poprzez eliminację mnożenia, wzywa do len i zmniejszenia liczby wyszukiwań pozycja na liście:

j = 0 
s = len(l) 
for i in range(0, s): 
    l_i = l[i] 
    l_i2 = l_i<<1 
    while l[j] < l_i2: 
     j += 1 
     if j == s: 
      return -1 
    if l[j] == l_i2: 
     return i 

Answer 2

można podzielić listę na dwie części tak, że dolna lista zawiera wszystkie numery z pierwszego na oryginale wyświetlić ostatnią liczbę, która jest równa lub mniejsza niż połowa maksymalnej wartości na liście. Przyspieszy to nieco twoje wyszukiwanie, ponieważ przejrzysz tylko połowę listy i przeszukasz, czy x * 2 znajduje się w drugiej połowie. Patrz przykład ryczeć

l = [1, 3, 5, 7, 10, 12, 15] 

max_l = l[-1] 

for i in range(len(l)): 
    if l[i] > max_l/2: 
    break 
    pos_mid_l = i 

print pos_mid_l # returns position 3 

lower_l = l[:pos_mid_l+1] 
upper_l = l[pos_mid_l+1:] 

print lower_l # returns lower half of your list 
print upper_l # returns upper half of your list 

for i in lower_l: 
    if i < upper_l[0]/2: 
    if i*2 in lower_l: 
     ans = i 
     break 
    else: 
    if i*2 in upper_l: 
     ans = i 
     break 

print ans # Your answer :) 

Answer 3

rozwiązanie Colin Pitrat jest bardzo dobra, ale chyba można go do góry podczas korzystania sortedcontainers.SortedSet

Mam wygenerowany plik z 1.000.000 liczb losowych (używając numpy.random.randint) i sprawdził, czy jest co najmniej jeden numer (w środku pliku), który spełnia twój warunek.

Porównajmy oba podejścia:

import filecmp 
from sortedcontainers import SortedSet 
from timeit import Timer 

def load2list(): 
    with open('data', 'r') as f: 
     return [int(line) for line in f] 

def save_result(i, fn): 
    with open(fn, 'a') as f: 
     print(i, file=f) 

def test_Colin_Pitrat(): 
    j = 0 
    for i in range(0, len(l)): 
     while l[j] < 2*l[i]: 
      j += 1 
      if j == len(l): 
       return -1 
     if l[j] == 2*l[i]: 
      save_result(l[i], 'Colin_Pitrat.out') 
      return l[i] 


def test_SortedSet(): 
    for i in sorted_set: 
     if i<<1 in sorted_set: 
      save_result(i, 'SortedSet.out') 
      return i 
    return -1 


if __name__=='__main__': 
    timeit_number = 10000 
    l = load2list() 
    sorted_set = SortedSet(l) 
    print('len(l):\t\t%d' % (len(l))) 
    print('len(sorted_set):\t%d' % (len(sorted_set))) 
    print('Timeit results with %d executions:' %timeit_number) 
    print('Colin_Pitrat:\t', Timer(test_Colin_Pitrat).timeit(timeit_number)) 
    print('SortedSet:\t', Timer(test_SortedSet).timeit(timeit_number)) 
    print("filecmp.cmp('Colin_Pitrat.out', 'SortedSet.out'):\t%s" % (filecmp.cmp('Colin_Pitrat.out', 'SortedSet.out'))) 

wyjściowa:

len(l):   1000001 
len(sorted_set):  999504 
Timeit results with 10000 executions: 
Colin_Pitrat: 35.94529931032006 
SortedSet:  2.548847197918647 
filecmp.cmp('Colin_Pitrat.out', 'SortedSet.out'):  True 

PS jak widać SortedSet jest bardzo szybki.

UPDATE: (teraz jestem testowania w domu, gdzie mój PC jest znacznie wolniej, więc zmniejszy liczbę egzekucji do 1.000)

Zgodnie z propozycją Colin Pitrat jestem generowania teraz dane (około 100 000 numerów) dla najgorszego scenariusza - gdy nie można znaleźć żadnego dopasowania. Teraz porównuję trzy funkcje: test_Colin_Pitrat, test_Colin_Pitrat2 (dostrojona wersja), test_SortedSet ...Skrypt generator

danych:

import numpy as np 

l = np.random.randint(10**7, 10**9, 200000) 
l = l[ l % 2 > 0 ] 
np.savetxt('data', np.sort(l), fmt='%d') 

Kod:

import filecmp 
from sortedcontainers import SortedSet 
from timeit import Timer 

def load2list(): 
    with open('data', 'r') as f: 
     return [int(line) for line in f] 

def save_result(i, fn): 
    with open(fn, 'a') as f: 
     print(i, file=f) 

def test_Colin_Pitrat(): 
    j = 0 
    for i in range(0, len(l)): 
     while l[j] < 2*l[i]: 
      j += 1 
      if j == len(l): 
       return -1 
     if l[j] == 2*l[i]: 
      return l[i] 

def test_Colin_Pitrat2(): 
    j = 0 
    s = len(l) 
    for i in range(0, s): 
     l_i = l[i] 
     l_i2 = l_i<<1 
     while l[j] < l_i2: 
      j += 1 
      if j == s: 
       return -1 
     if l[j] == l_i2: 
      return l[j] 


def test_SortedSet(): 
    for i in sorted_set: 
     if i<<1 in sorted_set: 
      return i 
    return -1 


if __name__=='__main__': 
    timeit_number = 1000 
    l = load2list() 
    sorted_set = SortedSet(l) 
    print('len(l):\t\t%d' % (len(l))) 
    print('len(sorted_set):\t%d' % (len(sorted_set))) 
    print('Timeit results for %d executions:' %timeit_number) 
    print('Colin_Pitrat:\t', Timer(test_Colin_Pitrat).timeit(timeit_number)) 
    print('Colin_Pitrat2:\t', Timer(test_Colin_Pitrat2).timeit(timeit_number)) 
    print('SortedSet:\t', Timer(test_SortedSet).timeit(timeit_number)) 

wyjściowa:

len(l):   99909 
len(sorted_set):  99899 
Timeit results for 1000 executions: 
Colin_Pitrat: 153.04753258882357 
Colin_Pitrat2: 103.68264272815443 
SortedSet:  99.59669211136577 

Wniosek: Colin_Pitrat2 wynosi 33% szybciej w porównaniu do Colin_Pitrat i prawie tak szybko jak SortedSet.

Answer 4

dodam kolejną odpowiedź, bo już przeciążony mój poprzedni ...

Teraz wpadłem na nowy pomysł - przecięcie SortedSets, który działa bardzo szybko w porównaniu do zmodyfikowana Colin i moje poprzednie rozwiązanie. Chodzi o to, aby wygenerować dwie SortedSets:

l2 - jest przecięcie obu listach/ustawia: pierwotna l i jednego zawierającego wszystkie elementy z l pomnożone przez 2: SortedSet(x*2 for x in l).

l1 - to SortedSet zawierający wszystkie elementy należące do l2, podzielona przez 2: SortedSet(x//2 for x in l2)

Kod:

from datetime import datetime as dt 
from sortedcontainers import SortedSet 
from timeit import Timer 

def load2list(): 
    with open('data', 'r') as f: 
     return [int(line) for line in f] 

def test_Colin_Pitrat2(): 
    j = 0 
    s = len(l) 
    for i in range(0, s): 
     l_i = l[i] 
     l_i2 = l_i<<1 
     while l[j] < l_i2: 
      j += 1 
      if j == s: 
       return -1 
     if l[j] == l_i2: 
      return l[i] 

def test_SortedSet(): 
    for i in sorted_set: 
     if i<<1 in sorted_set: 
      return i 
    return -1 

def test_SetIntersection(): 
    for i in l1: 
     if i*2 in l2: 
      return i 
    return -1 

if __name__=='__main__': 
    start_ts = dt.now() 
    timeit_number = 10000 
    l = load2list() 
    print('load2list() took:\t%d microseconds' %((dt.now() - start_ts).microseconds)) 

    start_ts = dt.now() 
    sorted_set = SortedSet(l) 
    l2 = SortedSet(l).intersection(SortedSet(x*2 for x in l)) 
    l1 = SortedSet(x//2 for x in l2) 
    print('preparing sets took:\t%d microseconds' %((dt.now() - start_ts).microseconds)) 

    print('len(l):\t\t%d' % (len(l))) 
    print('len(l1):\t%d' % (len(l1))) 
    print('len(l2):\t%d' % (len(l2))) 
    print('len(sorted_set):\t%d' % (len(sorted_set))) 

    print('Timeit results for %d executions:' %timeit_number) 
    print('Colin_Pitrat2:\t\t', Timer(test_Colin_Pitrat2).timeit(timeit_number)) 
    print('SortedSet:\t\t', Timer(test_SortedSet).timeit(timeit_number)) 
    print('SetIntersection:\t', Timer(test_SetIntersection).timeit(timeit_number)) 

wyjściowa:

load2list() took:  230023 microseconds 
preparing sets took: 58106 microseconds 
len(l):   498786 
len(l1):  256 
len(l2):  256 
len(sorted_set):  498562 
Timeit results for 10000 executions: 
Colin_Pitrat2:   23.557948959065648 
SortedSet:    6.658937808213555 
SetIntersection:   0.012540539222982261 

PS Bardzo podoba mi się to pytanie, ponieważ dało mi to szansę nauczenia się czegoś nowego. Podoba mi się również algorytm Colina - jest inteligentny. Już go przegłosowałem.

Answer 5

Wydaje mi się, że najlepszy algorytm użyłby wcześniejszej listy i zestawu.

#!/usr/local/pypy3-2.4.0/bin/pypy3 

import time 
import random 


def get_random_numbers(): 
    result = [] 
    for counter in range(99998): 
     random_number = (random.randrange(10**12, 10**14) // 2) * 2 
     result.append(random_number) 
    # Make sure there's at least one solution to the problem 
    moderately_large = 10**14 // 2 
    result.append(moderately_large) 
    result.append(moderately_large * 2) 
    # This sort is of course O(n*logn), but I don't think you're 
    # counting that, are you? 
    result.sort() 
    return result 


def get_best(list_): 
    # This is O(n) 
    set_ = set(list_) 
    for value in list_: 
     if value * 2 in set_: 
      return value 
    return None 


def main(): 
    list_ = get_random_numbers() 
    time0 = time.time() 
    result = get_best(list_) 
    time1 = time.time() 
    print(result) 
    print('{} seconds'.format(time1 - time0)) 


main() 

HTH