Bug 66418 - Optimize set_intersection when one list is much smaller and the other has random access
Summary: Optimize set_intersection when one list is much smaller and the other has ran...
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 6.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks:
 
Reported: 2015-06-04 09:18 UTC by Marc Glisse
Modified: 2015-06-05 21:45 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2015-06-04 00:00:00

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Marc Glisse 2015-06-04 09:18:20 UTC 
Computing the intersection of sorted lists of size N1 and N2 is done in time N1+N2. When we have random access to the second list, it is also possible to search each element of the first list in the second one in time N1*log(N2), which is faster when N1 is much smaller than N2.
Comment 1 Marc Glisse 2015-06-04 20:57:45 UTC 
Two relevant links to optimize set_intersection (they consider the intersection of k sets, but the case k=2 is still interesting)

http://erikdemaine.org/papers/SODA2000/
http://erikdemaine.org/papers/ALENEX2001/

(I am sure there are many others)