Tengo una lista de elementos que deben insertarse en una estructura de datos similar a una lista, uno tras otro, y tengo los índices en los que debe insertarse cada elemento. Por ejemplo:
items = ['itemX', 'itemY', 'itemZ'] indexes = [0, 0, 1] El resultado esperado es tener una lista como esta: result = ['itemY', 'itemZ', 'itemX'] .
Puedo obtener este resultado con este enfoque simple:
result = [] for index, item in zip(indexes, items): result.insert(index, item) Sin embargo, este es un enfoque muy lento una vez que las listas se vuelven enormes (la complejidad es O (n ^ 2)). ¿Hay alguna forma (relativamente simple de implementar) de mejorar mi enfoque básico? Supongo que tengo que mirar otras estructuras de datos mientras inserto elementos y finalmente transformo esa estructura de datos en mi lista de result . ¿Son los árboles una buena opción? La inserción podría hacerse tal vez en O (log (n)) (en lugar de O (n)), pero ¿qué estructura específica similar a un árbol debería usar?
O tal vez se pueda lograr algo bueno simplemente mirando todos los índices juntos (en lugar de usarlos uno por uno).
Este es probablemente el peor caso para mi enfoque lento (siempre inserte elementos al principio de la lista):
n = 10**6 # some large number items = list(range(n)) indexes = [0] * nAquí está el código de Python para un trep con una decoración de tamaño que permite la inserción en índices específicos y el reordenamiento de secciones contiguas completas. Fue adaptado del código C++, la solución de Kimiyuki Onaka al problema de Hackerrank, "Dame la orden". (No puedo garantizar que esta adaptación esté libre de errores; una copia del código original está disponible en la descripción de esta pregunta ).
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)Producción:
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 """Puede usarSortedList , neutralizar su clasificación con una función de tecla constante y solo usarlo para sus inserciones rápidas. Necesita la versión 1.5.10 o anterior, ya que se eliminó el insert .
def insertions(indexes, items): tmp = SortedList(key=lambda _: 0) for index, item in zip(indexes, items): tmp.insert(index, item) return list(tmp) (Me imagino que también hay algo así, pero sin clasificar eso debe neutralizarse, sortedcontainers es algo que conozco).
Resultados de referencia:
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 secondsEsas dos últimas soluciones son otra idea:
Use SortedList de la manera normal, pero anote cada elemento con una fracción de 0 a 1 (y ordene por eso). Para insertar entre dos elementos, use el medio de esos elementos.
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]]Versión optimizada haciendo fracciones yo mismo:
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]]