Python-초기 용량을 가진 목록 만들기

Python-초기 용량을 가진 목록 만들기

---

이와 같은 코드가 자주 발생합니다.

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

목록에 새 요소에 맞게 크기를 조정해야하므로 수천 개의 요소를 목록에 추가하려는 경우에는 실제로 속도가 느립니다.

Java에서는 초기 용량으로 ArrayList를 작성할 수 있습니다. 목록이 얼마나 큰지 알면 훨씬 효율적입니다.

나는 이와 같은 코드가 종종 목록 이해력으로 리팩터링 될 수 있음을 이해합니다. 그러나 for / while 루프가 매우 복잡한 경우 이는 불가능합니다. 우리 파이썬 프로그래머에게 동등한 것이 있습니까?

---

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

결론 . 간신히 중요합니다.

조기 최적화는 모든 악의 근원입니다.

---

파이썬리스트에는 내장 된 사전 할당이 없습니다. 실제로 목록을 작성해야하고 추가로 인한 오버 헤드를 피해야하는 경우 (및 확인해야 함) 다음을 수행 할 수 있습니다.

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

이런 식으로,리스트가 메모리에 모두 저장되는 것은 아니며, 필요에 따라 생성 될뿐입니다.

---

짧은 버전 : 사용

pre_allocated_list = [None] * size

목록을 미리 할당합니다 (즉, 목록을 추가하여 목록을 점차적으로 형성하는 대신 목록의 '크기'요소를 처리 할 수 ​​있도록). 이 작업은 큰 목록에서도 매우 빠릅니다. 나중에 요소를 나열하기 위해 할당 할 새 개체를 할당하면 시간이 많이 걸리고 성능 측면에서 프로그램의 병목 현상이 발생합니다.

긴 버전 :

초기화 시간을 고려해야한다고 생각합니다. 파이썬에서는 모든 것이 참조이므로 각 요소를 없음 또는 문자열로 설정했는지 여부는 중요하지 않습니다. 참조 할 각 요소에 대해 새 객체를 만들려면 시간이 더 오래 걸립니다.

파이썬 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의 대답은 매번 새로운 문자열을 포맷합니다. 꼭 필요한 것은 아닙니다. 일부 공간을 미리 할당하려면 없음 목록을 만든 다음 마음대로 목록 요소에 데이터를 할당하십시오. 어느 쪽이든 목록을 생성하는 동안 생성 한 후 또는 생성 한 후에 목록을 추가 / 확장하는 것보다 데이터를 생성하는 데 시간이 더 걸립니다. 그러나 드물게 채워진 목록을 원하면 없음 목록으로 시작하는 것이 훨씬 빠릅니다.

---

이를위한 Pythonic 방법은 다음과 같습니다.

x = [None] * numElements

또는 미리 채울 기본값, 예를 들어

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

[편집 : emptor 경고 의 [Beer()] * 99구문 생성 한 Beer 후, 동일한 단일 인스턴스 99 참조 배열을 채우는]

파이썬의 기본 접근 방식은 요소 수를 늘리면 효율성이 떨어지지 만 상당히 효율적 일 수 있습니다.

비교

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

여기서 중요한 점은 파이썬을 사용하면 7-8 %의 성능 향상을 달성 할 수 있으며, 고성능 앱을 작성한다고 생각하거나 웹 서비스 또는 무언가에 사용되는 것을 작성한다고 생각되면 스니핑되지는 않지만 언어 선택을 다시 생각해야 할 수도 있습니다.

또한 여기의 파이썬 코드는 실제로 파이썬 코드가 아닙니다. 진정한 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의 간격이 상당히 큽니다.

Obviously, the differences here really only apply if you are doing this more than a handful of times or if you are doing this on a heavily loaded system where those numbers are going to get scaled out by orders of magnitude, or if you are dealing with considerably larger lists.

The point here: Do it the pythonic way for the best performance.

But if you are worrying about general, high-level performance, Python is the wrong language. The most fundamental problem being that Python function calls has traditionally been upto 300x slower than other languages due to Python features like decorators etc (https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation).

---

As others have mentioned, the simplest way to pre-seed a list with NoneType objects.

That being said, you should understand the way Python lists actually work before deciding this is necessary. In the CPython implementation of a list, the underlying array is always created with overhead room, in progressively larger sizes ( 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), so that resizing the list does not happen nearly so often.

Because of this behavior, most list.append() functions are O(1) complexity for appends, only having increased complexity when crossing one of these boundaries, at which point the complexity will be O(n). This behavior is what leads to the minimal increase in execution time in S. Lott's answer.

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

---

i ran @s.lott's code and produced the same 10% perf increase by pre-allocating. tried @jeremy's idea using a generator and was able to see the perf of the gen better than that of the doAllocate. For my proj the 10% improvement matters, so thanks to everyone as this helps a bunch.

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

---

Concerns about pre-allocation in Python arise if you're working with numpy, which has more C-like arrays. In this instance, pre-allocation concerns are about the shape of the data and the default value.

Consider numpy if you're doing numerical computation on massive lists and want performance.

---

For some applications, a dictionary may be what you are looking for. For example, in the find_totient method, I found it more convenient to use a dictionary since I didn't have a zero index.

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])

This problem could also be solved with a preallocated list:

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])

I feel that this is not as elegant and prone to bugs because I'm storing None which could throw an exception if I accidentally use them wrong, and because I need to think about edge cases that the map lets me avoid.

It's true the dictionary won't be as efficient, but as others have commented, small differences in speed are not always worth significant maintenance hazards.

---

From what I understand, python lists are already quite similar to ArrayLists. But if you want to tweak those parameters I found this post on the net that may be interesting (basically, just create your own ScalableList extension):

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

참고URL : https://stackoverflow.com/questions/311775/python-create-a-list-with-initial-capacity