Каковы истинные временные сложности работы с сетами / диктами? - PullRequest
Новая
       84

Каковы истинные временные сложности работы с сетами / диктами?

2 голосов
/ 08 октября 2019

Фон

Я искал несколько способов сделать по существу одно и то же и хотел бы получить некоторую информацию о сложности времени и о том, верно ли это для питона вики или нет - и почему существуют общие различия в скорости. Я использую Python 3.7 для своих тестов (cpython).

Дополнительная информация о сложности времени здесь и здесь .

Тестируемый код 

import timeit

def test1():
    new_d = {}
    for i in range(0, 50000):
        new_d[i] = None

def test2():
    new_s = set()
    for i in range(0, 50000):
        new_s.add(i)

def test3():
    new_l = list(range(0, 50000))
    new_s = set(new_l)

def test3b():
    new_s = set(range(0, 50000))

def test4():
    new_l = list(range(0, 50000))
    new_d = dict.fromkeys(new_l)

def test4b():
    new_d = dict.fromkeys(range(0, 50000))

def test5():
    new_l = list(range(0, 50000))
    new_d = {key: None for key in new_l}

def test5b():
    new_d = {key: None for key in range(0, 50000)}

tests = [test1, test2, test3, test3b, test4, test4b, test5, test5b]
for test in tests:
    print(timeit.timeit(test, number=10000))

Рассуждение

Итак, выше приведены 5 способов сделать то, что кажется очень похожие операции. Идея, стоящая за ними, состоит в том, чтобы взять диапазон и добавить его к объекту хешированного типа (set или dict) для выполнения O (1) поиска.

test1 : Create a dict -> iterate range -> add to dict
test2 : Create a set -> iterate range -> add to set
test3 : List function on range -> [automatic] -> set function on list
test3b : . [automatic] -> [automatic] -> set function on range
test4 : List function on range -> [automatic] -> dict from keys on list
test4b : . [automatic] -> [automatic] -> dict from keys on range
test5 : List function on range -> [automatic] -> dict comprehension on list
test5b : . [automatic] -> [automatic] -> dict comprehension on range

Теперь для меня (не эксперта) общая логика всех этих 5 очень похожа, чтоитерировать диапазон и добавить в хеш-таблицу. Во всяком случае, я бы предположил, что test1 и test2 будут завершены раньше других, потому что они не создают список, а затем повторяют этот список (On * 2) и должны завершиться за одну итерацию.

Я бы также предположил, что каждая функция b будет быстрее, чем ее аналог, на величину O (n).

И, наконец, я бы предположил, что test1будет почти таким же, как test4b (и test4, test5 и test5b), test2 будет почти таким же, как test3b (и test3)

Результаты

Но, увы, я здесь, поэтому мои предположения неверны.

Методы: я тестировал на диапазонах 1000 (в среднем 3), 2000 (в среднем 3), 3000 (в среднем 3), 50000 (в среднем 2), 100000 (одиночный прогон) и все с timeit.timeit(number=10000). 

TOTAL TIME (truncated)
         test1      test2      test3      test3b     test4      test4b     test5      test5b
1000     0.5094     0.7135     0.2758     0.2377     0.3735     0.3424     0.5173     0.4591
2000     1.0769     1.4383     0.6109     0.5161     0.7880     0.7226     1.0211     0.9565
3000     1.7337     2.1061     0.8848     0.7470     1.3066     1.1763     1.6431     1.6390
50000   34.6455    37.0113    16.0184    19.6853    35.4731    32.4986    40.2696    41.2130
100000  84.9230    89.7245    55.3949    47.8195    82.1506    75.7063    94.4856    84.2978

ADJUSTED TIME PER 1000 (rounded)
         test1      test2      test3      test3b     test4      test4b     test5      test5b
1000     0.5094     0.7135     0.2758     0.2378    0.3736      0.3430     0.5174     0.4591
2000     0.5385     0.7192     0.3055     0.2581    0.3940      0.3613     0.5106     0.4783
3000     0.5779     0.7021     0.2950     0.249     0.4355      0.3921     0.5477     0.5464
50000    0.6929     0.7402     0.3204     0.3937    0.7095      0.6500     0.8054     0.8243
100000   0.8492     0.8972     0.5539     0.4782    0.8215      0.7571     0.9449     0.8430

Замечания и вопросы

Самый быстрый : test3bпочти всегда самый быстрый, сопровождаемый вскоре test3 (кроме 50 000)
Самый медленный : test2 самый медленный в небольших количествах, затем test5b при 50 000 и, наконец, test5 при 100 000

Скорость теста не изменяется линейно с изменением n, она растет выше, чем разница в n. Нормализовано до per 1000 Я ожидал увидеть гораздо более близкие числа. Я также ожидаю, что он достигнет максимума на 1000, а затем выровняется. Итак, как я уже признал, мои предположения и ожидания неверны.

Можете ли вы помочь мне с пониманием этого представления? Понятно, что test3b является самым быстрым методом на сегодняшний день, и что test2 работает плохо по сравнению, даже если они делают подобные вещи. Я полагаю, это связано с управлением памятью и выделением места для хеш-таблицы? Мой главный вопрос ... что здесь происходит и почему?

...