crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

7 страниц V   1 2 3 > »   
Ответить в данную темуНачать новую тему
> Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более
ViGOur
  опции профиля:
сообщение 21.8.2010, 17:39
Сообщение #1


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 21.8.2010, 19:26
Сообщение #2


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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


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

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


Сообщение отредактировал Алексей1153 - 21.8.2010, 19:49
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
BRE
  опции профиля:
сообщение 21.8.2010, 19:32
Сообщение #3


Профессионал
*****

Группа: Участник
Сообщений: 1112
Регистрация: 6.3.2009
Из: Ростов-на-Дону
Пользователь №: 591

Спасибо сказали: 264 раз(а)




Репутация:   44  


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

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

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

Код пока приводить не буду, интересны идеи других форумчан.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 21.8.2010, 19:38
Сообщение #4


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


вот

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

Сообщение отредактировал Алексей1153 - 21.8.2010, 22:16
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
BRE
  опции профиля:
сообщение 21.8.2010, 19:58
Сообщение #5


Профессионал
*****

Группа: Участник
Сообщений: 1112
Регистрация: 6.3.2009
Из: Ростов-на-Дону
Пользователь №: 591

Спасибо сказали: 264 раз(а)




Репутация:   44  


Алексей1153, что за метод такой resize у map?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 21.8.2010, 20:03
Сообщение #6


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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

Да на собеседовании задали, я ответил неправильно, только потом додумался как это можно сделать.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 21.8.2010, 20:08
Сообщение #7


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

упс, забыл потестить ) Это только идея. Сейчас подправлю
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
BRE
  опции профиля:
сообщение 21.8.2010, 20:16
Сообщение #8


Профессионал
*****

Группа: Участник
Сообщений: 1112
Регистрация: 6.3.2009
Из: Ростов-на-Дону
Пользователь №: 591

Спасибо сказали: 264 раз(а)




Репутация:   44  


Цитата(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
Сообщение #9


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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

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


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

Сообщение отредактировал Алексей1153 - 21.8.2010, 21:01
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
DEADHUNT
  опции профиля:
сообщение 21.8.2010, 21:38
Сообщение #10


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


Цитата(Алексей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
Сообщение #11


Профессионал
*****

Группа: Участник
Сообщений: 1112
Регистрация: 6.3.2009
Из: Ростов-на-Дону
Пользователь №: 591

Спасибо сказали: 264 раз(а)




Репутация:   44  


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

Как я уже писал в 3 посте, это очень долго.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
igor_bogomolov
  опции профиля:
сообщение 21.8.2010, 21:49
Сообщение #12


Профессионал
*****

Группа: Сомодератор
Сообщений: 1215
Регистрация: 22.3.2009
Из: Саратов
Пользователь №: 630

Спасибо сказали: 235 раз(а)




Репутация:   29  


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


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


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
Сообщение #14


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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
Сообщение #15


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


Алексей1153, как то у тебя нагромаждённо получается, наверняка можно было проще твой вариант сделать.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 21.8.2010, 22:19
Сообщение #16


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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 , то реализацию контейнера в виде класса (или его "размазанную" по коду процедуры реализацию) придётся также сочинять. И отлаживать

Сообщение отредактировал Алексей1153 - 21.8.2010, 22:10
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
igor_bogomolov
  опции профиля:
сообщение 21.8.2010, 22:24
Сообщение #17


Профессионал
*****

Группа: Сомодератор
Сообщений: 1215
Регистрация: 22.3.2009
Из: Саратов
Пользователь №: 630

Спасибо сказали: 235 раз(а)




Репутация:   29  


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

Интересно, возможно ли сделать оптимальнее чем у BRE
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
DEADHUNT
  опции профиля:
сообщение 21.8.2010, 22:38
Сообщение #18


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


Цитата(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
Сообщение #19


Профессионал
*****

Группа: Сомодератор
Сообщений: 1215
Регистрация: 22.3.2009
Из: Саратов
Пользователь №: 630

Спасибо сказали: 235 раз(а)




Репутация:   29  


Цитата(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
  опции профиля:
сообщение 21.8.2010, 23:00
Сообщение #20


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


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

а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
igor_bogomolov
  опции профиля:
сообщение 21.8.2010, 23:10
Сообщение #21


Профессионал
*****

Группа: Сомодератор
Сообщений: 1215
Регистрация: 22.3.2009
Из: Саратов
Пользователь №: 630

Спасибо сказали: 235 раз(а)




Репутация:   29  


Цитата(DEADHUNT @ 22.8.2010, 0:00) *
а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).
Я не знаю ответа на этот вопрос. Почему то разработчики Qt поступили именно так, и, при небольших количествах элементов, QList - это вектор
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 9:32
Сообщение #22


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


А вот мое решение.
    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
Сообщение #23


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

Сообщение отредактировал Алексей1153 - 24.8.2010, 10:04
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 10:10
Сообщение #24


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Это только для проверки. Он и является нужным контейнером.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 24.8.2010, 10:21
Сообщение #25


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


panter_dsd, в твоем случае не оптимально по скорости.
При добавлении нового элемента вектора, вектор расширяется, выделяется память для его нового элемента и копируются все элементы вектора в новый участок памяти. (вспомни, почему нельзя пользоваться полученными итераторами на элемент вектора, после добавления нового элемента, пускай даже в конец вектора).
При удалении первого элемента вектора "v" что происходит со всем вектором? Вроде как все элементы вектора сдвигаются. Насчет перераспределения памяти не помню, что происходит.
А так как ты для примера выбрал самый не трудоемкий случай, то это в принципе очень не критично, но если поменять цикл заполнения etalon от 0 до ... то это будет происходить в каждой итерации цикла.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 24.8.2010, 10:23
Сообщение #26


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


panter_dsd,
он имеет ввиду что вектор заполнить можно значительно быстрее чем делаешь ты.
при каждом твоем push_back происходит выделение памяти. хотя память под элементы можно выделить одним махом при создании вектора.
ну тут долгая песня
Скот Меерс в руки и вперед.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 10:27
Сообщение #27


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


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

Блин, создание эталонного массива просто для примера. Не смотрите туда.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 24.8.2010, 10:35
Сообщение #28


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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

p.s. эталон разумеется оставь, он для наглядности, только поменяй его заполнение на более сложный случай, когда последующее число больше предыдущего.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 10:38
Сообщение #29


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Я сейчас с телефона , позже выложу код.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 13:44
Сообщение #30


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


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

Сообщение отредактировал panter_dsd - 24.8.2010, 16:48
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 24.8.2010, 17:44
Сообщение #31


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

а ты выдели как отдельную функцию, я в шаблон переделаю )
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 17:56
Сообщение #32


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Готово. Сделал для любого кол-ва элементов. Хотелось бы еще для любого типа.
#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
Сообщение #33


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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


Сообщение отредактировал Алексей1153 - 24.8.2010, 20:07
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 19:50
Сообщение #34


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


1. Учту.
2. Согласен.
4. Учту.
5. Не согласен. Можно и нужно, если контейнер не изменяется. Зачем дергать функцию на каждой итерации?
6. Вполне получается. Что смущает?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 24.8.2010, 19:59
Сообщение #35


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


5 - в релизе там не будет функции :) Так что, дёргай без опаски
6 - ну, раз получается, тогда пользуйся на здоровье. У меня компилятор брыкается )) Ну оно и понятно
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 20:00
Сообщение #36


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


6. Компилятор ничего не говорит. По документации тоже можно, вроде бы. Завтра перепроверю.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 24.8.2010, 20:06
Сообщение #37


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


всё, 6 - мой косяк )) Исправил . Пропустил начальный итератор и не обратил внимание
    list_out.insert (list_out.begin() ,v.begin (), v.begin () + n);


Сообщение отредактировал Алексей1153 - 24.8.2010, 20:08
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 24.8.2010, 20:33
Сообщение #38


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


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

мои пять копеек.
я вот тоже в stl недавно стал вникаить.
так меерс советует в 4 совете использовать empty() вместо сравнения size() с нулем из-за постоянного времени выполнения функции.
stl
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 24.8.2010, 20:47
Сообщение #39


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


kwisp, ок, учтём ) Только обычно у меня такой вызов был не в цикле, а list ещё не доводилось пользоваться почему то ))
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 25.8.2010, 6:40
Сообщение #40


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Алексей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
Сообщение #41


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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
Сообщение #42


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


Цитата(Алексей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


Сообщение отредактировал DEADHUNT - 25.8.2010, 10:15
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 25.8.2010, 11:32
Сообщение #43


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Выкидывание 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
Сообщение #44


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Заканчиваем с оффтопом.
Вот последняя редакция, еще есть замечания?
#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
Сообщение #45


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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

Смотрите: Что есть что, с чем можно и куда....
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
AD
  опции профиля:
сообщение 25.8.2010, 22:46
Сообщение #46


Профессионал
*****

Группа: Участник
Сообщений: 2003
Регистрация: 4.2.2008
Из: S-Petersburg
Пользователь №: 84

Спасибо сказали: 70 раз(а)




Репутация:   17  


Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
DEADHUNT
  опции профиля:
сообщение 25.8.2010, 22:50
Сообщение #47


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


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

а в чём проблема, всё это можно переписать на чистый C, только сути это не изменит(просто будет больше кода и будет сложнее его понять)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 25.8.2010, 23:07
Сообщение #48


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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


Профессионал
*****

Группа: Участник
Сообщений: 2003
Регистрация: 4.2.2008
Из: S-Petersburg
Пользователь №: 84

Спасибо сказали: 70 раз(а)




Репутация:   17  


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

Да в том и проблема, что без использования стандартных средств для красивого и оптимального решения, все это выглядеть будет на чистом С++ (а не С) совсем по-другому! ;) :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
DEADHUNT
  опции профиля:
сообщение 26.8.2010, 11:19
Сообщение #50


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


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

STL является неотъемлемой частью C++, поэтому тот код и есть чистый C++.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
AD
  опции профиля:
сообщение 26.8.2010, 11:58
Сообщение #51


Профессионал
*****

Группа: Участник
Сообщений: 2003
Регистрация: 4.2.2008
Из: S-Petersburg
Пользователь №: 84

Спасибо сказали: 70 раз(а)




Репутация:   17  


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

Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется! ;)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
DEADHUNT
  опции профиля:
сообщение 26.8.2010, 12:02
Сообщение #52


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


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

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

Сообщение отредактировал DEADHUNT - 26.8.2010, 12:02
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 28.8.2010, 14:25
Сообщение #53


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


nth_element() - не катит?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
DEADHUNT
  опции профиля:
сообщение 28.8.2010, 16:00
Сообщение #54


Активный участник
***

Группа: Участник
Сообщений: 430
Регистрация: 15.4.2009
Пользователь №: 686

Спасибо сказали: 26 раз(а)




Репутация:   2  


Цитата(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
Сообщение #55


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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


Цитата
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
  опции профиля:
сообщение 25.1.2012, 10:59
Сообщение #56


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Как и обещал, код:
#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
Сообщение #57


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


1. rValue = ++n; - зачем в 2 строки делать?
2. std::vector<int> collMin( coll.begin(), coll.begin() + n); все же лучше.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 25.1.2012, 11:46
Сообщение #58


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


1. Кому как нравится. :)
2. Чем лучше?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 25.1.2012, 12:04
Сообщение #59


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


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

Сообщение отредактировал panter_dsd - 25.1.2012, 12:05
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 25.1.2012, 12:42
Сообщение #60


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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

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

Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение.
Тоесть только для наглядности! :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 25.1.2012, 20:14
Сообщение #61


фрилансер
******

Группа: Участник
Сообщений: 2944
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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


моё мнение - именно в 2 строки лучше. Нагляднее, плюс исключена ошибка. А то, что постфикс у простого типа - так это оптимизатор исправит сам, зато так красивее для глаза )
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 26.1.2012, 16:07
Сообщение #62


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


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


Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 26.1.2012, 20:08
Сообщение #63


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Объясни как. Можно использовать только два массива! :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.1.2012, 8:58
Сообщение #64


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


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


Множитель 'M' берется из линейности поиска в массиве значений, если данный массив поддерживать в сортированном виде, то поиск будет обходится в O(log2(M)), соответственно, получим более выгодную оценку для поиска.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
cross
  опции профиля:
сообщение 27.1.2012, 11:46
Сообщение #65


Новичок


Группа: Новичок
Сообщений: 2
Регистрация: 24.6.2010
Пользователь №: 1833

Спасибо сказали: 0 раз(а)




Репутация:   0  


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


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

7 страниц V   1 2 3 > » 
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0


RSS Рейтинг@Mail.ru Текстовая версия Сейчас: 24.7.2025, 1:23