Python 3: Cách hiệu quả nhất để tạo [func (i) cho tôi trong phạm vi (N)] danh sách hiểu

Question

Giả sử tôi có hàm func (i) tạo đối tượng cho số nguyên i và N là một số không âm số nguyên. Sau đó, cách nhanh nhất để tạo danh sách (không phải là phạm vi) bằng danh sách này

mylist = [func(i) for i in range(N)] 

mà không dùng phương pháp nâng cao như tạo hàm trong C? Mối quan tâm chính của tôi với việc hiểu danh sách ở trên là tôi không chắc liệu python có biết trước độ dài phạm vi (N) để preallocate danh sách của tôi không, và do đó phải dần phân bổ lại danh sách. Đó là trường hợp hoặc là python đủ thông minh để phân bổ danh sách của tôi đến độ dài N đầu tiên và sau đó tính toán các yếu tố của nó? Nếu không, cách tốt nhất để tạo danh sách của tôi là gì? Có lẽ điều này?

mylist = [None]*N 
for i in range(N): mylist[i] = func(i) 

RE-EDIT: Xóa thông tin gây hiểu lầm khỏi chỉnh sửa trước đó.

Answer 1

Ai đó đã viết: "" "Python là thông minh đủ Chừng nào các đối tượng bạn đang iterating trên có một phương pháp __len__ hay __length_hint__, Python sẽ gọi nó là để xác định kích thước và preallocate mảng.." ""

Theo như tôi có thể biết, không có preallocation trong danh sách hiểu. Python không có cách nào để nói với kích thước của INPUT kích thước của OUTPUT.

Nhìn vào Python 2.6 mã này:

>>> def foo(func, iterable): 
...  return [func(i) for i in iterable] 
... 
>>> import dis; dis.dis(foo) 
    2   0 BUILD_LIST    0 #### build empty list 
       3 DUP_TOP 
       4 STORE_FAST    2 (_[1]) 
       7 LOAD_FAST    1 (iterable) 
      10 GET_ITER 
     >> 11 FOR_ITER    19 (to 33) 
      14 STORE_FAST    3 (i) 
      17 LOAD_FAST    2 (_[1]) 
      20 LOAD_FAST    0 (func) 
      23 LOAD_FAST    3 (i) 
      26 CALL_FUNCTION   1 
      29 LIST_APPEND  #### stack[-2].append(stack[-1]); pop() 
      30 JUMP_ABSOLUTE   11 
     >> 33 DELETE_FAST    2 (_[1]) 
      36 RETURN_VALUE 

Nó chỉ xây dựng một danh sách rỗng, và gắn thêm bất cứ lặp đi lặp lại mang lại.

Bây giờ nhìn vào mã này, trong đó có một 'nếu' trong danh sách hiểu:

>>> def bar(func, iterable): 
...  return [func(i) for i in iterable if i] 
... 
>>> import dis; dis.dis(bar) 
    2   0 BUILD_LIST    0 
       3 DUP_TOP 
       4 STORE_FAST    2 (_[1]) 
       7 LOAD_FAST    1 (iterable) 
      10 GET_ITER 
     >> 11 FOR_ITER    30 (to 44) 
      14 STORE_FAST    3 (i) 
      17 LOAD_FAST    3 (i) 
      20 JUMP_IF_FALSE   17 (to 40) 
      23 POP_TOP 
      24 LOAD_FAST    2 (_[1]) 
      27 LOAD_FAST    0 (func) 
      30 LOAD_FAST    3 (i) 
      33 CALL_FUNCTION   1 
      36 LIST_APPEND 
      37 JUMP_ABSOLUTE   11 
     >> 40 POP_TOP 
      41 JUMP_ABSOLUTE   11 
     >> 44 DELETE_FAST    2 (_[1]) 
      47 RETURN_VALUE 
>>> 

Cùng mã, cộng với một số mã để tránh LIST_APPEND.

Trong Python 3.x, bạn cần phải đào sâu hơn một chút:

>>> import dis 
>>> def comprehension(f, iterable): return [f(i) for i in iterable] 
... 
>>> dis.dis(comprehension) 
    1   0 LOAD_CLOSURE    0 (f) 
       3 BUILD_TUPLE    1 
       6 LOAD_CONST    1 (<code object <listcomp> at 0x00C4B8D 
8, file "<stdin>", line 1>) 
       9 MAKE_CLOSURE    0 
      12 LOAD_FAST    1 (iterable) 
      15 GET_ITER 
      16 CALL_FUNCTION   1 
      19 RETURN_VALUE 
>>> dis.dis(comprehension.__code__.co_consts[1]) 
    1   0 BUILD_LIST    0 
       3 LOAD_FAST    0 (.0) 
     >> 6 FOR_ITER    18 (to 27) 
       9 STORE_FAST    1 (i) 
      12 LOAD_DEREF    0 (f) 
      15 LOAD_FAST    1 (i) 
      18 CALL_FUNCTION   1 
      21 LIST_APPEND    2 
      24 JUMP_ABSOLUTE   6 
     >> 27 RETURN_VALUE 
>>> 

Đó là schtick cũ: bắt đầu với việc xây dựng một danh sách rỗng, sau đó lặp qua các iterable, phụ thêm vào danh sách theo yêu cầu. Tôi thấy không có preallocation ở đây.

Tối ưu hóa mà bạn đang nghĩ đến được sử dụng bên trong một mã vạch duy nhất, ví dụ: việc thực hiện list.extend(iterable) có thể preallocate nếu iterable có thể báo cáo chính xác độ dài của nó. list.append(object) được cấp một đối tượng duy nhất, không được lặp lại.

Answer 2

Sử dụng tính năng hiểu danh sách để hoàn thành những gì bạn đang cố gắng thực hiện sẽ là cách để làm điều đó. Mặc dù hình phạt hiệu suất :).

Answer 3

Không có sự khác biệt về độ phức tạp tính toán giữa việc sử dụng mảng tự động hóa và preallocating một mảng. Tệ nhất là chi phí về O (2N). Xem ở đây:

Constant Amortized Time

Chi phí của các cuộc gọi chức năng cộng thêm bất cứ điều gì xảy ra trong chức năng của bạn sẽ làm cho phụ n không đáng kể. Đây không phải là điều bạn nên lo lắng. Chỉ cần sử dụng danh sách hiểu.

Answer 4

sẽ phải đồng ý với Javier đây ...

Với đoạn mã sau:

print '%5s | %6s | %6s' % ('N', 'l.comp', 'manual') 
print '------+--------+-------' 
for N in 10, 100, 1000, 10000: 
    num_iter = 1000000/N 

    # Time for list comprehension. 
    t1 = timeit.timeit('[func(i) for i in range(N)]', setup='N=%d;func=lambda x:x' % N, number=num_iter) 

    # Time to build manually. 
    t2 = timeit.timeit('''mylist = [None]*N 
for i in range(N): mylist[i] = func(i)''', setup='N=%d;func=lambda x:x' % N, number=num_iter) 

    print '%5d | %2.4f | %2.4f' % (N, t1, t2) 

tôi nhận được bảng sau:

N | l.comp | manual 
------+--------+------- 
    10 | 0.3330 | 0.3597 
    100 | 0.2371 | 0.3138 
1000 | 0.2223 | 0.2740 
10000 | 0.2185 | 0.2771 

Từ bảng này có vẻ như danh sách hiểu nhanh hơn phân bổ trước trong mọi trường hợp có độ dài khác nhau.

Answer 5

Nếu bạn sử dụng các module timeit, bạn có thể đi đến kết luận ngược lại: danh sách hiểu nhanh hơn preallocation:

f=lambda x: x+1 
N=1000000 
def lc(): 
    return [f(i) for i in range(N)] 
def prealloc(): 
    mylist = [None]*N 
    for i in range(N): mylist[i]=f(i) 
    return mylist 
def xr(): 
    return map(f,xrange(N)) 

if __name__=='__main__': 
    lc() 

Warning: Đây là những kết quả trên máy tính của tôi. Bạn nên tự mình thử các thử nghiệm này, vì kết quả của bạn có thể khác nhau tùy thuộc vào phiên bản Python và phần cứng của bạn. (Xem các ý kiến.)

% python -mtimeit -s"import test" "test.prealloc()" 
10 loops, best of 3: 370 msec per loop 
% python -mtimeit -s"import test" "test.lc()" 
10 loops, best of 3: 319 msec per loop 
% python -mtimeit -s"import test" "test.xr()" 
10 loops, best of 3: 348 msec per loop 

Lưu ý rằng không giống như câu trả lời Javier, tôi bao gồm mylist = [None]*N như một phần của timeit đang để thời gian khi sử dụng phương pháp "pre-phân bổ". (Nó không chỉ là một phần của thiết lập, vì nó là mã một sẽ chỉ cần nếu sử dụng phân bổ trước.)

PS. mô-đun time (và time (lệnh unix)) can give unreliable results. Nếu bạn muốn mã thời gian Python, tôi khuyên bạn nên gắn bó với mô-đun timeit.

Answer 6

Câu hỏi thú vị.Tính đến kiểm tra sau, có vẻ như preallocation không cải thiện hiệu suất trong việc thực hiện CPython hiện tại (Python 2 mã nhưng kết quả xếp hạng là như nhau, ngoại trừ việc không có xrange bằng Python 3):

N = 5000000 

def func(x): 
    return x**2 

def timeit(fn): 
    import time 
    begin = time.time() 
    fn() 
    end = time.time() 
    print "%-18s: %.5f seconds" % (fn.__name__, end - begin) 

def normal(): 
    mylist = [func(i) for i in range(N)] 

def normalXrange(): 
    mylist = [func(i) for i in xrange(N)] 

def pseudoPreallocated(): 
    mylist = [None] * N 
    for i in range(N): mylist[i] = func(i) 

def preallocated(): 
    mylist = [None for i in range(N)] 
    for i in range(N): mylist[i] = func(i) 

def listFromGenerator(): 
    mylist = list(func(i) for i in range(N)) 

def lazy(): 
    mylist = (func(i) for i in xrange(N)) 



timeit(normal) 
timeit(normalXrange) 
timeit(pseudoPreallocated) 
timeit(preallocated) 
timeit(listFromGenerator) 
timeit(lazy) 

Kết quả (xếp hạng trong dấu ngoặc đơn):

normal   : 7.57800 seconds (2) 
normalXrange  : 7.28200 seconds (1) 
pseudoPreallocated: 7.65600 seconds (3) 
preallocated  : 8.07800 seconds (5) 
listFromGenerator : 7.84400 seconds (4) 
lazy    : 0.00000 seconds 

nhưng với psyco.full():

normal   : 7.25000 seconds (3) 
normalXrange  : 7.26500 seconds (4) 
pseudoPreallocated: 6.76600 seconds (1) 
preallocated  : 6.96900 seconds (2) 
listFromGenerator : 10.50000 seconds (5) 
lazy    : 0.00000 seconds 

Như bạn thấy, giả preallocation là nhanh hơn với Psyco. Trong mọi trường hợp, không có nhiều sự khác biệt giữa giải pháp xrange (tôi khuyên bạn nên sử dụng) và các giải pháp khác. Nếu bạn không xử lý tất cả các phần tử của danh sách sau này, bạn cũng có thể sử dụng phương thức lười (được hiển thị trong đoạn mã trên) sẽ tạo ra một trình tạo ra các phần tử khi bạn lặp lại nó.