![]() |
Здравствуйте, гость ( Вход | Регистрация )
![]() ![]() |
![]() |
ViGOur |
![]()
Сообщение
#1
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей? |
|
|
Алексей1153 |
![]()
Сообщение
#2
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
А массив где находится? Отсортирован ли? Каков размер элементов?
пока свернул, чтобы Код пока приводить не буду, интересны идеи других форумчан. Раскрывающийся текст для неотсортированного случая можно, к примеру, так: берём мап, начинаем заполнять всеми по очереди элементами. Когда размер мапа перешёл от 100 к 101, удаляем наибольший элемент - и так далее. Щас попробую в коде выразить мысль )) Сообщение отредактировал Алексей1153 - 21.8.2010, 19:49 |
|
|
BRE |
![]()
Сообщение
#3
|
![]() Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: ![]() ![]() ![]() |
ViGOur, я так понимаю это одно из заданий с собеседования?
![]() Если не секрет, какие мысли были у тебя? Вот задача. Очевидный шаг это отсортировать массив и взять первые 100 значений. Посидел, подумал, набросал тестовый примерчик и оказалось, что даже без оптимизации кода, можно написать алгоритм который это делает значительно быстрее (на время не тестил и так все видно). Использовал контейнеры Qt. Функция состоит из 13 строк. Код пока приводить не буду, интересны идеи других форумчан. |
|
|
Алексей1153 |
![]()
Сообщение
#4
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
вот
<удалил это безобразие> Сообщение отредактировал Алексей1153 - 21.8.2010, 22:16 |
|
|
BRE |
![]()
Сообщение
#5
|
![]() Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: ![]() ![]() ![]() |
Алексей1153, что за метод такой resize у map?
|
|
|
ViGOur |
![]()
Сообщение
#6
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
Ну вот, вы сразу map и прочее, с map это халява.
Представьте, что нет никакого STL. Есть чистый С\С++ и все! Да на собеседовании задали, я ответил неправильно, только потом додумался как это можно сделать. |
|
|
Алексей1153 |
![]()
Сообщение
#7
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
BRE |
![]()
Сообщение
#8
|
![]() Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: ![]() ![]() ![]() |
Ну вот, вы сразу map и прочее, с map это халява. Представьте, что нет никакого STL. Есть чистый С\С++ и все! Да на собеседовании задали, я ответил неправильно, только потом додумался как это можно сделать. Ну по большому счету не важно на чем писать, мы же алгоритм обсуждаем. Мои мысли.
|
|
|
Алексей1153 |
![]()
Сообщение
#9
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
мда, с мапом затея не очень оказалась - итератор на наибольший элемент хрен так сразу получишь ) А искать его каждый раз - будет накладно
А ещё, креатор отказался понимать итераторы ![]()
хотя, если не используется шаблонный параметр, то итераторы креатор понимает Сообщение отредактировал Алексей1153 - 21.8.2010, 21:01 |
|
|
DEADHUNT |
![]()
Сообщение
#10
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
хотя, если не используется шаблонный параметр, то итераторы креатор понимает потому что правильно делать так:
потому что std::map зависит от параметра шаблона T. может получиться что у std::map не будет typedef iterator(или iterator не будет типом), поэтому надо указать компилятору что iterator - это имя типа. по сабжу: можно отсортировать(например qsort) и взять первые 100 элементов. |
|
|
BRE |
![]()
Сообщение
#11
|
![]() Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
igor_bogomolov |
![]()
Сообщение
#12
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Сомодератор Сообщений: 1215 Регистрация: 22.3.2009 Из: Саратов Пользователь №: 630 Спасибо сказали: 235 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
DEADHUNT |
![]()
Сообщение
#13
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
получаем сложность O(n) |
|
|
Алексей1153 |
![]()
Сообщение
#14
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
DEADHUNT, наверное, правильНЕЕ , но студия понимает и так
![]() Кстати, победил:
|
|
|
DEADHUNT |
![]()
Сообщение
#15
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
Алексей1153, как то у тебя нагромаждённо получается, наверняка можно было проще твой вариант сделать.
|
|
|
Алексей1153 |
![]()
Сообщение
#16
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
igor_bogomolov, а вот пример использования, который креатор тоже не прожевал, а студия понимает нормально. Тут то что не так ))
DEADHUNT, может и можно. Покажи, я готов учиться Кстати, о птичках. Потом интересно будет сравнить по скорости работы ) Представьте, что нет никакого STL. Есть чистый С\С++ и все! чистый C++ содержит STL , вообще то ) Ну а если задача стоИт - без STL , то реализацию контейнера в виде класса (или его "размазанную" по коду процедуры реализацию) придётся также сочинять. И отлаживать Сообщение отредактировал Алексей1153 - 21.8.2010, 22:10 |
|
|
igor_bogomolov |
![]()
Сообщение
#17
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Сомодератор Сообщений: 1215 Регистрация: 22.3.2009 Из: Саратов Пользователь №: 630 Спасибо сказали: 235 раз(а) Репутация: ![]() ![]() ![]() |
получаем сложность O(n) Всё равно медленнее, чем в варианте BRE. У тебя на каждом шаге происходит сортировка массива из 100 элементов со сложностью O(nlogn). В алгоритме BRE элемент встаёт на место за время O(logn) используя бинарный поискИнтересно, возможно ли сделать оптимальнее чем у BRE |
|
|
DEADHUNT |
![]()
Сообщение
#18
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
Всё равно медленнее, чем в варианте BRE. У тебя на каждом шаге происходит сортировка массива из 100 элементов со сложностью O(nlogn). В алгоритме BRE элемент встаёт на место за время O(logn) используя бинарный поиск Интересно, возможно ли сделать оптимальнее чем у BRE на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список. сортировка на самом деле лишняя, так как достаточно найти место куда вставить и всё.
без Qt кстати лучше получается. |
|
|
igor_bogomolov |
![]()
Сообщение
#19
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Сомодератор Сообщений: 1215 Регистрация: 22.3.2009 Из: Саратов Пользователь №: 630 Спасибо сказали: 235 раз(а) Репутация: ![]() ![]() ![]() |
на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список. Это Qt. QList - это не двусвязный список, и доступ до элемента осуществляется за O(1). http://doc.crossplatform.ru/qt/4.6.x/conta...hmic-complexity |
|
|
DEADHUNT |
![]()
Сообщение
#20
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
igor_bogomolov |
![]()
Сообщение
#21
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Сомодератор Сообщений: 1215 Регистрация: 22.3.2009 Из: Саратов Пользователь №: 630 Спасибо сказали: 235 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
panter_dsd |
![]()
Сообщение
#22
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
А вот мое решение.
|
|
|
Алексей1153 |
![]()
Сообщение
#23
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
тут одно только заполнение вектора etalon (зачем-то) всё время покроет )
Сообщение отредактировал Алексей1153 - 24.8.2010, 10:04 |
|
|
panter_dsd |
![]()
Сообщение
#24
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Это только для проверки. Он и является нужным контейнером.
|
|
|
ViGOur |
![]()
Сообщение
#25
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
panter_dsd, в твоем случае не оптимально по скорости.
При добавлении нового элемента вектора, вектор расширяется, выделяется память для его нового элемента и копируются все элементы вектора в новый участок памяти. (вспомни, почему нельзя пользоваться полученными итераторами на элемент вектора, после добавления нового элемента, пускай даже в конец вектора). При удалении первого элемента вектора "v" что происходит со всем вектором? Вроде как все элементы вектора сдвигаются. Насчет перераспределения памяти не помню, что происходит. А так как ты для примера выбрал самый не трудоемкий случай, то это в принципе очень не критично, но если поменять цикл заполнения etalon от 0 до ... то это будет происходить в каждой итерации цикла. |
|
|
kwisp |
![]()
Сообщение
#26
|
![]() астарожна ынтжинэр ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1404 Регистрация: 26.11.2008 Из: ТаганрогРодинаЧехова Пользователь №: 435 Спасибо сказали: 113 раз(а) Репутация: ![]() ![]() ![]() |
panter_dsd,
он имеет ввиду что вектор заполнить можно значительно быстрее чем делаешь ты. при каждом твоем push_back происходит выделение памяти. хотя память под элементы можно выделить одним махом при создании вектора. ну тут долгая песня Скот Меерс в руки и вперед. |
|
|
panter_dsd |
![]()
Сообщение
#27
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Согласен. Вставку не учел. На счет удаления знал, но решил пренебречь. заменяем вектор на лист и избавляемся от этого.
Блин, создание эталонного массива просто для примера. Не смотрите туда. |
|
|
ViGOur |
![]()
Сообщение
#28
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
Блин, создание эталонного массива просто для примера. Не смотрите туда. Я на эталон как раз потому и не смотрел.Обновленный код тогда в студию... ![]() p.s. эталон разумеется оставь, он для наглядности, только поменяй его заполнение на более сложный случай, когда последующее число больше предыдущего. |
|
|
panter_dsd |
![]()
Сообщение
#29
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Я сейчас с телефона , позже выложу код.
|
|
|
panter_dsd |
![]()
Сообщение
#30
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Вот измененный код. Коррективы приветствуются. Можно функцию в виде темплейта оформить, но пока не знаю как, еще не дошел до этого. ![]() Только заметил, что ищу 100 максимальных значений, лопухнулся. Ну, принцип тот же самый. Сообщение отредактировал panter_dsd - 24.8.2010, 16:48 |
|
|
Алексей1153 |
![]()
Сообщение
#31
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
panter_dsd |
![]()
Сообщение
#32
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Готово. Сделал для любого кол-ва элементов. Хотелось бы еще для любого типа.
Хотелось бы мнение узнать о правильности кода, а то stl только недавно начал учить. |
|
|
Алексей1153 |
![]()
Сообщение
#33
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
1)
Цитата if (n >= v.size ()) "size()" имеет тип unsigned int , а "n" у тебя - int 2) Передавать и возвращать контейнеры лучше по ссылке (а то нехилое по объёму копирование будет иногда происходить) Поэтому, лучше не возвращать из функции тип std::list<T> , а объявить переменную вне функции, а потом передать ссылку для заполнения контейнера в функции 3)объявление переменных-контейнеров частенько громоздкие - лучше определить синоним typedef std::list<T> td_LIST; это также поможет вносить быстрые исправления, если что. Но в данном примере это не сильно существенно - код небольшой 4) проверяй v.size()!=0 для любых контейнеров перед получением итератора или ссылки (.begin(),end(),[x] и так далее) 5) нет нужды делать вот так (и вообще нельзя) .... eEnd = v.end (); eIt != eEnd...... надо .... ; eIt != v.end()...... Цитата list_out.insert (v.begin (), v.begin () + n);//<< не получится так вставить из вектора в список. Надо - либо одинаковый тип делать, либо цикл Раскрывающийся текст
Сообщение отредактировал Алексей1153 - 24.8.2010, 20:07 |
|
|
panter_dsd |
![]()
Сообщение
#34
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
1. Учту.
2. Согласен. 4. Учту. 5. Не согласен. Можно и нужно, если контейнер не изменяется. Зачем дергать функцию на каждой итерации? 6. Вполне получается. Что смущает? |
|
|
Алексей1153 |
![]()
Сообщение
#35
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
5 - в релизе там не будет функции
![]() 6 - ну, раз получается, тогда пользуйся на здоровье. У меня компилятор брыкается )) Ну оно и понятно |
|
|
panter_dsd |
![]()
Сообщение
#36
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
6. Компилятор ничего не говорит. По документации тоже можно, вроде бы. Завтра перепроверю.
|
|
|
Алексей1153 |
![]()
Сообщение
#37
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
всё, 6 - мой косяк )) Исправил . Пропустил начальный итератор и не обратил внимание
Сообщение отредактировал Алексей1153 - 24.8.2010, 20:08 |
|
|
kwisp |
![]()
Сообщение
#38
|
![]() астарожна ынтжинэр ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1404 Регистрация: 26.11.2008 Из: ТаганрогРодинаЧехова Пользователь №: 435 Спасибо сказали: 113 раз(а) Репутация: ![]() ![]() ![]() |
4) проверяй v.size()!=0 для любых контейнеров перед получением итератора или ссылки (.begin(),end(),[x] и так далее) мои пять копеек. я вот тоже в stl недавно стал вникаить. так меерс советует в 4 совете использовать empty() вместо сравнения size() с нулем из-за постоянного времени выполнения функции. stl |
|
|
Алексей1153 |
![]()
Сообщение
#39
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
kwisp, ок, учтём ) Только обычно у меня такой вызов был не в цикле, а list ещё не доводилось пользоваться почему то ))
|
|
|
panter_dsd |
![]()
Сообщение
#40
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Алексей1153, что-то не компилируется твой код.
|
|
|
Алексей1153 |
![]()
Сообщение
#41
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
panter_dsd, я в студии делал - там компилится. А ты где?
А ты, случаем, не поставил main перед реализацией функции ? ) тогда предопределение попробуй добавить перед мейном:
И попробуй ещё дописать "typename" перед "std::list<T>& list_out" в списке аргументов функции |
|
|
DEADHUNT |
![]()
Сообщение
#42
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
И попробуй ещё дописать "typename" перед "std::list<T>& list_out" в списке аргументов функции typename не надо дописывать и в первом аргументе. и вообще typename должен применяться к qualified-id зависящего от шаблонного параметра: Цитата typename-specifier:
typename ::opt nested-name-specifier identifier typename ::opt nested-name-specifier templateopt simple-template-id Сообщение отредактировал DEADHUNT - 25.8.2010, 10:15 |
|
|
panter_dsd |
![]()
Сообщение
#43
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Выкидывание typename помогло.
Алексей1153, что-то мне интересно. С шаблонами хорошо знаком, а компилятор от IDE и библиотеки отделить не можешь... Я компилировал g++ (Gentoo 4.4.4-r1 p1.1, pie-0.4.5) 4.4.4. Т.е. не студийным компилером. |
|
|
panter_dsd |
![]()
Сообщение
#44
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
Заканчиваем с оффтопом.
Вот последняя редакция, еще есть замечания?
|
|
|
ViGOur |
![]()
Сообщение
#45
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
Перенес флейм в другую тему, В любимый Алексей1153 раздел "Треп", чтобы потрепаться.
![]() Смотрите: Что есть что, с чем можно и куда.... |
|
|
AD |
![]()
Сообщение
#46
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2003 Регистрация: 4.2.2008 Из: S-Petersburg Пользователь №: 84 Спасибо сказали: 70 раз(а) Репутация: ![]() ![]() ![]() |
Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему?
|
|
|
DEADHUNT |
![]()
Сообщение
#47
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему? а в чём проблема, всё это можно переписать на чистый C, только сути это не изменит(просто будет больше кода и будет сложнее его понять) |
|
|
ViGOur |
![]()
Сообщение
#48
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
AD |
![]()
Сообщение
#49
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2003 Регистрация: 4.2.2008 Из: S-Petersburg Пользователь №: 84 Спасибо сказали: 70 раз(а) Репутация: ![]() ![]() ![]() |
а в чём проблема, всё это можно переписать на чистый C, только сути это не изменит(просто будет больше кода и будет сложнее его понять) Да в том и проблема, что без использования стандартных средств для красивого и оптимального решения, все это выглядеть будет на чистом С++ (а не С) совсем по-другому! ![]() ![]() |
|
|
DEADHUNT |
![]()
Сообщение
#50
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
AD |
![]()
Сообщение
#51
|
Профессионал ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2003 Регистрация: 4.2.2008 Из: S-Petersburg Пользователь №: 84 Спасибо сказали: 70 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
DEADHUNT |
![]()
Сообщение
#52
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется! ![]() в C++0x стандарте описание языка C++ занимает 400 страниц, далее идёт описание стандартной библиотеки(STL) на 700+ страниц. Сообщение отредактировал DEADHUNT - 26.8.2010, 12:02 |
|
|
kwisp |
![]()
Сообщение
#53
|
![]() астарожна ынтжинэр ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 1404 Регистрация: 26.11.2008 Из: ТаганрогРодинаЧехова Пользователь №: 435 Спасибо сказали: 113 раз(а) Репутация: ![]() ![]() ![]() |
nth_element() - не катит?
|
|
|
DEADHUNT |
![]()
Сообщение
#54
|
Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: ![]() ![]() ![]() |
nth_element() - не катит? да кстати, всё реализовано в stl, сложность - линейная. и весь код тогда будет занимать одну строчку:
|
|
|
Алексей1153 |
![]()
Сообщение
#55
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
Цитата сложность - линейная Цитата 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 |
![]()
Сообщение
#56
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
Как и обещал, код:
Конструктивная критика приветствуется! ![]() |
|
|
panter_dsd |
![]()
Сообщение
#57
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
1. rValue = ++n; - зачем в 2 строки делать?
2. std::vector<int> collMin( coll.begin(), coll.begin() + n); все же лучше. |
|
|
ViGOur |
![]()
Сообщение
#58
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
1. Кому как нравится.
![]() 2. Чем лучше? |
|
|
panter_dsd |
![]()
Сообщение
#59
|
![]() Жаждущий знаний ![]() ![]() ![]() Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: ![]() ![]() ![]() |
1. Если хочется в 2 строки, то хотя бы префиксную версию инкремента юзай.
2. Избавляемся от лишнего заполнения нулями, плюс от else, который только путает. Сообщение отредактировал panter_dsd - 25.1.2012, 12:05 |
|
|
ViGOur |
![]()
Сообщение
#60
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
1. в данном случае точно разницы нет постфиксный инкремент или префиксный!
![]() 2. То, что избавляет от лишнего заполнения нолями, согласен. Но ИМХО мой вариант наглядней будет. Всё равно, можно сказать, что ты выиграл M процессорных тактов на заполнении нолями и столько же можно убрать из цикла! ![]() Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение. Тоесть только для наглядности! ![]() |
|
|
Алексей1153 |
![]()
Сообщение
#61
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2944 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
wiz29 |
![]()
Сообщение
#62
|
![]() Старейший участник ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
ViGOur |
![]()
Сообщение
#63
|
![]() Мастер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: ![]() ![]() ![]() |
Объясни как. Можно использовать только два массива!
![]() |
|
|
wiz29 |
![]()
Сообщение
#64
|
![]() Старейший участник ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
cross |
![]()
Сообщение
#65
|
Новичок Группа: Новичок Сообщений: 2 Регистрация: 24.6.2010 Пользователь №: 1833 Спасибо сказали: 0 раз(а) Репутация: ![]() ![]() ![]() |
Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации. Согласен (о чем и писал ранее в соседней теме про эту задачу). Единственный линейный алгоритм, который мне видится, это если значение элементов лежит в интервале от 0 до Х (где Х не велико и нам хватает памяти) заводим массив из Х элементов, в котором индекс - это величина элемента в исходном множестве, а значение - число появлений этого элемента в исходном множестве. За один проход пересчитываем все элементы и берем нужное количество минимальных. |
|
|
![]() ![]() |
![]() |
|
Текстовая версия | Сейчас: 24.7.2025, 1:23 |