[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의 간격이 상당히 큽니다.

분명히 여기의 차이점은 소수 이상의 작업을 수행하거나로드가 많은 시스템에서이 작업을 수행하는 경우에만 적용됩니다. 상당히 큰 목록.

요점은 다음과 같습니다. 최고의 성능을 얻으려면 pythonic 방식으로하십시오.

그러나 일반적인 높은 수준의 성능에 대해 걱정한다면 Python은 잘못된 언어입니다. 가장 근본적인 문제는 Python 함수 호출이 데코레이터 등과 같은 Python 기능으로 인해 전통적으로 다른 언어보다 최대 300 배 느리다는 것입니다 ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).


답변

다른 사람들이 언급했듯이 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/


답변

@ s.lott의 코드를 실행하고 사전 할당에 의해 동일한 10 % perf 증가를 생성했습니다. 발전기를 사용하여 @jeremy의 아이디어를 시도하고 doAllocate보다 gen의 성능을 더 잘 볼 수있었습니다. 내 프로젝트의 경우 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()

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


답변

파이썬에서 사전 할당에 대한 우려는 C와 같은 배열이 더 많은 numpy로 작업하는 경우 발생합니다. 이 경우 사전 할당 문제는 데이터의 모양과 기본값에 관한 것입니다.

대규모 목록에서 숫자 계산을 수행하고 성능을 원하면 numpy를 고려하십시오.