 |
|
Модераторы: Daevaorn |
 
|
|
Сортировка строк, чем быстрее тем лучше 
| FelikZ |
|
|||
 Старый Маразматик  Профиль Группа: Участник Сообщений: 380 Регистрация: 1.12.2006 Где: Vault 13 Репутация: нет Всего: 5 |
Подскажите плз как реализовать самую быструю сортировку массива из строк, при условии что
символы в строках могут быть не только буквами. -------------------------------------------------------------------- Ограничение оперативки 128 метров Максимум 100 000 строк --------------------  |
|||
|
||||
Загрузка ...
| Fedor |
|
|||
 Днепрянин Профиль Группа: Участник Сообщений: 2090 Регистрация: 8.2.2003 Где: Великий Репутация: нет Всего: 32 |
А обычная быстрая сортировка не прокатит?
100000*log(100000)=500000 Это примерно одна десятая секунды. -------------------- Мы - Днепряне. Мы всех сильней. |
|||
|
||||
| VaiMR |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 67 Регистрация: 25.11.2006 Репутация: нет Всего: 2 |
А строки по какому принципу сортируются?
|
|||
|
||||
| JackYF |
|
|||
 полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 18 Всего: 162 |
VaiMR, по лексикографическому.
Сравниваются первые буквы. Если равны, то вторые и т.д. |
|||
|
||||
| comp |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 61 Регистрация: 15.11.2006 Репутация: нет Всего: 1 |
По-моему, надо цифровую сортировку. Она как-то, по-моему, больше подходит для данных такого рода.
|
|||
|
||||
| zkv |
|
||||
 Профиль Группа: Участник Клуба Сообщений: 2133 Регистрация: 23.7.2006 Где: Санкт-Петербург Репутация: 26 Всего: 92 |
необязательно, можно написать свой предикат или функатор, в него закладываем нужный принцип  понимаю, что общеизвестно, но раз человек спросил, думаю стоит упомянуть. |
||||
|
|||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 18 Всего: 162 |
Это которая radix-sort ? Так она же для значений постоянной длины, и в основном применяется для не очень больших чисел... |
|||
|
||||
| comp |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 61 Регистрация: 15.11.2006 Репутация: нет Всего: 1 |
По-видимому digit sort будет звучать по-английски... А насчёт приминимости, решалась задача, где даны были числа, в кол-ве, 1000. И каждое число не превышало по значению 10^500... Она всё это сортировала меньше чем за секунду Это сообщение отредактировал(а) comp - 27.12.2006, 17:05 |
|||
|
||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 18 Всего: 162 |
Ну, там больше будет занимать перемещение самих чисел, чем сама сортировка. Для 1000 чисел? 1 секунда? ИМХО много. |
|||
|
||||
| FelikZ |
|
|||
|
Старый Маразматик Профиль Группа: Участник Сообщений: 380 Регистрация: 1.12.2006 Где: Vault 13 Репутация: нет Всего: 5 |
P.S.
Я пробывал сортировать через strcmp, но в этом случае на компе: AMD 850mHz 128mb Думало несколько секунд...(А надо чтобы максимум секунда) По-етому решил обратиться за помощью -------------------- |
|||
|
||||
| Любитель |
|
|||
|
Программист-романтик Профиль Группа: Комодератор Сообщений: 3645 Регистрация: 21.5.2005 Где: Воронеж Репутация: 24 Всего: 92 |
Сортировка своя? Я ничего против не имею, но всё таки производители компилеров очень хорошо юзают оптимизацию.
|
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 17 Всего: 110 |
а как строки меняются местами? (если указателями, то нормально, главное, чтобы копирований не было) -------------------- qqq |
|||
|
||||
| FelikZ |
|
|||
|
Старый Маразматик Профиль Группа: Участник Сообщений: 380 Регистрация: 1.12.2006 Где: Vault 13 Репутация: нет Всего: 5 |
да, менял местами указатели
-------------------- |
|||
|
||||
| BSOD |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 405 Регистрация: 1.11.2004 Где: Гомель Репутация: нет Всего: 3 |
походу радих должен помочь, тока в конец каждой строки нуна приписывать что-нить типа #, что б они одинаковой длины стали, ну а после сортировки все удалить (ну всмысле с конца строки
) -------------------- как корабль назовешь - то на нем и напишешь |
|||
|
||||
| comp |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 61 Регистрация: 15.11.2006 Репутация: нет Всего: 1 |
Господи... какое нафиг перемещение чисел!!!А зачем придумали индексацию... Я разве сказал - 1 секунда... я сказал, меньше чем за секунду, а если точнее, то 384ms... по-моему, вполне.
|
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.1527 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |