41 votos

Java combinación de 2 colecciones en O(1)

Tengo que ser capaz de combinar 2 grandes colecciones en 1. Que tipo de colección que puedo utilizar de la mejor manera? No necesito de acceso aleatorio a los elementos individuales. Por lo general, yo iría a por una linkedlist, sin embargo no puedo fusionar 2 linkedlist en Java con un tiempo de ejecución de O(1), lo que podría ser hecho en muchos otros idiomas, ya que voy a tener que copiar cada elemento de la nueva lista.

Edit: Gracias por todas tus respuestas. Sus respuestas fueron muy útiles, y me las arreglé para conseguir el trabajo hecho. La próxima vez voy a usar mi propia implementación de una lista enlazada, para empezar.

59voto

ColinD Puntos 48573

Usted puede crear un concatenados Iterable ver en O(1) uso de la Guayaba's Iterables.concat métodos:

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

Esto permitirá que usted para iterar sobre todos los elementos de ambas listas como un objeto sin la copia de alguno de los elementos.

12voto

Voo Puntos 11981

La solución más simple aquí es una Lista de Listas. Significa que usted necesita algunas de las sencillas funciones de contenedor, pero nada complicado.

10voto

hvgotcodes Puntos 55375

En teoría, usted puede combinar 2 listas enlazadas O(1), ya que todo lo que tiene que hacer es apuntar el último nodo de la primera en el primer nodo de la segunda (suponiendo que esas referencias).

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

No creo que hay alguna de las colecciones que se combinan en O(n). Usted podría tener que rodar sus propios.

3voto

yshavit Puntos 15028

Creo que su mejor mejor sería crear una aplicación de la Lista que toma una Lista> como sus argumentos, y entonces los delegados. En otras palabras, tener una lista de listas, y el alambre de arriba a actuar como una lista. Cuando se pasa de los elementos de la lista 1, de empezar a buscar en la lista 2.

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

2voto

Kevin Reid Puntos 8806

Si usted sólo quiere tener colecciones de objetos y combinarlos en O(1) vez, y no me importa que la implementación de su propia estructura de datos, entonces la manera más sencilla de hacer esto es utilizar un desequilibrio en el árbol binario: cada nodo es una hoja (para almacenar un valor) o la combinación de los dos árboles, y sólo se puede implementar estas dos clases con un resumen de la superclase o interfaz. Una profundidad de recorrido puede ser utilizado para extraer los elementos.

Este es esencialmente el mismo como ColinD la sugerencia de iterador de concatenación, pero más escueto.

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

No importa el anterior. Bajo este esquema, cada mezcla se agrega al menos un elemento, por lo que m < n y por lo que la iteración costo sigue siendo O(n). (Si usted hace uso de iterador de concatenación, asegúrese de que usted no está con frecuencia la concatenación de vacío iteradores como que habría que agregar el costo.)

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X