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

[ViGOur]

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

[Алексей1153]

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

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

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

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

для неотсортированного случая можно, к примеру, так:

берём мап, начинаем заполнять всеми по очереди элементами. Когда размер мапа перешёл от 100 к 101, удаляем наибольший элемент - и так далее. Щас попробую в коде выразить мысль ))

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

[BRE]

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

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

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

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

[Алексей1153]

вот

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

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

[BRE]

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

[ViGOur]

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

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

[Алексей1153]

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

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

[BRE]

Ну вот, вы сразу 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;
}

[Алексей1153]

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

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

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

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

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

[DEADHUNT]

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

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

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

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

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