Java fusionar 2 colecciones en O (1)

Question

Necesito poder combinar dos colecciones grandes en 1. ¿Qué tipo de colección puedo usar mejor? No necesito acceso aleatorio a los elementos individuales. Por lo general, elegiría una lista de enlaces; sin embargo, no puedo fusionar 2 listas enlazadas en Java con un tiempo de ejecución de O (1), lo que podría hacerse en muchos otros idiomas, ya que tendré que copiar cada elemento a la nueva lista. .

Editar: Gracias por todas sus respuestas. Sus respuestas fueron muy útiles y logré hacer el trabajo. La próxima vez usaré mi propia implementación de una lista vinculada para comenzar.

Answer 1

Se puede crear un Iterable vista concatenados en O (1) usando uno de Iterables.concat métodos Guava 's:

Iterable<T> combined = Iterables.concat(list1, list2); 

Esto le permitirá iterar sobre todos los elementos de ambas listas como un objeto sin copiar cualquier elemento

Answer 2

En teoría, puede unir 2 listas enlazadas en O (1), ya que todo lo que tiene que hacer es señalar el último nodo del primero al primer nodo del segundo (suponiendo que tenga esas referencias).

El método de recolección addAll parece implicar un tiempo de ejecución de O (n), ya que están hablando de iteradores. Los detalles pueden ser específicos de JVM ...

No creo que haya ninguna colección que se combine en O (n). Puede que tengas que hacer tu propio.

Answer 3

La solución más simple aquí realmente es una lista de listas. Significa que necesita algunas funciones de contenedor simples, pero nada complicado.

Answer 4

Creo que lo mejor que puede hacer es crear una implementación de Lista que tome una Lista> como sus argumentos, y luego delegue. En otras palabras, tenga una lista de listas y conéctelas para que actúen como una lista. Cuando pasas los elementos de la lista 1, empiezas a buscar en la lista 2.

Por alguna razón, pensé que la guayaba tenía esa lista. Pero no puedo encontrarlo en sus javadocs.

Answer 5

La fusión de listas vinculadas es de hecho O (1), y puede considerar las listas basadas en matrices de la misma manera, es decir, tener varios Objetos [] vinculados entre sí.

Existen implementaciones de lo anterior, es más rápido que ArrayList al quitar/insertar desde el medio/inicio. Y la iteración es prácticamente la misma. Sin embargo, el acceso aleatorio puede ser un poco más lento.

Answer 6

Quería sugerir la clase CompositeCollection de apache.commons, pero mirando el source code esto también se ejecuta en O (n). Si solo necesita iterar sobre los elementos y no desea usar Google Collections como sugiere ColinD, puede crear fácilmente su propio iterador compuesto, p.

public class CompositeCollectionIterator<T> implements Iterator<T>{ 

    private Iterator<T>[] iterators; 
    private int currentIteratorIndex = 0; 
    public CompositeCollectionIterator(Collection<T>... aCollections) { 
    iterators = new Iterator[ aCollections.length]; 
    for (int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++) { 
     Collection<T> collection = aCollections[ i ]; 
     iterators[i] = collection.iterator(); 
    } 
    } 

    public boolean hasNext() { 
    if (iterators[currentIteratorIndex].hasNext()) return true; 
    else if (currentIteratorIndex < iterators.length - 1){ 
     currentIteratorIndex++; 
     return hasNext(); 
    } 
    return false; 
    } 

    public T next() { 
    return iterators[currentIteratorIndex].next(); 
    } 

    public void remove() { 
    iterators[currentIteratorIndex].remove(); 
    } 
} 

Answer 7

Si simplemente quieren tener colecciones de objetos y unirlos en O (1) tiempo, y no les importa la implementación de su propia estructura de datos, entonces la forma más sencilla de hacer esto es utilizar una árbol binario desequilibrado: cada nodo es una hoja (que almacena un valor) o la combinación de dos árboles, y puede implementarlos como dos clases con una superclase o interfaz abstracta. Se puede usar un recorrido transversal en profundidad para extraer los elementos.

Esto es esencialmente lo mismo que la sugerencia de ColinD de concatenación de iterador, pero más escueto.

El problema es que la iteración en esta colección no ser O (n )! Será O ( n + m) donde m es el número de fusiones que ha realizado (dado que cada uno es un nodo a atravesar). Esto es cierto tanto de mi solución como de ColinD. No sé si es cierto para todas las posibles soluciones a este problema.

No importa lo anterior. Bajo este esquema, cada fusión agrega al menos un elemento, entonces m < n y por lo tanto el costo de la iteración sigue siendo O (n). (Si usted hace uso de la concatenación iterador, asegúrese de que usted no está con frecuencia concatenando iteradores vacías como que añadiría costes.)

Answer 8

Mediante el uso de dos listas enlazadas como sus colecciones, y almacenar punteros a la primera último elemento de y cada lista (ambos indicadores posiblemente necesitarían actualizarse al agregar/eliminar elementos), puede fusionar ambas listas en O (1) - simplemente conecte el último elemento de la primera lista al primer elemento de la segunda lista, y ajuste el primero/último punteros en consecuencia.

Me temo que había necesidad de rodar su propia implementación de listas enlazadas en Java, ya que no tiene acceso directo a los nodos subyacentes de LinkedList, y por lo tanto no se puede conectar el último elemento de la primera lista para el primer elemento de la segunda lista.

Afortunadamente, es fácil encontrar implementaciones de listas enlazadas en Java, ya que es un tema muy común en los cursos de estructura de datos. Por ejemplo, here es uno, lo sé, los nombres están en español, pero el código en ListaEncadenada ("LinkedList") y NodoLista ("ListNode") es bastante simple y debe explicarse por sí mismo, y lo más importante: la implementación contiene apunta al primer y último elemento de la lista, y se puede modificar fácilmente para adaptarlo a sus necesidades.