|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko 2:5020/400 27 Dec 2002 07:07:41
To : Andrew Ezhguroff
Subject : Re: быстpая соpтиpовка
--------------------------------------------------------------------------------
Andrew Ezhguroff wrote:
> Hо рекурсия все же нужна. И, следовательно, дополнительная память для
> организации рекурсии нужна (так что в п.3 ты не прав).
При программировании микроконтроллеров обычно подразумеваются
раздельные секции кода, данных, стека, I/O page. И обычно они никак не
пересекаются, тем более, что секция кода вообще лежит в ПЗУ.
Именно это я и подразумевал в п.3, когда писал "память данных".
Там я подразумевал, что стек болтается в своем сегменте, и с данными
не перемешивается.
Извини, если невнятно обьяснился.
> Пирамидальная сортировка обеспечивает O(N*log(N)) для любых данных (правда с
> большим коэф. пропорциональности - она работает медленнее лучшего случая
> быстрой сортировки) и не требует рекурсии и дополнительных массивов.
Да я же не спорю. Побитовая сортировка тоже имеет свои недостатки.
Hо в данном конкретном применении - а именно "16-и разрядные числа в
8-битовой машине" - она демонстрирует некоторые преимущества, связаные с
возможность "уполовинивать" сортируемые слова.
Так, например, если на данном этапе идет сортировка по биту 8..15
(старший байт), то для проверки битмаски не обязательно затаскивать в
процессор из памяти все слово целиком в два присеста (старший байт, а
потом младший байт). Достаточно втянуть только старший, байт, наложить
на него маску, а потом решать - переходить ли к след. элементу массива
(ежели маска не сработала), или же заниматься этим словом целиком.
Таким образом, при побитовой сортировке на данном этапе сравниваются
только старшие байты, а переставляются (только когда надо) младшие со
старшими, то есть слова целиком. То есть обращение к младшим байтам
сортируемых слов идет только для их перестановки - в сравнении они не
учавствуют.
Аналогичное упрощение можно получить на этапе сортировки по биту из
младшего байта. Так как старший байт уже отсортирован, то в текущем
подмассиве все биты, старше чем маска, у всех элементов одинаковы.
Это позволяет вообще не трогать старший байт, а свести и сравнения, и
перестановки 16-битовых слов к сравнениям/перестановкам младших байтов
этих слов.
Если же учесть, что в таких примитивных микроконтроллерах аппаратного
сравнения 16-битных слов обычно не бывает (я не знаю, есть ли это в
конкретной железке "заказчика"), а оно делается путем вызова
спец. функции, то замена сравнения слов сравнением байтов (которое
аппаратно везде есть) также даст хороший выигрыш в скорости.
Я оцениваю суммарный выигрыш по скорости от всех трех описаных выше
"байт-модификаций" где-то в 30..50%. И этот выигрыш можно получить
только при поразрядной сортировке, когда сравнивается/переставляется
не все слово целиком. Все остальные способы сортировки (кроме
radix-sort), в том числе и heap-sort рассматривают сравниваемое
слово как атомарный обьект, и с "кусочками ключей" не работают
принципиально. Поэтому фокусы типа вышеописаных там принципиально
не могут быть примененны.
Покроет ли выигрыш в скорости от уполовинивания ключей потери памяти
от использования стека - заказчику решать. Он лучше меня знает,
сколько у него еще есть доступной памяти.
Я свое мнение высказал и обосновал. А дальше пусть заказчик думает,
что ему лучше.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
