Самая быстрая структура данных, чтобы вернуть последовательность элементов в порядке

Question

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

Я пытался использовать dict для сопоставления всех входных данных с предполагаемыми решениями.

class DictSolution():
    DATA = {x:x for x in range(1000000)}

    def compute(self, x):
        return self.DATA[x]

Затем я подумал, поскольку знаю, в каком порядкевходы будут проверены, мне не нужно «искать это».Поэтому я попытался использовать set и игнорировать все входные данные.

class SetSolution():
    DATA = {i for i in range(1000000)}

    def compute(self, x):
        return self.DATA.pop()

К моему удивлению, это было немного медленнее, чем dict, каждый раз на 1-2% медленнее.Кстати, вот как я их рассчитываю.

def test_dict():
    sol = DictSolution()
    for i in range(1000000):
        sol.compute(i

ds = timeit.timeit(test_dict, number=1)
ss = timeit.timeit(test_set,  number=1)
print ("Dict Solution:", ds)
print ("Set  Solution:", ss)

>> Dict Solution: 0.11734077199999998
>> Set  Solution: 0.11939082499999998

Вопросы:

1. Почему set медленнее?
2. Логически говоря, возвращать что-то по порядку должно быть быстрее, чем искать это в таблице.Поэтому я не верю, что путь dict - самый быстрый.Что я могу сделать, чтобы добиться лучшего времени?

Answer 1

Я считаю, что предложение @schwobaseggl верно.Начиная с здесь , сложность доступа к элементу равна O(1) для dict и list, это было несколько повторено в этом вопросе , фактически в предыдущей настройке list был чуть быстрее, чем dict.Я повторил ваш тест и добавил другие структуры данных, в полном объеме:

• Список
• Словарь
• Установить (используя pop)
• Deque (из коллекции)
• Кортеж

Код:

import timeit
from collections import deque


class DictSolution:
    DATA = {x: x for x in range(1000000)}

    def compute(self, x):
        return self.DATA[x]


class SetSolution:
    DATA = {i for i in range(1000000)}

    def compute(self, x):
        return self.DATA.pop()


class DequeSolution:
    DATA = deque(i for i in range(1000000))

    def compute(self, x):
        return self.DATA.popleft()


class ListSolution:
    DATA = [i for i in range(1000000)]

    def compute(self, x):
        return self.DATA[x]


class TupleSolution:
    DATA = tuple(i for i in range(1000000))

    def compute(self, x):
        return self.DATA[x]


def test_dict():
    sol = DictSolution()
    for i in range(1000000):
        sol.compute(i)


def test_set():
    sol = SetSolution()
    for i in range(1000000):
        sol.compute(i)


def test_deque():
    sol = DequeSolution()
    for i in range(1000000):
        sol.compute(i)


def test_list():
    sol = ListSolution()
    for i in range(1000000):
        sol.compute(i)


def test_tuple():
    sol = TupleSolution()
    for i in range(1000000):
        sol.compute(i)


def test_pop_list():
    sol = PopListSolution()
    for i in range(1000000):
        sol.compute(i)


des = timeit.timeit(test_deque, number=1)
ss = timeit.timeit(test_set, number=1)
ds = timeit.timeit(test_dict, number=1)
ls = timeit.timeit(test_list, number=1)
ts = timeit.timeit(test_tuple, number=1)
times = [("Dict Solution:", ds), ("Set Solution:", ss), ("Deque Solution:", des), ("List Solution:", ls), ("Tuple Solution:", ts)]

for label, time in sorted(times, key=lambda e: e[1]):
    print(label, time)

Вывод

Tuple Solution: 0.1597294129896909
List Solution: 0.16653884798870422
Dict Solution: 0.17414769899914972
Set Solution: 0.190879073983524
Deque Solution: 0.1914772919844836

Я запустилсценарий несколько раз, и результаты были похожи с решением кортеж и список решений, чередуя лид.Обратите внимание, что SetSolution и DequeSolution были самыми медленными.Итак, чтобы ответить на ваши вопросы:

1. И set, и deque медленнее, потому что вы удаляете элемент из списка, в других структурах вы получаете доступ только к элементам.
2. Это было частично дано в предыдущем ответе, pop не только возвращает элемент из структуры данных, но и удаляет элемент из него.Поэтому я ожидаю, что обновление структуры данных будет медленнее, чем доступ только к одному из ее элементов.

Примечания Хотя pop работает с set для тестав общем случае такое поведение не ожидается, например:

test = {'e' + str(i) for i in range(10)}
while test:
    print(test.pop())

Вывод (заданное значение)

e5
e8
e6
e0
e1
e3
e7
e4
e9
e2

Подробнее по этой теме можно найти здесь .

Я также протестировал решение, используя list.pop(0), хотя и с меньшим диапазоном: 100000 и меньшим количеством кандидатов (list, tuple и dict).Результаты были следующие:

('List Solution:', 0.018702030181884766)
('Tuple Solution:', 0.021403074264526367)
('Dict Solution:', 0.02230381965637207)
('List Pop Solution', 1.8658080101013184)

Тест был выполнен на следующей установке:

Intel(R) Core(TM) i7-4500U CPU @ 1.80GHz
16GB
Ubuntu 16.04
Python 3.5.2

Answer 2

DICT - самая быстрая структура данных поиска, потому что она реализована с использованием хеш-таблицы: для поиска ключа в хеш-таблице требуется почти постоянное время.Проверьте ссылку ниже для получения дополнительной информации:

Этот PDF из MIT объясняет тему