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

[AD]

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

Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется!

[DEADHUNT]

Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется!

в C++0x стандарте описание языка C++ занимает 400 страниц, далее идёт описание стандартной библиотеки(STL) на 700+ страниц.

Сообщение отредактировал DEADHUNT - 26.8.2010, 12:02

[kwisp]

nth_element() - не катит?

[DEADHUNT]

nth_element() - не катит?

да кстати, всё реализовано в stl, сложность - линейная.
и весь код тогда будет занимать одну строчку:

std::vector<int> values; // 100000000 чисел
std::nth_element(values.begin(), values.begin() + 100, values.end()); // первые 100 чисел в values - минимальные

[Алексей1153]

сложность - линейная

The nth_element algorithm partitions the sequence [First..Last) on the value referenced by Nth. All the elements less than or equal to the value are placed before value and all elements greater than value are placed after value in the sequence. The nonpredicate version of nth_element uses operator< for comparisons.

а про сортировку ни слова Может, поэтому

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

[ViGOur]

Как и обещал, код:

#include <algorithm>
#include <vector>

void fillValue( int &rValue)
{
    static int n = 0;
    n++;
    rValue = n;
}

int main()
{    
    const size_t N = 10000;
    const size_t M = 10;
    std::vector<int> coll( N);
    std::for_each( coll.begin(), coll.end(), fillValue); // заполняем
    std::random_shuffle( coll.begin(), coll.end());      // рандомизируем, чтобы числа были не по порядку
    std::vector<int> collMin( M, 0);
    size_t collSize = coll.size();
    size_t collMinSize = collMin.size();
    // Здесь мы делали подготовительную работу по наполнению и эмуляции массивов, далее будет основная...

    for( size_t n = 0; n < collSize; ++n)
    {
        if( n >= collMinSize)
        {
            int nMaxNumPos = 0;
            for( size_t x = 0; x < collMinSize; ++x)
            {
                if( collMin[x] > collMin[nMaxNumPos])
                    nMaxNumPos = x;
            }
            if( collMin[nMaxNumPos] > coll[n])
                collMin[nMaxNumPos] = coll[n];
        }
        else
        {
            collMin[n] = coll[n];
        }
    }
   
    return 0;
}

Конструктивная критика приветствуется!

[panter_dsd]

1. rValue = ++n; - зачем в 2 строки делать?
2. std::vector<int> collMin( coll.begin(), coll.begin() + n); все же лучше.

[ViGOur]

1. Кому как нравится.
2. Чем лучше?

[panter_dsd]

1. Если хочется в 2 строки, то хотя бы префиксную версию инкремента юзай.
2. Избавляемся от лишнего заполнения нулями, плюс от else, который только путает.

Сообщение отредактировал panter_dsd - 25.1.2012, 12:05

[ViGOur]

1. в данном случае точно разницы нет постфиксный инкремент или префиксный!
2. То, что избавляет от лишнего заполнения нолями, согласен. Но ИМХО мой вариант наглядней будет.

Всё равно, можно сказать, что ты выиграл M процессорных тактов на заполнении нолями и столько же можно убрать из цикла!

Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение.
Тоесть только для наглядности!