package sortedseq_intersect
A divide-and-conquer algorithm in OCaml for the intersection of sorted sequences
Install
Dune Dependency
Authors
Maintainers
Sources
v0.1.0.tar.gz
md5=57f23144c9ac13ff526c21d59b3e1a21
sha512=e124cfbb04db5a0f26e81c4c824c58a9ea4a11670ded7380065d316e79887f6b3494210cbfc406bf8b825c269512106a080e39b2575231ae8fa97b9ec9a79c81
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)
Published: 04 May 2022
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.
sectionYPositions = computeSectionYPositions($el), 10)"
x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)"
>
On This Page