https://issues.dlang.org/show_bug.cgi?id=12992

bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc

--- Comment #1 from bearophile_hugs@eml.cc ---
Interpolated search is nice, but it requires a knowledge of the distribution of the data. In general it's not easy to know it (and even if you know it, you need a give a lambda to the search function).

--

https://issues.dlang.org/show_bug.cgi?id=12992

--- Comment #2 from Andrei Alexandrescu <andrei@erdani.com> ---
(In reply to bearophile_hugs from comment #1)
> Interpolated search is nice, but it requires a knowledge of the distribution of the data.

That's why it's a policy chosen by the caller.

> In general it's not easy to know it (and even if you know it, you need a give a lambda to the search function).

If the element type is numeric no lambda is needed.

--

https://issues.dlang.org/show_bug.cgi?id=12992

--- Comment #3 from bearophile_hugs@eml.cc ---
(In reply to Andrei Alexandrescu from comment #2)

> If the element type is numeric no lambda is needed.

I don't agree or I don't understand. If you have an array of sorted integers with a uniform distribution you need a certain interpolating function. if your array of sorted integers has a squared distribution, you need a different interpolating function, otherwise your search is slower than a standard binary search. Unless the interpolated search performs a statistics on the data, the user has to supply in both cases some kind of function that specifies that distribution.

--

https://issues.dlang.org/show_bug.cgi?id=12992

--- Comment #4 from Andrei Alexandrescu <andrei@erdani.com> ---
(In reply to bearophile_hugs from comment #3)
> (In reply to Andrei Alexandrescu from comment #2)
> 
> > If the element type is numeric no lambda is needed.
> 
> I don't agree or I don't understand. If you have an array of sorted integers with a uniform distribution you need a certain interpolating function. if your array of sorted integers has a squared distribution, you need a different interpolating function, otherwise your search is slower than a standard binary search. Unless the interpolated search performs a statistics on the data, the user has to supply in both cases some kind of function that specifies that distribution.

I was thinking of supporting the uniform distribution assumption.

--

https://issues.dlang.org/show_bug.cgi?id=12992

--- Comment #5 from bearophile_hugs@eml.cc ---
(In reply to Andrei Alexandrescu from comment #4)

> I was thinking of supporting the uniform distribution assumption.

OK, then this strict assumption needs to be stated clearly in the docs.

--

https://issues.dlang.org/show_bug.cgi?id=12992

Iain Buclaw <ibuclaw@gdcproject.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P1                          |P4

--

https://issues.dlang.org/show_bug.cgi?id=12992

--- Comment #6 from dlangBugzillaToGithub <robert.schadek@posteo.de> ---
THIS ISSUE HAS BEEN MOVED TO GITHUB

https://github.com/dlang/phobos/issues/10065

DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB

--