Java: SortedSet itérateur "cursor" -style

J'ai besoin d'itérer à la fois vers l'avant et vers l'arrière dans un ensemble trié. Si j'utilise NavigableSet, j'obtiens un itérateur strictement vers l'avant et un itérateur strictement vers l'arrière (iterator() et descendingIterator()) mais aucun qui peut avancer et reculer. Quelle est la complexité temporelle de NavigableSet.lower() et higher()? Je peux les utiliser à la place, mais je suis réticent à le faire s'ils sont inefficaces.Java: SortedSet itérateur "cursor" -style

Source

2010-07-16 Jason S

Avez-vous (temps) testé les alternatives avec un jeu de données représentatif? – matiasf

vous avez un point - si vous devez optimiser, vous devez être prêt à mesurer - mais c'est pourquoi j'ai demandé ici, pour gagner la sagesse de ceux d'entre vous qui sont plus expérimentés. (pour ne pas mentionner cela devrait être dans la documentation mais n'est pas .grrrr.) –

Il n'y a que deux implémentations de NavigableSet. Dire que vous avez opté pour le TreeSet, alors que je n'ai pas la source à portée de main, le Javadoc dit qu'il est basé sur un TreeMap providing O(log(n)) for get/put/containsKey/remove. Au pire, cela permettrait d'obtenir une valeur pour trouver la valeur inférieure/supérieure pour, plus une recherche supplémentaire pour obtenir la valeur suivante/précédente, en fournissant O (2log (n)) = O (log (n)) .

Les arbres sont le cas le plus défavorable O (n) pour la recherche dans le cas où il s'agit réellement d'une liste, mais en général, O (hauteur).

Source

2010-07-16 21:56:37 apiri

y a-t-il des arbres qui sont plus rapides pour l'itération entre les éléments adjacents? –

C'est un compromis entre les opérations. Cela dépend de la taille de 'n'. Pour un arbre, get est 'O (log n)' et l'itération est aussi 'O (log n)'. En utilisant un tableau/liste trié, get est 'O (n)' et l'itération est 'O (1)'. – Andy

ok, merci. Je suis assez sûr que SkipLists a O (log n) obtenir, et O (1) itération. –

En fonction de vos besoins exacts, vous pouvez convertir l'ensemble trié en liste, indiquer une liste de matrices et utiliser un list iterator pour la traversée. Il peut être utilisé dans les deux sens via les méthodes next() et previous(), qui peuvent être mélangées librement.

Source

2010-07-16 22:12:02 starblue

Ceci est un bon point, et une meilleure description de l'utilisation serait utile. Cependant, au moins aussi loin que ceux fournis avec l'API Java, les seules options pour SortedSet (TreeSet, ConcurrentSkipListSet) sont aussi NavigableSets. Donc, il y aurait juste le temps supplémentaire de convertir en une liste, et ensuite la procédure spécifiée par Andy dans le commentaire de ma réponse. – apiri

Java: SortedSet itérateur "cursor" -style

Répondre

Questions connexes