Слияние двух дел в O (1)

Question

Есть ли способ объединить два Python запроса в O(1)?

Двойные связанные списки можно объединить в O(1) и deque - реализация двойного связанного списка. Однако из документации я не вижу способа эффективно объединить два запроса. a.extend(b) и a += b, упомянутые в этого вопроса , фактически повторяются по всем элементам b, поэтому сложность по времени составляет O(len(b)), а не O(1).

Answer 1

Неа. deque не являются простыми двусвязными списками. Это связанный список блоков с несколькими значениями (в справочном интерпретаторе CPython каждый блок может содержать до 64 значений), где только начальный и конечный блоки могут быть неполными; ни один из блоков не может быть разреженным. Таким образом, он должен заполнить конечный блок с левой стороны, что означает, что следующий блок заполняется из смеси двух блоков, и т. Д. c.

Помимо этого, поскольку не существует такой вещи, как деструктивная итерация в Python (язык в любом случае не поддерживается), она не может фактически передавать блоки, даже если конечный блок слева и начальный блок справа были заполнены. Копии должны произойти, владение блоком не может быть передано.

Answer 2

Я публикую это как отдельный ответ, а не продолжаю беседовать в комментариях под Хороший ответ ShadowRanger . :)

ShadowRanger правильно указывает, что один из инвариантов deque состоит в том, что блоки в середине списка всегда заполнены на 100%. Следовательно, если бы у вас было два запроса типа

X = (. . . 1) (2 3 4 5) (6 7 . .)  [3 blocks, 7 elements]
Y = (8 9 A B) (C D E .)            [2 blocks, 7 elements]

, буквально не было бы возможности объединить их за O (1) время при сохранении порядка, потому что инвариант deque не позволяет вам express результат в виде

X+Y = (. . . 1) (2 3 4 5) (6 7 . .) (8 9 A B) (C D E .)  [invalid]

Вы бы имели , чтобы отрегулировать позиции всех элементов в одном или другом из deques, например, так:

X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .)  [adjusted elements 8 thru E]

или как это:

X+Y = (. 1 2 3) (4 5 6 7) (8 9 A B) (C D E .)  [adjusted elements 1 thru 7]

Это простые замены указателей, поэтому они быстрые; но их по-прежнему осталось O (n).

---

Однако предположим, что вы передаете два запроса, чьи выравнивания просто совпадают?

X = (. . . 1) (2 3 4 5) (6 7 . .)  [3 blocks, 7 elements]
Y = (. . 8 9) (A B C D) (E . . .)  [3 blocks, 7 elements]

X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .)  [can be done in O(1)]

Здесь, после добавления вручную предметы 8 и 9, физически возможно возможно похитить весь хвост правого deque в O (1). И deque может обнаружить эту возможность в O (1); и ручное добавление этих первых нескольких элементов занимает O(block size) = O (1). Так что да, физически возможно для объединения двух требований, которые будут реализованы за O (1) время, при особых обстоятельствах, которые не всегда выполняются.

Однако вы бы для вызова этой операции что-то отличное от x += y или x.extend(y). Эти две операции определены , чтобы не изменять их правый операнд . Стандарт deque от collections не предусматривает каких-либо «разрушительных» операций, подобных этому. (Но, если бы он существовал, я бы ожидал, что он будет назван splice.)

Вы можете увидеть реализацию оператора deque += (как реализовано в CPython ) здесь .