Я играл с реализацией lookandsay (OEIS A005150) в J. Я сделал две версии, очень простые, с использованием структур управления типа while.. Один повторяется, другой зацикливается. Поскольку я навязчивый, я начал использовать сравнительный тайминг для версий.
посмотрите и скажите - это последовательность 1 11 21 1211 111221, s, один, два, и т. Д.
Для ранних элементов списка (примерно до 20) цикличная версия выигрывает, но лишь на небольшую величину. Времена около 30 приводят к победе рекурсивной версии на достаточно большое количество, чтобы рекурсивная версия могла бы быть предпочтительнее, если бы пространство стека было достаточным для ее поддержки. Я посмотрел на почему и считаю, что это связано с обработкой промежуточных результатов. 30-е число в последовательности имеет 5808 цифр. (32-е число, 9898 цифр, 34-е, 16774.)
Когда вы решаете проблему с рекурсией, вы можете удерживать промежуточные результаты в рекурсивном вызове, а расстановка в конце создает результаты так, чтобы обработка результатов была минимальной.
В версии списка вам нужна переменная для хранения результата. Каждая итерация цикла требует добавления двух элементов к результату.
Проблема, на мой взгляд, заключается в том, что я не могу найти в J способа каким-либо образом изменить существующий массив без его полной переназначения. Итак, я говорю
try. o =. o,e,(0&{y) catch. o =. e,(0&{y) end.
поместить элемент в o, где o может не иметь значения при запуске. Это может быть заметно медленнее, чем
o =. i.0
.
.
.
o =. (,o),e,(0&{y)
Дело в том, что результат получается неправильной формы без бреда, или так кажется. Он как-то наследует форму от i.0.
Но даже такие функции, как} edit, не изменяют список, они возвращают список, в который были внесены изменения, и если вы хотите сохранить список, вам необходимо назначить его. По мере увеличения размера назначенного списка (когда вы проходите число от начала до конца, делая следующий номер), назначение, похоже, занимает больше времени и больше времени. Это присваивание - единственное, что я могу видеть: элемент 32, 9898 цифр, занимает меньше времени в рекурсивной версии, в то время как элемент 20 (408 цифр) занимает меньше времени в цикличной версии.
Рекурсивная версия создает возврат с помощью:
e,(0&{y),(,lookandsay e }. y)
Приведенная выше строка является и строкой возврата из функции, и рекурсией, поэтому весь вектор возврата создается сразу по мере того, как вызов достигает конца строки, и все стекируется.
В APL я думал, что можно что-то сказать порядка:
a[1+rho a] <- new element
Но когда я пытаюсь это сделать в NARS2000, я обнаруживаю, что это вызывает ошибку индекса. У меня нет доступа к любому другому APL, возможно, я помню эту идиому из APL Plus, я сомневаюсь, что она работала таким образом в APL \ 360 или APL \ 1130. Возможно, я полностью запомнил это.
Я не могу найти способ сделать это в J. Может быть, что нет способа сделать это, но следующая мысль состоит в том, чтобы предварительно выделить массив, который может содержать результаты, и изменить отдельные записи. Я также не вижу способа сделать это - то есть J не поддерживает идиому APL:
a<- iota 5
a[3] <- -1
Является ли это одним из тех побочных эффектов, которые запрещены из-за языковой чистоты?
Признает ли переводчик a=. a,foo или некоторые из его вариантов, что он должен быстро перейти к a[>:#a]=.foo внутри?
Это рекурсивная версия, черт побери. Я пробовал несколько разных версий, и я считаю, что чем дольше программа, тем медленнее, и, как правило, чем сложнее, тем медленнее. Как правило, программа может быть объединена в цепочку, так что, если вам нужен n-ый номер, вы можете выполнить поиск и сказать ^: n] y. Я перепробовал несколько оптимизаций, но проблема в том, что я не могу сказать, в какую среду я отправляю свой вывод. Если бы я мог сказать, что отправляю его на следующую итерацию программы, я бы отправил его как массив цифр, а не как большое число.
Я также подозреваю, что если бы я мог понять, как сделать молчаливую версию кода, он работал бы быстрее, основываясь на моем выводе, что когда я добавляю что-то в код, который должен сделать его короче, он работает дольше.
lookandsay=: 3 : 0
if. 0 = # ,y do. return. end. NB. return on empty argument
if. 1 ~: #@$ y do. NB. convert rank 0 argument to list of digits
y =. (10&#.^:_1) x: y
f =. 1
assert. 1 = #@$ y NB. the converted argument must be rank 1
else.
NB. yw =. y
f =. 0
end.
NB. e should be a count of the digits that match the leading digit.
e=.+/*./\y=0&{y
if. f do.
o=. e,(0&{y),(,lookandsay e }. y)
assert. e = 0&{ o
10&#. x: o
return.
else.
e,(0&{y),(,lookandsay e }. y)
return.
end.
)
Меня интересовали характеристики произведенных чисел.Я обнаружил, что если вы начинаете с 1, цифры никогда не становятся выше 3. Если вы начинаете с цифры больше 3, она выживет как одиночка, и вы также можете получить число в сгенерированные числа, начав с чего-токак 888888888, который сгенерирует число с одним 9 и одним 8 в конце номера.Но, кроме синглетонов, ни одна цифра не становится выше 3.
Редактировать: я сделал еще несколько измерений.Первоначально я написал программу для работы с вектором или скаляром, идея заключалась в том, чтобы внутренне я работал с вектором.Я думал о передаче вектора из одного слоя кода в другой, и я все еще мог бы использовать левый аргумент для управления кодом.Когда я передаю вектор верхнего уровня, код выполняется чрезвычайно быстро, поэтому я предполагаю, что большая часть процессора съедается путем преобразования очень длинных чисел из векторов в цифры.Рекурсивная процедура всегда пропускает вектор, когда он повторяется, возможно, поэтому он почти такой же быстрый, как цикл.
Это не меняет моего вопроса.
У меня есть ответ на этот вопрос, которыйЯ не могу писать в течение трех часов.Тогда я опубликую это, пожалуйста, не делайте тонны исследования, чтобы ответить на него.