Cla*_*diu 182 python dictionary initialization list
像这样的代码经常发生:
l = []
while foo:
#baz
l.append(bar)
#qux
如果您要将数千个元素追加到列表中,这非常慢,因为必须不断调整列表大小以适应新元素.
在Java中,您可以创建具有初始容量的ArrayList.如果您对列表的大小有所了解,那么效率会更高.
我知道像这样的代码通常可以重新考虑到列表理解中.但是,如果for/while循环非常复杂,那么这是不可行的.我们的Python程序员有没有相同的东西？
S.L*_*ott 121
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
结果.(评估每个功能144次并平均持续时间)
simple append 0.0102
pre-allocate 0.0098
结论.这几乎不重要.
过早优化是万恶之源.
Ned*_*der 76
Python列表没有内置的预分配.如果你真的需要制作一个列表,并且需要避免附加的开销(你应该验证你这样做),你可以这样做:
l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
# baz
l[i] = bar
# qux
也许您可以通过使用生成器来避免列表:
def my_things():
while foo:
#baz
yield bar
#qux
for thing in my_things():
# do something with thing
这样,列表并不是全部存储在内存中,只是根据需要生成.
LRN*_*LRN 45
简短版:使用
pre_allocated_list = [None] * size
预先分配一个列表(即,能够解决列表的'size'元素,而不是通过附加逐渐形成列表).即使在大型列表中,此操作也非常快.分配稍后将分配给列表元素的新对象将花费更长时间,并且将成为程序中的瓶颈,性能方面.
长版:
我认为应该考虑初始化时间.因为在python中,一切都是引用,无论你是将每个元素设置为None还是一些字符串都无关紧要 - 无论哪种方式,它都只是一个引用.如果要为每个要引用的元素创建新对象,则需要更长的时间.
对于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()
评价:
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] = ()
正如您所看到的,只需创建一个对同一None对象的引用的大列表,只需要很少的时间.
前置或延长需要更长的时间(我没有做任何平均值,但在运行几次之后我可以告诉你,延伸和追加大致需要相同的时间).
为每个元素分配新对象 - 这是花费最多时间的.而S.Lott的答案就是这样 - 每次都会格式化一个新的字符串.这不是严格要求的 - 如果您想预先分配一些空间,只需创建一个None列表,然后随意将数据分配给列表元素.无论哪种方式,生成数据都需要花费更多时间而不是追加/扩展列表,无论是在创建列表时生成还是在生成列表之后生成数据.但是如果你想要一个人口稀少的列表,那么从None列表开始肯定会更快.
kfs*_*one 22
Pythonic的方法是:
x = [None] * numElements
或者您希望预先填写的任何默认值,例如
bottles = [Beer()] * 99
sea = [Fish()] * many
vegetarianPizzas = [None] * peopleOrderingPizzaNotQuiche
[编辑:买者自负的[Beer()] * 99语法创建一个 Beer,然后填充与99次的引用数组相同的单个实例]
Python的默认方法非常有效,尽管随着元素数量的增加,效率会下降.
相比
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)
同
#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);
}
在我的Windows 7 i7上,64位Python给出了
Elements: 100000, Iterations: 144
doAppend: 3587.204933ms
doAllocate: 2701.154947ms
doGenerator: 1721.098185ms
虽然C++给出(使用MSVC,64位,启用优化)
Elements: 100000, Iterations: 144
doAppend: 74.0042ms
doReserve: 27.0015ms
doAllocate: 5.0003ms
C++调试版本生成:
Elements: 100000, Iterations: 144
doAppend: 2166.12ms
doReserve: 2082.12ms
doAllocate: 273.016ms
这里的要点是,使用Python可以实现7-8%的性能提升,如果您认为自己正在编写高性能应用程序(或者如果您正在编写用于Web服务或其他内容的东西),那么不要被嗤之以鼻,但你可能需要重新考虑你选择的语言.
此外,这里的Python代码不是真正的Python代码.切换到真正的Pythonesque代码可以提供更好的性能:
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)
这使
Elements: 100000, Iterations: 144
doAppend: 2153.122902ms
doAllocate: 1346.076965ms
doGenerator: 1614.092112ms
(在32位doGenerator中比doAllocate更好).
这里doAppend和doAllocate之间的差距要大得多.
显然,这里的差异实际上只适用于您执行此操作的次数超过少数几次,或者如果您在负载较重的系统上执行此操作,其中这些数字将按数量级扩展,或者如果您正在处理更大的清单.
重点在于:以最佳性能的pythonic方式.
但是如果你担心一般的高级性能,Python就是错误的语言.最基本的问题是Python函数调用传统上比其他语言慢300倍,这是由于像装饰器等Python功能(https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation).
小智 8
正如其他人所提到的,使用NoneType对象预先设置列表种子的最简单方法.
话虽这么说,你应该理解Python列出实际工作的方式,然后再决定这是必要的.在列表的CPython实现中,底层数组总是以开销空间创建,逐渐变大( 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),因此调整列表大小几乎不会发生.
由于这种行为,大多数 list.append()函数都是O(1)附加的复杂性,只是在跨越这些边界之一时具有增加的复杂性,此时复杂性将是O(n).这种行为导致了S. Lott的答案中执行时间的最小增加.
资料来源:http://www.laurentluce.com/posts/python-list-implementation/
小智 5
我运行了S.Lott 的代码，通过预分配实现了同样 10% 的性能提升。我使用生成器尝试了 Ned Batchelder 的想法，并且能够看到生成器的性能比 doAllocate 的性能更好。对于我的项目来说，10% 的改进很重要，所以感谢大家，因为这对很多人都有帮助。
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()
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()