Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Бысрый способ получить 100 наименьших элементов
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
Страницы: 1, 2
AD
Цитата(DEADHUNT @ 26.8.2010, 12:19) *
STL является неотъемлемой частью C++, поэтому тот код и есть чистый C++.

Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется! ;)
DEADHUNT
Цитата(AD @ 26.8.2010, 12:58) *
Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется! ;)

в C++0x стандарте описание языка C++ занимает 400 страниц, далее идёт описание стандартной библиотеки(STL) на 700+ страниц.
kwisp
nth_element() - не катит?
DEADHUNT
Цитата(kwisp @ 28.8.2010, 15:25) *
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.


а про сортировку ни слова :) Может, поэтому
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, который только путает.
ViGOur
1. в данном случае точно разницы нет постфиксный инкремент или префиксный! :)
2. То, что избавляет от лишнего заполнения нолями, согласен. Но ИМХО мой вариант наглядней будет.

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

Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение.
Тоесть только для наглядности! :)
Алексей1153
Цитата(panter_dsd @ 25.1.2012, 14:41) *
1. rValue = ++n; - зачем в 2 строки делать?


моё мнение - именно в 2 строки лучше. Нагляднее, плюс исключена ошибка. А то, что постфикс у простого типа - так это оптимизатор исправит сам, зато так красивее для глаза )
wiz29
Цитата(ViGOur @ 25.1.2012, 11:59) *
Как и обещал, код:


Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.
ViGOur
Объясни как. Можно использовать только два массива! :)
wiz29
Цитата(ViGOur @ 26.1.2012, 21:08) *
Объясни как. Можно использовать только два массива! :)


Множитель 'M' берется из линейности поиска в массиве значений, если данный массив поддерживать в сортированном виде, то поиск будет обходится в O(log2(M)), соответственно, получим более выгодную оценку для поиска.
cross
Цитата(wiz29 @ 26.1.2012, 17:07) *
Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.


Согласен (о чем и писал ранее в соседней теме про эту задачу). Единственный линейный алгоритм, который мне видится, это если значение элементов лежит в интервале от 0 до Х (где Х не велико и нам хватает памяти) заводим массив из Х элементов, в котором индекс - это величина элемента в исходном множестве, а значение - число появлений этого элемента в исходном множестве. За один проход пересчитываем все элементы и берем нужное количество минимальных.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2024 IPS, Inc.