Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Бысрый способ получить 100 наименьших элементов
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
Страницы: 1, 2
ViGOur
Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей?
Алексей1153
А массив где находится? Отсортирован ли? Каков размер элементов?

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


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

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

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

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

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

<удалил это безобразие>
BRE
Алексей1153, что за метод такой resize у map?
ViGOur
Ну вот, вы сразу map и прочее, с map это халява.
Представьте, что нет никакого STL. Есть чистый С\С++ и все!

Да на собеседовании задали, я ответил неправильно, только потом додумался как это можно сделать.
Алексей1153
Цитата(BRE @ 21.8.2010, 22:58) *
Алексей1153, что за метод такой resize у map?

упс, забыл потестить ) Это только идея. Сейчас подправлю
BRE
Цитата(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
мда, с мапом затея не очень оказалась - итератор на наибольший элемент хрен так сразу получишь ) А искать его каждый раз - будет накладно

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

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


хотя, если не используется шаблонный параметр, то итераторы креатор понимает
DEADHUNT
Цитата(Алексей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
Цитата(DEADHUNT @ 21.8.2010, 22:38) *
по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов.

Как я уже писал в 3 посте, это очень долго.
igor_bogomolov
Цитата(DEADHUNT @ 21.8.2010, 22:38) *
по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов.
Это будет медленнее. В твоём случае порядок роста O(n log n). В варианте BRE O(n)
DEADHUNT
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
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
Алексей1153, как то у тебя нагромаждённо получается, наверняка можно было проще твой вариант сделать.
Алексей1153
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
Цитата(DEADHUNT @ 21.8.2010, 23:00) *
получаем сложность O(n)
Всё равно медленнее, чем в варианте BRE. У тебя на каждом шаге происходит сортировка массива из 100 элементов со сложностью O(nlogn). В алгоритме BRE элемент встаёт на место за время O(logn) используя бинарный поиск

Интересно, возможно ли сделать оптимальнее чем у BRE
DEADHUNT
Цитата(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
Цитата(DEADHUNT @ 21.8.2010, 23:38) *
на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список.
Это Qt. QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).
http://doc.crossplatform.ru/qt/4.6.x/conta...hmic-complexity
DEADHUNT
Цитата(igor_bogomolov @ 21.8.2010, 23:54) *
QList - это не двусвязный список, и доступ до элемента осуществляется за O(1).

а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).
igor_bogomolov
Цитата(DEADHUNT @ 22.8.2010, 0:00) *
а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).
Я не знаю ответа на этот вопрос. Почему то разработчики Qt поступили именно так, и, при небольших количествах элементов, QList - это вектор
panter_dsd
А вот мое решение.
    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
тут одно только заполнение вектора etalon (зачем-то) всё время покроет )
panter_dsd
Это только для проверки. Он и является нужным контейнером.
ViGOur
panter_dsd, в твоем случае не оптимально по скорости.
При добавлении нового элемента вектора, вектор расширяется, выделяется память для его нового элемента и копируются все элементы вектора в новый участок памяти. (вспомни, почему нельзя пользоваться полученными итераторами на элемент вектора, после добавления нового элемента, пускай даже в конец вектора).
При удалении первого элемента вектора "v" что происходит со всем вектором? Вроде как все элементы вектора сдвигаются. Насчет перераспределения памяти не помню, что происходит.
А так как ты для примера выбрал самый не трудоемкий случай, то это в принципе очень не критично, но если поменять цикл заполнения etalon от 0 до ... то это будет происходить в каждой итерации цикла.
kwisp
panter_dsd,
он имеет ввиду что вектор заполнить можно значительно быстрее чем делаешь ты.
при каждом твоем push_back происходит выделение памяти. хотя память под элементы можно выделить одним махом при создании вектора.
ну тут долгая песня
Скот Меерс в руки и вперед.
panter_dsd
Согласен. Вставку не учел. На счет удаления знал, но решил пренебречь. заменяем вектор на лист и избавляемся от этого.

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

p.s. эталон разумеется оставь, он для наглядности, только поменяй его заполнение на более сложный случай, когда последующее число больше предыдущего.
panter_dsd
Я сейчас с телефона , позже выложу код.
panter_dsd
#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
Цитата(panter_dsd @ 24.8.2010, 16:44) *
Можно функцию в виде темплейта оформить,

а ты выдели как отдельную функцию, я в шаблон переделаю )
panter_dsd
Готово. Сделал для любого кол-ва элементов. Хотелось бы еще для любого типа.
#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
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
1. Учту.
2. Согласен.
4. Учту.
5. Не согласен. Можно и нужно, если контейнер не изменяется. Зачем дергать функцию на каждой итерации?
6. Вполне получается. Что смущает?
Алексей1153
5 - в релизе там не будет функции :) Так что, дёргай без опаски
6 - ну, раз получается, тогда пользуйся на здоровье. У меня компилятор брыкается )) Ну оно и понятно
panter_dsd
6. Компилятор ничего не говорит. По документации тоже можно, вроде бы. Завтра перепроверю.
Алексей1153
всё, 6 - мой косяк )) Исправил . Пропустил начальный итератор и не обратил внимание
    list_out.insert (list_out.begin() ,v.begin (), v.begin () + n);
kwisp
Цитата(Алексей1153 @ 24.8.2010, 19:54) *
4) проверяй
v.size()!=0
для любых контейнеров перед получением итератора или ссылки (.begin(),end(),[x] и так далее)

мои пять копеек.
я вот тоже в stl недавно стал вникаить.
так меерс советует в 4 совете использовать empty() вместо сравнения size() с нулем из-за постоянного времени выполнения функции.
stl
Алексей1153
kwisp, ок, учтём ) Только обычно у меня такой вызов был не в цикле, а list ещё не доводилось пользоваться почему то ))
panter_dsd
Алексей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
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
Цитата(Алексей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
Выкидывание typename помогло.
Алексей1153, что-то мне интересно. С шаблонами хорошо знаком, а компилятор от IDE и библиотеки отделить не можешь...
Я компилировал g++ (Gentoo 4.4.4-r1 p1.1, pie-0.4.5) 4.4.4. Т.е. не студийным компилером.
panter_dsd
Заканчиваем с оффтопом.
Вот последняя редакция, еще есть замечания?
#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
Перенес флейм в другую тему, В любимый Алексей1153 раздел "Треп", чтобы потрепаться. :)

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

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

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

STL является неотъемлемой частью C++, поэтому тот код и есть чистый C++.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2018 IPS, Inc.