Re: быстpая соpтиpовка

From

Oleg Khovayko ()

To

Andrew Ezhguroff

Date

2002-12-27T06:07:41Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Andrew Ezhguroff wrote:

> Но рекурсия все же нужна. И, следовательно, дополнительная память для
> организации рекурсии нужна (так что в п.3 ты не прав).

При программировании микроконтроллеров обычно подразумеваются
раздельные секции кода, данных, стека, I/O page. И обычно они никак не 
пересекаются, тем более, что секция кода вообще лежит в ПЗУ.
Именно это я и подразумевал в п.3, когда писал "память данных".
Там я подразумевал, что стек болтается в своем сегменте, и с данными
не перемешивается.
Извини, если невнятно обьяснился.

> Пирамидальная сортировка обеспечивает O(N*log(N)) для любых данных (правда с
> большим коэф. пропорциональности - она работает медленнее лучшего случая
> быстрой сортировки) и не требует рекурсии и дополнительных массивов.

Да я же не спорю. Побитовая сортировка тоже имеет свои недостатки.
Но в данном конкретном применении - а именно "16-и разрядные числа в 
8-битовой машине" - она демонстрирует некоторые преимущества, связаные с 
возможность "уполовинивать" сортируемые слова.

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

Аналогичное упрощение можно получить на этапе сортировки по биту из
младшего байта. Так как старший байт уже отсортирован, то в текущем 
подмассиве все биты, старше чем маска, у всех элементов одинаковы.
Это позволяет вообще не трогать старший байт, а свести и сравнения, и 
перестановки 16-битовых слов к сравнениям/перестановкам младших байтов 
этих слов.

Если же учесть, что в таких примитивных микроконтроллерах аппаратного 
сравнения 16-битных слов обычно не бывает (я не знаю, есть ли это в 
конкретной железке "заказчика"), а оно делается путем вызова
спец. функции, то замена сравнения слов сравнением байтов (которое 
аппаратно везде есть) также даст хороший выигрыш в скорости.

Я оцениваю суммарный выигрыш по скорости от всех трех описаных выше
"байт-модификаций" где-то в 30..50%. И этот выигрыш можно получить
только при поразрядной сортировке, когда сравнивается/переставляется
не все слово целиком. Все остальные способы сортировки (кроме
radix-sort), в том числе и heap-sort рассматривают сравниваемое
слово как атомарный обьект, и с "кусочками ключей" не работают 
принципиально. Поэтому фокусы типа вышеописаных там принципиально
не могут быть примененны.

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


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)