7
\$\begingroup\$

I recently discovered the exponential search algorithm which can be used to find whether a value exists in an ordered range. An exponential search checks whether a value is smaller than the \$2^n\$th element of the range, then if the searched value is indeed smaller, it performs a binary search in the range \$[2^n, 2^{n-1})\$ to check whether the value exists in this range, otherwise it starts again by comparing the value to the \$2^{n+1}\$th element, etc... Here is my implementation of the algorithm for random-access iterators (I coud make it work with forward iterators too but it has a cost):

#include <algorithm>
#include <functional>
#include <iterator>

template<
    typename Iterator,
    typename T,
    typename Compare = std::less<>
>
auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool
{
    using difference_type = typename std::iterator_traits<Iterator>::difference_type;

    difference_type size = std::distance(first, last);
    if (first == last) return false;

    difference_type bound = 1;
    while (bound < size && not compare(key, first[bound]))
    {
        bound *= 2;
    }

    auto end = first + std::min(bound, size);
    return std::binary_search(first + bound / 2, end, key, compare);
}

However, I remember while implementing this algorithm a nice property of the the binary search, exploited by the Ford-Johnson merge-insertion sort: searching a value in \$2^n\$ elements and in \$2^{n+1}-1\$ takes the same number of comparisons (e.g. binary search in collections of size \$16\$ and \$31\$ requires the same number of comparisons). Therefore I modified the algorithm so that it would always search in sequences whose size is \$2^n-1\$ to maximize its efficiency:

#include <algorithm>
#include <functional>
#include <iterator>

template<
    typename Iterator,
    typename T,
    typename Compare = std::less<>
>
auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool
{
    using difference_type = typename std::iterator_traits<Iterator>::difference_type;

    difference_type size = std::distance(first, last);
    if (first == last) return false;

    difference_type bound = 1;
    while (bound < size && not compare(key, first[bound]))
    {
        first += bound;
        size -= bound;
        bound = std::min((bound + 1) * 2 - 1, size);
    }

    return std::binary_search(first, first + bound, key, compare);
}

My tests show that it always perform at worst as many comparisons as the original version, and often less when looking for the same element in the same sequence (except when looking for the second element of the collection for some reason).

I know that the algorithm could be more efficient when equivalent values appear in the collection, but I didn't find any elegant way to solve this, even though three-way comparators could have been a nice solution.

Is there any way I can improve this algorithm, be it from a style, correctness or efficiency point of view?

\$\endgroup\$
  • \$\begingroup\$ Exponential search has no inherent advantages, it is just one of many ways of skewing the search order compared to binary search in order to take advantage of skewed input distributions (or anyway special properties of the input distribution). Interpolation search is another such example, but - unlike exponential search - it can often improve things with certain types of naturally occurring input. Exponential search has no such merits, and you won't see any improvement over binary search unless you feed it inputs that are tailored to its expected 'target profile'. \$\endgroup\$ – DarthGizka Feb 11 '16 at 21:41
2
\$\begingroup\$

Just a few miscellaneous comments about a few points:

template<
    typename Iterator,
    typename T,
    typename Compare = std::less<>
>

Rather than just Iterator, I'd rather see it given a name reflecting the (minimum) category of iterator expected. In this case, it looks like it probably only really makes sense for a random-access iterator, but I'm not entirely certain of that.

auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool

I realize some people like to use trailing return types (in general), but I'd prefer to see them reserved for times they're really needed. In a case like this, it just adds syntactic noise.

using difference_type = typename std::iterator_traits<Iterator>::difference_type;

difference_type size = std::distance(first, last);
if (first == last) return false;

Given that you've just computed the size, it's probably at least worth considering whether to use that result, and just use:

if (size == 0) return false;

...instead of pretty much re-computing the same thing via first == last.

Below you use first[bound] and in general, the algorithm seems to really require random access iterators to make much sense. If so, I'd rather just use last - first instead of std::distance to compute the difference.

\$\endgroup\$
  • \$\begingroup\$ Concerning the size computation, I agree that it's useless to compute it then throw it away, but performing the check before the size computation seems to be a better alternative. I use std::distance because I am often wondering what I am actually subtracting when I have to deal with many pointers and integral values; it really helps when I need to read my code again. \$\endgroup\$ – Morwenn Feb 11 '16 at 23:04
  • \$\begingroup\$ Also, I should really consider starting a full-on war against people who prefer the old function syntax to the new one :p \$\endgroup\$ – Morwenn Feb 11 '16 at 23:04
  • \$\begingroup\$ @Morwenn: Feel free. By all rights, you'll lose. This isn't "new" vs. "old". It's a question of whether something that was invented for one specific purpose in one situation should be put to all sorts of purposes to which it's poorly suited, and in which it causes syntactic noise. \$\endgroup\$ – Jerry Coffin Feb 11 '16 at 23:10
  • \$\begingroup\$ I never implied it was a "new" vs. "old" (ok, the formulation was poor), just that I feel that the trailing syntax feels more natural (we feed things to a function then it may return things), allows to always properly align function declarations and to always be consistent. The most important part of function hen you're looking for it is its name and the trailing syntax helps to always see the name before anything else. All pros, no cons. \$\endgroup\$ – Morwenn Feb 11 '16 at 23:13
  • \$\begingroup\$ @Morwenn: I have to disagree. First, if you really want to see the name easily, you just insert line break between the return type and the name. Second, it's not anywhere close to "always consistent", until or unless they add a syntax like auto x -> int; Otherwise, it's irretrievably inconsistent. Even if they did add that, it would be inconsistent with decades of existing code without gaining anything. Any gain here is purely illusory. \$\endgroup\$ – Jerry Coffin Feb 11 '16 at 23:19
0
\$\begingroup\$

I agree with most of the remarks by @JerryCoffin. In addition, I would shorten the computation of size and bound to a single initialization using auto:

{
    if (first == last) return false;

    auto size = std::distance(first, last), bound = 1;
    // as before
}

This will enforce that size and bound have the same type, and you'd probably don't really care what type that is (it's not used in your interface anyway).

If you really like the iterator traits, then I'd suggest writing an auxiliary helper trait:

template<class It>
using difference_t = typename std::iterator_traits<It>::difference_type;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.