May 18, 2014 [Issue 12762] New: Missing documentation for std.range.SearchPolicy.linear | ||||
---|---|---|---|---|
| ||||
https://issues.dlang.org/show_bug.cgi?id=12762 Issue ID: 12762 Summary: Missing documentation for std.range.SearchPolicy.linear Product: D Version: D2 Hardware: All OS: All Status: NEW Severity: minor Priority: P1 Component: websites Assignee: nobody@puremagic.com Reporter: bearophile_hugs@eml.cc In this page: http://dlang.org/phobos/std_range.html#SearchPolicy The documentation about the enum std.range.SearchPolicy states: enum SearchPolicy: int; Policy used with the searching primitives lowerBound, upperBound, and equalRange of SortedRange below. trot Searches with a step that is grows linearly (1, 2, 3,...) leading to a quadratic search schedule (indexes tried are 0, 1, 3, 6, 10, 15, 21, 28,...) Once the search overshoots its target, the remaining interval is searched using binary search. The search is completed in ?(sqrt(n)) time. Use it when you are reasonably confident that the value is around the beginning of the range. gallop Performs a galloping search algorithm, i.e. searches with a step that doubles every time, (1, 2, 4, 8, ...) leading to an exponential search schedule (indexes tried are 0, 1, 3, 7, 15, 31, 63,...) Once the search overshoots its target, the remaining interval is searched using binary search. A value is found in ?(log(n)) time. But in the source code the enum contains a "linear" too: /** Policy used with the searching primitives $(D lowerBound), $(D upperBound), and $(D equalRange) of $(LREF SortedRange) below. */ enum SearchPolicy { /** Searches in a linear fashion. */ linear, /** Searches with a step that is grows linearly (1, 2, 3,...) leading to a quadratic search schedule (indexes tried are 0, 1, 3, 6, 10, 15, 21, 28,...) Once the search overshoots its target, the remaining interval is searched using binary search. The search is completed in $(BIGOH sqrt(n)) time. Use it when you are reasonably confident that the value is around the beginning of the range. */ trot, -- |
Copyright © 1999-2021 by the D Language Foundation