Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ Задача на сортировку

Автор: klem4 21.04.2011 20:05

Есть следующая задача:

Входные данные
Дано число N (1 ≤ N ≤ 100000), а затем в одной или нескольких строках N натуральных чисел из диапазона от 1 до 100.
Выходные данные
Выведите в одной строке N чисел в неубывающем порядке.

Есть ограничения:
Лимит времени: 0.1 секунды

Понятно, что сортировать тут ничего не нужно, так как в заданное время не уложиться, есть решение:

Спойлер (Показать/Скрыть)


Но оно проходит всего-лишь 78.6% тестов, на остальных - превышение времени, максимальное время работы 0.109 секунды из 0.1 секунды, то есть превышение в 0.009с. От куда мне их взять ума не приложу sad.gif Пробовал кучу разных вариантов, без векторов, без строк, все только хуже. Нид хелп smile.gif

Добавлено через 19 мин.
вопрос решен, помогла замена iostream на stdio.h smile.gif

Автор: DarkWishmaster 22.04.2011 1:35

В С не разбираюсь, но наверное ты пузырьковой сортируешь.
почитай тут
http://forum.pascal.net.ru/index.php?showtopic=3065

Автор: Freedom 22.04.2011 3:06

Цитата(DarkWishmaster @ 21.04.2011 22:35) *

В С не разбираюсь, но наверное ты пузырьковой сортируешь.
почитай тут
http://forum.pascal.net.ru/index.php?showtopic=3065

Явно видно что не пузырьковый метод. Для этого случая он будет долго выполнятся.

Автор: klem4 22.04.2011 11:35

DarkWishmaster
Как я уже указал в первом по посте

Цитата
Понятно, что сортировать тут ничего не нужно
smile.gif где тебе там пузырек почудился, я не знаю ;) Примененный мною метод некоторые как выяснилось называют "сортировкой подсчетом".

ps про раздел сортировок на этом форуме я в курсе, два метода там описаны мною smile.gif

Автор: Lapp 22.04.2011 11:49

То, что потоки работают медленее, чем стандартный ввод/вывод, кажется довольно понятным, но.. задним числом )).

Цитата(klem4 @ 22.04.2011 8:35) *
Примененный мною метод некоторые как выяснилось называют "сортировкой подсчетом".
Очень эффективно для длинных последовательностей при небольшом множестве сортируемых объектов.

Цитата
ps про раздел сортировок на этом форуме я в курсе, два метода там описаны мною smile.gif
good.gif
Может, добавишь и этот? ))

Автор: TarasBer 22.04.2011 13:01

(старожил форума, многое знает):
> [код с вылизанным алгоритмом]
(новичок, только начал учиться программировать):
> В С не разбираюсь, но наверное ты пузырьковой сортируешь.
> почитай тут
> Методы сортировок

Мне кажется, это надо добавить в перлы форума.


Добавлено через 16 мин.
Ещё из методов сортировок могу предложить такой метод. Он вообще для массива строк предназначен, но работает для массива чего угодно, так как что угодно можно представить строкой (например, 32-битное число - это строка из 4 символов, 80-битное вещественное - строка из 10 символов).

Просто загоняем все строки в префиксное дерево. А потом обходим это дерево и выводим в новый массив. Если надо, чтобы массив умел повторяющиемся строки не выбрасывать, то в вершинах префиксного дерева храним число раз, сколько строка встретилась в массиве.

Время пропорционально суммарной длине строк в массиве.
То есть для массива вещественных чисел время будет теоретически линейное.
На практике - не знаю, выделение памяти для вершин дерева и недружелюбный к кешу обход этого дерева сильно всё портят.
Кто-то сравнивал поразрядную сортировку и кусорт, так вот поразрядная обгоняла кусорт только на какой-то совсем дикой длине массива, за миллиард.

Автор: Lapp 22.04.2011 14:43

Цитата(TarasBer @ 22.04.2011 10:01) *
Мне кажется, это надо добавить в перлы форума.
Да ладно тебе, не смущай молодежь! ))
А если кажется - добавляй.
Надеюсь, чувство юмора есть у всех (или же пусть развивают)) и обид не будет.
А вообще, я просто восхищен сдержанностью, с которой Клема ответил )), +1

Цитата
работает для массива чего угодно, так как что угодно можно представить строкой (например, 32-битное число - это строка из 4 символов, 80-битное вещественное - строка из 10 символов).
Так ли?
В строке спереди - младшие байты, а экспонента содержится в старших..

Автор: TarasBer 22.04.2011 15:05

> В строке спереди - младшие байты, а экспонента содержится в старших..

Ну будет сортировка по такому вот кривому признаку. Понятно, что можно и символы в строке попереставлять, и учесть то, что отрицательные числа будут отсортированы наоборот. Это детали. Я про идею алгоритма.

Автор: Guest 22.04.2011 18:17

Топикстартеру: смотрим, как работает 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++);
for(; it != cont.end(); it++) ss << " " << (*it);
, и строку сразу можно забросить в cout...

Автор: TarasBer 22.04.2011 18:30

> обогнать отшлифованный годами стандартный класс вряд-ли удастся

Насколько я знаю, СТЛ не отличается быстротой (т.е. алгоритмическая сложность хорошая, но из-за нюансов и универсальности страдает константа), у него другие задачи.

Автор: karpinsky 22.04.2011 19:51

Ничего у него не страдает, если правильно использовать (в данном конкретном случае работаем не с какими-то своими хитрыми классами, на которых может быть потеря времени, а с обычным int, тут все будет в порядке). Просто для решения задачи нужно сначала подумать, а потом начинать программировать. В данном случае было принято неверное решение об использовании вектора, его придется отдельно сортировать, либо обрабатывать специальным образом, чтобы получить желаемый результат. Мультимапу же ничего подобного делать не надо, он будет содержать добавляемую информацию уже в сортированном виде (кстати, в виде того же дерева, которое предложено выше), и достаточно будет данные только перенести в строку и вывести на печать.

Причем, работать это будет вне зависимости от типа данных, которые нужно упорядочить, критерий сортировки и тип обрабатываемых данных задается пользователем при описании типа мультимапа.

P.S. Заранее извиняюсь за вторжение на форум под названием "Все о Паскале", как раз к Паскалю и его потомкам я равнодушен, но в этом разделе может и найдется что-нибудь интересное...

Автор: -TarasBer- 22.04.2011 20:31

Ты всерьёз считаешь, что этот самый мультимап (внутри - дерево, т.е. это аллокации и кэш-промахи) будет быстрее сортировки подсчётом?!
Кстати, почему такие вещи в известных мне реализация СТЛ сделаны деревьями, а не хешами?
Так вот, любой, кто хочет выжать максимум из своей программы, пусть даже ценой нечитаемого кода (игрострой), первым делом отказывается от СТЛ.
Так что не надо мне про вылизанный СТЛ. Он для тех, кому проверенное решение важнее скорости.
В общем, напиши своё решение, пошли ОПу, пусть он сравнит. Я ставлю на разницу по скорости в 5 раз.

Автор: karpinsky 22.04.2011 20:49

Цитата
Ты всерьёз считаешь, что этот самый мультимап (внутри - дерево, т.е. это аллокации и кэш-промахи) будет быстрее сортировки подсчётом?!
А ты всерьез считаешь, что пробежаться по дереву одним циклом будет медленнее, чем организовать несколько (до 100) циклов, и в каждом из них делать что-то, а потом еще и по результирующей строке пройтись erase-ом? Сортировка сортировкой, но ее результаты надо еще обработать, и представить в нужной форме.

Цитата
В общем, напиши своё решение, пошли ОПу, пусть он сравнит.
Знаешь, я вообще не обязан ничего никому посылать. Я предложил метод решения, у себя, разумеется, проверил его. На миллионе входных значений (из файла) никакого проседания (тем более - пятикратного) multimap-а не заметил, если ТС заинтересуется - сделает и проверит. Если у тебя комплятор - дерьмо - это твои личные проблемы. Интеловский компилер уделает мультимапом любую из самописных сортировок. А равняться на слабачков типа M$ или Борланд я как-то не привык.

Цитата
любой, кто хочет выжать максимум из своей программы, пусть даже ценой нечитаемого кода (игрострой), первым делом отказывается от СТЛ.
Не надо мне про игрострой. STL применяется в таких проектах, что у тебя диска не хватит исходники сохранить, и никто не собирается от него отказываться (я не про игрострой, игрушки меня давно не интересуют). Единственный недостаток STL - это увеличение времени _компиляции_ программы. Времени выполнения это не касается. А коли сидеть на VC6 (или еще ниже) - так это уж дело каждого, либо переходить на современное ПО и получать выгоду, либо плестись в конце колонны в попытках хитромудрыми ухищрениями выиграть в скорости за счет потери читабельности и вообще всего, чего можно, и все равно проигрывать современным компиляторам на современных камнях.

Автор: -TarasBer- 22.04.2011 21:51

> А ты всерьез считаешь, что пробежаться по дереву одним циклом будет медленнее, чем организовать несколько (до 100) циклов, и в каждом из них делать что-то

Ты вообще поразрядную сортировку знаешь, или как?
Проверь, а потом говори, ладно?

> а потом еще и по результирующей строке пройтись erase-ом?

Тут согласен - удаление символа из начала строки - это неправильно.
Лучше бы он писал не "пробел-число", а "число-пробел", а потом удалял символ из конца.

> Знаешь, я вообще не обязан ничего никому посылать.

То есть аргументировать свои утверждения не можешь?

> На миллионе входных значений (из файла) никакого проседания (тем более - пятикратного) multimap-а не заметил

А ты сравнивал его с поразрядной сортировкой? По сравнению с ЧЕМ проседания ты не заметил?

> Если у тебя комплятор - дерьмо - это твои личные проблемы.

Причём тут компилятор, если мы алгоритм обсуждаем?

> Интеловский компилер уделает мультимапом любую из самописных сортировок.

Ты понимаешь разницу между оптимизацией микрокода и реализацией стандартной библиотеки? Это непересекающиеся вещи. Если алгоритм из библиотеки не подходит под данную задачу (а универсальные вещи всегда сливают узкоспециализированным), то никакой компилятор тебе не сделает неправильный алгоритм правильным.
Давай, чтобы честно было, прогони и поразрядную сортировку через ICC.

> STL применяется в таких проектах, что у тебя диска не хватит исходники сохранить, и никто не собирается от него отказываться

Да только в участках, где нужна предельная скорость, СТЛ заменяется на велосипеды. А если не заменяется, значит там скорость всех устраивает и выжимать такты никому не надо.

> и все равно проигрывать современным компиляторам на современных камнях.

Ах, нам ещё и современный камень нужен, да?
Если уж говорить о крупных проектах, то там вообще С++ не нужен. Дешевле вот именно, взять язык попроще и тот самый современный камень прикупить, чем платить несчастным крестопрограммистам за их непроизводительный (а на С++ он другим не будет) труд. Я вообще не знаю, где С++ нужен, он держится только на старых библиотеках.