Python - Buat daftar dengan kapasitas awal

Kode seperti ini sering terjadi:

l = []
while foo:
    #baz
    l.append(bar)
    #qux

Ini sangat lambat jika Anda akan menambahkan ribuan elemen ke daftar Anda, karena daftar harus terus diubah ukurannya agar sesuai dengan elemen baru.

Di Jawa, Anda bisa membuat ArrayList dengan kapasitas awal. Jika Anda tahu seberapa besar daftar Anda, ini akan jauh lebih efisien.

Saya mengerti bahwa kode seperti ini sering dapat difaktorkan ulang ke dalam daftar pemahaman. Namun, jika for / while loop sangat rumit, ini tidak mungkin. Apakah ada yang setara dengan kami programmer Python?

def doAppend( size=10000 ):
    result = []
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result.append(message)
    return result

def doAllocate( size=10000 ):
    result=size*[None]
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result[i]= message
    return result

Hasil . (mengevaluasi setiap fungsi 144 kali dan rata-rata durasinya)

simple append 0.0102
pre-allocate  0.0098

Kesimpulan . Itu hampir tidak penting.

Optimalisasi prematur adalah akar dari semua kejahatan.

Daftar python tidak memiliki pra-alokasi bawaan. Jika Anda benar-benar perlu membuat daftar, dan perlu menghindari biaya tambahan untuk menambahkan (dan Anda harus memverifikasi bahwa Anda melakukannya), Anda dapat melakukan ini:

l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
    # baz
    l[i] = bar
    # qux

Mungkin Anda bisa menghindari daftar dengan menggunakan generator sebagai gantinya:

def my_things():
    while foo:
        #baz
        yield bar
        #qux

for thing in my_things():
    # do something with thing

Dengan cara ini, daftar tidak semua disimpan dalam memori sama sekali, hanya dihasilkan sesuai kebutuhan.

Versi singkat: gunakan

pre_allocated_list = [None] * size

untuk pra-mengalokasikan daftar (yaitu, untuk dapat mengatasi 'ukuran' elemen daftar daripada secara bertahap membentuk daftar dengan menambahkan). Operasi ini SANGAT cepat, bahkan pada daftar besar. Mengalokasikan objek baru yang nantinya akan ditugaskan ke elemen daftar akan memakan waktu JAUH lebih lama dan akan menjadi hambatan dalam program Anda, kinerja-bijaksana.

Versi panjang:

Saya pikir waktu inisialisasi harus diperhitungkan. Karena dalam python semuanya adalah referensi, tidak masalah apakah Anda mengatur setiap elemen menjadi Tidak Ada atau string - baik itu hanya referensi. Meskipun akan lebih lama jika Anda ingin membuat objek baru untuk setiap elemen untuk referensi.

Untuk Python 3.2:

import time
import copy

def print_timing (func):
  def wrapper (*arg):
    t1 = time.time ()
    res = func (*arg)
    t2 = time.time ()
    print ("{} took {} ms".format (func.__name__, (t2 - t1) * 1000.0))
    return res

  return wrapper

@print_timing
def prealloc_array (size, init = None, cp = True, cpmethod=copy.deepcopy, cpargs=(), use_num = False):
  result = [None] * size
  if init is not None:
    if cp:
      for i in range (size):
          result[i] = init
    else:
      if use_num:
        for i in range (size):
            result[i] = cpmethod (i)
      else:
        for i in range (size):
            result[i] = cpmethod (cpargs)
  return result

@print_timing
def prealloc_array_by_appending (size):
  result = []
  for i in range (size):
    result.append (None)
  return result

@print_timing
def prealloc_array_by_extending (size):
  result = []
  none_list = [None]
  for i in range (size):
    result.extend (none_list)
  return result

def main ():
  n = 1000000
  x = prealloc_array_by_appending(n)
  y = prealloc_array_by_extending(n)
  a = prealloc_array(n, None)
  b = prealloc_array(n, "content", True)
  c = prealloc_array(n, "content", False, "some object {}".format, ("blah"), False)
  d = prealloc_array(n, "content", False, "some object {}".format, None, True)
  e = prealloc_array(n, "content", False, copy.deepcopy, "a", False)
  f = prealloc_array(n, "content", False, copy.deepcopy, (), False)
  g = prealloc_array(n, "content", False, copy.deepcopy, [], False)

  print ("x[5] = {}".format (x[5]))
  print ("y[5] = {}".format (y[5]))
  print ("a[5] = {}".format (a[5]))
  print ("b[5] = {}".format (b[5]))
  print ("c[5] = {}".format (c[5]))
  print ("d[5] = {}".format (d[5]))
  print ("e[5] = {}".format (e[5]))
  print ("f[5] = {}".format (f[5]))
  print ("g[5] = {}".format (g[5]))

if __name__ == '__main__':
  main()

Evaluasi:

prealloc_array_by_appending took 118.00003051757812 ms
prealloc_array_by_extending took 102.99992561340332 ms
prealloc_array took 3.000020980834961 ms
prealloc_array took 49.00002479553223 ms
prealloc_array took 316.9999122619629 ms
prealloc_array took 473.00004959106445 ms
prealloc_array took 1677.9999732971191 ms
prealloc_array took 2729.999780654907 ms
prealloc_array took 3001.999855041504 ms
x[5] = None
y[5] = None
a[5] = None
b[5] = content
c[5] = some object blah
d[5] = some object 5
e[5] = a
f[5] = []
g[5] = ()

Seperti yang Anda lihat, hanya membuat daftar besar referensi ke objek None yang sama membutuhkan waktu sangat sedikit.

Membebani atau memperpanjang membutuhkan waktu lebih lama (saya tidak melakukan rata-rata apa pun, tetapi setelah menjalankan ini beberapa kali saya dapat memberi tahu Anda bahwa perluasan dan penambahan memakan waktu yang hampir bersamaan).

Mengalokasikan objek baru untuk setiap elemen - itulah yang paling memakan waktu. Dan jawaban S.Lott melakukan itu - memformat string baru setiap kali. Yang tidak sepenuhnya diperlukan - jika Anda ingin pra-mengalokasikan beberapa ruang, cukup buat daftar Tidak Ada, lalu tetapkan data ke daftar elemen sesuka hati. Apa pun cara yang dibutuhkan lebih banyak waktu untuk menghasilkan data daripada menambahkan / memperpanjang daftar, apakah Anda menghasilkannya saat membuat daftar, atau setelah itu. Tetapi jika Anda menginginkan daftar yang jarang penduduknya, maka memulai dengan daftar Tidak Ada jelas lebih cepat.

Cara Pythonic untuk ini adalah:

x = [None] * numElements

atau nilai default apa pun yang ingin Anda siapkan, mis

bottles = [Beer()] * 99
sea = [Fish()] * many
vegetarianPizzas = [None] * peopleOrderingPizzaNotQuiche

[EDIT: Caveat Emptor The [Beer()] * 99sintaks menciptakan satu Beer dan kemudian Mempopulai sebuah array dengan referensi 99 untuk satu contoh yang sama]

Pendekatan default Python bisa sangat efisien, meskipun efisiensi itu meluruh ketika Anda meningkatkan jumlah elemen.

Membandingkan

import time

class Timer(object):
    def __enter__(self):
        self.start = time.time()
        return self

    def __exit__(self, *args):
        end = time.time()
        secs = end - self.start
        msecs = secs * 1000  # millisecs
        print('%fms' % msecs)

Elements   = 100000
Iterations = 144

print('Elements: %d, Iterations: %d' % (Elements, Iterations))


def doAppend():
    result = []
    i = 0
    while i < Elements:
        result.append(i)
        i += 1

def doAllocate():
    result = [None] * Elements
    i = 0
    while i < Elements:
        result[i] = i
        i += 1

def doGenerator():
    return list(i for i in range(Elements))


def test(name, fn):
    print("%s: " % name, end="")
    with Timer() as t:
        x = 0
        while x < Iterations:
            fn()
            x += 1


test('doAppend', doAppend)
test('doAllocate', doAllocate)
test('doGenerator', doGenerator)

dengan

#include <vector>
typedef std::vector<unsigned int> Vec;

static const unsigned int Elements = 100000;
static const unsigned int Iterations = 144;

void doAppend()
{
    Vec v;
    for (unsigned int i = 0; i < Elements; ++i) {
        v.push_back(i);
    }
}

void doReserve()
{
    Vec v;
    v.reserve(Elements);
    for (unsigned int i = 0; i < Elements; ++i) {
        v.push_back(i);
    }
}

void doAllocate()
{
    Vec v;
    v.resize(Elements);
    for (unsigned int i = 0; i < Elements; ++i) {
        v[i] = i;
    }
}

#include <iostream>
#include <chrono>
using namespace std;

void test(const char* name, void(*fn)(void))
{
    cout << name << ": ";

    auto start = chrono::high_resolution_clock::now();
    for (unsigned int i = 0; i < Iterations; ++i) {
        fn();
    }
    auto end = chrono::high_resolution_clock::now();

    auto elapsed = end - start;
    cout << chrono::duration<double, milli>(elapsed).count() << "ms\n";
}

int main()
{
    cout << "Elements: " << Elements << ", Iterations: " << Iterations << '\n';

    test("doAppend", doAppend);
    test("doReserve", doReserve);
    test("doAllocate", doAllocate);
}

Pada Windows 7 i7 saya, Python 64-bit memberi

Elements: 100000, Iterations: 144
doAppend: 3587.204933ms
doAllocate: 2701.154947ms
doGenerator: 1721.098185ms

Sementara C ++ memberi (dibangun dengan MSVC, 64-bit, Pengoptimalan diaktifkan)

Elements: 100000, Iterations: 144
doAppend: 74.0042ms
doReserve: 27.0015ms
doAllocate: 5.0003ms

C ++ debug build menghasilkan:

Elements: 100000, Iterations: 144
doAppend: 2166.12ms
doReserve: 2082.12ms
doAllocate: 273.016ms

Intinya di sini adalah bahwa dengan Python Anda dapat mencapai peningkatan kinerja 7-8%, dan jika Anda berpikir Anda sedang menulis aplikasi berkinerja tinggi (atau jika Anda sedang menulis sesuatu yang digunakan dalam layanan web atau sesuatu) maka itu tidak bisa diendus, tetapi Anda mungkin perlu memikirkan kembali pilihan bahasa Anda.

Juga, kode Python di sini bukan kode Python. Beralih ke kode Pythonesque yang sesungguhnya di sini memberikan kinerja yang lebih baik:

import time

class Timer(object):
    def __enter__(self):
        self.start = time.time()
        return self

    def __exit__(self, *args):
        end = time.time()
        secs = end - self.start
        msecs = secs * 1000  # millisecs
        print('%fms' % msecs)

Elements   = 100000
Iterations = 144

print('Elements: %d, Iterations: %d' % (Elements, Iterations))


def doAppend():
    for x in range(Iterations):
        result = []
        for i in range(Elements):
            result.append(i)

def doAllocate():
    for x in range(Iterations):
        result = [None] * Elements
        for i in range(Elements):
            result[i] = i

def doGenerator():
    for x in range(Iterations):
        result = list(i for i in range(Elements))


def test(name, fn):
    print("%s: " % name, end="")
    with Timer() as t:
        fn()


test('doAppend', doAppend)
test('doAllocate', doAllocate)
test('doGenerator', doGenerator)

Pemberian yang mana

Elements: 100000, Iterations: 144
doAppend: 2153.122902ms
doAllocate: 1346.076965ms
doGenerator: 1614.092112ms

(dalam doGenerator 32-bit lebih baik daripada doAllocate).

Di sini kesenjangan antara doAppend dan doAllocate secara signifikan lebih besar.

Jelas, perbedaan di sini benar-benar hanya berlaku jika Anda melakukan ini lebih dari beberapa kali atau jika Anda melakukan ini pada sistem yang sarat dengan beban di mana angka-angka itu akan diperkecil oleh urutan besarnya, atau jika Anda berurusan dengan daftar jauh lebih besar.

Intinya di sini: Lakukan dengan cara pythonic untuk kinerja terbaik.

Tetapi jika Anda khawatir tentang kinerja tingkat tinggi yang umum, Python adalah bahasa yang salah. Masalah yang paling mendasar adalah bahwa panggilan fungsi Python secara tradisional lebih lambat hingga 300x daripada bahasa lain karena fitur Python seperti dekorator dll ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

Seperti yang disebutkan orang lain, cara paling sederhana untuk melakukan pra-seeding daftar dengan NoneTypeobjek.

Yang sedang berkata, Anda harus memahami cara daftar Python benar-benar berfungsi sebelum memutuskan ini diperlukan. Dalam implementasi daftar CPython, array yang mendasari selalu dibuat dengan ruang overhead, dalam ukuran yang semakin besar ( 4, 8, 16, 25, 35, 46, 58, 72, 88, 106, 126, 148, 173, 201, 233, 269, 309, 354, 405, 462, 526, 598, 679, 771, 874, 990, 1120, etc), sehingga mengubah ukuran daftar tidak terjadi hampir begitu sering.

Karena perilaku ini, sebagian besar list.append() fungsi adalah O(1)kompleksitas untuk ditambahkan, hanya memiliki peningkatan kompleksitas ketika melewati salah satu dari batas-batas ini, pada titik mana kompleksitas akan terjadi O(n). Perilaku ini yang mengarah pada peningkatan minimal dalam waktu eksekusi dalam jawaban S. Lott.

Sumber: http://www.laurentluce.com/posts/python-list-implementation/

saya menjalankan kode @ s.lott dan menghasilkan peningkatan perf 10% yang sama dengan pra-alokasi. mencoba ide @ jeremy menggunakan generator dan mampu melihat perf gen lebih baik daripada doAllocate. Untuk proyek saya, 10% peningkatan penting, jadi terima kasih kepada semua orang karena ini membantu banyak orang.

def doAppend( size=10000 ):
    result = []
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result.append(message)
    return result

def doAllocate( size=10000 ):
    result=size*[None]
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result[i]= message
    return result

def doGen( size=10000 ):
    return list("some unique object %d" % ( i, ) for i in xrange(size))

size=1000
@print_timing
def testAppend():
    for i in xrange(size):
        doAppend()

@print_timing
def testAlloc():
    for i in xrange(size):
        doAllocate()

@print_timing
def testGen():
    for i in xrange(size):
        doGen()


testAppend()
testAlloc()
testGen()

testAppend took 14440.000ms
testAlloc took 13580.000ms
testGen took 13430.000ms

Kekhawatiran tentang pra-alokasi dalam Python muncul jika Anda bekerja dengan numpy, yang memiliki lebih banyak array mirip-C. Dalam hal ini, kekhawatiran pra-alokasi adalah tentang bentuk data dan nilai default.

Pertimbangkan numpy jika Anda melakukan perhitungan numerik pada daftar besar dan menginginkan kinerja.

Untuk beberapa aplikasi, kamus mungkin sesuai dengan yang Anda cari. Misalnya, dalam metode find_totient, saya merasa lebih nyaman menggunakan kamus karena saya tidak memiliki indeks nol.

def totient(n):
    totient = 0

    if n == 1:
        totient = 1
    else:
        for i in range(1, n):
            if math.gcd(i, n) == 1:
                totient += 1
    return totient

def find_totients(max):
    totients = dict()
    for i in range(1,max+1):
        totients[i] = totient(i)

    print('Totients:')
    for i in range(1,max+1):
        print(i,totients[i])

Masalah ini juga dapat diselesaikan dengan daftar yang sudah dialokasikan:

def find_totients(max):
    totients = None*(max+1)
    for i in range(1,max+1):
        totients[i] = totient(i)

    print('Totients:')
    for i in range(1,max+1):
        print(i,totients[i])

Saya merasa bahwa ini tidak elegan dan rentan terhadap bug karena saya menyimpan Tidak ada yang bisa mengeluarkan pengecualian jika saya tidak sengaja menggunakannya salah, dan karena saya perlu berpikir tentang kasus tepi bahwa peta memungkinkan saya menghindari.

Memang benar kamus tidak akan seefisien, tetapi seperti yang telah dikomentari orang lain, perbedaan kecil dalam kecepatan tidak selalu berarti bahaya pemeliharaan yang signifikan .

Dari apa yang saya mengerti, daftar python sudah sangat mirip dengan ArrayLists. Tetapi jika Anda ingin mengubah parameter tersebut, saya menemukan posting ini di internet yang mungkin menarik (pada dasarnya, buat saja ScalableListekstensi Anda sendiri ):

http://mail.python.org/pipermail/python-list/2000-May/035082.html