Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ Бысрый способ получить 100 наименьших элементов

Автор: ViGOur 21.8.2010, 17:39

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

Автор: Алексей1153 21.8.2010, 19:26

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

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

Цитата(BRE @ 21.8.2010, 22:32) *
Код пока приводить не буду, интересны идеи других форумчан.


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

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

Автор: BRE 21.8.2010, 19:32

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

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

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

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

Автор: Алексей1153 21.8.2010, 19:38

вот

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

Автор: BRE 21.8.2010, 19:58

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

Автор: ViGOur 21.8.2010, 20:03

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

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

Автор: Алексей1153 21.8.2010, 20:08

Цитата(BRE @ 21.8.2010, 22:58) *
Алексей1153, что за метод такой resize у map?

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

Автор: BRE 21.8.2010, 20:16

Цитата(ViGOur @ 21.8.2010, 21:03) *
Ну вот, вы сразу 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 21.8.2010, 20:44

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

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

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


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

Автор: DEADHUNT 21.8.2010, 21:38

Цитата(Алексей1153 @ 21.8.2010, 21:44) *
хотя, если не используется шаблонный параметр, то итераторы креатор понимает

потому что правильно делать так:
template<typename T>
void F()
{
    typename std::map<T,int>::iterator it;
}

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

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

Автор: BRE 21.8.2010, 21:48

Цитата(DEADHUNT @ 21.8.2010, 22:38) *
по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов.

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

Автор: igor_bogomolov 21.8.2010, 21:49

Цитата(DEADHUNT @ 21.8.2010, 22:38) *
по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов.
Это будет медленнее. В твоём случае порядок роста O(n log n). В варианте BRE O(n)

Автор: DEADHUNT 21.8.2010, 22:00

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)

Автор: Алексей1153 21.8.2010, 22:00

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

Автор: DEADHUNT 21.8.2010, 22:04

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

Автор: Алексей1153 21.8.2010, 22:19

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

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


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

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

Цитата(ViGOur @ 21.8.2010, 23:03) *
Представьте, что нет никакого STL. Есть чистый С\С++ и все!

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

Автор: igor_bogomolov 21.8.2010, 22:24

Цитата(DEADHUNT @ 21.8.2010, 23:00) *
получаем сложность O(n)
Всё равно медленнее, чем в варианте BRE. У тебя на каждом шаге происходит сортировка массива из 100 элементов со сложностью O(nlogn). В алгоритме BRE элемент встаёт на место за время O(logn) используя бинарный поиск

Интересно, возможно ли сделать оптимальнее чем у BRE

Автор: DEADHUNT 21.8.2010, 22:38

Цитата(igor_bogomolov @ 21.8.2010, 23:24) *
Всё равно медленнее, чем в варианте 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 кстати лучше получается.

Автор: igor_bogomolov 21.8.2010, 22:54

Цитата(DEADHUNT @ 21.8.2010, 23:38) *
на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список.
Это Qt. QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).
http://doc.crossplatform.ru/qt/4.6.x/containers.html#algorithmic-complexity

Автор: DEADHUNT 21.8.2010, 23:00

Цитата(igor_bogomolov @ 21.8.2010, 23:54) *
QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).

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

Автор: igor_bogomolov 21.8.2010, 23:10

Цитата(DEADHUNT @ 22.8.2010, 0:00) *
а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).
Я не знаю ответа на этот вопрос. Почему то разработчики Qt поступили именно так, и, при небольших количествах элементов, QList - это вектор

Автор: panter_dsd 24.8.2010, 9:32

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

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


Автор: Алексей1153 24.8.2010, 10:03

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

Автор: panter_dsd 24.8.2010, 10:10

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

Автор: ViGOur 24.8.2010, 10:21

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

Автор: kwisp 24.8.2010, 10:23

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

Автор: panter_dsd 24.8.2010, 10:27

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

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

Автор: ViGOur 24.8.2010, 10:35

Цитата(panter_dsd @ 24.8.2010, 11:27) *
Блин, создание эталонного массива просто для примера. Не смотрите туда.
Я на эталон как раз потому и не смотрел.
Обновленный код тогда в студию... :)

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

Автор: panter_dsd 24.8.2010, 10:38

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

Автор: panter_dsd 24.8.2010, 13:44

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

Автор: Алексей1153 24.8.2010, 17:44

Цитата(panter_dsd @ 24.8.2010, 16:44) *
Можно функцию в виде темплейта оформить,

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

Автор: panter_dsd 24.8.2010, 17:56

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

#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 только недавно начал учить.

Автор: Алексей1153 24.8.2010, 18:54

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

Автор: panter_dsd 24.8.2010, 19:50

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

Автор: Алексей1153 24.8.2010, 19:59

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

Автор: panter_dsd 24.8.2010, 20:00

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

Автор: Алексей1153 24.8.2010, 20:06

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

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

Автор: kwisp 24.8.2010, 20:33

Цитата(Алексей1153 @ 24.8.2010, 19:54) *
4) проверяй
v.size()!=0
для любых контейнеров перед получением итератора или ссылки (.begin(),end(),[x] и так далее)

мои пять копеек.
я вот тоже в stl недавно стал вникаить.
так меерс советует в 4 совете использовать empty() вместо сравнения size() с нулем из-за постоянного времени выполнения функции.
http://lib.rus.ec/b/191841/read

Автор: Алексей1153 24.8.2010, 20:47

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

Автор: panter_dsd 25.8.2010, 6:40

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

Автор: Алексей1153 25.8.2010, 6:54

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" в списке аргументов функции

Автор: DEADHUNT 25.8.2010, 10:14

Цитата(Алексей1153 @ 25.8.2010, 7:54) *
И попробуй ещё дописать "typename" перед "std::list<T>& list_out" в списке аргументов функции

typename не надо дописывать и в первом аргументе.
и вообще typename должен применяться к qualified-id зависящего от шаблонного параметра:
Цитата
typename-specifier:
typename ::opt nested-name-specifier identifier
typename ::opt nested-name-specifier templateopt simple-template-id

Автор: panter_dsd 25.8.2010, 11:32

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

Автор: panter_dsd 25.8.2010, 18:40

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

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


Автор: ViGOur 25.8.2010, 20:10

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

Смотрите: http://www.forum.crossplatform.ru/index.php?showtopic=5486.

Автор: AD 25.8.2010, 22:46

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

Автор: DEADHUNT 25.8.2010, 22:50

Цитата(AD @ 25.8.2010, 23:46) *
Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему?

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

Автор: ViGOur 25.8.2010, 23:07

Цитата(AD @ 25.8.2010, 23:46) *
Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему?
Да пускай резвятся. Потом покажу как можно и без stl cделать. И так же быстро, если сами не решат сделать. :)

Автор: AD 26.8.2010, 8:59

Цитата(DEADHUNT @ 25.8.2010, 23:50) *
а в чём проблема, всё это можно переписать на чистый C, только сути это не изменит(просто будет больше кода и будет сложнее его понять)

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

Автор: DEADHUNT 26.8.2010, 11:19

Цитата(AD @ 26.8.2010, 9:59) *
все это выглядеть будет на чистом С++ (а не С) совсем по-другому! ;) :)

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

Автор: AD 26.8.2010, 11:58

Цитата(DEADHUNT @ 26.8.2010, 12:19) *
STL является неотъемлемой частью C++, поэтому тот код и есть чистый C++.

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

Автор: DEADHUNT 26.8.2010, 12:02

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

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

Автор: kwisp 28.8.2010, 14:25

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

Автор: DEADHUNT 28.8.2010, 16:00

Цитата(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 28.8.2010, 16:16

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


Цитата
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 25.1.2012, 10:59

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

#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 25.1.2012, 11:41

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

Автор: ViGOur 25.1.2012, 11:46

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

Автор: panter_dsd 25.1.2012, 12:04

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

Автор: ViGOur 25.1.2012, 12:42

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

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

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

Автор: Алексей1153 25.1.2012, 20:14

Цитата(panter_dsd @ 25.1.2012, 14:41) *
1. rValue = ++n; - зачем в 2 строки делать?


моё мнение - именно в 2 строки лучше. Нагляднее, плюс исключена ошибка. А то, что постфикс у простого типа - так это оптимизатор исправит сам, зато так красивее для глаза )

Автор: wiz29 26.1.2012, 16:07

Цитата(ViGOur @ 25.1.2012, 11:59) *
Как и обещал, код:


Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.

Автор: ViGOur 26.1.2012, 20:08

Объясни как. Можно использовать только два массива! :)

Автор: wiz29 27.1.2012, 8:58

Цитата(ViGOur @ 26.1.2012, 21:08) *
Объясни как. Можно использовать только два массива! :)


Множитель 'M' берется из линейности поиска в массиве значений, если данный массив поддерживать в сортированном виде, то поиск будет обходится в O(log2(M)), соответственно, получим более выгодную оценку для поиска.

Автор: cross 27.1.2012, 11:46

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


Согласен (о чем и писал ранее в соседней теме про эту задачу). Единственный линейный алгоритм, который мне видится, это если значение элементов лежит в интервале от 0 до Х (где Х не велико и нам хватает памяти) заводим массив из Х элементов, в котором индекс - это величина элемента в исходном множестве, а значение - число появлений этого элемента в исходном множестве. За один проход пересчитываем все элементы и берем нужное количество минимальных.

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)