Задача на сортировку |
1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!
Задача на сортировку |
klem4 |
21.04.2011 16:05
Сообщение
#1
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Есть следующая задача:
Входные данные Дано число N (1 ≤ N ≤ 100000), а затем в одной или нескольких строках N натуральных чисел из диапазона от 1 до 100. Выходные данные Выведите в одной строке N чисел в неубывающем порядке. Есть ограничения: Лимит времени: 0.1 секунды Понятно, что сортировать тут ничего не нужно, так как в заданное время не уложиться, есть решение: Спойлер (Показать/Скрыть)
Но оно проходит всего-лишь 78.6% тестов, на остальных - превышение времени, максимальное время работы 0.109 секунды из 0.1 секунды, то есть превышение в 0.009с. От куда мне их взять ума не приложу Пробовал кучу разных вариантов, без векторов, без строк, все только хуже. Нид хелп Добавлено через 19 мин. вопрос решен, помогла замена iostream на stdio.h -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
DarkWishmaster |
21.04.2011 21:35
Сообщение
#2
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
В С не разбираюсь, но наверное ты пузырьковой сортируешь.
почитай тут Методы сортировок Сообщение отредактировано: DarkWishmaster - 21.04.2011 21:36 |
Freedom |
21.04.2011 23:06
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 113 Пол: Мужской Реальное имя: Надир Репутация: 6 |
Явно видно что не пузырьковый метод. Для этого случая он будет долго выполнятся. -------------------- From ZERO to HERO
|
klem4 |
22.04.2011 7:35
Сообщение
#4
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
DarkWishmaster
Как я уже указал в первом по посте Цитата Понятно, что сортировать тут ничего не нужно где тебе там пузырек почудился, я не знаю ;) Примененный мною метод некоторые как выяснилось называют "сортировкой подсчетом".ps про раздел сортировок на этом форуме я в курсе, два метода там описаны мною -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Lapp |
22.04.2011 7:49
Сообщение
#5
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
То, что потоки работают медленее, чем стандартный ввод/вывод, кажется довольно понятным, но.. задним числом )).
Примененный мною метод некоторые как выяснилось называют "сортировкой подсчетом". Очень эффективно для длинных последовательностей при небольшом множестве сортируемых объектов.Цитата ps про раздел сортировок на этом форуме я в курсе, два метода там описаны мною Может, добавишь и этот? )) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
22.04.2011 9:01
Сообщение
#6
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
(старожил форума, многое знает):
> [код с вылизанным алгоритмом] (новичок, только начал учиться программировать): > В С не разбираюсь, но наверное ты пузырьковой сортируешь. > почитай тут > Методы сортировок Мне кажется, это надо добавить в перлы форума. Добавлено через 16 мин. Ещё из методов сортировок могу предложить такой метод. Он вообще для массива строк предназначен, но работает для массива чего угодно, так как что угодно можно представить строкой (например, 32-битное число - это строка из 4 символов, 80-битное вещественное - строка из 10 символов). Просто загоняем все строки в префиксное дерево. А потом обходим это дерево и выводим в новый массив. Если надо, чтобы массив умел повторяющиемся строки не выбрасывать, то в вершинах префиксного дерева храним число раз, сколько строка встретилась в массиве. Время пропорционально суммарной длине строк в массиве. То есть для массива вещественных чисел время будет теоретически линейное. На практике - не знаю, выделение памяти для вершин дерева и недружелюбный к кешу обход этого дерева сильно всё портят. Кто-то сравнивал поразрядную сортировку и кусорт, так вот поразрядная обгоняла кусорт только на какой-то совсем дикой длине массива, за миллиард. -------------------- |
Lapp |
22.04.2011 10:43
Сообщение
#7
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Мне кажется, это надо добавить в перлы форума. Да ладно тебе, не смущай молодежь! ))А если кажется - добавляй. Надеюсь, чувство юмора есть у всех (или же пусть развивают)) и обид не будет. А вообще, я просто восхищен сдержанностью, с которой Клема ответил )), +1 Цитата работает для массива чего угодно, так как что угодно можно представить строкой (например, 32-битное число - это строка из 4 символов, 80-битное вещественное - строка из 10 символов). Так ли?В строке спереди - младшие байты, а экспонента содержится в старших.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
22.04.2011 11:05
Сообщение
#8
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> В строке спереди - младшие байты, а экспонента содержится в старших..
Ну будет сортировка по такому вот кривому признаку. Понятно, что можно и символы в строке попереставлять, и учесть то, что отрицательные числа будут отсортированы наоборот. Это детали. Я про идею алгоритма. -------------------- |
Guest |
22.04.2011 14:17
Сообщение
#9
|
Гость |
Топикстартеру: смотрим, как работает std::multimap и не придумываем доморощенных алгоритмов сотрировки - обогнать отшлифованный годами стандартный класс вряд-ли удастся, а вот времени на это уйдет море.
Также смотрим на строку s.erase(s.begin()); до просветления, и думаем, сколько она сожрет времени. При переносе из любого контейнера в stringstream с использованием разделителя, не делают for(container_type::iterator it = cnt.begin(); it != cnt.end(); it++) ss << " " << (*it); , чтобы потом удалять ненужный разделитель из начала строки, а делают container_type::iterator it = cnt.begin(); ss << (*it++);, и строку сразу можно забросить в cout... |
TarasBer |
22.04.2011 14:30
Сообщение
#10
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> обогнать отшлифованный годами стандартный класс вряд-ли удастся
Насколько я знаю, СТЛ не отличается быстротой (т.е. алгоритмическая сложность хорошая, но из-за нюансов и универсальности страдает константа), у него другие задачи. -------------------- |
karpinsky |
22.04.2011 15:51
Сообщение
#11
|
Группа: Пользователи Сообщений: 8 Пол: Мужской Репутация: 2 |
Ничего у него не страдает, если правильно использовать (в данном конкретном случае работаем не с какими-то своими хитрыми классами, на которых может быть потеря времени, а с обычным int, тут все будет в порядке). Просто для решения задачи нужно сначала подумать, а потом начинать программировать. В данном случае было принято неверное решение об использовании вектора, его придется отдельно сортировать, либо обрабатывать специальным образом, чтобы получить желаемый результат. Мультимапу же ничего подобного делать не надо, он будет содержать добавляемую информацию уже в сортированном виде (кстати, в виде того же дерева, которое предложено выше), и достаточно будет данные только перенести в строку и вывести на печать.
Причем, работать это будет вне зависимости от типа данных, которые нужно упорядочить, критерий сортировки и тип обрабатываемых данных задается пользователем при описании типа мультимапа. P.S. Заранее извиняюсь за вторжение на форум под названием "Все о Паскале", как раз к Паскалю и его потомкам я равнодушен, но в этом разделе может и найдется что-нибудь интересное... Сообщение отредактировано: karpinsky - 22.04.2011 15:53 |
-TarasBer- |
22.04.2011 16:31
Сообщение
#12
|
Гость |
Ты всерьёз считаешь, что этот самый мультимап (внутри - дерево, т.е. это аллокации и кэш-промахи) будет быстрее сортировки подсчётом?!
Кстати, почему такие вещи в известных мне реализация СТЛ сделаны деревьями, а не хешами? Так вот, любой, кто хочет выжать максимум из своей программы, пусть даже ценой нечитаемого кода (игрострой), первым делом отказывается от СТЛ. Так что не надо мне про вылизанный СТЛ. Он для тех, кому проверенное решение важнее скорости. В общем, напиши своё решение, пошли ОПу, пусть он сравнит. Я ставлю на разницу по скорости в 5 раз. |
karpinsky |
22.04.2011 16:49
Сообщение
#13
|
Группа: Пользователи Сообщений: 8 Пол: Мужской Репутация: 2 |
Цитата Ты всерьёз считаешь, что этот самый мультимап (внутри - дерево, т.е. это аллокации и кэш-промахи) будет быстрее сортировки подсчётом?! А ты всерьез считаешь, что пробежаться по дереву одним циклом будет медленнее, чем организовать несколько (до 100) циклов, и в каждом из них делать что-то, а потом еще и по результирующей строке пройтись erase-ом? Сортировка сортировкой, но ее результаты надо еще обработать, и представить в нужной форме.Цитата В общем, напиши своё решение, пошли ОПу, пусть он сравнит. Знаешь, я вообще не обязан ничего никому посылать. Я предложил метод решения, у себя, разумеется, проверил его. На миллионе входных значений (из файла) никакого проседания (тем более - пятикратного) multimap-а не заметил, если ТС заинтересуется - сделает и проверит. Если у тебя комплятор - дерьмо - это твои личные проблемы. Интеловский компилер уделает мультимапом любую из самописных сортировок. А равняться на слабачков типа M$ или Борланд я как-то не привык.Цитата любой, кто хочет выжать максимум из своей программы, пусть даже ценой нечитаемого кода (игрострой), первым делом отказывается от СТЛ. Не надо мне про игрострой. STL применяется в таких проектах, что у тебя диска не хватит исходники сохранить, и никто не собирается от него отказываться (я не про игрострой, игрушки меня давно не интересуют). Единственный недостаток STL - это увеличение времени _компиляции_ программы. Времени выполнения это не касается. А коли сидеть на VC6 (или еще ниже) - так это уж дело каждого, либо переходить на современное ПО и получать выгоду, либо плестись в конце колонны в попытках хитромудрыми ухищрениями выиграть в скорости за счет потери читабельности и вообще всего, чего можно, и все равно проигрывать современным компиляторам на современных камнях.Сообщение отредактировано: karpinsky - 22.04.2011 16:57 |
-TarasBer- |
22.04.2011 17:51
Сообщение
#14
|
Гость |
> А ты всерьез считаешь, что пробежаться по дереву одним циклом будет медленнее, чем организовать несколько (до 100) циклов, и в каждом из них делать что-то
Ты вообще поразрядную сортировку знаешь, или как? Проверь, а потом говори, ладно? > а потом еще и по результирующей строке пройтись erase-ом? Тут согласен - удаление символа из начала строки - это неправильно. Лучше бы он писал не "пробел-число", а "число-пробел", а потом удалял символ из конца. > Знаешь, я вообще не обязан ничего никому посылать. То есть аргументировать свои утверждения не можешь? > На миллионе входных значений (из файла) никакого проседания (тем более - пятикратного) multimap-а не заметил А ты сравнивал его с поразрядной сортировкой? По сравнению с ЧЕМ проседания ты не заметил? > Если у тебя комплятор - дерьмо - это твои личные проблемы. Причём тут компилятор, если мы алгоритм обсуждаем? > Интеловский компилер уделает мультимапом любую из самописных сортировок. Ты понимаешь разницу между оптимизацией микрокода и реализацией стандартной библиотеки? Это непересекающиеся вещи. Если алгоритм из библиотеки не подходит под данную задачу (а универсальные вещи всегда сливают узкоспециализированным), то никакой компилятор тебе не сделает неправильный алгоритм правильным. Давай, чтобы честно было, прогони и поразрядную сортировку через ICC. > STL применяется в таких проектах, что у тебя диска не хватит исходники сохранить, и никто не собирается от него отказываться Да только в участках, где нужна предельная скорость, СТЛ заменяется на велосипеды. А если не заменяется, значит там скорость всех устраивает и выжимать такты никому не надо. > и все равно проигрывать современным компиляторам на современных камнях. Ах, нам ещё и современный камень нужен, да? Если уж говорить о крупных проектах, то там вообще С++ не нужен. Дешевле вот именно, взять язык попроще и тот самый современный камень прикупить, чем платить несчастным крестопрограммистам за их непроизводительный (а на С++ он другим не будет) труд. Я вообще не знаю, где С++ нужен, он держится только на старых библиотеках. |
Текстовая версия | 28.03.2024 11:54 |