Cara tercepat untuk memeriksa apakah ada nilai dalam daftar

Apa cara tercepat untuk mengetahui apakah ada nilai dalam daftar (daftar dengan jutaan nilai di dalamnya) dan apa indeksnya?

Saya tahu bahwa semua nilai dalam daftar adalah unik seperti dalam contoh ini.

Metode pertama yang saya coba adalah (3,8 detik dalam kode asli saya):

a = [4,2,3,1,5,6]

if a.count(7) == 1:
    b=a.index(7)
    "Do something with variable b"

Metode kedua yang saya coba adalah (2x lebih cepat: 1,9 detik untuk kode asli saya):

a = [4,2,3,1,5,6]

try:
    b=a.index(7)
except ValueError:
    "Do nothing"
else:
    "Do something with variable b"

Metode yang diusulkan dari pengguna Stack Overflow (2,74 detik untuk kode asli saya):

a = [4,2,3,1,5,6]
if 7 in a:
    a.index(7)

Dalam kode asli saya, metode pertama membutuhkan 3,81 detik dan metode kedua membutuhkan 1,88 detik. Ini peningkatan yang bagus, tetapi:

Saya seorang pemula dengan Python / scripting, dan apakah ada cara yang lebih cepat untuk melakukan hal yang sama dan menghemat lebih banyak waktu pemrosesan?

Penjelasan lebih spesifik untuk aplikasi saya:

Di Blender API saya bisa mengakses daftar partikel:

particles = [1, 2, 3, 4, etc.]

Dari sana, saya dapat mengakses lokasi partikel:

particles[x].location = [x,y,z]

Dan untuk setiap partikel saya menguji apakah ada tetangga dengan mencari setiap lokasi partikel seperti:

if [x+1,y,z] in particles.location
    "Find the identity of this neighbour particle in x:the particle's index
    in the array"
    particles.index([x+1,y,z])

7 in a

Cara paling jelas dan tercepat untuk melakukannya.

Anda juga dapat mempertimbangkan untuk menggunakan set, tetapi membuat set dari daftar Anda itu mungkin memakan waktu lebih lama daripada yang akan menghemat pengujian keanggotaan. Satu-satunya cara untuk memastikan adalah melakukan benchmark dengan baik. (ini juga tergantung pada operasi apa yang Anda butuhkan)

Seperti yang dinyatakan oleh orang lain, inbisa sangat lambat untuk daftar besar. Berikut adalah beberapa perbandingan pertunjukan untuk in, setdan bisect. Perhatikan waktu (dalam detik) dalam skala log.

Kode untuk pengujian:

import random
import bisect
import matplotlib.pyplot as plt
import math
import time

def method_in(a,b,c):
    start_time = time.time()
    for i,x in enumerate(a):
        if x in b:
            c[i] = 1
    return(time.time()-start_time)   

def method_set_in(a,b,c):
    start_time = time.time()
    s = set(b)
    for i,x in enumerate(a):
        if x in s:
            c[i] = 1
    return(time.time()-start_time)

def method_bisect(a,b,c):
    start_time = time.time()
    b.sort()
    for i,x in enumerate(a):
        index = bisect.bisect_left(b,x)
        if index < len(a):
            if x == b[index]:
                c[i] = 1
    return(time.time()-start_time)

def profile():
    time_method_in = []
    time_method_set_in = []
    time_method_bisect = []

    Nls = [x for x in range(1000,20000,1000)]
    for N in Nls:
        a = [x for x in range(0,N)]
        random.shuffle(a)
        b = [x for x in range(0,N)]
        random.shuffle(b)
        c = [0 for x in range(0,N)]

        time_method_in.append(math.log(method_in(a,b,c)))
        time_method_set_in.append(math.log(method_set_in(a,b,c)))
        time_method_bisect.append(math.log(method_bisect(a,b,c)))

    plt.plot(Nls,time_method_in,marker='o',color='r',linestyle='-',label='in')
    plt.plot(Nls,time_method_set_in,marker='o',color='b',linestyle='-',label='set')
    plt.plot(Nls,time_method_bisect,marker='o',color='g',linestyle='-',label='bisect')
    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc = 'upper left')
    plt.show()

Anda bisa memasukkan barang Anda ke dalam set. Pengaturan pencarian sangat efisien.

Mencoba:

s = set(a)
if 7 in s:
  # do stuff

sunting Di komentar, Anda mengatakan ingin mendapatkan indeks elemen. Sayangnya, set tidak memiliki gagasan tentang posisi elemen. Alternatifnya adalah dengan melakukan pre-sorting daftar Anda dan kemudian menggunakan pencarian biner setiap kali Anda perlu menemukan elemen.

def check_availability(element, collection: iter):
    return element in collection

Pemakaian

check_availability('a', [1,2,3,4,'a','b','c'])

Saya percaya ini adalah cara tercepat untuk mengetahui apakah nilai yang dipilih ada dalam array.

a = [4,2,3,1,5,6]

index = dict((y,x) for x,y in enumerate(a))
try:
   a_index = index[7]
except KeyError:
   print "Not found"
else:
   print "found"

Ini hanya akan menjadi ide yang baik jika a tidak berubah dan dengan demikian kita dapat melakukan bagian dict () sekali dan kemudian menggunakannya berulang kali. Jika a memang berubah, harap berikan detail lebih lanjut tentang apa yang Anda lakukan.

Pertanyaan aslinya adalah:

Apa cara tercepat untuk mengetahui apakah ada nilai dalam daftar (daftar dengan jutaan nilai di dalamnya) dan apa indeksnya?

Jadi ada dua hal yang harus dicari:

1. adalah item dalam daftar, dan
2. apa indeksnya (jika ada dalam daftar).

Terhadap ini, saya memodifikasi kode @xslittlegrass untuk menghitung indeks dalam semua kasus, dan menambahkan metode tambahan.

Hasil

Metode adalah:

1. in - pada dasarnya jika x in b: return b.index (x)
2. coba - coba / tangkap di b.index (x) (melompati harus memeriksa apakah x dalam b)
3. set - pada dasarnya jika x dalam set (b): return b.index (x)
4. membagi dua - urut b dengan indeksnya, pencarian biner untuk x diurutkan (b). Catat mod dari @xslittlegrass yang mengembalikan indeks dalam b yang diurutkan, daripada yang asli b)
5. terbalik - bentuk kamus pencarian terbalik d untuk b; lalu d [x] memberikan indeks x.

Hasil menunjukkan bahwa metode 5 adalah yang tercepat.

Menariknya, coba dan metode yang ditetapkan setara dalam waktu.

Kode Uji

import random
import bisect
import matplotlib.pyplot as plt
import math
import timeit
import itertools

def wrapper(func, *args, **kwargs):
    " Use to produced 0 argument function for call it"
    # Reference https://www.pythoncentral.io/time-a-python-function/
    def wrapped():
        return func(*args, **kwargs)
    return wrapped

def method_in(a,b,c):
    for i,x in enumerate(a):
        if x in b:
            c[i] = b.index(x)
        else:
            c[i] = -1
    return c

def method_try(a,b,c):
    for i, x in enumerate(a):
        try:
            c[i] = b.index(x)
        except ValueError:
            c[i] = -1

def method_set_in(a,b,c):
    s = set(b)
    for i,x in enumerate(a):
        if x in s:
            c[i] = b.index(x)
        else:
            c[i] = -1
    return c

def method_bisect(a,b,c):
    " Finds indexes using bisection "

    # Create a sorted b with its index
    bsorted = sorted([(x, i) for i, x in enumerate(b)], key = lambda t: t[0])

    for i,x in enumerate(a):
        index = bisect.bisect_left(bsorted,(x, ))
        c[i] = -1
        if index < len(a):
            if x == bsorted[index][0]:
                c[i] = bsorted[index][1]  # index in the b array

    return c

def method_reverse_lookup(a, b, c):
    reverse_lookup = {x:i for i, x in enumerate(b)}
    for i, x in enumerate(a):
        c[i] = reverse_lookup.get(x, -1)
    return c

def profile():
    Nls = [x for x in range(1000,20000,1000)]
    number_iterations = 10
    methods = [method_in, method_try, method_set_in, method_bisect, method_reverse_lookup]
    time_methods = [[] for _ in range(len(methods))]

    for N in Nls:
        a = [x for x in range(0,N)]
        random.shuffle(a)
        b = [x for x in range(0,N)]
        random.shuffle(b)
        c = [0 for x in range(0,N)]

        for i, func in enumerate(methods):
            wrapped = wrapper(func, a, b, c)
            time_methods[i].append(math.log(timeit.timeit(wrapped, number=number_iterations)))

    markers = itertools.cycle(('o', '+', '.', '>', '2'))
    colors = itertools.cycle(('r', 'b', 'g', 'y', 'c'))
    labels = itertools.cycle(('in', 'try', 'set', 'bisect', 'reverse'))

    for i in range(len(time_methods)):
        plt.plot(Nls,time_methods[i],marker = next(markers),color=next(colors),linestyle='-',label=next(labels))

    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc = 'upper left')
    plt.show()

profile()

Sepertinya aplikasi Anda mungkin mendapatkan keuntungan dari penggunaan struktur data Bloom Filter.

Singkatnya, pencarian filter bloom dapat memberi tahu Anda dengan sangat cepat jika nilainya TIDAK PASTI hadir dalam satu set. Jika tidak, Anda dapat melakukan pencarian lebih lambat untuk mendapatkan indeks dari nilai yang MUNGKIN MENJADI dalam daftar. Jadi jika aplikasi Anda cenderung mendapatkan hasil "tidak ditemukan" lebih sering daripada hasil "ditemukan", Anda mungkin melihat percepatan dengan menambahkan Bloom Filter.

Untuk detail, Wikipedia memberikan tinjauan yang baik tentang cara kerja Bloom Filter, dan pencarian web untuk "python bloom filter library" akan menyediakan setidaknya beberapa implementasi yang bermanfaat.

Ketahuilah bahwa inoperator menguji tidak hanya persamaan ( ==) tetapi juga identitas ( is), inlogika untuk lists kira - kira setara dengan yang berikut (sebenarnya ditulis dalam C dan bukan Python, setidaknya dalam CPython):

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

Dalam sebagian besar keadaan, detail ini tidak relevan, tetapi dalam beberapa keadaan mungkin membuat pemula Python terkejut, misalnya, numpy.NANmemiliki properti yang tidak biasa yaitu tidak sama dengan dirinya sendiri :

>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True

Untuk membedakan antara kasus-kasus yang tidak biasa ini, Anda dapat menggunakan any()seperti:

>>> lst = [numpy.NAN, 1 , 2]
>>> any(element == numpy.NAN for element in lst)
False
>>> any(element is numpy.NAN for element in lst)
True 

Perhatikan bahwa inlogika untuk lists any()adalah:

any(element is target or element == target for element in lst)

Namun, saya harus menekankan bahwa ini adalah kasus tepi, dan untuk sebagian besar kasus, inoperator sangat dioptimalkan dan tentu saja apa yang Anda inginkan (baik dengan a listatau dengan a set).

Atau gunakan __contains__:

sequence.__contains__(value)

Demo:

>>> l=[1,2,3]
>>> l.__contains__(3)
True
>>> 

Solusi @Winston Ewert menghasilkan percepatan besar untuk daftar yang sangat besar, tetapi jawaban stackoverflow ini menunjukkan bahwa coba: / kecuali: / lain: konstruk akan melambat jika cabang kecuali sering dicapai. Alternatifnya adalah memanfaatkan .get()metode untuk dikt:

a = [4,2,3,1,5,6]

index = dict((y, x) for x, y in enumerate(a))

b = index.get(7, None)
if b is not None:
    "Do something with variable b"

The .get(key, default)Metode ini hanya untuk kasus ketika Anda tidak dapat menjamin kunci akan di dict. Jika kunci adalah hadir, ia mengembalikan nilai (seperti yang akan dict[key]), tetapi jika tidak, .get()mengembalikan nilai default (di sini None). Anda harus memastikan dalam hal ini bahwa default yang dipilih tidak akan masuk a.

Ini bukan kode, tetapi algoritma untuk pencarian yang sangat cepat.

Jika daftar Anda dan nilai yang Anda cari semuanya angka, ini cukup mudah. Jika string: lihat bagian bawah:

• -Biarkan "n" menjadi panjang daftar Anda
• -Langkah opsional: jika Anda membutuhkan indeks elemen: tambahkan kolom kedua ke daftar dengan indeks elemen saat ini (0 hingga n-1) - lihat nanti
• Pesan daftar Anda atau salinannya (.sort ())
• Loop melalui:
  • Bandingkan nomor Anda dengan elemen ke-2 dari daftar
    • Jika lebih besar, lingkaran lagi di antara indeks n / 2-n
    • Jika lebih kecil, lingkaran lagi di antara indeks 0-n / 2
    • Jika sama: Anda menemukannya
• Tetap persempit daftar sampai Anda menemukannya atau hanya memiliki 2 angka (di bawah dan di atas yang Anda cari)
• Ini akan menemukan elemen apa pun dalam paling banyak 19 langkah untuk daftar 1.000.000 (log (2) n tepatnya)

Jika Anda juga membutuhkan posisi asli nomor Anda, cari di kolom indeks kedua.

Jika daftar Anda tidak terbuat dari angka, metode ini masih berfungsi dan akan menjadi yang tercepat, tetapi Anda mungkin perlu mendefinisikan fungsi yang dapat membandingkan / memesan string.

Tentu saja, ini membutuhkan investasi dari metode disortir (), tetapi jika Anda terus menggunakan kembali daftar yang sama untuk memeriksa, mungkin layak dilakukan.

Karena pertanyaannya tidak selalu harus dipahami sebagai cara teknis tercepat - saya selalu menyarankan cara tercepat yang paling mudah untuk memahami / menulis: pemahaman daftar, one-liner

[i for i in list_from_which_to_search if i in list_to_search_in]

Saya punya list_to_search_indengan semua item, dan ingin mengembalikan indeks item di list_from_which_to_search.

Ini mengembalikan indeks dalam daftar yang bagus.

Ada cara lain untuk memeriksa masalah ini - namun daftar pemahamannya cukup cepat, menambah fakta menulisnya cukup cepat, untuk menyelesaikan masalah.

Bagi saya itu adalah 0,030 detik (nyata), 0,026 detik (pengguna), dan 0,004 detik (sys).

try:
print("Started")
x = ["a", "b", "c", "d", "e", "f"]

i = 0

while i < len(x):
    i += 1
    if x[i] == "e":
        print("Found")
except IndexError:
    pass

Kode untuk memeriksa apakah ada dua elemen dalam array yang produknya sama dengan k:

n = len(arr1)
for i in arr1:
    if k%i==0:
        print(i)