Python Есть ли влияние на производительность при использовании списков?

Question

Это может показаться глупым вопросом, но у меня есть список из 400 000 элементов, и производительность кажется такой же, как если бы список был в количестве 100 элементов. Мне кажется, что вы ограничены только объемом оперативной памяти и максимальным размером списка?

Чтобы быть конкретным:

1. Если бы мне пришлось искать в этом списке (item in bigList), есть ли хит производительности?
2. Будет ли снижение производительности, если я добавлю, скажем, 200 000 элементов на этот 400 000 пунктов списка?
3. Будет ли снижение производительности только в том случае, если я прокручиваю каждый элемент в список
4. Если при использовании списков возникают проблемы с производительностью, Типичный максимальный размер?

Answer 1

из руководства :

Списки Python действительно массивы переменной длины

это означает, что поиск выполняется за O (N)где N - длина списка.Вы можете посмотреть collection , если вам нужна другая реализация.или используйте набор (внутренне хеш-таблицу)

Answer 2

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

В качестве отправной точки я указал небольшой скрипт:

from sys import getsizeof
from timeit import timeit
from random import randint

MIN_EXP, MAX_EXP = 1, 8 # list-size from 10^1 to 10^8 as default
TEST_ITERATIONS = 1

class ListTest(object):
    def __init__(self, number, item):
        self.number = number
        self.item = item
        self.size = '0'
        self.time = 0.0

    def test_01_creation_list_comprehension(self):
        list_ = []
        def profile():
            list_ = [self.item for n in range(self.number)]
        self.time = timeit(profile, number = TEST_ITERATIONS)
        self.size = "%.3f" % (getsizeof(list_) / 1024.0,)

    def test_02_creation_list_append(self):
        list_ = []
        def profile():
            for n in range(self.number):
                list_.append(self.item)
        self.time = timeit(profile, number = TEST_ITERATIONS)                
        self.size = "%.3f" % (getsizeof(list_) / 1024.0,)

    def test_03_find_item(self):        
        list_ = [self.item for n in range(self.number)]
        searchstr = 'find me!'
        list_[randint(0,self.number)] = searchstr
        def profile():
            foundya = list_.index(searchstr)            
        self.time = timeit(profile, number = TEST_ITERATIONS)                


tests = [ListTest(10**n,'string-item') for n in range(MIN_EXP,MAX_EXP)]
for test in tests:
    print "-"*78,"\nListTest with %d items:" % test.number
    for subtest in [st for st in dir(test) if st.startswith('test_')]:
        getattr(test, subtest)()
        print "%15s" % "%s: %.4f s" % (subtest, test.time)
        print "%32s" % "%s %14s %s"  % ("Memory used:", test.size, "kB")

я получаю список с 10 миллионами записей этих результатов (100 миллионов не вычисляются с моими настройками памяти)

 >>>   ListTest with 10000000 items:
 >>>        test_01_creation_list_comprehension: 1.7200 s
 >>>                         Memory used:          0.031 kB
 >>>        test_02_creation_list_append: 2.8455 s
 >>>                         Memory used:      39808.621 kB
 >>>        test_03_find_item: 0.1657 s
 >>>                         Memory used:      39808.621 kB

Использование памяти - это больше показатель величины, чем реальное потребление. Функция sys.getsizeof в основном корректна для стандартных типов, включает накладные расходы gc, но не работает хорошо для сложных объектов или внешних (внешних) объектов.

Answer 3

Если бы я искал этот список (элемент в bigList)

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

Будет ли снижение производительности, если я добавлю, скажем, 200 000 элементов в этот список 400 000 элементов?

Нет, добавление занимает одно и то же время, независимо от размера списка.

Если при использовании списков возникают проблемы с производительностью, каков будет максимальный размер?

Не имеет смысла, списки можно использовать по-разному. Короче говоря, списки хороши в хранении и плохо в поиске вещей.