Seberapa besar kamus python bisa

Bayangkan Anda sedang menyelenggarakan konferensi ilmu data. Anda membuat daftar peserta. Nanti Anda ingin mencari nama di daftar hadir ini. Berapa lama waktu yang diperlukan untuk menemukan nama jika Anda menyimpan data sebagai daftar, dan sebagai kamus? . Anda dapat menyimpan data Anda dalam daftar atau kamus. Anda bahkan dapat membuat tabel Excel dan menggunakan kunci INDEX dan MATCH untuk menemukan nama yang Anda inginkan

Bagaimana jika Anda menyimpan miliaran nama?

Di blog ini, saya akan menjawab pertanyaan terkait waktu tentang daftar dan kamus

Izinkan saya memberikan definisi singkat tentang daftar dan kamus

Daftar adalah salah satu tipe data yang paling umum digunakan di Python. Daftar adalah urutan item dalam urutan

list1 = [4, 0.22, “Hello”, [1, 2, 3], -2.5, 0.22]

Daftar dapat berubah, dapat diubah setelah dibuat

Mengakses elemen daftar

Kita dapat mengakses elemen daftar dengan indeksnya

print ( list1[0] )4

Kamus adalah kumpulan pasangan kunci-nilai, atau item yang tidak diurutkan

dict1 = {key1: value1, key2: value2, key3: value3}

Kamus juga bisa berubah, kita dapat menambah, menghapus, dan/atau mengubah item sesuai kebutuhan

Mengakses elemen kamus

Kita dapat mengakses elemen kamus dengan kuncinya

print( dict1[key1] )value1

Saatnya menjalankan pengujian dan membandingkan kecepatan pencarian kamus dan daftar

Di bawah ini adalah konfigurasi perangkat keras dan perangkat lunak perangkat saya. Hasil tes dapat bervariasi tergantung pada konfigurasi komputer Anda

Daftar Uji Coba

Tentukan fungsi untuk menemukan nomor dalam daftar

def find_number_in_list(lst, number):
    if number in lst:
        return True
    else:
        return False

Buat daftar panjang dan daftar pendek untuk membandingkan kecepatan pencarian

short_list = list(range(100))long_list = list(range(10000000))

Panggil fungsi dan ukur waktu dengan timeit

%timeit find_number_in_list(short_list, 99)
1.4 µicrosecond = 0.0000014 second%timeit find_number_in_list(long_list, 9999999)
123 millisecond = 0.123 second

Seperti yang bisa kita lihat dalam uji coba, semakin besar daftarnya, semakin lama waktu yang dibutuhkan

List length comparison:  10000000 / 100 = 100000
Lookup time comparison:  0.123 / 0.0000014 = 87857

Uji coba kamus

Tentukan fungsi untuk menemukan nomor dalam kamus

def find_number_in_dict(dct, number):
    if number in dct.keys():
        return True
    else:
        return False

Buat kamus panjang dan kamus pendek untuk membandingkan kecepatan pencarian

short_dict = {x:x*5 for x in range(1,100)}long_dict = {x:x*5 for x in range(1,10000000)}

Panggil fungsi dan ukur waktu menggunakan timeit

print ( list1[0] )4

Seperti yang dapat kita lihat dalam uji coba, panjang kamus tidak memengaruhi waktu pencarian

print ( list1[0] )4

Dalam contoh sederhana ini, dengan konfigurasi laptop saya,

Untuk 100 item

0. 0000014 detik /0. 00000021 detik = 6. 66

kamus adalah 6. 6 kali lebih cepat dari daftar saat kami mencari 100 item

Untuk 10.000.000 item

0. 123 detik /0. 00000021detik = 585714. 28

Jika menyangkut 10.000.000 item, pencarian kamus bisa 585714 kali lebih cepat daripada pencarian daftar

6. 6 atau 585714 hanyalah hasil dari uji coba sederhana yang dijalankan dengan komputer saya. Ini dapat berubah dalam kasus lain

• Anda harus melalui seluruh daftar untuk mendapatkan apa yang Anda inginkan. Namun, kamus akan mengembalikan nilai yang Anda minta tanpa melalui semua kunci
• Dua kali di atas untuk 100 dan 10000000 hampir sama untuk kamus, karena kamus hampir dapat langsung melompat ke kunci yang diminta berkat pencarian
• Pencarian lebih cepat dalam kamus karena Python mengimplementasikannya menggunakan tabel hash
• Jika kami menjelaskan perbedaannya dengan konsep Big O, kamus memiliki kompleksitas waktu yang konstan, O(1) sedangkan daftar memiliki kompleksitas waktu linier, O(n)

Cara tercepat untuk berulang kali mencari data dengan jutaan entri di Python menggunakan kamus. Karena kamus adalah tipe pemetaan bawaan di Python sehingga sangat dioptimalkan. Namun, kami memiliki pertukaran ruang-waktu yang khas dalam kamus dan daftar. Ini berarti kami dapat mengurangi waktu yang diperlukan untuk algoritme kami, tetapi kami perlu menggunakan lebih banyak ruang di memori

Meskipun kamus lebih dioptimalkan di Python 3. 6, mereka masih menggunakan lebih banyak memori daripada daftar, karena Anda juga perlu menggunakan ruang untuk kunci dan pencarian, sedangkan daftar menggunakan ruang hanya untuk nilai

1. Perbandingan kompleksitas waktu dari operasi lain seperti menambahkan, menghapus, membalikkan daftar dan kamus dari Geeks untuk Geeks
2. Penjelasan yang sangat bagus tentang kompleksitas waktu dan notasi O besar oleh CS Dojo

3. Penjelasan rapi 6 menit untuk tabel hash dan pencarian oleh Gayle Laakmann, penulis buku Cracking The Coding Interview

Terima kasih sudah membaca

Jika Anda ingin menghubungi saya, Anda dapat mengirim email kepada saya di seymatas@gmail. com, atau Anda dapat menemukan saya di https. // www. linkedin. com/in/seyma-tas/

Berapa lama kamus dengan Python?

Seberapa besar kamus Python?

Berapa banyak data yang dapat disimpan oleh kamus Python?

Berapa banyak entri yang bisa dimiliki kamus Python?