Fusion de Java 2 collections en O (1)

Question

J'ai besoin d'être en mesure de fusionner 2 grandes collections en 1. Qui type de collection puis-je utiliser le mieux? Je n'ai pas besoin d'un accès aléatoire à des éléments individuels. Habituellement, j'irais pour une linkedlist, cependant je ne peux pas fusionner 2 linkedlist en Java avec un temps d'exécution de O(1), ce qui pourrait être fait dans de nombreuses autres langues, puisque je vais avoir à copier chaque élément de la nouvelle liste.

Edit: Merci pour toutes vos réponses. Vos réponses ont été très utiles, et j'ai réussi à obtenir le travail fait. La prochaine fois je vais utiliser mon propre mise en œuvre d'une liste chaînée pour commencer.

Answer 1

Vous pouvez créer un concaténées Iterable vue en O(1) à l'aide de l'un de Goyave's Iterables.concat méthodes:

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

Cela vous permettra de parcourir tous les éléments de deux listes comme un objet sans avoir à copier les éléments.

Answer 2

La solution la plus simple ici est vraiment une Liste de Listes. Signifie que vous avez besoin d'un simple wrapper fonctions, mais rien de compliqué.

Answer 3

En théorie, vous pouvez fusionner les 2 listes de O(1), puisque tout ce que vous avez à faire est de pointer le dernier nœud de la première dans le premier nœud de la deuxième (en supposant que vous avez ces références).

L' addAll méthode de collecte semble impliquer un temps d'exécution de O(n), puisqu'ils parlent des itérateurs. Les détails pourraient être JVM spécifiques...

Je ne pense pas qu'il existe des collections qui combinent en O(n). Vous pourriez avoir à rouler votre propre.

Answer 4

Je pense que votre meilleur, le mieux serait de créer une mise en œuvre de la Liste qui prend une Liste> comme arguments, et puis les délégués. En d'autres termes, avoir une liste de listes, et les fils dans une liste. Lorsque vous passez devant les éléments de la liste 1, vous commencez à regarder la liste 2.

Pour une raison quelconque, j'ai pensé à la goyave avait une telle liste. Mais je ne le trouve pas dans leur documentation javadoc.

Answer 5

Si vous avez juste envie d'avoir des collections d'objets et de les fusionner en O(1) temps, et ne pas l'esprit de la mise en œuvre de votre propre structure de données, alors le moyen le plus simple pour ce faire est d'utiliser un déséquilibré arbre binaire: chaque nœud est soit une feuille (de stocker une valeur) ou la combinaison des deux arbres, et vous pouvez mettre en œuvre ces deux classes avec une super-classe abstraite ou une interface. Profondeur d'abord la traversée peut être utilisé pour extraire les éléments.

C'est essentiellement le même que ColinD la suggestion de l'itérateur de concaténation, mais plus de bare-bones.

Le hic, c'est que de parcourir cette collection va pas être O(n)! Il sera en O(n + m) où m est le nombre de fusions que vous avez effectué (chacun étant un nœud à traverser). C'est le cas de ma solution et ColinD de l'. Je ne sais pas si c'est vrai pour toutes les solutions possibles à ce problème.

Jamais l'esprit ci-dessus. En vertu de ce régime, chaque fusion ajoute au moins un élément, de sorte que m < n et donc l'itération coût est toujours en O(n). (Si vous ne l'utilisez itérateur de concaténation, assurez-vous que vous n'êtes pas souvent la concaténation de vide itérateurs comme qui permettrait d'ajouter le coût).