스키마 문자열 추가? 문자열을 복제하는 재귀

Question

문자열 s와 숫자 n을 소비하는 프로그램을 디자인하고 문자열 s와 숫자 n을 사용하고 sn 시간과 각 s 인스턴스 사이의 공백을 연결 한 문자열을 반환합니다. 즉

-dup "a"3) => "aaa" 복제를 사용하지 않고 우리는 string-append를 사용할 수 있다고 생각합니다.

지금까지 나는이는 나에게 하나의 문자열 "A"를 가질 수 있습니다, 그러나

(define (string-dup s n) 
(cond 
    [(zero? n) ""] 
    [else 
    (cond 
    [(= n 1) s] 
    [(> n 1)(string-dup (string-append s " ") (sub1 n))])])) 

을 얻었다. 목록에있는 경우 할 수있는시기를 알고 있습니까

(cons s (string-cp s (sub1 n))) 

이 경우 어떻게 적용할까요? 감사.

Answer 1

string-dup에 대한 재귀 호출은 다른 방법이 아닌 string-append의 매개 변수 여야합니다. 다음은 수정 된 (및 리팩토링) 버전입니다 :

(define (string-dup s n) 
    (cond 
    [(< n 1) ""] 
    [(= n 1) s] 
    [else (string-append s " " (string-dup s (sub1 n)))])) 

Answer 2

성능 문제 (예를 들어 n가 큰), 문자의 목록과 작업하는 직접 상당히 속도를 증가시킬 수 있습니다 때. 함수 faster-string-dup 아래 :

• 행 1-5는 수락 된 대답에서와 같이 기본 조건부 분기를 수행합니다.

• 라인 6은 else 절에서 두 개의 로컬 값에 대한 클로저를 시작합니다.

• 라인 7-8는 단일 문자, #\space을 포함하는 목록에 문자 appended의리스트로 변환 string입니다 s1을 정의합니다.

• 라인 9-14는 꼬리 재귀 함수 next을 정의합니다. 정수 n과 문자 목록 acc의 두 매개 변수를 취해 문자 목록을 반환합니다.

• 라인 15는 else 절의 트램펄린입니다. 그것은 :

  1. 문자 목록에서 재귀 호출을 시작합니다.
  2. 재귀 호출에서 반환 된 문자 목록을 다시 문자열로 변환합니다.
  3. 원래 문자열을 추가합니다. 이로 인해 s1은 하나가 아닌 공백으로 끝납니다. 이것은 문제에 대한 우리의 직관적 인 이해와 일치합니다. 즉, 각 복제에 문자열과 공간을 추가합니다.

라켓 6을 사용

1: (define (faster-string-dup s n) 

2: (cond 

3:  [(< n 1) ""] 

4:  [(= n 1) s] 

5:  [else 

6:  (letrec 

7:   ((s1 (append (string->list s) 

8:      (list #\space))) 

9:   (next (lambda (n acc) 

10:     (if (> n 2) 

11: 

12:     (next (sub1 n) 

13:       (append s1 acc)) 

14:      acc)))) 

15:   (string-append (list->string (next n s1)) s))])) 

시간 비교 .명령 줄에서 1 :

• string-dup이 허용 대답

• duplications에게있다는

• dump 10,000 스크린 인쇄를 많이 방지 그냥 변경 가능한 변수입니다.

허용되는 답변보다 훨씬 빠르게 실행합니다.

-->(time (set! dump (string-dup "string" duplications))) 
cpu time: 1125 real time: 1129 gc time: 262 
-->(time (set! dump (faster-string-dup "string" duplications))) 
cpu time: 3 real time: 2 gc time: 0 

계획 및 기타 Lisps 때로는 Lisps 기계 코드에 대한 교체는 원래 있었고, 금속에 가까운 실행하도록 튜닝 할 수 있다는 사실을 모호하게 높은 수준의 프로그래밍을 용이하게함으로써 제공하는 전원.