 Бысрый способ получить 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 опции профиля:
|
28.8.2010, 16:16
Сообщение
#2
|
 фрилансер Группа: Участник Сообщений: 2939 Регистрация: 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 Бысрый способ получить 100 наименьших элементов 21.8.2010, 17:39
Алексей1153 А массив где находится? Отсортирован ли? Каков раз... 21.8.2010, 19:26 BRE ViGOur, я так понимаю это одно из заданий с собесе... 21.8.2010, 19:32 Алексей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 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
|
|
Текстовая версия | Сейчас: 25.4.2024, 17:01 |