Беглый просмотр документации на Фактор вызвал подозрение, что в нем нет возможности создавать определяющие слова. В большинстве языков способы создания новых понятий жестко зашиты в язык. У Форта имеется механизм создания определяющих слов. Которыми в примере являются make_value и make_delimeter. В Форте можно не просто создавать новые понятия, а создавать необходимые инструменты для создания понятий.
Совершенно справедливо. Да, пример безусловно демонстрационный. Цель была — подогреть интерес. Приятно слышать, что язык активно используется и есть люди хорошо его знающие.
О боже! Зачем городить такой огород? Форт тем и прелестен, что он вещь в себе. Нет никаких проблем сделать так, чтобы весь Форт-интерактив шел через браузер. Сделать все это средствами самого Форта.
80 порт в приведенной программе я назначил не просто так. К этому наносерверу можно подключиться любым браузером из любой точки интернета, если позволяет файервол.
Придется во второй части развить тему.
Все сортировки без сравнений похожи. Суть — распределить n чисел по m классам. Только мало кто догадывается, что классов должно быть не менее n.
Кстати, свежая догадка. Если классов взять больше n, вплоть до nmax-nmin, то тогда слипаний станет существенно меньше, а при m= nmax-nmin их не будет вовсе. Разумеется, последнее справедливо для целых чисел. То-есть в массиве Indxs(i) будут только нули и единицы, вследствие чего сборка будет происходить за линейное время без дополнительных действий. Пугает расход памяти, но это решаемая проблема.
Конечно, реализован будет промежуточный вариант. Возможно, m=n*3 будет достаточно для существенного сокращения обычно большого количества пар и троек.
>> Поведение нелинейности может напоминать вообще какую-нибудь хитрую недосинусоидную псевдоэкспоненту, которая станет очевидна только в конце процесса.
Проще. Отсортированный рост является неубывающим. А если договориться о неразличимости одинаковых чисел, то и строго возрастающим. И чаще всего его вид будет кусочно линейно-нелинейным.
Этот алгоритм сортировки сам в некоторой степени являет собой кусочно-линейную аппроксимацию. С разрывами на стыках кусков. Естественно, что в линейной версии он спотыкается на экспоненте, которую как ни дифференцируй — она остается экспонентой. Но не страшно, для нее у нас припасен логарифм. Вопрос, похоже, становится чисто организационным. Когда выгоднее логарифмировать, в первом проходе, во втором или вообще запускать обе версии параллельно.
Что касается расходов по памяти — их можно сильно уменьшить. Массив количества индексов никуда не денется, конечно. Но вместо копирования самих чисел мы сохраняем указатели на них. Особенно выгодно получается, если работаем с действительными числами полной точности. (Само число — 10 байт, ссылка на него — 2 или 4 байта). Итого — памяти нужно не более 4n. В байтах: 10*n+ 2*3 n.
>>Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
Вот. Именно. Еще одна фундаментальная мысль. Если имеется дополнительная информация об обрабатываемых неким алгоритмом данных, то она позволяет снизить сложность алгоритма. Как пример — таблицы Брадиса. Можно считать синусы с помощью рядов, а можно выбрать значение из таблицы.
Кстати, она прекрасно работает и с вещественными числами. Для логарифмов сдвигаем весь набор вправо на n min+ основание логарифма. Назад числа в наборе уменьшать не нужно. Сами числа мы не трогаем. Сдвиг нам нужен только для вычисления индексов.
Главная фишка в том, что наборы чисел, которые в отсортированном виде ложатся на прямую delta*i+n min, i=0..n сортировать вообще не нужно. Достаточно сгенерировать заново этот набор.
Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.
Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
1) Если данные линейны или близки к линейным, оперируем со значениями.
2) Если нелинейны, причем сильно — логарифмируем. Натуральные логарифмы вполне годятся.
Вообще в нелинейном случае стоит задача сжать динамический диапазон значений. Может быть, арктангенс подойдет даже лучше.
Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.
Родилось решение по сортировке факториалов и быстрого роста.
Вычисление индекса надо производить над логарифмами сортируемых значений.
delta=(log(n max)-log(n-min))/n+1
indx=(log(n i)-log(n min))/delta+1
Подходящее основание логарифма от 1,1 до 2.
Логарифмирование не отменяет следующих итераций, которые уже можно делать над самими значениями, но исключает квадратичную сложность.
Да, факториалы крайне неприятны для сортировки. Интересно, есть ли алгоритм сортирующий их за время меньше квадратичного? Навскидку, для неприятностей хватает даже не факториального роста, а лишь степенного.
Обдумываю тоже эту тему. Надо каким-то образом выявить сильную нелинейность. Пока осмысливается критерий того что что-то не так — вызов второй итерации, для которой количество значений несущественно меньше, чем начальное n. Раз так, то вместо того чтобы дальше сортировать с квадратичной сложностью, нужно либо интерполировать поточнее, либо использовать какой-то другой алгоритм сортировки.
Да, верно. Математический склад ума все-таки отличается от обывательского. Никогда бы не пришло в голову сортировать факториалы. У факториалов и прочих сильно растущих функций есть один недостаток — сложно выписать достаточно много значений. Разрядность ограничена.
Кроме того, можно применить «ход конем». Если имеются предположения о функции, порождающей отсортированный массив, можно применить нелинейное распределение значений по местам. Перемешанные факториалы, экспоненты и подобные сильно меняющиеся значения довольно специфичны.
Соглашусь, очень похоже. Но есть принципиальные отличия, меняющие картину. Пресловутая досортировка здесь сводится к минимуму. Она производится для массивчиков из 2-х, 3-х и 4-х чисел, где она тривиальна и мало затратна.
Во вторую итерацию попадают подмассивы с разностью n max — n min близкой к n, то-есть уже во второй итерации слипаний, а значит и операций сравнения будет немного. То-есть даже на плохих данных сложность не должна превосходить n log n.
Одна простая, но очень важная мысль: «В массиве из n чисел всегда не более чем n различных значений».
Можно порадоваться за родную науку. Еще в 1979 году была выпущена научно-популярная книжка на тему работы зрения. Автор: Вячеслав Демидов. «Как мы видим, то что видим»
80 порт в приведенной программе я назначил не просто так. К этому наносерверу можно подключиться любым браузером из любой точки интернета, если позволяет файервол.
Придется во второй части развить тему.
Кстати, свежая догадка. Если классов взять больше n, вплоть до nmax-nmin, то тогда слипаний станет существенно меньше, а при m= nmax-nmin их не будет вовсе. Разумеется, последнее справедливо для целых чисел. То-есть в массиве Indxs(i) будут только нули и единицы, вследствие чего сборка будет происходить за линейное время без дополнительных действий. Пугает расход памяти, но это решаемая проблема.
Конечно, реализован будет промежуточный вариант. Возможно, m=n*3 будет достаточно для существенного сокращения обычно большого количества пар и троек.
Проще. Отсортированный рост является неубывающим. А если договориться о неразличимости одинаковых чисел, то и строго возрастающим. И чаще всего его вид будет кусочно линейно-нелинейным.
Этот алгоритм сортировки сам в некоторой степени являет собой кусочно-линейную аппроксимацию. С разрывами на стыках кусков. Естественно, что в линейной версии он спотыкается на экспоненте, которую как ни дифференцируй — она остается экспонентой. Но не страшно, для нее у нас припасен логарифм. Вопрос, похоже, становится чисто организационным. Когда выгоднее логарифмировать, в первом проходе, во втором или вообще запускать обе версии параллельно.
Что касается расходов по памяти — их можно сильно уменьшить. Массив количества индексов никуда не денется, конечно. Но вместо копирования самих чисел мы сохраняем указатели на них. Особенно выгодно получается, если работаем с действительными числами полной точности. (Само число — 10 байт, ссылка на него — 2 или 4 байта). Итого — памяти нужно не более 4n. В байтах: 10*n+ 2*3 n.
>>Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
Вот. Именно. Еще одна фундаментальная мысль. Если имеется дополнительная информация об обрабатываемых неким алгоритмом данных, то она позволяет снизить сложность алгоритма. Как пример — таблицы Брадиса. Можно считать синусы с помощью рядов, а можно выбрать значение из таблицы.
Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.
Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
1) Если данные линейны или близки к линейным, оперируем со значениями.
2) Если нелинейны, причем сильно — логарифмируем. Натуральные логарифмы вполне годятся.
Вообще в нелинейном случае стоит задача сжать динамический диапазон значений. Может быть, арктангенс подойдет даже лучше.
Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.
Вычисление индекса надо производить над логарифмами сортируемых значений.
delta=(log(n max)-log(n-min))/n+1
indx=(log(n i)-log(n min))/delta+1
Подходящее основание логарифма от 1,1 до 2.
Логарифмирование не отменяет следующих итераций, которые уже можно делать над самими значениями, но исключает квадратичную сложность.
Кроме того, можно применить «ход конем». Если имеются предположения о функции, порождающей отсортированный массив, можно применить нелинейное распределение значений по местам. Перемешанные факториалы, экспоненты и подобные сильно меняющиеся значения довольно специфичны.
Во вторую итерацию попадают подмассивы с разностью n max — n min близкой к n, то-есть уже во второй итерации слипаний, а значит и операций сравнения будет немного. То-есть даже на плохих данных сложность не должна превосходить n log n.
Одна простая, но очень важная мысль: «В массиве из n чисел всегда не более чем n различных значений».