Совокупные максимумы, обозначенные буквой X в APL
Третий элемент в библиотеке FinnAPL называется "Кумулятивные максимумы (⌈) субвекторов Y, обозначенных X", где X - двоичный вектор, а Y - вектор чисел. Вот пример его использования:
X←1 0 0 0 1 0 0 0
Y←9 78 3 2 50 7 69 22
Y[A⍳⌈\A←⍋A[⍋(+\X)[A←⍋Y]]] ⍝ output 9 78 78 78 50 50 69 69
Вы можете видеть, что, начиная с начала или любого значения 1 в массиве X, кумулавный максимум находится для всех соответствующих цифр в Y, пока в X не будет найдена еще одна цифра 1. В приведенном примере X делит массив на два равные части по 4 номера в каждой. В первой части 9 - максимумы до 78, а во второй части 50 - максимумы до 69.
Это достаточно легко понять, и я мог бы слепо использовать его как есть, но я хотел бы понять, как он работает, потому что идиомы APL - это, по сути, алгоритмы, состоящие из операторов и функций. Чтобы хорошо понимать APL, важно понимать, как мастера смогли объединить все это в такие компактные и элегантные строки кода.
Я нахожу эту особую идиому особенно трудной для понимания из-за глубины вложенности двухуровневой индексации. Итак, мой вопрос, что делает эту идиому галочкой?
2 ответа
Эта идиома может быть разбита на более мелкие идиомы, и что наиболее важно, она содержит идиому № 11 из библиотеки FinnAPL под названием:
Повышение (⍋) для сортировки субвекторов Y, обозначенных X
Используя те же значения для X и Y, которые приведены в вопросе, вот пример его использования:
X←1 0 0 0 1 0 0 0
Y←9 78 3 2 50 7 69 22
A[⍋(+\X)[A←⍋Y]] ⍝ output 4 3 1 2 6 8 5 7
Как и прежде, X делит вектор на две половины, и выходные данные указывают, для каждой позиции, какая цифра Y необходима для сортировки каждой из половин. Итак, 4 в выводе говорит, что ему нужна 4-ая цифра Y (2) в 1-й позиции; 3 обозначает 3-ю цифру (3) во 2-й позиции; 1 обозначает первую цифру (9) в третьей позиции; и т.д. Таким образом, если мы применим это индексирование к Y, мы получим:
Y[A[⍋(+\X)[A←⍋Y]]] ⍝ output 2 3 9 78 7 22 50 69
Чтобы понять индексацию в рамках этой идиомы повышения квалификации, рассмотрим, что происходит со следующим:
(+\X)[A←⍋Y] ⍝ Sorted Cumulative Addition
Разбивая это шаг за шагом:
A←⍋Y ⍝ 4 3 6 1 8 5 7 2
+\X ⍝ 1 1 1 1 2 2 2 2
(+\X)[A←⍋Y] ⍝ 1 1 2 1 2 2 2 1 SCA
A[⍋(+\X)[A←⍋Y]] ⍝ 4 3 1 2 6 8 5 7
Вы можете видеть, что отсортированное совокупное сложение (SCA) X 1 1 2 1 2 2 2 1 применяется к A действует как комбинация компрессии влево и компрессии вправо. Все значения A, совпадающие с 1, сдвигаются влево, а значения, совпадающие с 2, сдвигаются вправо. Конечно, если бы X имел больше 1 с, он бы сжимал и определял местоположение сжатых пакетов в порядке, указанном значениями результата SCA. Например, если SCA X были похожи 3 3 2 1 2 2 1 1 1В итоге вы получите 4 цифры, соответствующие 1 секундам, затем 3 цифры, соответствующие 2 секундам, и, наконец, 2 цифры, соответствующие 3 секундам.
Возможно, вы заметили, что я пропустил шаг, который покажет эффект повышения ⍋:
(+\X)[A←⍋Y] ⍝ 1 1 2 1 2 2 2 1 SCA
⍋(+\X)[A←⍋Y] ⍝ 1 2 4 8 3 5 6 7 Grade up
A[⍋(+\X)[A←⍋Y]] ⍝ 4 3 1 2 6 8 5 7
Эффект сжатия и перестановки не достигается одной только SCA. Это эффективно действует как звание, как я обсуждал в другом посте. Также в этом посте я говорил о том, что ранг и индекс по сути являются двумя сторонами одной медали, и вы можете использовать оценку вверх для переключения между ними. Следовательно, это то, что происходит здесь: SCA преобразуется в индекс для применения к A, и эффект - это сортированные по вектору субвекторы, как указано X.
От отсортированных субвекторов к совокупным максимумам
Как уже было описано, результатом сортировки субвекторов является индекс, который при применении к Y сжимает данные в пакеты и упорядочивает эти пакеты в соответствии с X. Дело в том, что это индекс, и снова применяется повышение класса, который конвертирует индексы в ранги:
⍋A[⍋(+\X)[A←⍋Y]] ⍝ 3 4 2 1 7 5 8 6
Вопрос здесь в том, почему? Что ж, следующим шагом является применение кумулятивных максимумов, и это действительно имеет смысл, только если оно применяется к значениям для ранга, которые представляют относительную величину в каждом пакете. Глядя на значения, вы можете видеть, что 4 - это максимумы для первой группы из 4, а 8 - для второй группы. Эти значения соответствуют входным значениям 78 и 69, что мы и хотим. Не имеет смысла (по крайней мере, в этом случае) применять максимумы к значениям индекса, которые представляют позицию, поэтому необходимо преобразование в ранг. Применение кумулятивных максимумов дает:
⌈\A←⍋A[⍋(+\X)[A←⍋Y]] ⍝ 3 4 4 4 7 7 8 8
Это оставляет последний шаг для завершения индекса. После выполнения операции кумулятивных максимумов векторные значения по-прежнему представляют ранг, поэтому их необходимо преобразовать обратно в значения индекса. Для этого используется оператор index-of. Он принимает значение в правом аргументе и возвращает их позицию, найденную в левом аргументе:
A⍳⌈\A←⍋A[⍋(+\X)[A←⍋Y]] ⍝ 1 2 2 2 5 5 7 7
Чтобы было легче увидеть:
3 4 2 1 7 5 8 6 left argument
3 4 4 4 7 7 8 8 right argument
1 2 2 2 5 5 7 7 result
4 находится во 2-й позиции в левом аргументе, поэтому результат показывает 2 для каждых 4 в правом аргументе. Индекс завершен, поэтому, применив его к Y, мы получим ожидаемый результат:
Y[A⍳⌈\A←⍋A[⍋(+\X)[A←⍋Y]]] ⍝ 9 78 78 78 50 50 69 69
Моя реализация:
X←1 0 0 0 1 0 0 0
Y←9 78 3 2 50 7 69 22
¯1+X/⍳⍴X ⍝ position
0 4
(,¨¯1+X/⍳⍴X)↓¨⊂Y
9 78 3 2 50 7 69 22 50 7 69 22
(1↓(X,1)/⍳⍴X,1)-X/⍳⍴X ⍝ length
4 4
(,¨(1↓(X,1)/⍳⍴X,1)-X/⍳⍴X)↑¨(,¨¯1+X/⍳⍴X)↓¨⊂Y
9 78 3 2 50 7 69 22
⌈\¨(,¨(1↓(X,1)/⍳⍴X,1)-X/⍳⍴X)↑¨(,¨¯1+X/⍳⍴X)↓¨⊂Y
9 78 78 78 50 50 69 69
∊⌈\¨(,¨(1↓(X,1)/⍳⍴X,1)-X/⍳⍴X)↑¨(,¨¯1+X/⍳⍴X)↓¨⊂Y
9 78 78 78 50 50 69 69
Хорошего дня.