Объяснение быстрой сортировки в APL

Question

Я пытаюсь понять классическую c быструю сортировку в APL:

Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}

Есть некоторые вещи, которые я не понимаю, и некоторые стилистические c варианты, которые меня беспокоят, поэтому я ' Я собираюсь перечислить их всех. Я надеюсь, что кто-то сможет мне их объяснить.

1. Я понимаю, что внутри { } defn, ⍺ - левый аргумент, а ⍵ - правильный аргумент. Что такое ⍺⍺ в S←{⍺⌿⍨⍺ ⍺⍺ ⍵}? Точно так же есть ⍵⍵? Указывает ли ⍺ внутри S на левый аргумент S или левый аргумент Q?

Я предполагаю, что ⍺ внутри S относится к левому аргументу S. ⍺⍺ относится к ⍺ включающей функции (ie, ⍺ из Q).

Почему обильное использование коммутирует (⍨)? Не так ли ясен код, записанный как:

Q←{1≥≢⍵:⍵ ⋄ S←{(⍺ ⍺⍺ ⍵)⌿⍺} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵[?≢⍵]}

Единственное, что я могу подумать об использовании коммутирования, - это сокращение использования скобок () и [], но это вряд ли стоит потеря разборчивости. Я что-то упускаю из «пути APL» здесь?

Это на самом деле не выполняет быструю сортировку, не так ли? Быстрая сортировка определяется как на месте . Однако мое понимание семантики APL состоит в том, что этот фрагмент кода на самом деле строит новые массивы на рекурсивных под-вызовах и объединяет их, используя ⍪. Действительно, это та же самая критика , которая направлена ​​на быструю сортировку Haskell . Что-то мне не хватает в семантике APL, которая сообщает, что эта операция выполняется "на месте"? Обратите внимание, что меня не интересуют аргументы «достаточно умного компилятора», так как анализ массива является принципиально сложной задачей. Если компилятор APL действительно превращает это в алгоритм на месте , я бы очень оценил детали того, как ему удается выполнить этот анализ - это довольно большое достижение!

Зачем использовать ≢⍵, чтобы найти размерный размер? Почему не ⍴⍵? В целом, я нахожу, что люди используют ≢ над ⍴, чтобы запросить размер по внешнему измерению, , даже когда единственный случай, когда работа функции находится в 1D . Опять же, я предполагаю, что в APL есть что-то, чего мне не хватает.

Большое спасибо.

Answer 1

1. Я понимаю, что внутри { } defn, ⍺ - левый аргумент, а ⍵ - правильный аргумент. Что такое ⍺⍺ в S←{⍺⌿⍨⍺ ⍺⍺ ⍵}? Аналогично, существует ли ⍵⍵?

S←{⍺⌿⍨⍺ ⍺⍺ ⍵}, называемый доп . Подобно тому, как dfn является пользовательской функцией, dop является пользовательским оператором, который ведет себя как ¨, ⍨ или ∘.

Сводка семантики:

• Если допинг упоминает только ⍺⍺ (не ⍵⍵), он становится оператором монади c, который можно использовать как x (m S) y.
• Если допинг упоминает ⍵⍵, он становится оператором c, который вы можете использовать как x (m S n) y.
• В обоих случаях ⍺⍺ (который будет иметь значение m) и ⍵⍵ (которые будут иметь значение n) могут быть массивом или функцией.
• Вы также можете решить не использовать ⍺ в теле допинга, в котором Если вы можете назвать его как (m S) y или (m S n) y, пропуская левый аргумент .
• m называется левый операнд и n является правым операндом . Это разные вещи из левого аргумента (x) и правого аргумента (y).

В вашем примере S упоминает только ⍺⍺, поэтому он называется x (m S) y. Если вы наберете S как 1 2 3 >S 2, оно будет равно 1 2 3⌿⍨1 2 3 > 2, что будет одним 3.

Указывает ли ⍺ внутри S на левый аргумент S или левый аргумент Q?

Внутри тела S все, что состоит из ⍺ и ⍵ символов, относится к аргументу / операнду S. Исходные аргументы Q являются невидимыми (если они не назначены сначала переменной, в этом случае они отображаются как имя переменной).

Почему обильное использование коммутирует (⍨)?

Я считаю, что это в основном стилистический выбор c. Я также предпочитаю писать заключенный в скобки код вместо использования его в производственном коде, за исключением случаев, когда использование легко распознается как идиома APL. Я пишу, например, 3÷⍨whatever вместо (whatever)÷3 для деления на константу.

Это на самом деле не выполняет быструю сортировку, не так ли?

Вы правы. Как вы уже упоминали, Quicksort предназначен для работы на месте, чтобы действительно стать Quick (TM). APL может выполнять предварительное выделение памяти и совместное использование массива, чтобы уменьшить часть копирования и выделения памяти, но, по крайней мере, некоторые копии неизбежны, когда создаются три подмассива (элементы которых меньше / равны / больше, чем сводная), и позже объединены.

Следует отметить, что в отличие от Haskell, APL имеет назначение на месте, которое выглядит как x[i]←v. Если бы кто-то правильно реализовал Quicksort в APL, ему пришлось бы кодировать, как если бы он кодировал в C (передача индексов рекурсивным вызовам и тому подобное).

Зачем использовать ≢⍵, чтобы найти размерный размер? Почему бы не ⍴⍵?

≢ называется "подсчет", а ⍴ - "форма". ≢ всегда возвращает скалярное значение, в то время как ⍴ возвращает вектор (это будет вектор длины один, если задан аргумент вектора). Хотя скаляр и вектор длины один ведут себя одинаково в большинстве сценариев ios, они являются разными вещами, например 1≡,1 ложно.

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