IPB
ЛогинПароль:

> Внимание!

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с. От куда мне их взять ума не приложу sad.gif Пробовал кучу разных вариантов, без векторов, без строк, все только хуже. Нид хелп smile.gif

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 21.04.2011 21:35
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


В С не разбираюсь, но наверное ты пузырьковой сортируешь.
почитай тут
Методы сортировок

Сообщение отредактировано: DarkWishmaster - 21.04.2011 21:36
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Freedom
сообщение 21.04.2011 23:06
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 113
Пол: Мужской
Реальное имя: Надир

Репутация: -  6  +


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

В С не разбираюсь, но наверное ты пузырьковой сортируешь.
почитай тут
Методы сортировок

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


--------------------
From ZERO to HERO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
klem4
сообщение 22.04.2011 7:35
Сообщение #4


Perl. Just code it!
******

Группа: Модераторы
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 22.04.2011 7:49
Сообщение #5


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
TarasBer
сообщение 22.04.2011 9:01
Сообщение #6


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


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

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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 22.04.2011 10:43
Сообщение #7


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
TarasBer
сообщение 22.04.2011 11:05
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
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++);
for(; it != cont.end(); it++) ss << " " << (*it);
, и строку сразу можно забросить в cout...
 К началу страницы 
+ Ответить 
TarasBer
сообщение 22.04.2011 14:30
Сообщение #10


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
karpinsky
сообщение 22.04.2011 15:51
Сообщение #11





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  2  +


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

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

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

Сообщение отредактировано: karpinsky - 22.04.2011 15:53
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
-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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
-TarasBer-
сообщение 22.04.2011 17:51
Сообщение #14


Гость






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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 28.03.2024 11:54
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"