Re: О сортировке. Алгоритм QSort



Posted by Владимир Секретев, Клуб Любителей Бухгалтерского Учета on December 18, 1998 at 11:13:12:

In Reply to: Re: О сортировке. Алгоритм QSort posted by Анатолий Таланин on December 16, 1998 at 09:21:15:

: Хочется получить объяснение различий в расходовании памяти при работе с одним и тем же объёмом данных при помощи фактов или экстрапараметров. Если "нагрузка" ложится на накладные расходы, то какие в пропорциях к данным?

Такого анализа я не проводил. Однако позволю себе предположить, что экстрапараметры с % не "двоятся" при режиме DUAL, и, кроме того, они "пропадают" при обновлении контекста, то есть имеют тенденцию к самоочищению, их не приходится таскать за собой из года в год. Преимуществ достаточно, чтобы отказаться от сортировки по фактам даже "при прочих равных".

--------------------------------------------------------------------------------------------------------------
: Владимир, уточните, что за функция tt в тексте алгоритма?
: x = [get %, PA+[intsn [tt (l+r)/2]]]

Конечно, это функция [tr], простите за очепятку.

--------------------------------------------------------------------------------------------------------------
: Предлагаю текст программы округления, которую мы применяем в расчётах. Конечно она очень похожа на приведённую на сайте с реализацией алгоритма QuickSort.
:....
: RO = [tr RO/PC+0.5] * PC
:....
: Очевидно применение точности округления в естественном, а не обратном представлении более оправдано.

Когда имеешь дело с последовательным делением и умножением, то всегда предпочтительно сначала выполнить умножение, чтобы не потерять точность. Поэтому я применяю коэффициент 100 для округления с точностью до целых копеек, например.

RO = [tr RO*PC+0.5]/PC

Не знаю что лучше - умножать на 100 или делить на 0.01. С точки зрения абсолютной математики - эквивалентно. Но мы имеем дело с внутренней механикой преобразования чисел в двоичный формат и обратно. Что там происходит, лучше спросить у Аркадия Григорьевича.
Я себя чувствую спокойнее, когда в моих программах сначала числа перемножаются, а потом делятся.




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