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

А массив где находится? Отсортирован ли? Каков размер элементов?

пока свернул, чтобы

ViGOur, я так понимаю это одно из заданий с собеседования?
Если не секрет, какие мысли были у тебя?

Вот задача. Очевидный шаг это отсортировать массив и взять первые 100 значений.
Посидел, подумал, набросал тестовый примерчик и оказалось, что даже без оптимизации кода, можно написать алгоритм который это делает значительно быстрее (на время не тестил и так все видно).

Использовал контейнеры Qt. Функция состоит из 13 строк.

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

вот

<удалил это безобразие>

Алексей1153, что за метод такой resize у map?

Ну вот, вы сразу map и прочее, с map это халява.
Представьте, что нет никакого STL. Есть чистый С\С++ и все!

Да на собеседовании задали, я ответил неправильно, только потом додумался как это можно сделать.

упс, забыл потестить ) Это только идея. Сейчас подправлю

Ну по большому счету не важно на чем писать, мы же алгоритм обсуждаем.

Мои мысли.

typedef    quint32    Number;
typedef    QVector<Number>    VecNumber;
typedef    QList<Number> LstResult;

const int sizeDataVector = 10000000;
const int sizeResultList = 100;

LstResult find100min( const VecNumber &vec )
{
    Number maxValue = -1;
    LstResult result;

    // Заполняем список результатов максимально возможными значениями
    for( int i = 0; i < sizeResultList; ++i )
        result.append( -1 );

    foreach( Number val, vec )
    {
        // Если текущее значение больше самого большого значения в результатах, то прорускаем его
        if( val > maxValue )
            continue;
        
        // иначе, вставляем его в результаты
        result.insert( qLowerBound( result.begin(), result.end(), val ), val );
        // отбрасываем последнее значение
        result.removeLast();
        // устанавливаем maxValue равное последнему элементу результата
        maxValue = result.last();
    }
    
    return result;
}

мда, с мапом затея не очень оказалась - итератор на наибольший элемент хрен так сразу получишь ) А искать его каждый раз - будет накладно

А ещё, креатор отказался понимать итераторы , поэтому пробовал в студии

template<typename T>
void F()
{
    std::map<T,int>::iterator it;
}

хотя, если не используется шаблонный параметр, то итераторы креатор понимает

потому что правильно делать так:

template<typename T>
void F()
{
    typename std::map<T,int>::iterator it;
}

потому что std::map зависит от параметра шаблона T. может получиться что у std::map не будет typedef iterator(или iterator не будет типом), поэтому надо указать компилятору что iterator - это имя типа.

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

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

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

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)

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;
    }
}

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

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

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

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

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


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

Всё равно медленнее, чем в варианте 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 кстати лучше получается.

Это Qt. QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).
http://doc.crossplatform.ru/qt/4.6.x/conta...hmic-complexity

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

Я не знаю ответа на этот вопрос. Почему то разработчики Qt поступили именно так, и, при небольших количествах элементов, QList - это вектор

А вот мое решение.

    std::vector <int> etalon;

    for (int i = 10000000; i > 0; i--) {
        etalon.push_back (i);
    }

    std::vector <int> v (100);
    copy (etalon.begin (), etalon.begin () + 100, v.begin ());
    sort (v.begin (), v.end ());

    for (std::vector <int>::const_iterator eIt = etalon.begin () + 100, eEnd = etalon.end (); eIt != eEnd; ++eIt) {
        if (*eIt < *v.begin ()) {
            continue;
        }

        std::vector <int>::iterator it = find (v.begin () + 1, v.end (), *eIt);
        v.insert (it, *eIt);
        v.erase (v.begin ());
    }

тут одно только заполнение вектора etalon (зачем-то) всё время покроет )

Это только для проверки. Он и является нужным контейнером.

panter_dsd, в твоем случае не оптимально по скорости.
При добавлении нового элемента вектора, вектор расширяется, выделяется память для его нового элемента и копируются все элементы вектора в новый участок памяти. (вспомни, почему нельзя пользоваться полученными итераторами на элемент вектора, после добавления нового элемента, пускай даже в конец вектора).
При удалении первого элемента вектора "v" что происходит со всем вектором? Вроде как все элементы вектора сдвигаются. Насчет перераспределения памяти не помню, что происходит.
А так как ты для примера выбрал самый не трудоемкий случай, то это в принципе очень не критично, но если поменять цикл заполнения etalon от 0 до ... то это будет происходить в каждой итерации цикла.

panter_dsd,
он имеет ввиду что вектор заполнить можно значительно быстрее чем делаешь ты.
при каждом твоем push_back происходит выделение памяти. хотя память под элементы можно выделить одним махом при создании вектора.
ну тут долгая песня
Скот Меерс в руки и вперед.

Согласен. Вставку не учел. На счет удаления знал, но решил пренебречь. заменяем вектор на лист и избавляемся от этого.

Блин, создание эталонного массива просто для примера. Не смотрите туда.

Я на эталон как раз потому и не смотрел.
Обновленный код тогда в студию...

p.s. эталон разумеется оставь, он для наглядности, только поменяй его заполнение на более сложный случай, когда последующее число больше предыдущего.

Я сейчас с телефона , позже выложу код.

#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 максимальных значений, лопухнулся. Ну, принцип тот же самый.

а ты выдели как отдельную функцию, я в шаблон переделаю )

Готово. Сделал для любого кол-ва элементов. Хотелось бы еще для любого типа.

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

std::list <int> getNLager (const std::vector <int> &v, int n);

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);

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

    return 0;
}

std::list <int> getNLager (const std::vector <int> &v, int n)
{
    if (n >= v.size ()) {
        return std::list <int> ();
    }

    std::list <int> l (v.begin (), v.begin () + n);
    l.sort ();
    
    for (std::vector <int>::const_iterator eIt = v.begin () + n, eEnd = v.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 ();
    }

    return l;
}

Хотелось бы мнение узнать о правильности кода, а то stl только недавно начал учить.

1)

"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);//<<

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

1. Учту.
2. Согласен.
4. Учту.
5. Не согласен. Можно и нужно, если контейнер не изменяется. Зачем дергать функцию на каждой итерации?
6. Вполне получается. Что смущает?

5 - в релизе там не будет функции Так что, дёргай без опаски
6 - ну, раз получается, тогда пользуйся на здоровье. У меня компилятор брыкается )) Ну оно и понятно

6. Компилятор ничего не говорит. По документации тоже можно, вроде бы. Завтра перепроверю.

всё, 6 - мой косяк )) Исправил . Пропустил начальный итератор и не обратил внимание

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

мои пять копеек.
я вот тоже в stl недавно стал вникаить.
так меерс советует в 4 совете использовать empty() вместо сравнения size() с нулем из-за постоянного времени выполнения функции.
stl

kwisp, ок, учтём ) Только обычно у меня такой вызов был не в цикле, а list ещё не доводилось пользоваться почему то ))

Алексей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’ в этой области видимости

panter_dsd, я в студии делал - там компилится. А ты где?

А ты, случаем, не поставил main перед реализацией функции ? )

тогда предопределение попробуй добавить перед мейном:

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

И попробуй ещё дописать "typename" перед "std::list<T>& list_out" в списке аргументов функции

typename не надо дописывать и в первом аргументе.
и вообще typename должен применяться к qualified-id зависящего от шаблонного параметра:

Выкидывание typename помогло.
Алексей1153, что-то мне интересно. С шаблонами хорошо знаком, а компилятор от IDE и библиотеки отделить не можешь...
Я компилировал g++ (Gentoo 4.4.4-r1 p1.1, pie-0.4.5) 4.4.4. Т.е. не студийным компилером.

Заканчиваем с оффтопом.
Вот последняя редакция, еще есть замечания?

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

template<typename T>
void getNLager (const std::vector <T> &v, std::vector<T>& vOut, uint n)
{
    vOut.clear();

    if (v.empty () || n >= v.size ()) {
        return;
    }

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

        const typename std::list <T>::iterator it = lower_bound (l.begin (), l.end (), *eIt);

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

    vOut.reserve (n);
    vOut.assign (l.begin (), l.end ());
}


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::vector <int> v;
    getNLager (etalon, v, 100);

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

    return 0;
}

Перенес флейм в другую тему, В любимый Алексей1153 раздел "Треп", чтобы потрепаться.

Смотрите: Что есть что, с чем можно и куда....

Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему?

а в чём проблема, всё это можно переписать на чистый C, только сути это не изменит(просто будет больше кода и будет сложнее его понять)

Да пускай резвятся. Потом покажу как можно и без stl cделать. И так же быстро, если сами не решат сделать.

Да в том и проблема, что без использования стандартных средств для красивого и оптимального решения, все это выглядеть будет на чистом С++ (а не С) совсем по-другому!

STL является неотъемлемой частью C++, поэтому тот код и есть чистый C++.