 Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
Здравствуйте, гость ( Вход | Регистрация )
ViGOur опции профиля:
|
 21.8.2010, 17:39
Сообщение
#1
|
 Мастер  Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация:  40 
 |
Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей? |
 |
  
|
 |
Ответов
|
ViGOur опции профиля:
|
25.1.2012, 12:42
Сообщение
#2
|
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40
|
1. в данном случае точно разницы нет постфиксный инкремент или префиксный!
 2. То, что избавляет от лишнего заполнения нолями, согласен. Но ИМХО мой вариант наглядней будет. Всё равно, можно сказать, что ты выиграл M процессорных тактов на заполнении нолями и столько же можно убрать из цикла! Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение. Тоесть только для наглядности! |
|
|
|
Сообщений в этой теме
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 Алексей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 Алексей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 |
Теги
Нет тегов для показа
14 чел. читают эту тему (гостей: 14, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 17.2.2025, 20:58 |