Deque random acces O (n) в python, а O (1) в С++, почему?
С++ deque:
Случайный доступ - постоянный O (1)
Python deque:
Индексированный доступ - это O (1) с обоих концов, но замедляется до O (n) в середине.
Если я ничего не пропущу, все остальное будет одинаково быстро для deques в python и на С++, по крайней мере сложным. Есть ли что-то, что делает python лучше для некоторых случаев? Если нет, то почему бы им просто не переключиться на то, что С++ имеет?
Ответы
Ответ 1
Отказ от ответственности: этот ответ во многом вдохновлен комментарием Джеффа и ответом, уже опубликованным в Почему дека реализована как связанный список вместо кругового массива?
Ваш вопрос отличается по своей природе, но заголовок, приведенный выше, сам по себе является ответом: в Python модуль collection.deque имеет линейную временную сложность при доступе к элементам в середине, потому что он реализован с использованием связанного списка.
Из pydoc:
Список, подобный последовательности, оптимизированной для доступа к данным вблизи своих конечных точек.
Теперь, если вам интересно, почему была выбрана эта реализация, ответ уже доступен в сообщении, указанном Джеффом.
Ответ 2
Поскольку Deque - это структура данных, предназначенная для использования определенным образом, доступ к которой осуществляется первым или последним элементом,
Но python иногда делает странные вещи со своими структурами данных и добавляет к ним больше функций или использует составленные структуры данных
В этом случае python имеет функцию
remove(value)
#Remove the first occurrence of value. If not found, raises a ValueError.
это позволяет вам получить доступ к элементам структуры данных в середине deque, это не "основная" операция этой структуры данных,
вызывает "но замедляет O (n) в середине".
Поскольку в этом случае он ведет себя как массив (проверяя значения один за другим)
