Dlaczego pętla jest tak powolna w kodzie Racket

Question

Próbuję znaleźć najmniejszy nie będący dzielnikiem liczb (https://codegolf.stackexchange.com/questions/105412/find-the-smallest-number-that-doesnt-divide-n). Kolejna wersja używając 'Niech nazwie' działa prawidłowo:

(define (f1 m) 
    (let loop ((n 2)) 
    (cond 
     [(= 0 (modulo m n)) 
     (loop (+ 1 n))] 
     [else n]))) 

Mam testowanie z:

(f 24) 
(f 1234567) 
(f 12252240) 
(f 232792560) 

Przede wersji wywołuje natychmiastowe wyjście: 5 2 19 i 23.

Jednak po wersji która używa wbudowanej pętli for jest bardzo powolna i faktycznie zawiesza się z powodu błędu braku pamięci przy większych numerach:

(define (f2 m) 
    (for/first ((i (range 2 m)) 
       #:when (not (= 0 (modulo m i))) 
       #:final (not (= 0 (modulo m i)))) 
    i)) 

Czy jest jakiś błąd w kodzie drugiej wersji, czy też jest to for nieefektywna pętla w porównaniu z nazwaną let in Racket?

Answer 1

Funkcja range faktycznie przydziela listę, więc czas dla twojej funkcji jest zdominowany przez ogromną alokację listy. Użyj in-range zamiast:

(define (f2 m) 
    (for/first ([i (in-range 2 m)] 
       #:when (not (= 0 (modulo m i))) 
       #:final (not (= 0 (modulo m i)))) 
    i)) 

Zobacz także sekcję for performance w Racket Przewodnik po więcej informacji dotyczącej względnej prędkości różnych form sekwencji.

Answer 2

Moim zdaniem, rekurencja jest bardziej odpowiednia dla rakiety niż pętli. Podejdę do problemu w ten sposób ...

(define start-counter 1) 

(define (f number counter) 
    (cond [(not (= (modulo number counter) 0)) counter] 
     [else (f number (add1 counter))])) 

(define (f2 number) 
    (f number start-counter))