Способ использования sort с любой заданной упорядоченностью алфавита



Posted by Аркадий Водяник (195.58.229.56) on June 03, 2002 at 02:58:59:

In Reply to: Новое знание №12 posted by Владимир Секретев on May 31, 2002 at 00:01:47:

Владимир Секретев прав, говоря:

: Оператор SORT задает жесткую и не всегда удобную последовательность сортировки.

В то же время, такой алгоритм как сортировка, написанный на языке ФБП,
будет значительно уступать в быстродействии такому же алгоритму,
написанному, например, на C, и над которым поработал оптимизирующий
компилятор - именно так и сделан встроенный оператор SORT.

Поэтому я склоняюсь к использованию встроенного оператора и
предварительной подготовке сортируемого материала путем перекодирования
исходного набора слов в нужную кодировку, записанную в массиве.
Рассмотрим, какая скорость перекодирования достигается.
Задействуем функцию [hc s,i], выдающую код i-го знака строки s.


Вpеменной пpофиль фоpмы (машина P233, RAM 64Mb)

Количество выполнений: 1.
На это количество выполнений потpебовалось 424 мс = 100%
Распpеделение вpемени по стpокам исходного текста в относительных %, и мс:

~ ~¦0001 * Пусть необычный алфавит для сортировки задан массивом а.
~ ~¦0002 * В данном случае коды символов 'переворачиваются':
~ ~¦0003 *
~ 3¦0004 for i=1 to 255 [a i,256-i]; endfor
~ ~¦0005 *
~ ~¦0006 * Пусть p - подлежащий сортировке массив.
~ ~¦0007 * Для наших целей достаточно иметь только один элемент массива,
~ ~¦0008 * так как в этом примере мы не будем вызывать собственно SORT,
~ ~¦0009 * а сколько бы элементов массива не было на самом деле, на замерах
~ ~¦0010 * времени перекодирования это не скажется.
~ ~¦0011 *
~ 1¦0012 [p 1,'qwertyuiopasdfghjklz']
~ ~¦0013 *
~ ~¦0014 * Пусть нам требуется перекодировать 1000 элементов массива:
~ ~¦0015 *
~ ~¦0016 for j=1 to 1000
3.8% 16¦0017 L=[length [p 1]]; t=[ch [a [hc [p 1],1]]]
# 8.3% 35¦0018 for i=2 to L
############ 62.7% 266¦0019 t=t+[ch [a [hc [p 1],i]]]
#### 21.7% 92¦0020 [q 1,t]
2.6% 11¦0021 endfor
~ ~¦0022 endfor

Видно, что расходы времени на преобразование вполне терпимые.
Видно также, что в языке ФБП не хватает конструкции для замены знака строки,
поэтому приходится прибегать к "пересборке" строки (62.7%, строка программы - 19).

Когда массив Q с требуемым алфавитом готов, можно применить вызов:


sort Q, Z, n

где n - количество слов, подлежащих сортировке, а Z - массив, в который будут
помещены числа - номера элементов массива P так, что при распечатке вида:

for i=1 to n
printstr [P [Z i]]

endfor


мы получим список элементов массива P, упорядоченных в соответствии с перекодированием,
заданным в массиве A.


Пpишедшие ответы: