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

[ViGOur]

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

[Алексей1153]

1)

if (n >= v.size ())

"size()" имеет тип unsigned int , а "n" у тебя - int

2)
Передавать и возвращать контейнеры лучше по ссылке (а то нехилое по объёму копирование будет иногда происходить)
Поэтому, лучше не возвращать из функции тип std::list<T> , а объявить переменную вне функции, а потом передать ссылку для заполнения контейнера в функции

3)объявление переменных-контейнеров частенько громоздкие - лучше определить синоним
typedef std::list<T> td_LIST;
это также поможет вносить быстрые исправления, если что. Но в данном примере это не сильно существенно - код небольшой

4) проверяй
v.size()!=0
для любых контейнеров перед получением итератора или ссылки (.begin(),end(),[x] и так далее)

5) нет нужды делать вот так (и вообще нельзя)
.... eEnd = v.end (); eIt != eEnd......
надо

.... ; eIt != v.end()......

6)

list_out.insert (v.begin (), v.begin () + n);//<<

не получится так вставить из вектора в список. Надо - либо одинаковый тип делать, либо цикл

Раскрывающийся текст

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

template<typename T>
void getNLager (typename const std::vector <T> &v, unsigned int n,std::list<T>& list_out)
{
    typedef std::list<T>  td_LIST;
    list_out.clear();

    if(!v.size ())return;
    if (n >= v.size ()) return;

                                                        list_out.insert (list_out.begin() ,v.begin (), v.begin () + n);
                                                        
    list_out.sort ();
    
    for (typename std::vector<T>::const_iterator eIt = v.begin() + n; eIt != v.end(); ++eIt)
    {
        if (*eIt < *list_out.begin ())
        {
            continue;
        }

        typename td_LIST::iterator it = lower_bound (list_out.begin (), list_out.end (), *eIt);

        list_out.insert (it, *eIt);
        list_out.pop_front ();
    }
}


int main (int argc, char **argv)
{
    std::vector <int> etalon;
    etalon.reserve (1000000);

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

    std::list <int> l;
    getNLager (etalon, 100, l);

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

    return 0;
}

Сообщение отредактировал Алексей1153 - 24.8.2010, 20:07

[panter_dsd]

Алексей1153, что-то не компилируется твой код.

g++ ./main.cpp
./main.cpp:7: ошибка: переменная или поле ‘getNLager’ объявлено void
./main.cpp:7: ошибка: expected nested-name-specifier before ‘const’
./main.cpp:7: ошибка: expected ‘(’ before ‘const’
./main.cpp:7: ошибка: expected primary-expression before ‘unsigned’
./main.cpp:7: ошибка: expected primary-expression before ‘&’ token
./main.cpp:7: ошибка: нет декларации ‘outList’ в этой области видимости
./main.cpp: In function ‘int main(int, char**)’:
./main.cpp:48: ошибка: нет декларации ‘getNLager’ в этой области видимости