Словарь Итерационные скорости

Question

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

Я не был уверен, почему преподаватель сказал, что это не имеет значения, поскольку я считаю, что скорость является ключом к обработке больших наборов данных. Я прочитал и нашел очень полезный пост (Python: List vs Dict for look up table).

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

Чтобы перевести это в другой контекст - воспользуемся следующим примером: Скажем, что мы ищем цену кучу кешью в словаре, который содержит 10 000 записей. В этом случае, если записи были помещены случайным образом в словаре - будет ли скорость поиска этой записи «быстрее», если бы она была отсортирована, а не беспорядочно размещена в любом месте?

спасибо!

Answer 1

Чтобы поместить это более контекст - давайте использовать следующий пример: Скажем, мы ищем по цене кучи кешью в словаре , который имеет 10000 записей. В этом случае, если записи были помещены в случайным образом в словаре - будет ли скорость в поиске , что запись будет «быстрее», если бы она была отсортирована, а не беспорядочно размещена где угодно?

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

В словарях используется хэш-таблица для извлечения элементов ключом. Это означает, что неважно, в каком порядке хранятся элементы, потому что скорость/метод/функция поиска не зависят от порядка вставки.

Другими словами, когда у вас есть словарь d и вы делаете операцию, такие как:

print(d[some_key]) 

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

Answer 2

Чтобы добавить это в более конкретный контекст, давайте воспользуемся следующим примером: скажем, что мы ищем цену кучу кешью в словаре с 10 000 записей. В этом случае, если записи были помещены случайным образом в словаре - будет ли скорость поиска этой записи «быстрее», если бы она была отсортирована, а не беспорядочно размещена в любом месте?

Ну ... словари уже имеют сортировку, поскольку они являются hashtables. Разница в том, что они сортируются по их хешу, а не по самому ключу. Это означает, что, как только хеш был рассчитан, по существу ничего больше не может быть сделано для ускорения доступа. Приобретения можно найти в алгоритме хеширования, а не в самих элементах или структуре.