README for pts_lbsearch ^^^^^^^^^^^^^^^^^^^^^^^ pts_lbsearch is a fast binary search in a line-sorted text file. It finds and prints lines within a given range or with a given prefix. It works even if lines have variable length. pts_lbsearch is written in C, it is optimized for speed and it is using buffering and cache to avoid unnecessary read(2)s and lseek(2)s. It also has a very small, constant memory footprint: barely larger than the read buffer (8KB by default). Send donations to the author of pts-line-bisect: https://flattr.com/submit/auto?user_id=pts&url=https://github.com/pts/pts-line-bisect pts_lbsearch gives correct results only if the bytes of the input file are sorted lexicographically. Use LC_ALL=C to get 8-bit, bytewise, locale-independent sort(1): $ LC_ALL=C sort file.sorted Prefix search: print all lines starting with foo, sorted: $ pts_lbsearch -p file.sorted foo Prefix search: print all lines starting with foo, sorted, but ignore the last incomplete line (if any): $ pts_lbsearch -pi file.sorted foo Prefix range search: print all lines starting with bar or foo or between: $ pts_lbsearch -p file.sorted bar foo Closed ended interval search: print all lines at least foo and at most bar: $ pts_lbsearch -t file.sorted bar foo Open ended interval search: print all lines at least foo and smaller than bar: $ pts_lbsearch -e file.sorted bar foo Prefix detection: exit(0) iff a line starting with foo is present: $ pts_lbsearch -qp file.sorted foo Exact detection: exit(0) iff a line equals to foo is present: $ pts_lbsearch -qt file.sorted foo Prepend position: print the smallest offset where foo can be inserted (please note that this does not report whether foo is present, always exit(0)). $ pts_lbsearch -oe file.sorted foo Append position: print the largest offset where foo can be inserted (please note that this does not report whether foo is present, always exit(0), also you may need to append a '\n' before appending foo at EOF). $ pts_lbsearch -oae file.sorted foo Prefix range: print the range (start byte offset and after-the-last-byte end offset) of lines starting with foo: $ pts_lbsearch -op file.sorted foo Exact range: print the range (start byte offset and after-the-last-byte end offset) of lines containing only foo: $ pts_lbsearch -ot file.sorted foo See http://pts.github.io/pts-line-bisect/line_bisect_evolution.html for a detailed article about the design and analysis of the algorithms pts_lbsearch implements. pts_lbsearch supports only '\n' as the line separator. '\r' is treated as a regular character within the line. pts_lbsearch supports incomplete lines at the end of the input. When printing them, it never adds a '\n' to the end if there wasn't one. To make it ignore the incomplete last line (possibly because an other, slow process has not finished writing it), pass the `-i' flag. If the input is not sorted, pts_lbsearch may print incorrect lines or offsets (can be more or less than expected). But it wouldn't crash or fall to an infinite loop. pts_lbsearch works for large files (i.e. larger than 2GB) correctly. Please note that a lookup in a btree or hash index is usually faster than a binary search, beause btree and hash need much fewer disk seeks because of the large branching factor. So if you can afford to build an index, there are faster lookup solutions than binary search. But if indeed you want binary search on variable-length records, most probably pts_lbsearch is the fastest. Python implementation ~~~~~~~~~~~~~~~~~~~~~ There is a Python implementation in the file pts_line_bisect.py. Differences in the C and Python implementations: * The C implementation is much faster, because avoids lseek(2) and read(2) calls as much as possible, while the Python implementation doesn't, because in Python the `file' object discards the read buffer after each file.seek. * The Python implementation is more compact, contains more comments, and it is easier to understand, to reuse as a library and to extend. * The C implementation has a more versatile command-line interface. The Python implementation supports flags -etco only. * The Python implementation has unit tests. * The C implementation supports prefix search (CM_LP). * The C equivalent of bisect_interval does a CM_LE search and then a CM_LT for the rest. This is faster if the result interval is a short range near the end of the file. * The C implementation has a very small memory footprint: only dozens of offsets and flags in addition to a single file read buffer (of 8KB by default). * The C implementation doesn't do any dynamic memory allocation (except possibly by the printfs generating messages), it's so lightweight and so low-overhead that it can be used in memory-constrained environments such as routers. __EOF__