Временная сложность создания вложенных списков в Python - PullRequest
Новая
       7

Временная сложность создания вложенных списков в Python

3 голосов
/ 06 ноября 2011

У меня возникла странность с созданием вложенных списков в Python 2.6.6.

Рассмотрим следующие две функции: 

def lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = []
    print time.time() - start_time

def simple_lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = False
    print time.time() - start_time

Они оба выделяют массив размером n * n. Один назначает все значения как «Ложь», а другой назначает все значения как пустые списки. Они оба должны работать в O (n ^ 2), насколько я вижу. Тем не менее, это не так ... Обратите внимание на следующие тестовые прогоны: 

>>> for i in [4000, 8000, 16000]: simple_lists(i)
2.11170578003
8.67467808723
34.0958559513
>>> for i in [1000, 2000, 4000]: lists(i)
1.13742399216
7.39806008339
78.0808939934

Как вы можете видеть, simple_lists (), кажется, увеличивается примерно на O (n ^ 2), тогда как lists (), кажется, растет на O (n ^ 3)!

Что здесь происходит? Эта причудливость полностью и полностью разрушает сложность моего кода, и я не могу объяснить, почему он так себя ведет. У кого-нибудь есть идеи?

Редактировать: Понимание списка, кажется, вызывает те же проблемы сложности.

Переопределение списков () как 

def lists(n):
    start_time = time.time()
    lists = [[[] for y in xrange(n)] for x in xrange(n)]
    print time.time() - start_time

вызывает следующие результаты 

>>> for i in [1000, 2000, 4000]: lists(i)
0.388785839081
4.45830011368
65.6449248791

... который все еще явно растет в темпе быстрее, чем O (n ^ 2) (и даже быстрее, чем O (n ^ 3) - шиш).

edit2: После некоторого дальнейшего изучения проблемы, кажется, это вызвано сборщиком мусора. После запуска gc.disable() это результат с исходным определением lists (): 

>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266

это чертовски аккуратно O (n ^ 2).

Мораль истории: не доверяйте сборщику мусора!

Ответы [ 2 ]

2 голосов
/ 06 ноября 2011

Оказывается, странное поведение было вызвано сборщиком мусора. Отключение с помощью gc.disable() привело к следующему: 

>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266

которая подходит O (n ^ 2) как перчатка.

2 голосов
/ 06 ноября 2011

На моей машине 

for i in [1000, 2000, 4000]: lists(i)

дает 

0.994000196457
4.31200003624
17.9900000095

, что является хорошим аккуратным O (n ^ 2).Последний занимает 1 ГБ памяти, поэтому списки (8000) перебивают жесткий диск и приводят к неправильной работе моей машины.Вероятно, delnan прав, и я бы проверил свободную память вашего компьютера и потребление памяти python во время операции.

...