在列表（或其他数据结构）中有效地插入多个元素以保持其顺序

Question

我有一个应该依次插入到类似列表的数据结构中的项目列表，并且我有每个项目应该插入的索引。例如：

items = ['itemX', 'itemY', 'itemZ']
indexes = [0, 0, 1]

预期的结果是有一个像这样的列表：result = ['itemY', 'itemZ', 'itemX'].

我可以通过这种简单的方法得到这个结果：

result = []
for index, item in zip(indexes, items):
    result.insert(index, item)

但是，一旦列表变大（复杂度为 O(n^2)），这是一种非常缓慢的方法。有什么（实施起来相对简单的）方法可以改进我的基本方法吗？我想我必须在插入元素时查看其他数据结构，并最终将该数据结构转换为我的 result 列表。树木是一个好的选择吗？插入可能在 O(log(n)) 中完成（而不是 O(n)），但我应该使用哪种特定的树状结构？

或者通过一起查看所有索引（而不是一个一个地使用它们）可能会取得一些好处。

这可能是我缓慢方法的最坏情况（总是在列表的开头插入项目）：

n = 10**6 # some large number
items = list(range(n))
indexes = [0] * n

Answer 1

这里是 python 带有大小装饰的 treap 代码，允许在特定索引处插入，并对整个连续部分重新排序。它改编自 C++ 代码，Kimiyuki Onaka 对 Hackerrank 问题的解决方案，"Give Me the Order." (I cannot guarantee that this adaptation is bug free -- a copy of the original code is available in the description of 。）

import random

class Treap:
  def __init__(self, value=None):
    self.value = value
    self.key = random.random()
    self.size = 1
    self.left = None
    self.right = None


def size(t):
  return t.size if t else 0


def update(t):
  if t:
    t.size = 1 + size(t.left) + size(t.right)
  return t


def merge(a, b):
  if not a:
    return b
  if not b:
    return a

  if a.key > b.key:
    a.right = merge(a.right, b)
    return update(a)
  else:
    b.left = merge(a, b.left)
    return update(b)


def split(t, i):
  if not t:
    return None, None

  if i <= size(t.left):
    u, t.left = split(t.left, i)
    return u, update(t)
  else:
    t.right, u = split(t.right, i - size(t.left) - 1)
    return update(t), u


def insert(t, i, value):
  left, right = split(t, i)
  u = Treap(value)
  return merge(merge(left, u), right)


def inorder(treap):
  if not treap:
    return

  if treap.left:
    inorder(treap.left)

  print(treap.value)

  if treap.right:
    inorder(treap.right)

输出：

lst = ['itemX', 'itemY', 'itemZ']
idxs = [0, 0, 1]

t = None

for i in range(len(lst)):
  t = insert(t, idxs[i], lst[i])

inorder(t)

"""
itemY
itemZ
itemX
"""

Answer 2

您可以使用 SortedList，用常量键函数中和它的排序，并且只将它用于快速插入。需要 1.5.10 或更早版本，因为 insert 已被删除。

def insertions(indexes, items):
    tmp = SortedList(key=lambda _: 0)
    for index, item in zip(indexes, items):
        tmp.insert(index, item)
    return list(tmp)

（我想也有类似的东西但是没有排序需要中和，sortedcontainers 只是我知道的。）

基准测试结果：

               indexes =   [0] * 10**6     [randint(0, i) for i in range(10**6)]
--------------------------------------------------------------------------------
original                  1540 seconds     759 seconds
neutralized SortedList      13 seconds      31 seconds
sorted mediants            201 seconds     249 seconds
sorted mediants optimized   42 seconds      72 seconds

最后两个解决方案是另一个想法：

按正常方式使用 SortedList，但用 0 到 1 之间的分数注释每个项目（并以此排序）。要在两个项目之间插入，请使用这些项目的 mediant.

from sortedcontainers import SortedList
from fractions import Fraction

def insertions(indexes, items):
    xs = SortedList([(Fraction(0), None), (Fraction(1), None)])
    for index, item in zip(indexes, items):
        a, c = xs[index][0].as_integer_ratio()
        b, d = xs[index + 1][0].as_integer_ratio()
        xs.add((Fraction(a+b, c+d), item))
    return [item for _, item in xs[1:-1]]

优化版自己做分数：

from sortedcontainers import SortedList

class X(tuple):
    def __lt__(self, other):
        return self[0] * other[1] < self[1] * other[0]

def insertions(indexes, items):
    xs = SortedList([X((0, 1, None)), X((1, 1, None))])
    for index, item in zip(indexes, items):
        L, R = xs[index : index+2]
        xs.add(X((L[0] + R[0], L[1] + R[1], item)))
    return [x[2] for x in xs[1:-1]]

在列表（或其他数据结构）中有效地插入多个元素以保持其顺序

Efficiently insert multiple elements in a list (or another data structure) keeping their order

python

algorithm

data-structures

python-3.x