 Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
Здравствуйте, гость ( Вход | Регистрация )
ViGOur опции профиля:
|
 21.8.2010, 17:39
Сообщение
#1
|
 Мастер  Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация:  40 
 |
Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей? |
 |
  
|
 |
Ответов
|
BRE опции профиля:
|
21.8.2010, 19:32
Сообщение
#2
|
 Профессионал Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: 44
|
ViGOur, я так понимаю это одно из заданий с собеседования?
 Если не секрет, какие мысли были у тебя? Вот задача. Очевидный шаг это отсортировать массив и взять первые 100 значений. Посидел, подумал, набросал тестовый примерчик и оказалось, что даже без оптимизации кода, можно написать алгоритм который это делает значительно быстрее (на время не тестил и так все видно). Использовал контейнеры Qt. Функция состоит из 13 строк. Код пока приводить не буду, интересны идеи других форумчан. |
|
|
|
Сообщений в этой теме
ViGOur Бысрый способ получить 100 наименьших элементов 21.8.2010, 17:39
Алексей1153 А массив где находится? Отсортирован ли? Каков раз... 21.8.2010, 19:26 Алексей1153 вот
<удалил это безобразие> 21.8.2010, 19:38 BRE Алексей1153, что за метод такой resize у map? 21.8.2010, 19:58 ViGOur Ну вот, вы сразу map и прочее, с map это халява.
П... 21.8.2010, 20:03
BRE Цитата(ViGOur @ 21.8.2010, 21:03) Ну вот,... 21.8.2010, 20:16 Алексей1153 Цитата(BRE @ 21.8.2010, 22:58) Алексей115... 21.8.2010, 20:08 Алексей1153 мда, с мапом затея не очень оказалась - итератор н... 21.8.2010, 20:44 DEADHUNT Цитата(Алексей1153 @ 21.8.2010, 21:44) хо... 21.8.2010, 21:38 BRE Цитата(DEADHUNT @ 21.8.2010, 22:38) по са... 21.8.2010, 21:48 igor_bogomolov Цитата(DEADHUNT @ 21.8.2010, 22:38) по са... 21.8.2010, 21:49 DEADHUNT std::vector<int> min_elements... 21.8.2010, 22:00 Алексей1153 DEADHUNT, наверное, правильНЕЕ , но студия понимае... 21.8.2010, 22:00 DEADHUNT Алексей1153, как то у тебя нагромаждённо получаетс... 21.8.2010, 22:04 Алексей1153 igor_bogomolov, а вот пример использования, которы... 21.8.2010, 22:19 igor_bogomolov Цитата(DEADHUNT @ 21.8.2010, 23:00) получ... 21.8.2010, 22:24 DEADHUNT Цитата(igor_bogomolov @ 21.8.2010, 23:24)... 21.8.2010, 22:38 igor_bogomolov Цитата(DEADHUNT @ 21.8.2010, 23:38) на са... 21.8.2010, 22:54 DEADHUNT Цитата(igor_bogomolov @ 21.8.2010, 23:54)... 21.8.2010, 23:00 igor_bogomolov Цитата(DEADHUNT @ 22.8.2010, 0:00) а смыс... 21.8.2010, 23:10 panter_dsd А вот мое решение.
std::vector <int... 24.8.2010, 9:32 Алексей1153 тут одно только заполнение вектора etalon (зачем-т... 24.8.2010, 10:03 panter_dsd Это только для проверки. Он и является нужным конт... 24.8.2010, 10:10 ViGOur panter_dsd, в твоем случае не оптимально по скорос... 24.8.2010, 10:21 kwisp panter_dsd,
он имеет ввиду что вектор заполнить м... 24.8.2010, 10:23 panter_dsd Согласен. Вставку не учел. На счет удаления знал, ... 24.8.2010, 10:27 ViGOur Цитата(panter_dsd @ 24.8.2010, 11:27) Бли... 24.8.2010, 10:35 panter_dsd Я сейчас с телефона , позже выложу код. 24.8.2010, 10:38 panter_dsd #include <iostream>
#include <vector... 24.8.2010, 13:44 Алексей1153 Цитата(panter_dsd @ 24.8.2010, 16:44) Мож... 24.8.2010, 17:44 panter_dsd Готово. Сделал для любого кол-ва элементов. Хотело... 24.8.2010, 17:56 Алексей1153 1)
Цитатаif (n >= v.size ())
"size()... 24.8.2010, 18:54 panter_dsd 1. Учту.
2. Согласен.
4. Учту.
5. Не согласен. Мо... 24.8.2010, 19:50 panter_dsd Алексей1153, что-то не компилируется твой код.
g++... 25.8.2010, 6:40 Алексей1153 5 - в релизе там не будет функции Так что, дёргай... 24.8.2010, 19:59 panter_dsd 6. Компилятор ничего не говорит. По документации т... 24.8.2010, 20:00 Алексей1153 всё, 6 - мой косяк )) Исправил . Пропустил начальн... 24.8.2010, 20:06 kwisp Цитата(Алексей1153 @ 24.8.2010, 19:54) 4)... 24.8.2010, 20:33 Алексей1153 kwisp, ок, учтём ) Только обычно у меня такой вызо... 24.8.2010, 20:47 Алексей1153 panter_dsd, я в студии делал - там компилится. А т... 25.8.2010, 6:54 DEADHUNT Цитата(Алексей1153 @ 25.8.2010, 7:54) И п... 25.8.2010, 10:14 panter_dsd Выкидывание typename помогло.
Алексей1153, что-то ... 25.8.2010, 11:32 ViGOur Перенес флейм в другую тему, В любимый Алексей1153... 25.8.2010, 20:10 AD Эдик, я вот одного не понял. Ты поставил условие -... 25.8.2010, 22:46 DEADHUNT Цитата(AD @ 25.8.2010, 23:46) Эдик, я вот... 25.8.2010, 22:50 AD Цитата(DEADHUNT @ 25.8.2010, 23:50) а в ч... 26.8.2010, 8:59 ViGOur Цитата(AD @ 25.8.2010, 23:46) Эдик, я вот... 25.8.2010, 23:07 DEADHUNT Цитата(AD @ 26.8.2010, 9:59) все это выгл... 26.8.2010, 11:19 AD Цитата(DEADHUNT @ 26.8.2010, 12:19) STL я... 26.8.2010, 11:58 DEADHUNT Цитата(AD @ 26.8.2010, 12:58) Ну это уже ... 26.8.2010, 12:02 kwisp nth_element() - не катит? 28.8.2010, 14:25 DEADHUNT Цитата(kwisp @ 28.8.2010, 15:25) nth_elem... 28.8.2010, 16:00 Алексей1153 Цитатасложность - линейная
ЦитатаThe nth_element ... 28.8.2010, 16:16 ViGOur Как и обещал, код:
#include <algorithm>
#i... 25.1.2012, 10:59 wiz29 Цитата(ViGOur @ 25.1.2012, 11:59) Как и о... 26.1.2012, 16:07 panter_dsd 1. rValue = ++n; - зачем в 2 строки делать?
2. std... 25.1.2012, 11:41 ViGOur 1. Кому как нравится.
2. Чем лучше? 25.1.2012, 11:46 panter_dsd 1. Если хочется в 2 строки, то хотя бы префиксную ... 25.1.2012, 12:04 ViGOur 1. в данном случае точно разницы нет постфиксный и... 25.1.2012, 12:42 Алексей1153 Цитата(panter_dsd @ 25.1.2012, 14:41) 1. ... 25.1.2012, 20:14 ViGOur Объясни как. Можно использовать только два массива... 26.1.2012, 20:08 wiz29 Цитата(ViGOur @ 26.1.2012, 21:08) Объясни... 27.1.2012, 8:58 cross Цитата(wiz29 @ 26.1.2012, 17:07) Сложност... 27.1.2012, 11:46 |
Теги
Нет тегов для показа
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 10.4.2025, 18:31 |