Сжатие довольно большой таблицы в APL
В настоящее время я работаю над поиском палиндрома, состоящего из перемножения чисел длины 3 (от 900 до 1000). Я могу создать таблицу палиндромов в двоичном формате (1/0). Однако функция сжатия (/) выдает ошибку в отношении хранения. Я не уверен, почему сжатие данной двоичной таблицы может вызвать такую проблему.
new_set ← (900 + ⍳100)
{(⊃⍵)≡⌽⊃⍵}¨ ⊂∘⍕¨ (new_set ∘.× new_set)
{(⊃⍵)≡⌽⊃⍵}¨ ⊂∘⍕¨ (new_set ∘.× new_set) / ∘⍕¨(new_set ∘.× new_set)
WS FULL: Maximum workspace is 512 kilobytes.
Обновлено: изменение new_set на (⍳10) дает то же решение в третьей строке, что и строка перед ней (двоичная). Очень нужна помощь с функцией сжатия. Любая помощь очень ценится.
Хорошо. Я подумал, что может быть хороший способ запустить команду на tryapl.org. Однако их онлайн-веб-сервер может не допустить внесения изменений. Спасибо, @LdBeth.
На самом деле я попробовал эту функцию на меньшем подмножестве new_set, и она создает ту же двоичную таблицу... Тьфу.
Ответы 2
{(⊃⍵)≡⌽⊃⍵}¨ ⊂∘⍕¨ (новый_набор ∘.× новый_набор) / ∘⍕¨(новый_набор ∘.× новый_набор)
Помните, что в APL каждая функция вычисляется правоассоциативно. Это означает, что левый аргумент /∘⍕¨ выше на самом деле (new_set ∘.× new_set). Вам нужно будет использовать круглые скобки, чтобы задать желаемый порядок оценки. А еще лучше попробуйте найти другое написание, в котором вообще не используются круглые скобки.
Однако каждый (¨) здесь означает, что /∘⍕ вызывается для каждой пары элементов в new_set ∘.× new_set, а это означает, что для каждого элемента new_set левый аргумент для / оказывается некоторым числом порядка 500 000, а правый аргумент — строковым представлением. этого числа. Другими словами, вы повторяете каждую цифру примерно 500 000 раз для каждого из этих чисел. Это примерно 300e9 = 6×500 000×100 000 байт или 300 ГБ. Даже моя локальная машина с ограничением рабочей области 12 ГБ не может справиться с этим!
На этом этапе я хотел бы дать вам несколько небольших советов по устранению вышеуказанной проблемы, но, честно говоря, я не совсем уверен, каково ваше намерение в приведенном выше фрагменте кода.
Ознакомьтесь с документацией для Replicate и обратите внимание, что левый аргумент должен быть вектором. Однако ваш левый аргумент представляет собой массив 100 на 100. Если вам на самом деле больше не нужна информация о форме, то сначала зачисление (∊) аргументов может привести вас туда, куда вы хотите.
Еще раз спасибо, @B. Уилсон!! Проверьте это: ∪({(⊃⍵)≡⌽⊃⍵}¨ ⊂∘⍕¨ (new_set ∘.× new_set)) / ∘⍕¨(new_set ∘.× new_set). Это как раз то, что мне нужно. Это не очень красиво, но определенно работает. С вербовкой все хрустит... Но эта уникальность (у), хоть и не эстетичная, но свое дело делает. Как вы думаете, этого будет достаточно?
Красивый! Рад, что ты смог что-то выговорить. Что касается использования Unique (∪), я не думаю, что это так уж плохо. Как указывает ниже Авагга, поскольку умножение является коммутативным, любое решение, использующее внешний продукт, должно будет каким-то образом справляться с дубликатами, и Unique — это очевидный и простой способ их устранения. Если хватит, то хватит! Это конкретное решение не очень хорошо масштабируется для больших наборов данных, но эй, эта проблема не использует большой набор данных, так что у нас все хорошо.
Расширяя ответ Б. Уилсона,
Итак, задача — мы хотим вернуть найденные в таблице умножения палиндромы целых чисел в диапазоне от 900 до 1000.
Мы можем начать с диапазона:
n ← (900 + ⍳100)
Прямолинейный и, как было сказано, APL является правоассоциативным, то есть функции применяются ко всему справа и к одному аргументу слева. Учитывая это, эти скобки лишние, и мы можем их удалить.
Далее, для создания таблицы:
n ∘.× n
Большой. Все любят внешний продукт, и поскольку эта проблема по своей сути является O(n^2), мы мало что можем сделать, чтобы избежать WS FULL на больших аргументах.
Вот где тонко вводится - нужны ли нам уникальные умножения? Например, должны ли мы включать 901×901, а также 902×901 и 901×902, если нет — есть несколько вещей, которые мы можем сделать, чтобы уменьшить пространство.
⊃,/(1↓n)×,\¯1↓n
Это выражение является одним из способов избежать именно таких случаев.
Теперь о палиндромах. Как известно, в APL идиоматично использовать логические маски для фильтрации элементов.
Ваш подход был
{(⊃⍵)≡⌽⊃⍵}¨ ⊂∘⍕¨
Работает хорошо! Замечу, что ⊂ лишний, так как мы сразу выполняем обратную операцию при вызове функции.
Итак, мы можем написать:
{⍵≡⌽⍵}∘⍕¨
Наконец, фильтр. Вы заметили, что каждый элемент маски не связан с каждым элементом таблицы. Правильно, для неодноэлементных масок / будет фильтроваться по основным ячейкам. Например:
1 0 1 / 3 3⍴⍳9
1 3
4 6
7 9
Итак, чтобы обойти вашу проблему, мы можем заранее распутать (сгладить) обе стороны:
{(,{⍵≡⌽⍵}∘⍕¨⍵)/,⍵} n ∘.× n
Полное решение! Я предложу некоторые альтернативы (незначительные изменения) для исследования.
{⍵/⍨(≡∘⌽⍨⍕)¨⍵}⊃,/(1↓n)×,\¯1↓n
{⍵/⍨⍥,(≡∘⌽⍨⍕)¨⍵}∘.×⍨
Красивый. Я попробовал ваше решение, и оно работает! Однако последний вызывает у меня проблемы. Я ввел ({⍵/⍨⍥,(≡∘⌽⍨⍕)¨⍵}∘.×⍨) / ∘⍕¨(new_set ∘.× new_set). TryAPL выдает ошибку «Ошибка домена». Тем не менее, я пошел дальше и принял ваше решение. Спасибо!
вы можете установить для MAXWS гораздо большее значение в файле конфигурации, см. раздел руководства, соответствующий вашей платформе.