Кумулятивные максимумы, обозначенные X в APL

Question

Третий пункт в FinnAPL Library называется «Кумулятивные максимумы (⌈) подвекторов Y, обозначенных X», где X - бинарный вектор, а Y os - вектор чисел. Вот пример его использования:

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, максимальная cumulave не найдено для всех соответствующих цифр в Y до другого 1 находится в X. В приведенном примере X разбивает массив на две равные части по 4 числа каждый. В первой части 9 - максимумы до 78, и во второй части 50 указаны максимумы до 69.

Это достаточно легко понять, и я мог вслепую использовать его, как есть, но я хотел бы понять, как это работает, потому что идиомы APL суть алгоритмы, состоящие из операторов и функций. Чтобы хорошо понять APL, важно понять, как мастера смогли сплести все это вместе в такие компактные и элегантные строки кода.

Я нахожу эту особую идиому особенно трудной для понимания из-за индексации вложенных двух слоев в глубину. Итак, мой вопрос заключается в том, что делает эту идиому тикающей?

Answer 1

Эта идиома может быть разбита на более мелкие идиомы, а самое главное, он содержит идиомы # 11 из библиотеки FinnAPL под названием:

Grade вверх (⍋) для сортировки подвекторы 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 

Как и прежде, Х деления вектора на две половины, а выходной сигнал указывает на то, для каждая позиция, какая цифра Y необходима для сортировки каждой из половин. Таким образом, 4 на выходе говорят, что ему нужна четвертая цифра Y (2) в 1-й позиции; 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) Х 1 1 2 1 2 2 2 1 применяется к А действует как ас ombination компрессии левого и сжатого правого. Все значения A, которые совпадают с 1, перемещаются влево, а те, которые выстраиваются в линию, перемещаются вправо. Конечно, если X было больше 1 с, это было бы сжатие и размещение сжатых пакетов в порядке, указанном значениями результата SCA. Например, если SCA X были похожи на 3 3 2 1 2 2 1 1 1, вы должны были бы получить 4 цифры, соответствующие 1s, за которыми следуют 3 цифры, соответствующие 2s, и, наконец, 2 цифры, соответствующие 3s.

Вы, возможно, заметили, что я пропустил шаг, который показал бы эффект класса до ⍋:

(+\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 

Эффект сжатия и перегруппировки не accomplised по SCA в одиночку. Он эффективно действует как ранг, как я обсуждал в другом post. Также в этом посте я говорил о том, как ранг и индекс являются по существу двумя сторонами одной и той же монеты, и вы можете использовать класс, чтобы переключаться между ними. Таким образом, это то, что происходит здесь: SCA преобразовывается в индекс, чтобы применить к А, а эффект класса вверх отсортирован Подвекторы как указано X.

из отсортированного Подвекторы в накопительном Maxima

Как уже было описано, результатом сортировки подвекторов является индекс, который при применении к 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 

Это последний последний шаг к завершению индекса. После выполнения операции кумулятивного максимума векторные значения по-прежнему представляют собой ранг, поэтому их необходимо преобразовать обратно в значения индекса. Для этого используется индекс-оператора. Он принимает значение из правого аргумента и возвращает свои позиции, как найти в левый аргумент:

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 

Answer 2

Моя реализация:

 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 

Иметь хороший день.