crossplatform.ru

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

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


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

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

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




Репутация:   40  


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


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

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


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

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


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

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

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




Репутация:   40  


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

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


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

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


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

Группа: Участник
Сообщений: 2886
Регистрация: 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 элементов.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

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


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




RSS Текстовая версия Сейчас: 18.10.2019, 1:34