Бысрый способ получить 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