crossplatform.ru

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

> Бысрый способ получить 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
  опции профиля:
сообщение 26.1.2012, 20:08
Сообщение #2


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

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

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




Репутация:   40  


Объясни как. Можно использовать только два массива! :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.1.2012, 8:58
Сообщение #3


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

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




Репутация:   12  


Цитата(ViGOur @ 26.1.2012, 21:08) *
Объясни как. Можно использовать только два массива! :)


Множитель 'M' берется из линейности поиска в массиве значений, если данный массив поддерживать в сортированном виде, то поиск будет обходится в O(log2(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
- - 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




RSS Текстовая версия Сейчас: 28.3.2024, 23:43