Biaya fungsi len ()

Jawaban:

341

Ini O (1) (waktu konstan, tidak tergantung dari panjang sebenarnya elemen - sangat cepat) pada setiap jenis yang Anda sebutkan, plus setdan lainnya seperti array.array.

Alex Martelli
sumber
17
Terima kasih atas jawaban bermanfaatnya! Apakah ada jenis asli yang bukan ini masalahnya?
mvanveen
141

Memanggil len () pada tipe data tersebut adalah O (1) dalam CPython , implementasi paling umum dari bahasa Python. Berikut ini tautan ke tabel yang menyediakan kompleksitas algoritmik berbagai fungsi di CPython:

Halaman TimeComplexity Python Wiki

James Thompson
sumber
84

Semua benda itu melacak panjangnya sendiri. Waktu untuk mengekstrak panjangnya kecil (O (1) dalam notasi O besar) dan sebagian besar terdiri dari [deskripsi kasar, ditulis dalam istilah Python, bukan istilah C]: cari "len" dalam kamus dan kirim ke fungsi built_in len yang akan mencari __len__metode objek dan memanggil itu ... yang harus dilakukan adalahreturn self.length

John Machin
sumber
3
Saya pikir ini adalah jawaban yang paling tepat karena ini memberikan wawasan tentang detail implementasi.
AK
mengapa tidak lengthmuncul di kamus oleh dir(list)?
ViFI
inilah yang saya cari
Visakh Vijayan
@ViFI Karena ini hanya sebuah contoh. list.lenghtVariabel yang diilustrasikan diimplementasikan dalam C, bukan Python.
Kowalski
73

Pengukuran di bawah ini memberikan bukti yaitu len()O (1) untuk struktur data yang sering digunakan.

Catatan tentang timeit: Ketika -sbendera digunakan dan dua string dilewatkan ke timeitstring pertama dieksekusi hanya sekali dan tidak waktunya.

Daftar:

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

Tuple:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

Tali:

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

Kamus (kamus-pemahaman tersedia dalam 2.7+):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

Himpunan:

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

Set (set-pemahaman tersedia dalam 2.7+):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

Deque:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop
mechanical_meat
sumber
1
Ini bukan tolok ukur yang baik meskipun menunjukkan apa yang sudah kita ketahui. Ini karena rentang (10) dan rentang (1000000) tidak seharusnya menjadi O (1).
Tidak diketahui
3
Sejauh ini, inilah jawaban terbaik. Anda hanya perlu menambahkan kesimpulan kalau-kalau seseorang tidak menyadari waktu yang konstan.
santiagobasulto
4
Terima kasih atas komentarnya. Saya menambahkan catatan tentang kompleksitas O (1) len(), dan juga memperbaiki pengukuran untuk menggunakan -sflag dengan benar.
mechanical_meat
Penting untuk dicatat bahwa menyimpan panjang ke dalam variabel dapat menghemat waktu komputasi yang signifikan: python -m timeit -s "l = range(10000);" "len(l); len(l); len(l)"223 nsec per loop python -m timeit -s "l = range(100);" "len(l)"66.2 nsec per loop
Radostin Stoyanov
16

len adalah O (1) karena dalam RAM Anda, daftar disimpan sebagai tabel (serangkaian alamat yang berdekatan). Untuk mengetahui kapan tabel berhenti, komputer membutuhkan dua hal: panjang dan titik awal. Itu sebabnya len () adalah O (1), komputer menyimpan nilai, jadi hanya perlu mencarinya.

RAHUL KUMAR
sumber
3

Saya telah memikirkan len () dalam Python tergantung pada ukuran daftar, jadi saya selalu menyimpan panjangnya dalam sebuah variabel jika saya menggunakan beberapa kali. Tapi hari ini ketika debugging, saya perhatikan atribut __len__ dalam objek daftar, jadi len () harus mengambilnya saja, yang membuat kompleksitas O (1). Jadi saya hanya googled jika seseorang sudah menanyakannya dan menemukan posting ini.

AYUSH SENAPATI
sumber
Tetapi __len__funtion, bukan variabel yang mewakili panjang daftar.
Kowalski
@Kowalski ya len adalah fungsi tetapi semua yang dilakukannya adalah, ia mengembalikan self.length
AYUSH SENAPATI
Tetapi posting Anda tidak mengatakan apa-apa tentang itu. Bagaimana Anda tahu bahwa list.__len__fungsi berjalan dalam waktu yang konstan? Memang, tetapi bukan hanya karena itu adalah fungsi. Karena diimplementasikan seperti itu.
Kowalski