Add a NavigableSet-specific implementation of Sets.intersection()

[GoogleCodeExporter]

(This issue was split out from issue #1083)

Rationale:

  Sets.intersection() suffers from the flaw that even if the intersection of two sets is empty, iterating their intersection takes time proportional to the size of first of the two sets given, no matter how small the second set is. Since often you won't know which set is smaller, this means you have a 50% chance of getting it badly wrong. 

  For two NavigableSets that use the same Comparator, there is a more efficient algorithm that iterates in O(N) queries, where N is the number of elements in the *smallest* of the two sets - no matter in which order they are presented.

  In common scenarios such as iterating through key/value ranges in large datasets, this can make a huge difference.

I have an implementation for this intersection iteration algorithm here: 
https://code.google.com/p/jsimpledb/source/browse/trunk/src/java/org/jsimpledb/u
til/IntersectionNavigableSet.java

Original issue reported on code.google.com by archie.c...@gmail.com on 16 Jul 2014 at 6:47

• Merged into: #368

[GoogleCodeExporter]

Sorry, typo: This issue was split out from  issue #1803, not issue #1083.

Original comment by archie.c...@gmail.com on 16 Jul 2014 at 6:48

[GoogleCodeExporter]

Original comment by lowas...@google.com on 16 Jul 2014 at 6:50

• Changed state: Duplicate

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<issue id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:08

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:07

• Added labels: Restrict-AddIssueComment-Commit