Python - создать список с начальной емкостью

188

Такой код часто бывает:

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

Это очень медленно, если вы собираетесь добавить тысячи элементов в свой список, так как список должен будет постоянно изменяться, чтобы соответствовать новым элементам.

В Java вы можете создать ArrayList с начальной емкостью. Если у вас есть представление о том, насколько большим будет ваш список, это будет намного эффективнее.

Я понимаю, что подобный код часто может быть преобразован в понимание списка. Однако, если цикл for / while очень сложен, это невозможно. Есть ли какой-нибудь эквивалент для нас, программистов на Python?

Клаудиу
источник
12
Насколько я знаю, они похожи на ArrayLists в том, что они каждый раз удваивают свой размер. Амортизированное время этой операции постоянно. Это не такой большой удар по производительности, как вы думаете.
mmcdole
Кажется, ты прав!
Клавдиу
11
Возможно, предварительная инициализация не является строго необходимой для сценария OP, но иногда она определенно необходима: у меня есть несколько предварительно проиндексированных элементов, которые необходимо вставить по определенному индексу, но они выходят из строя. Мне нужно заранее увеличить список, чтобы избежать IndexErrors. Спасибо за этот вопрос.
Нил Трэфт
1
@Claudiu Принятый ответ вводит в заблуждение. Комментарий с наибольшим количеством голосов под ним объясняет почему. Рассматриваете ли вы принять один из других ответов?
Нил Гокли

Ответы:

126
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

Заключение . Это едва имеет значение.

Преждевременная оптимизация - корень всего зла.

С. Лотт
источник
18
Что, если метод предварительного выделения (размер * [Нет]) сам по себе неэффективен? Виртуальная машина Python фактически распределяет список сразу или постепенно увеличивает его, как это делает append ()?
haridsv
9
Привет. Предположительно это можно выразить в Python, но никто еще не разместил его здесь. Пункт haridsv заключался в том, что мы просто предполагаем, что int * list не просто добавляется к списку элемент за элементом. Это предположение, вероятно, верно, но точка зрения Харидсва состояла в том, что мы должны это проверить. Если это неверно, это объясняет, почему две функции, которые вы показали, занимают почти одинаковое время - потому что под прикрытием они делают одно и то же, следовательно, фактически не проверяли предмет этого вопроса. С уважением!
Джонатан Хартли
136
Это не действительно; вы форматируете строку с каждой итерацией, что занимает вечно относительно того, что вы пытаетесь проверить. Кроме того, учитывая, что 4% все еще могут быть значительными в зависимости от ситуации, и это недооценивает ...
Филипп Гин
40
Как отмечает @Philip, заключение здесь вводит в заблуждение. Предварительное распределение здесь не имеет значения, потому что операция форматирования строки стоит дорого. Я протестировал с дешевой операцией в цикле и обнаружил, что предварительное распределение почти в два раза быстрее.
Кит
12
Неправильные ответы со многими ответами - еще один корень зла.
Хасимото
80

Списки 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

Таким образом, список не хранится в памяти, а просто генерируется по мере необходимости.

Нед Бэтчелдер
источник
7
+1 Генераторы вместо списков. Многие алгоритмы могут быть немного пересмотрены для работы с генераторами вместо полностью материализованных списков.
S.Lott
генераторы хорошая идея, правда. Я хотел общий способ сделать это, кроме настройки на месте. Я думаю, разница незначительна, thoguh.
Клавдиу
50

Короткая версия: использовать

pre_allocated_list = [None] * 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 занимает очень мало времени.

Предварительное добавление или расширение занимает больше времени (я ничего не усреднял, но после нескольких попыток могу сказать, что расширение и добавление занимают примерно одно и то же время).

Выделение нового объекта для каждого элемента - это то, что занимает больше всего времени. И ответ С. Лотта делает это - каждый раз форматирует новую строку. Что не является строго обязательным - если вы хотите предварительно выделить некоторое пространство, просто составьте список None, а затем назначьте данные элементам списка по желанию. В любом случае для создания данных требуется больше времени, чем для добавления / расширения списка, независимо от того, генерируете ли вы его при создании списка или после него. Но если вы хотите малонаселенный список, то начинать со списка None определенно быстрее.

LRN
источник
хм интересно. поэтому ответ на этот вопрос таков: действительно не имеет значения, выполняете ли вы какую-либо операцию для помещения элементов в список, но если вы действительно просто хотите получить большой список всех одинаковых элементов, вы должны использовать []*подход
Claudiu
26

Pythonic путь для этого:

x = [None] * numElements

или любое другое значение по умолчанию, с которым вы хотите подготовиться, например

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

[EDIT: Caveat Emptor[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%, и если вы думаете, что пишете высокопроизводительное приложение (или если вы пишете что-то, что используется в веб-сервисе или чем-то еще), то это не должно быть обнюхено, но вам, возможно, придется пересмотреть свой выбор языка.

Кроме того, код 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 значительно больше.

Очевидно, что различия здесь действительно применимы, только если вы делаете это более чем несколько раз или если вы делаете это в сильно загруженной системе, где эти числа будут уменьшены на порядки или если вы имеете дело с значительно большие списки.

Суть здесь: сделать это питонским способом для лучшей производительности.

Но если вы беспокоитесь об общей производительности на высоком уровне, Python - не тот язык. Наиболее фундаментальная проблема заключается в том, что вызовы функций Python традиционно были в 300 раз медленнее, чем другие языки, из-за таких функций Python, как декораторы и т. Д. ( Https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

kfsone
источник
@NilsvonBarth C ++ не имеетtimeit
kfsone
Python имеет timeit, что вы должны использовать при синхронизации вашего кода Python; Я не говорю о C ++, очевидно.
Нильс фон Барт,
4
Это не правильный ответ. bottles = [Beer()] * 99не создает 99 объектов пива. Вместо этого создается один объект Beer с 99 ссылками на него. Если вы измените его, все элементы в списке будут видоизменены, причина (bottles[i] is bootles[j]) == Trueдля каждого i != j. 0<= i, j <= 99.
erhesto
@erhesto Вы оценили ответ как неправильный, потому что автор использовал ссылки в качестве примера для заполнения списка? Во-первых, никому не нужно создавать 99 объектов Beer (по сравнению с одним объектом и 99 ссылками). В случае предпопуляции (о чем он говорил), чем быстрее, тем лучше, так как значение будет заменено позже. Во-вторых, ответ вовсе не касается ссылок или мутаций. Вам не хватает общей картины.
Юнвэй Ву
@YongweiWu Ты прав на самом деле прав. Этот пример не делает весь ответ неправильным, он может быть просто вводящим в заблуждение, и его просто стоит упомянуть.
erhesto
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). Именно такое поведение приводит к минимальному увеличению времени выполнения в ответе С. Лотта.

Источник: http://www.laurentluce.com/posts/python-list-implementation/

Рассел Троксель
источник
4

я запустил код @ s.lott и произвел такое же увеличение производительности на 10%, предварительно выделив. попробовал идею @ jeremy, используя генератор, и смог лучше увидеть характеристики генов, чем у 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()

testAppend took 14440.000ms
testAlloc took 13580.000ms
testGen took 13430.000ms
Джейсон Винер
источник
5
«Для моего проекта улучшение на 10% имеет значение»? В самом деле? Вы можете доказать , что распределение списка узкого места ? Я хотел бы увидеть больше об этом. У вас есть блог, где вы могли бы объяснить, как это на самом деле помогло?
С.Лотт
2
@ S.Lott попробуйте увеличить размер на порядок; производительность падает на 3 порядка (по сравнению с C ++, где производительность падает чуть больше, чем на один порядок).
kfsone
2
Это может иметь место, потому что по мере роста массива его, возможно, придется перемещать в памяти. (Подумайте о том, как объекты хранятся там один за другим.)
Евгений Сергеев
3

Озабоченность по поводу предварительного выделения в Python возникает, если вы работаете с numpy, который имеет больше C-подобных массивов. В этом случае проблемы перед выделением связаны с формой данных и значением по умолчанию.

Подумайте, если вы делаете числовые вычисления в больших списках и хотите повысить производительность.

J450n
источник
0

Для некоторых приложений словарь может быть тем, что вы ищете. Например, в методе find_totient мне было удобнее использовать словарь, поскольку у меня не было нулевого индекса.

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

Эта проблема также может быть решена с помощью предварительно выделенного списка:

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

Я чувствую, что это не так элегантно и подвержено ошибкам, потому что я храню None, который может вызвать исключение, если я их случайно использую неправильно, и потому что мне нужно подумать о крайних случаях, которых карта позволяет мне избежать.

Да, словарь не будет таким эффективным, но, как отмечали другие, небольшие различия в скорости не всегда стоят значительных рисков при обслуживании.

Иосия Йодер
источник
-1

Насколько я понимаю, списки Python уже очень похожи на ArrayLists. Но если вы хотите настроить эти параметры, я нашел этот пост в сети, который может быть интересным (в основном, просто создайте свой собственныйScalableList расширение):

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

Петр Лесницкий
источник