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.
Respuestas
¿Demasiados anuncios?
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.
Voo
Puntos
11981
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.
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.
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.)
