Разница во времени выполнения для поиска «в» через «список» и «набор» с использованием Python
Мое понимание списка и набора в Python в основном состоит в том, что список допускает дублирование, список допускает упорядоченную информацию, а список содержит информацию о позициях. Я обнаружил, что когда пытался найти элемент в списке, время выполнения будет намного быстрее, если я сначала преобразую список в набор. Например, я написал код, пытающийся найти самую длинную последовательную последовательность в списке. В качестве примера используйте список от 0 до 10000, самая длинная последовательность — 10001. При использовании списка:
start_time = datetime.now()
nums = list(range(10000))
longest = 0
for number in nums:
if number - 1 not in nums:
length = 0
##Search if number + 1 also in the list##
while number + length in nums:
length += 1
longest = max(length, longest)
end_time = datetime.now()
timecost = 'Duration: {}'.format(end_time - start_time)
print(timecost)
Время выполнения приведенного выше кода: «Продолжительность: 0:00:01.481939». Добавив только одну строку, чтобы преобразовать список в третью строку ниже:
start_time = datetime.now()
nums = list(range(10000))
nums = set(nums)
longest = 0
for number in nums:
if number - 1 not in nums:
length = 0
##Search if number + 1 also in the set(was a list)##
while number + length in nums:
length += 1
longest = max(length, longest)
end_time = datetime.now()
timecost = 'Duration: {}'.format(end_time - start_time)
print(timecost)
Время выполнения приведенного выше кода с использованием набора теперь составляет «Продолжительность: 0:00:00.005138», что во много раз меньше, чем при поиске по списку. Может ли кто-нибудь помочь мне понять причину этого? Благодарю вас!
Ответы 1
Это большой вопрос.
Проблема с массивами заключается в том, что нет более разумного способа поиска в каком-либо массиве a, кроме простого сравнения каждого элемента по одному.
- Иногда вам повезет, и вы получите совпадение по первому элементу
a. - Иногда вам не повезет, и вы не найдете совпадения до последнего элемента
aили, возможно, вообще не найдете совпадения. - В среднем вам придется каждый раз искать половину элементов массива.
Говорят, что это имеет «временную сложность» O(len(a)) или, в просторечии, O(n). Это означает, что время, затрачиваемое алгоритмом (поиск значения в массиве), линейно зависит от размера входных данных (количества элементов в массиве, которые необходимо найти). Вот почему это называется «линейный поиск». О, ваш массив стал в 2 раза больше? Что ж, ваши поиски стали в 2 раза медленнее. в 1000 раз больше? в 1000 раз медленнее.
Массивы великолепны, но они ? для поиска, если количество элементов становится слишком большим.
Наборы хитрые. В Python они реализованы так, как если бы они были словарем с ключами и без значений. Как и словари, они поддерживаются структурой данных, называемой хеш-таблица.
Хеш-таблица использует хэш значения как быстрый способ получить «сводку» объекта. Эта «сводка» затем используется для сужения поиска, так что ему нужно только линейно искать очень небольшое подмножество всех элементов. Поиск в хеш-таблице временной сложности O(1). Обратите внимание, что здесь нет «n» или len(the_set). Это связано с тем, что время, затрачиваемое на поиск в хеш-таблице, не увеличивается с ростом размера хеш-таблицы. Итак, говорят, что он имеет постоянная временная сложность.
По аналогии, вы ищете молочный остров только тогда, когда ищете молоко. Вы знаете, что хеш-значение молока (скажем, это остров) «молочное», а не «гастроном», поэтому вам не нужно тратить время на поиск молока.
Естественный последующий вопрос: «Тогда почему мы не всегда используем наборы?». Ну, есть компромисс.
- Как вы упомянули, наборы не могут содержать дубликатов, поэтому, если вы хотите сохранить два элемента чего-либо, это не будет началом.
- До версии Python 3.7 они также были неупорядоченными, поэтому, если вас волнует порядок элементов, они тоже не подойдут. * Наборы обычно имеют большие накладные расходы процессора/памяти, которые складываются при использовании множества наборов, содержащих небольшое количество элементов.
- Кроме того, возможно что из-за причудливых функций ЦП (таких как кэши ЦП и ответвления предсказание), линейный поиск в небольших массивах на самом деле может быть Быстрее, чем поиск в наборах на основе хеша.
Я бы рекомендовал вам дополнительно изучить структуры данных и алгоритмы. Этот материал совершенно не зависит от языка. Теперь, когда вы знаете, что set и dict используют хэш-таблицу за кулисами, вы можете найти ресурс, который охватывает хеш-таблицы на любом языке, и это должно помочь. Также есть некоторые ресурсы, ориентированные на Python, например https://www.interviewcake.com/concept/python/hash-map.
Я бы не назвал "O(N)" разговорным языком. Это правильный способ выразить, как сложность ведет себя в бесконечности, иначе сложность поиска элемента в списке составляет О (длина (а) / 2) в среднем en.wikipedia.org/wiki/Big_O_notation.
@pavel Я бы хотел. Небрежный характер того, как определяется «n», делает людей склонными к тому, что Миа случайно сообщает о сложностях времени или сворачивает в него разрозненные переменные. Например, при поиске значения в квадратной матрице это будет O(n) (где n — общее количество элементов) или O(n^2) (где n — высота и ширина). Оба верны, но ни один из них не является более очевидным. Быть менее удобным и более явным, как O(w*h), полностью решает эту проблему.
Хотя «n» полезен при обобщении классов сложности или их абстрактном сравнении, например. на такие вопросы, как «что медленнее, O(n!) или O(2^n)?». Я утверждаю, что это не лучший способ говорить о том или ином конкретном алгоритме. Кстати O(len(a) / 2) и O(len(a)) эквивалентны. Постоянный коэффициент 2 отменяется, когда вы расширяете определение и вычисляете предел.
Я думаю, что для матриц стандартным способом измерения сложности является O(n*m) (который становится O(n^2) в случае квадратной матрицы) по той простой причине, что программный поиск элемента в матрице обычно представлены вложенными циклами for. Здесь O(n) было бы просто неправильным, поскольку обычно нет алгоритма, который вы могли бы реализовать, который будет масштабироваться на основе только одной переменной в этом случае.
Мне нравился твой ответ, пока я не добрался до ?, потому что он кажется таким… несовершеннолетним.
@pavel, вы иллюстрируете мою точку зрения, говоря «на основе одной переменной». Люди могут разумно не согласиться с тем, что мы называем переменной. Правильная временная сложность зависит от того, как вы определяете свою переменную. Если вы определяете «n» как «количество элементов в матрице», то линейный поиск в матрице — это O(n). Это может показаться надуманным, но большинство матричных математических библиотек размещают элементы многомерных матриц, используя один непрерывный массив элементов.
@martineau Думаю, важно не относиться к себе слишком серьезно ?. Я рад, что тебе это нравится
Но что касается компьютерных алгоритмов, O(n) в случае матрицы не имеет смысла. Матрицы имеют двойное индексирование, поэтому для перебора элементов матрицы необходимо перебирать оба индекса. Может быть, есть языки, где это не так, но в общем случае это так. И поскольку в этом контексте мы обязательно подразумеваем, что нотация big-O представляет сложность алгоритма, вы не можете на самом деле использовать O (n) (поскольку вы не можете просто получить доступ к n-му элементу матрицы) и вы не можете использовать это для обоснования своей позиции.
@pavel, пожалуйста, найдите любую популярную библиотеку матриц и посмотрите, как они реализуют поточечное сложение или сложение скаляра. Вы не найдете ни одного вложенного цикла. «Матрицы имеют двойное индексирование, поэтому для перебора элементов матрицы необходимо перебирать оба индекса». это верно на уровне пользовательского API, но абсолютно неверно для базовой структуры данных. Хорошо реализованная двумерная матрица использует один буфер, в котором хранятся все строки (или столбцы, если используется основной порядок столбцов) подряд, который может быть проиндексирован абсолютно одним индексом, и это так.
Чтобы уточнить, я имею в виду обобщенную многомерную матричную библиотеку, такую как структуры данных, которые поддерживают R или Matlab, а не какую-то конкретную 2D-реализацию матрицы.
Согласен, но я так понимаю, хоть значения и хранятся в виде непрерывного массива в памяти, но корректный доступ именно для матричных операций все равно требует внутреннего вычисления соответствующих индексов.
@pavel Это не так. Представьте, что у вас есть 2D-матрица 3x3, и вы добавляете ее к другой 2D-матрице 3x3. Вы мог реализуете его с 2 вложенными for циклами. Но это было бы излишне неуниверсальным (что, если я хочу матрицу 1D, матрицу 3D или матрицу 100 000D?). Вы можете приложить усилия, чтобы (i, j) было равно (0, 0), (0, 1), (0, 2), тогда (1, 0) ... (2, 2). Но зачем беспокоиться? Когда дело доходит до нахождения адреса памяти каждого элемента, вы в конечном итоге делаете index = base_pointer + i * matrix_with + j... в конце концов это сводится к 1 числу, от 0 до 8.
@pavel Нет смысла поддерживать 2 счетчика циклов, только чтобы в конечном итоге свести их с помощью математики индексов в один индекс в вашем буфере. Вам лучше просто зацикливаться на 1-м измерении и выполнять поэлементное сложение, как если бы у вас было два 9-элементных 1D-массива.
Я не знал этих подробностей. Хорошая дискуссия, спасибо!
Давайте продолжить обсуждение в чате.
Да, вычислительная сложность поиска элемента в наборе равна O(1), т.е. это примерно постоянное время и не зависит от размера набора. С другой стороны, поиск элемента в списке в среднем занимает O(n), поэтому требуемое время растет линейно с размером списка. Я считаю, что основная причина заключается в том, что наборы хэшируются, подобно тому, как поиск по ключам словаря также является сложностью O (1).