Ну что ж, засучим рукава!



Posted by Владимир Секретев (24.42.161.96) on June 04, 2002 at 22:22:31:

In Reply to: Способ использования sort с любой заданной упорядоченностью алфавита posted by Аркадий Водяник on June 03, 2002 at 02:58:59:

Не подлежит никакому сомнению, что

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

Однако, процесс подготовки данных тоже что-то «весит» и, по этому, не все так однозначно.
Короче говоря, я «засучил рукава» и проделал небольшой эксперимент.


Во-первых, перенес все подпрограммы сортировки из FIRST.RPT в форму, для того, чтобы получать реальную картину в профилере. Затем, воспользовавшись профилером сервера, выявил узкие места алгоритма и нешуточно их улучшил – достиг 30% улучшения производительности (см. таблицу).

Во-вторых, соорудил форму сортировки с перекодированием на основании алгоритма, предложенного Аркадием.

Постольку поскольку неотъемлемой частью этого алгоритма является косвенное извлечение данных (замедляющее процесс), то для чистоты эксперимента был сохранен цикл вывода данных в обоих формах, но без собственно оператора распечатки, чтобы не формировать файл. То есть так:


В «сортировке с перекодированием»

for i=LG to MG
A = [a [z i]]
endfor


В Qsort

for i =LG to MG
A = [a i]
endfor

Далее следует таблица, в которой в колонке SORT показаны цифры «сортировки с перекодированием», а в колонке Qsort показаны цифры, которые дает мой алгоритм.
В круглых скобках указано удельное время сортировки на один элемент.

Сразу скажу, что чуда не произошло. SORT с перекодировкой обгоняет меня.


Кол-во SORT Qsort v1.0 Qsort v1.3 Загрузка в клиента
------------------------------------------------------------------

1000 0.43 (0.43) 1.5 (1.50) 1.0 (1.0) 4 сек
2000 0.79 (0.39) 2.9 (1.45) 2.1 (1.1) 8 сек
3000 1.11 (0.37) 4.4 (1.47) 3.2 (1.1) 15 сек


Что это на практике – видно из таблицы. Сортировка 1000 элементов за пол секунды или за 1 секунду – большой разницы нет, особенно принимая во внимание время загрузки в клиента – примерно 4 сек на машине P266.

Время, полученное мною очень похоже на время, полученное Аркадием на подобной машине. К сожалению, тягаться с PIII-600 Бориса пока нет возможности, но чем лучше машина, тем незаметнее будет проигрыш. То есть 0.1 сек. против 0.3 сек., вообще никакого значения не имеет.

Резюме.

Есть хорошее готовое решение проблемы, которое можно приобрести на
ПКП. Всего за 4 VD.

Нет сомнения, что ваше приобретение окупится, так как новое лицензионное соглашение позволяет использовать настоящий алгоритм в своих коммерческих целях.


В комплект поставки входят:

1. Пример Qsort на экстра параметрах [%] для тех, кто не хочет пользоваться массивами.
2. Пример Qsort на массивах, для тех, кто не хочет пользоваться экстра параметрами и хочет достичь максимальной производительности.
3. Пример формы для сетевой версии, демонстрирующей возможность организовать сортировку по нескольким законам в одной форме и переключение между ними налету при помощи аргументов формы.
4. Форма, применявшаяся при тестировании быстродействия Qsort.
5. Форма, применявшаяся при тестировании «сортировки с перекодировкой», по алгоритму, предложенному А. Водяником (бесплатное приложение).
6. Подробное описание по установке и применению.


И последнее. Все купившие и зарегистрировавшие Qsort уже получили бесплатно новую версию 1.3 от 03.06.02.

Присоединяйтесь!


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