всем привет

есть следующая задача:
найти заданный элемент в массиве из 1000 элементах (каждый по 20 байт)
массив отсортирован, написал функцию быстрого поиска, где сравнение выполняю с помощью memcmp()

вопрос в следующем:
будет ли функция поиска работать быстрее... если я буду сравнивать по 4 байта, а не по 20?
т.е. у элементов сравниваю первые 4 байта, при совпадении сравниваю следующие 4 байта... и т.д., если не совпали — перехожу к след. уэлементам.

как устроена memcmp? на сколько быстрее она сравнит 4 байта и 20 байт?

всем спасибо)

gem>как устроена memcmp? на сколько быстрее она сравнит 4 байта и 20 байт?

напиши тест и сравни результаты.

А ты проверь

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

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

gem>найти заданный элемент в массиве из 1000 элементах (каждый по 20 байт)
gem>массив отсортирован, написал функцию быстрого поиска, где сравнение выполняю с помощью memcmp()

Если массив действительно отсортирован то надо использовать бинарный поис в место memcmp ибо memcmp имеет линейную сложность те она произведет 1000 сравнений в то время как бинарный поиск log2(1000)~=10 сравнений, а для 1000000 примерно 20 сравнений. Как говорится почувствойте разницу
например

template<class iter_t, class val_t> 
inline iter_t binary_search_iter(iter_t begin, iter_t end, val_t const& val)
{
    iter_t iter=std::lower_bound(begin, end, val);
    if(iter==end)
        return end;
    if(val < *iter)
        return end;
    else
        return iter;
}
template<class iter_t, class val_t>
void test(iter_t begin, iter_t end, val_t val)
{
    iter_t iter=binary_search_iter
        (begin
        ,end
        ,val
        );
    if(end!=iter)
        std::cout<<"found\n";
    else
        std::cout<<"not found\n";
}
int main()
{
    std::vector<int> v(1000);
    std::generate
        (v.begin()
        ,v.end()
        ,lm::bind(rand)%100
        );
    std::sort
        (v.begin()
        ,v.end()
        );
    test
        (v.begin()
        ,v.end()
        ,12
        );
    return 0;
}

ЗЫ Какого std::binary_search возвращает bool, а не итератор?

WH>ЗЫ Какого std::binary_search возвращает bool, а не итератор?

Используй std::lower_bound вместо.

Как я понял, автор имеет в виду, что операция сравнения при бинарном поиске реализована через memcmp().

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

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

gem>>найти заданный элемент в массиве из 1000 элементах (каждый по 20 байт)
gem>>массив отсортирован, написал функцию быстрого поиска, где сравнение выполняю с помощью memcmp()

WH>Если массив действительно отсортирован то надо использовать бинарный поис в место memcmp ибо memcmp имеет линейную сложность те она произведет 1000 сравнений в то время как бинарный поиск log2(1000)~=10 сравнений, а для 1000000 примерно 20 сравнений. Как говорится почувствойте разницу

WH>ЗЫ Какого std::binary_search возвращает bool, а не итератор?

спасибо за пример... но:
у меня функция быстрого поиска !!!
находит элемент из 1024 элементов за 10 сравнений!

а вопрос заключался в следующем:
как эффективнее будет воспользоваться memcmp(), т.е по сколько байт сравнивать наиболее эффективно или в данном случае выигрыша не будет? )

gem>а вопрос заключался в следующем:
gem>как эффективнее будет воспользоваться memcmp(), т.е по сколько байт сравнивать наиболее эффективно или в данном случае выигрыша не будет? )

Выигрыша по твоему способу не будет.
memcmp завершится, как только будут найдены различия в массивах байт.

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


gem>>а вопрос заключался в следующем:
gem>>как эффективнее будет воспользоваться memcmp(), т.е по сколько байт сравнивать наиболее эффективно или в данном случае выигрыша не будет? )

RB>Выигрыша по твоему способу не будет.
RB>memcmp завершится, как только будут найдены различия в массивах байт.

всем спасибо за обсуждение