Install
dune-project
Dependency
Authors
Maintainers
Sources
md5=4cb1652561ad66afe6aed5b4cce8842c
sha512=9936c3988dd5dcfca760fa08cd56f8c3ffd1d6b01408d9c5da3f2fc48454ca8de2f0d810ed954c841fe98ac053b611f7ed726d4c54cfe559d02082b9cc86445d
Description
The algorithm is described in this paper:
Fast Intersection Algorithms for Sorted Sequences Ricardo Baeza-Yates and Alejandro Salinger Algorithms and Applications 2010 (LNCS 6060, pp. 45–61)
README
sortedseq_intersect
A divide-and-conquer algorithm in OCaml for the intersection of sorted sequences. The algorithm is described in this paper:
Complexity is O(m log(n/m)), where m,n are the sizes of the sequences. If m is o(n/log n), this algorithm is better than linear merging, which is O(m+n). On the other hand, if m << n, it's better to do m binary searches. An adaptive version of the algorithm further improves the performance on average by switching from divide-and-conquer to linear merge based on the sizes of the sequences.
Dev Dependencies
None
Optional Dependencies
None
Used by
None
Conflicts
None
Build status
Results of building sortedseq_intersect with each compiler on check.ci.ocaml.org, run of against opam-repository 78c202b. All results for this package.
Each result links to its build log. To keep crawlers from overloading the site, build logs require a GitHub sign-in (see ocurrent/opam-health-check). On your first log, GitHub asks you to “Authorize opam-health-check”, the OCurrent app that runs these checks; it sees only your public profile, not your repositories. The sign-in lasts 30 days.
| Version | OCaml 4.11 | OCaml 4.14 | OCaml 5.2 | OCaml 5.4 | OCaml 5.5 |
|---|---|---|---|---|---|
| 0.2.0 (this version) | good | good | good | good | good |
- good Package successfully built
- partial One of the dependencies failed to build
- bad Package failed to build
- n/a Package is not available in this environment
- internal Internal failure