Tại sao cho vòng lặp quá chậm trong mã Vợt

Question

Tôi đang cố gắng tìm số không nhỏ nhất của số (https://codegolf.stackexchange.com/questions/105412/find-the-smallest-number-that-doesnt-divide-n). Sau phiên bản sử dụng 'tên let' hoạt động đúng:

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

Tôi đang thử nghiệm với:

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

Trên phiên bản sản xuất đầu ra kịp thời: 5 2 19 và 23.

Tuy nhiên, phiên bản sau sử dụng vòng lặp được xây dựng trong for rất chậm và thực sự gặp sự cố với lỗi lớn hơn với số lớn hơn:

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

Có một số lỗi trong mã của phiên bản thứ hai hoặc là for vòng lặp không hiệu quả so với tên cho phép trong vợt?

Answer 1

Hàm range thực sự phân bổ danh sách, do đó, thời gian cho hàm của bạn bị chi phối bởi phân bổ danh sách lớn. Sử dụng in-range thay vì:

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

Xem thêm phần trên for performance trong Hướng dẫn vợt cho các ghi chú thêm về tốc độ tương đối của các hình thức chuỗi khác nhau.

Answer 2

Theo ý kiến ​​của tôi, đệ quy thường phù hợp hơn với Racket so với vòng lặp. Tôi sẽ tiếp cận vấn đề theo cách này ...

(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))