Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более Опции

[BRE]

по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов.

Как я уже писал в 3 посте, это очень долго.

[igor_bogomolov]

по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов.

Это будет медленнее. В твоём случае порядок роста O(n log n). В варианте BRE O(n)

[DEADHUNT]

std::vector<int> min_elements(100, values[0]);
for (std::list<int>::const_iterator it = values.begin();
    it != values.end(); ++it)
{
    if (min_elements.back() > *it)
    {
        min_elements.back() = *it;
        std::sort(min_elements.begin(), min_elements.end());
    }
}

получаем сложность O(n)

[Алексей1153]

DEADHUNT, наверное, правильНЕЕ , но студия понимает и так

Кстати, победил:

template<typename T>
void find_most_little_elenents(std::vector<T>& vResut,const T* beg,const T* end,const unsigned int countToFind)
{
    struct Tr
    {
        T t;
        Tr(T& t):t(t){}
        bool operator<(const Tr& o2)const{return t>o2.t;}
    };

    vResut.clear();

    typedef std::multimap<Tr,int> td_mapOut;
    td_mapOut mapOut;
    
    for(T* t=(T*)beg;t<end;t++)
    {
        if(mapOut.size()==countToFind && mapOut.begin()->first.t <= *t)
        {
        }
        else
        {
            mapOut.insert(td_mapOut::value_type(*t,0));
            
            if(mapOut.size()>countToFind)
            {
                mapOut.erase(mapOut.begin());
            }
        }
    }

    unsigned int dwd=0;
    vResut.resize(mapOut.size());
    for(
        td_mapOut::reverse_iterator it=mapOut.rbegin();
        it!=mapOut.rend();
        it++,dwd++
            )
    {
        vResut[dwd]=it->first.t;
    }
}

[DEADHUNT]

Алексей1153, как то у тебя нагромаждённо получается, наверняка можно было проще твой вариант сделать.

[Алексей1153]

igor_bogomolov, а вот пример использования, который креатор тоже не прожевал, а студия понимает нормально. Тут то что не так ))

    char c[]="183743652425643758462";
    std::vector<char> vec;
    find_most_little_elenents(vec,c,c+sizeof(c)-1,5);//<<ругается сюда

DEADHUNT, может и можно. Покажи, я готов учиться

Кстати, о птичках. Потом интересно будет сравнить по скорости работы )

Представьте, что нет никакого STL. Есть чистый С\С++ и все!

чистый C++ содержит STL , вообще то )
Ну а если задача стоИт - без STL , то реализацию контейнера в виде класса (или его "размазанную" по коду процедуры реализацию) придётся также сочинять. И отлаживать

Сообщение отредактировал Алексей1153 - 21.8.2010, 22:10

[igor_bogomolov]

получаем сложность O(n)

Всё равно медленнее, чем в варианте BRE. У тебя на каждом шаге происходит сортировка массива из 100 элементов со сложностью O(nlogn). В алгоритме BRE элемент встаёт на место за время O(logn) используя бинарный поиск

Интересно, возможно ли сделать оптимальнее чем у BRE

[DEADHUNT]

Всё равно медленнее, чем в варианте BRE. У тебя на каждом шаге происходит сортировка массива из 100 элементов со сложностью O(nlogn). В алгоритме BRE элемент встаёт на место за время O(logn) используя бинарный поиск

Интересно, возможно ли сделать оптимальнее чем у BRE

на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список. сортировка на самом деле лишняя, так как достаточно найти место куда вставить и всё.

std::vector<int> min_elements(100, values[0]);
for (std::list<int>::const_iterator it = values.begin();
    it != values.end(); ++it)
{
    if (min_elements.back() > *it)
    {
        std::vector<int>::iterator pos = std::lower_bound(min_elements.begin(), min_elements.end(), *it);
        *pos = *it;
    }
}

без Qt кстати лучше получается.

[igor_bogomolov]

на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список.

Это Qt. QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).
Link

[DEADHUNT]

QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).

а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).