package sortedseq_intersect

  1. Overview
  2. Docs
A divide-and-conquer algorithm to intersect sorted sequences

Install

Dune Dependency

github.com Readme MIT License Edit opam file Versions (2)

Authors

  1. F
    Fermin Reig

Maintainers

  1. F
    Fermin Reig

Sources

v0.2.0.tar.gz
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)

Published: 21 Jun 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.

Dependencies (2)

  1. dune >= "2.0.0"
  2. ocaml >= "4.08.0"

Dev Dependencies

None

Used by

None

Conflicts

None