Java：SortedSet「光標」風格的迭代器

我需要在一個有序集合中向前和向後迭代。如果我使用NavigableSet，我得到一個嚴格向前迭代器和一個嚴格向後迭代器（iterator()和descendingIterator()），但沒有一個可以前進和後退。Java：SortedSet「光標」風格的迭代器

NavigableSet.lower()和higher()的時間複雜度是多少？我可以使用它們，但如果效率低下，我不願意這麼做。

來源

2010-07-16 Jason S

您是否（時間）用代表性數據集測試了替代方案？ – matiasf 2010-07-16 21:46:18

你有一點 - 如果你不得不優化，你應該準備好測量 - 但這就是爲什麼我在這裏問，從你那些更有經驗的人那裏獲得智慧。（更不用說它應該在文檔中，但不是。grrrr。） – 2010-07-16 21:49:46

NavigableSet只有兩個實現。說你選擇了TreeSet，雖然我沒有源代碼，Javadoc說它基於TreeMap providing O(log(n)) for get/put/containsKey/remove。在最糟糕的情況下，這將執行一個找到我們找到更低/更高值的值，再加上額外的搜索以獲得下一個/上一個值，提供O（2log（n））= O（log（n））。

樹是最壞的情況下O（n）的搜索事件，它實際上是一個列表，但一般來說，O（高度）。

來源

2010-07-16 21:56:37 apiri

是否有樹在相鄰元素之間迭代更快？ – 2010-07-16 22:03:53

這是操作之間的折衷。這取決於'n'的大小。對於一棵樹，get是'O（log n）'，迭代也是'O（log n）'。使用排序的數組/列表，get是'O（n）'，迭代是'O（1）'。 – Andy 2010-07-16 22:09:59

好的，謝謝。我非常肯定SkipLists有O（log n）get和O（1）迭代。 – 2010-07-16 22:47:29

根據您的確切需求，您可以將已排序的集合轉換爲列表（例如數組列表），並使用list iterator進行遍歷。它可以通過next()和previous()方法在兩個方向上使用，這些方法可以自由混合使用。

來源

2010-07-16 22:12:02 starblue

這是一個公平的觀點，更好地描述使用情況會有所幫助。但是，至少就與Java API捆綁在一起而言，SortedSet（TreeSet，ConcurrentSkipListSet）的唯一選項也是NavigableSets。所以只需要添加時間轉換爲列表，然後按照Andy在評論中指定的過程給我的答案。 – apiri 2010-07-16 22:16:51

Java：SortedSet「光標」風格的迭代器

回答

相關問題