crossplatform.ru

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

7 страниц V  « < 4 5 6 7 >  
Ответить в данную темуНачать новую тему
> Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более
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


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

Группа: Участник
Сообщений: 2900
Регистрация: 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


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

Группа: Модератор
Сообщений: 3291
Регистрация: 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


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

Группа: Модератор
Сообщений: 3291
Регистрация: 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


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

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

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




Репутация:   40  


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

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

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

7 страниц V  « < 4 5 6 7 >
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


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




RSS Текстовая версия Сейчас: 14.8.2020, 2:37