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

[ViGOur]

Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей?

[panter_dsd]

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main (int argc, char **argv) {
    //This is only for test!!!
    std::vector <int> etalon;
    etalon.reserve (10000000);

    for (int i = 0; i < 10000000; i++) {
        etalon.push_back (i);
    }

    std::cout << "Start" << std::endl;
    //Start
    std::list <int> l (etalon.begin (), etalon.begin () + 100);
    l.sort ();
    
    for (std::vector <int>::const_iterator eIt = etalon.begin () + 100, eEnd = etalon.end (); eIt != eEnd; ++eIt) {
        if (*eIt < *l.begin ()) {
            continue;
        }

        std::list <int>::iterator it = lower_bound (l.begin (), l.end (), *eIt);
        l.insert (it, *eIt);
        l.pop_front ();
    }

    for (std::list <int>::iterator it = l.begin (), end = l.end (); it != end; ++it) {
        std::cout << *it << std::endl;
    }

    return 0;
}

Вот измененный код. Коррективы приветствуются.
Можно функцию в виде темплейта оформить, но пока не знаю как, еще не дошел до этого.
Только заметил, что ищу 100 максимальных значений, лопухнулся. Ну, принцип тот же самый.

Сообщение отредактировал panter_dsd - 24.8.2010, 16:48