min_element в контейнере с известным наименьшем элементом - C/C++

Привет.

Есть задача поиска минимального элемента в контейнере. std::min_element подходит в большинстве случаев, но не всегда является оптимальным решением.

Например, когда значения элементов ограничены снизу (типичный случай -- вектор беззнаковых целых).
В этом случае, даже если это гарантированно минимальное значение встретится, min_element все равно пройдет по всему контейнеру.

Другой пример: нужно найти "почти минимальный элемент": т.е. стараемся найти минимальный, но если уж нашли какой-нибудь меньше определенного значения, то он вполне подойдет.

Вот мой велосипед для этих целей:

template <class ForwardIterator, class T>
inline
ForwardIterator
min_element_bounded(ForwardIterator first,
                    ForwardIterator last,
                    T const& v)
{
    if (first == last)
        return last;

    ForwardIterator lowest = first;
    if (!(v < *lowest))
        return lowest;

    while (++first != last) {
        if (*first < *lowest) {
            lowest = first;
            if (!(v < *lowest))
                return lowest;
        }
    }
    return lowest;
}

Т.е. это std::min_element плюс условие для раннего return. Соответственно, есть max_element_bounded() и версии с компаратором.

Хотелось бы услышать критику этого решения, начиная с "это противоречит философии STL", продолжая "это уже есть в бусте" и заканчивая любым конструктивом в смысле именования и реализации.

Сразу отвечу на аргумент "если min_element является узким местом -- вероятно, надо сортировать контейнер": это не всегда возможно и не всегда оправдано.

Здравствуйте, Alexander Poluektov, Вы писали:

AP>Вот мой велосипед для этих целей:

хороший велик, имхо

Здравствуйте, Alexander Poluektov, Вы писали:
AP>Вот мой велосипед для этих целей:
AP>

AP>template <class ForwardIterator, class T>
AP>inline
AP>ForwardIterator
AP>min_element_bounded(ForwardIterator first,
AP>                    ForwardIterator last,
AP>                    T const& v)
AP>{
AP>    if (first == last)
AP>        return last;

AP>    ForwardIterator lowest = first;
AP>    if (!(v < *lowest))
AP>        return lowest;

AP>    while (++first != last) {
AP>        if (*first < *lowest) {
AP>            lowest = first;
AP>            if (!(v < *lowest))
AP>                return lowest;
AP>        }
AP>    }
AP>    return lowest;
AP>}
AP>

То же самое, но короче:

template <class ForwardIterator, class T>
inline
ForwardIterator
min_element_bounded(ForwardIterator first,
                    ForwardIterator last,
                    T const& v)
{
    if (first == last)
        return last;

    ForwardIterator lowest = first;
    while (v < *lowest && ++first != last) {
        if (*first < *lowest)
            lowest = first;
    }
    return lowest;
}

AP>Хотелось бы услышать критику этого решения, начиная с "это противоречит философии STL", продолжая "это уже есть в бусте" и заканчивая любым конструктивом в смысле именования и реализации.

А что тут критиковать? Код как код.

Здравствуйте, gegMOPO4, Вы писали:

MOP>То же самое, но короче:
у вас часто проверяется условие v < *lowest, даже если lowest не меняется
можно еще короче (= извращеннее), однако исходный код изначально хорош

template <class ForwardIterator, class T>
ForwardIterator min_element_bounded(ForwardIterator first, ForwardIterator last, T const& v)
{
  if (first == last || *first <= v)
    return first;

  auto second = min_element_bounded(first + 1, last, v);
  return (second == last || *first < *second) ? first : second;
}

Здравствуйте, uzhas, Вы писали:
U>Здравствуйте, gegMOPO4, Вы писали:
MOP>>То же самое, но короче:
U>у вас часто проверяется условие v < *lowest, даже если lowest не меняется

Упс, ошибся, подковал Левша блоху. Надо так:

template <class ForwardIterator, class T>
inline
ForwardIterator
min_element_bounded(ForwardIterator first,
                    ForwardIterator last,
                    T const& v)
{
    if (first != last) {
        while (v < *first) {
            ForwardIterator lowest = first;
            do {
                if (++first == last)
                    return lowest;
            } while (!(*first < *lowest));
        }
    }
    return first;
}

U>можно еще короче (= извращеннее), однако исходный код изначально хорош
U>

Да уж, извращённее рекурсии не придумаешь.

Всем спасибо, велики теперь стоят на github.

Туда же добавил некое подобие документации.
Желающим попинать или добавить своих велосипедов -- welcome

Здравствуйте, Alexander Poluektov, Вы писали:

интересную табличку нашел http://www.richelbilderbeek.nl/CppAlgorithm.htm
иногда приходитя дублировать то, что в новый стандарт уже вкрячили

AP>Желающим попинать или добавить своих велосипедов -- welcome

а в чем смысл добавлять свои велики?
можете заняться импортом буста

Здравствуйте, Alexander Poluektov, Вы писали:

AP>Другой пример: нужно найти "почти минимальный элемент": т.е. стараемся найти минимальный, но если уж нашли какой-нибудь меньше определенного значения, то он вполне подойдет.

STL way.

template<class Iterator, class Value>
Iterator nearly_min_element(Iterator begin, Iterator end, Value const& treshold)
{
  Iterator last = find_if(begin,end, _1<treshold);
  return (last!=end) ? last : min_element(begin,end);
}

Идея в следующем.
Мы ищем элемент, такой, что a[i] < a[0..i) || a[i] < treshold

В любом случае, мы не знаем, нашли минимальный элемент или ещё нет, пока не дойдём до точки отсечки.
То есть, нам не миновать всех проверок на отсечку, поэтому можем смело вынести эти проверки в отдельную фазу — find_if.

Теперь есть два варианта:
1) Точка отсечки найдена, [last] < treshold, — соответственно, [0..last) >= treshold
То есть, на [begin..last] именно [last] является минимумом и искомым значением. Никаких дополнительных проверок делать не нужно, т.к. они будут тривиальными:
min_element(begin,last+1) == last.

2) Отсечки нет, все элементы >= treshold. Тогда делаем честный поиск минимума на всём диапазоне.

Требование к итератору — forward_iterator (два прохода по диапазону), такое же, как для min_element, то есть, мы не заузили ситуацию.

Здравствуйте, Кодт, Вы писали:

AP>>Другой пример: нужно найти "почти минимальный элемент": т.е. стараемся найти минимальный, но если уж нашли какой-нибудь меньше определенного значения, то он вполне подойдет.

К>STL way.
К>

К>template<class Iterator, class Value>
К>Iterator nearly_min_element(Iterator begin, Iterator end, Value const& treshold)
К>{
К>  Iterator last = find_if(begin,end, _1<treshold);
К>  return (last!=end) ? last : min_element(begin,end);
К>}
К>

Мой вариант выполняет меньше сравнений:
— в лучшем случае ([begin; end) сортирован по возрастанию) d сравнений
— в худшем ([begin; end) сортирован по убыванию) 2*d.
— в среднем, как я понимаю, что-то около 1.5*d,
где d = distance(begin,last)

В твоем варианте сравнений всегда 2*d.

Это как с boost::minmax (теперь std::minmax): в идеале, STL-way -- посчитать std::min и std::max, а на практике хочется лишней работы не делать.

Здравствуйте, Alexander Poluektov, Вы писали:
AP>Мой вариант выполняет меньше сравнений:
AP>- в лучшем случае ([begin; end) сортирован по возрастанию) d сравнений
AP>- в худшем ([begin; end) сортирован по убыванию) 2*d.
AP>- в среднем, как я понимаю, что-то около 1.5*d,
AP>где d = distance(begin,last)
AP>В твоем варианте сравнений всегда 2*d.
AP>Это как с boost::minmax (теперь std::minmax): в идеале, STL-way -- посчитать std::min и std::max, а на практике хочется лишней работы не делать.

А вот std::min_element всегда d сравнений.

Здравствуйте, gegMOPO4, Вы писали:

AP>>Мой вариант выполняет меньше сравнений:
AP>>- в лучшем случае ([begin; end) сортирован по возрастанию) d сравнений
AP>>- в худшем ([begin; end) сортирован по убыванию) 2*d.
AP>>- в среднем, как я понимаю, что-то около 1.5*d,
AP>>где d = distance(begin,last)
AP>>В твоем варианте сравнений всегда 2*d.
AP>>Это как с boost::minmax (теперь std::minmax): в идеале, STL-way -- посчитать std::min и std::max, а на практике хочется лишней работы не делать.

MOP>А вот std::min_element всегда d сравнений.

Нет. В std::min_element сравнений всегда distance(begin, end). Что может быть лучше d, а может быть и намного хуже.

Здравствуйте, Alexander Poluektov, Вы писали:
AP>Здравствуйте, gegMOPO4, Вы писали:
AP>>>Мой вариант выполняет меньше сравнений:
AP>>>- в лучшем случае ([begin; end) сортирован по возрастанию) d сравнений
AP>>>- в худшем ([begin; end) сортирован по убыванию) 2*d.
AP>>>- в среднем, как я понимаю, что-то около 1.5*d,
AP>>>где d = distance(begin,last)
AP>>>В твоем варианте сравнений всегда 2*d.
AP>>>Это как с boost::minmax (теперь std::minmax): в идеале, STL-way -- посчитать std::min и std::max, а на практике хочется лишней работы не делать.
MOP>>А вот std::min_element всегда d сравнений.
AP>Нет. В std::min_element сравнений всегда distance(begin, end). Что может быть лучше d, а может быть и намного хуже.

Ах да, моя невнимательность.

Некоторое время назад я написал большой комментарий-исследование разных случаев, но он, к сожалению, пропал, потому, что у меня не прав постить в форум «Мусор». Повторю некоторые моменты.

В варианте Кодта будет d сравнений, если есть элемент меньше treshold (кстати, алгоритмы не тождественны, у вас ищется не больше, но это исправимо), и 2*n, если нет (при этом d=n). Если p — вероятность того, что такой элемент есть, a — среднее d для этого случая (a<n), то среднее число сравнений будет:

p*1.5*a+(1-p)*1.5*n — для вашего алгоритма;
a+(1-p)*n — для алгоритма Кодта;
n — std::min_element.

Алгоритм Кодта выгоднее вашего, если (2-3*p)*a < (1-p)*n.
Ваш алгоритм выгоднее std::min_element, если 3*p*a < (3*p-1)*n.
Алгоритм Кодта выгоднее std::min_element, если a < p*n.

При p < 1/3 std::min_element заведомо выгоднее вашего.
При p > 1/2 алгоритм Кодта заведомо выгоднее вашего.
Ваш алгоритм выгоднее только если 1/3 < p < 1/2 и (1-p)/(2-3*p) < a/n < (3*p-1)/(3*p). Эта система неравенств не имеет решения.

Здравствуйте, gegMOPO4, Вы писали:

MOP>>>А вот std::min_element всегда d сравнений.
AP>>Нет. В std::min_element сравнений всегда distance(begin, end). Что может быть лучше d, а может быть и намного хуже.

MOP>Ах да, моя невнимательность.

Да нет, моя -- это ведь я не заметил, что алгоритм Кодта в случае "успеха" делает d сравнений, а не 2*d.

MOP>Некоторое время назад я написал большой комментарий-исследование разных случаев, но он, к сожалению, пропал, потому, что у меня не прав постить в форум «Мусор».

Причем тут форум "Мусор" я, к сожалению, не понял. Какое-то действие с моей стороны повлекло потерю Вашего комментария?

Раз мы перешли на язык вероятностей и систем неравенств, придется уточнить среднее количество сравнений в случае моего алгоритма.
Оно равно (1+k)*d, где k = 1/e, e — основание натурального логарифма.

Кроме того, я полагаю, что для алгоритма Кодта среднее число сравнений p*a+(1-p)*2*n, а не a+(1-p)*n.

Таким образом, если p — вероятность того, что такой элемент есть, a — среднее d для этого случая (a<n), то среднее число сравнений будет:

p*(1+k)*a+(1-p)*(1+k)*n — для моего алгоритма;
+(1-p)*n, а не — для алгоритма Кодта;
n — std::min_element.

Выписывать здесь систему неравенств теперь сил никаких нет, потому что (1+k) теперь никуда не сокращается, читать такие дроби, записанные в строку, довольно сложно, а в Latex'е я не копенгаген.

Но и так очевидно, что решения она имеет. Вот парочка:

n = 1000, a = 500, p = 0.6
среднее количество сравнений:
min_element: 1000
алгоритм Кодта: 1100
мой алгоритм: 958

n = 1000, a = 100, p = 0.6
среднее количество сравнений:
min_element: 1000
алгоритм Кодта: 840
мой алгоритм: 630

n = 1000, a = 100, p = 0.4
среднее количество сравнений:
min_element: 1000
алгоритм Кодта: 1240
мой алгоритм: 876

Копипаст заело, извините

AP>p*(1+k)*a+(1-p)*(1+k)*n — для моего алгоритма;
AP>p*a+(1-p)*2*n — для алгоритма Кодта;
AP>n — std::min_element.

Здравствуйте, Alexander Poluektov, Вы писали:

template <class ForwardIterator, class T>
inline
ForwardIterator
min_element_bounded(ForwardIterator first,
                    ForwardIterator last,
                    T const& v)
{
    if (first == last)
        return last;

    ForwardIterator lowest = first;
    if (!(v < *lowest))
        return lowest; // A

    while (++first != last) {
        if (*first < *lowest) {
            lowest = first;
            if (!(v < *lowest))
                return lowest;
        }
    }
    return lowest;
}

AP>Мой вариант выполняет меньше сравнений:
AP>- в лучшем случае ([begin; end) сортирован по возрастанию) d сравнений

Вообще-то, кажется, не d, а только 1: из точки "A" мы можем вывалиться после одного сравнения. Если это не лучший случай — то я уж тогда и не знаю...

AP>- в худшем ([begin; end) сортирован по убыванию) 2*d.

Полностью согласен, в худшем случае придется пройти все элементы — это когда все элементы больше v, но самый малый находится в конце ( [begin, end) отсортирован по убыванию).

AP>- в среднем, как я понимаю, что-то около 1.5*d,

А точнее — d.

"Мы, конечно, в академиях не учились", так что буду рад, если уважаемые коллеги поправят мои выкладки. Вот они:
пусть, имеем d элементов. Вероятность того, что поиск завершится на шаге k равна 1/d — мы же не знаем ничего о распределении элементов в диапазоне. Как говорится, "вероятность встретить на улице динозавра равна 1/2: либо встретишь, либо нет". На каждом шаге имеем 2 сравнения. Значит, среднее число сравнений — (sum([2 * k for k in range(0, d)], 0)) / d . т.е. d

P.S. Опровержения приветствуются.

_>"Мы, конечно, в академиях не учились",
в этом треде, видимо, никто не соображает в вероятностях

основная проблема с корректным определением вероятностного пространства
прицепились к какому-то мутному параметру d, который имеет слабое отношение к "среднему кол-ву сравнений в алгоритме"

Здравствуйте, uzhas, Вы писали:

U>основная проблема с корректным определением вероятностного пространства
Про "теорему о динозавре" см. выше.

U>прицепились к какому-то мутному параметру d, который имеет слабое отношение к "среднему кол-ву сравнений в алгоритме"

Параметр d здесь, насколько я понимаю, есть просто-напросто длина последовательности. Короче, синоним для того, что по классике принято обозначать буквой N.

Вообще же, откровенно говоря, все эти выкладки, приводимые авторами в ветке, меня несколько озадачили. Ну вот, берем наугад товарища Николу Вирта, "Алгоритмы и структуры данных", анализ простой сортировки вставками.

Число сравнений ключей в i-м просеивании не больше i-1, как минимум равно 1, и — предполагая, что все перестановки ключей равновероятны, — в среднем равно i/2.

Сравнение ключей в просеивании (то бишь итерации) — тот же поиск, только в профиль. Предполагаем, что вставка в 1-ю позицию не менее, но и не более вероятна, чем вставка в i-ю. Или нет? Где мы с Николой оплошали?

Здравствуйте, slava_phirsov, Вы писали:

_>Вообще же, откровенно говоря, все эти выкладки, приводимые авторами в ветке, меня несколько озадачили. Ну вот, берем наугад товарища Николу Вирта, "Алгоритмы и структуры данных", анализ простой сортировки вставками.
_>

_>Число сравнений ключей в i-м просеивании не больше i-1, как минимум равно 1, и — предполагая, что все перестановки ключей равновероятны, — в среднем равно i/2.

Что такое "Сравнение ключей в i-м просеивании"?

Если речь о среднем количестве инверсий в перестановке из N элементов, то оно стремится к 1/e, а не 1/2.

Здравствуйте, slava_phirsov, Вы писали:

_>Здравствуйте, Alexander Poluektov, Вы писали:

_>

_>template <class ForwardIterator, class T>
_>inline
_>ForwardIterator
_>min_element_bounded(ForwardIterator first,
_>                    ForwardIterator last,
_>                    T const& v)
_>{
_>    if (first == last)
_>        return last;

_>    ForwardIterator lowest = first;
_>    if (!(v < *lowest))
_>        return lowest; // A

_>    while (++first != last) {
_>        if (*first < *lowest) {
_>            lowest = first;
_>            if (!(v < *lowest))
_>                return lowest;
_>        }
_>    }
_>    return lowest;
_>}
_>

_>"Мы, конечно, в академиях не учились", так что буду рад, если уважаемые коллеги поправят мои выкладки. Вот они:
_>пусть, имеем d элементов. Вероятность того, что поиск завершится на шаге k равна 1/d — мы же не знаем ничего о распределении элементов в диапазоне. Как говорится, "вероятность встретить на улице динозавра равна 1/2: либо встретишь, либо нет". На каждом шаге имеем 2 сравнения.

Ошибка выделена. Среднее количество "доволнительных" (выделены в коде) сравнений равно среднему количеству инверсий в перестановке, т.е. N/e.

От:	Alexander Poluektov	http://www.google.com/profiles/alexander.poluektov#buzz
Дата:	01.09.11 06:35
Оценка:

От:	Alexander Poluektov	http://www.google.com/profiles/alexander.poluektov#buzz
Дата:	01.09.11 06:36
Оценка:

	От:	uzhas
	Дата:	01.09.11 06:58
	Оценка:	1 (1)

	От:	gegMOPO4
	Дата:	01.09.11 11:50
	Оценка:	4 (1)

	От:	uzhas
	Дата:	01.09.11 13:36
	Оценка:	8 (2)

	От:	Кодт
	Дата:	08.09.11 12:45
	Оценка:

	От:	slava_phirsov
	Дата:	13.09.11 15:17
	Оценка:

	От:	slava_phirsov
	Дата:	14.09.11 07:47
	Оценка: