Memoization w J

Question

Za każdym razem, gdy używam przysłówka J M., wydajność znacznie się pogarsza. Ponieważ podejrzewam, że Iverson i Hui są znacznie mądrzejsi ode mnie, muszę zrobić coś złego.

Weź pod uwagę Collatz conjecture. Wydaje się, że istnieje wiele możliwości zapamiętywania tutaj, ale nie ważne gdzie umieszczam M., wydajność jest straszna. Na przykład:

hotpo =: -:`(>:@(3&*))@.(2&|) M. 
collatz =: hotpo^:(>&1)^:a:"0 
#@collatz 1+i.10000x 

Bez M., to działa w około 2 sekundy na moim komputerze. Z M., cóż, czekałem ponad dziesięć minut, aż to się zakończyło i ostatecznie zrezygnowałem. Ja również umieszczone M. w innych pozycjach z podobnie złych wyników, np

hotpo =: -:`(>:@(3&*))@.(2&|) 
collatz =: hotpo^:(>&1)M.^:a:"0 
#@collatz 1+i.10000x  

Może ktoś wyjaśnić prawidłowego wykorzystania M.?

Answer 1

M. nic tu dla ciebie nie robi.

Kod buduje łańcuch, jeden link na raz:

-:`(>:@(3&*))@.(2&|)^:(>&1)^:a:"0 M. 5 5 
5 16 8 4 2 1 
5 16 8 4 2 1 

Tutaj pamięta, że ​​5 prowadzi do 16, 16 prowadzi do 8, 8 prowadzi do 4, etc ... Ale co Czy to ci służy? Zastępuje pewną prostą arytmetykę przy pomocy przeszukiwania pamięci, ale arytmetyka jest tak banalna, że ​​prawdopodobnie jest szybsza od wyszukiwania. (Jestem zaskoczony, że twój przykład zajmuje 10 pełnych minut, ale to nie ma sensu.)

Aby poprawić pamięć, należy zastąpić droższe obliczenia.

Dla tego konkretnego problemu, może chcesz funkcję, która pobiera liczbę całkowitą i zwraca 1 jeśli i gdy sekwencja przybywa 1. Na przykład:

-:`(>:@(3&*))@.(2&|)^:(>&1)^:_"0 M. 5 5 
1 1 

Ja tylko wymienić ^:a: z ^:_ , aby odrzucić wyniki pośrednie. Nawet wtedy, to nie robi wielkiej różnicy, ale można użyć timespacex aby zobaczyć efekt:

timespacex '-:`(>:@(3&*))@.(2&|)^:(>&1)^:_"0  i.100000' 
17.9748 1.78225e7 
    timespacex '-:`(>:@(3&*))@.(2&|)^:(>&1)^:_"0 M. i.100000' 
17.9625 1.78263e7 

Uzupełnienie: Umieszczenie M. względem "0 nie wydaje się, aby ogromna różnica. Myślałem, że zrobiłem tam błąd, ale szybki test wykazał, że ich zamiana spowodowała ogromne straty wydajności zarówno w czasie i przestrzeni:

timespacex '-:`(>:@(3&*))@.(2&|)^:(>&1)^:_ M. "0 i.100000' 
27.3633 2.41176e7 

M. zachowuje rangę podstawowej czasownika, więc dwa są semantycznie równoważny, ale podejrzewam, że z "0 na zewnątrz w ten sposób, M. nie wie, że ma do czynienia z skalarami. Więc domyślam się, że tutaj jest pewna, że ​​M. wie, z czym ma do czynienia. :)

---

BTW, jeśli przypuszczenie Collatz okazały się fałszywe, a karmione ten kod kontrprzykład, to wpada w nieskończoną pętlę zamiast produkować odpowiedź.

Aby rzeczywiście wykryć kontrprzykład, należy monitorować wyniki pośrednie, aż do znalezienia cyklu, a następnie zwrócić najniższą liczbę w cyklu. Aby to zrobić, prawdopodobnie chcesz zaimplementować niestandardowe przysłówek, który zastąpi ^:n.