길이 함수를 복사하는 효과적인 방법

Question

나는 단지 & cdr을 사용하여 라켓의 길이 함수를 복제하여 두리스트의 길이를 비교하고 그 중 더 짧은 것을 반환합니다.

간단히 말하자면 길이 함수이다

(define length 
(lambda (list) 
    (if (null? list) 
     0 
     (+ 1 (length (cdr list)))))) 

및 '(a B의 C)을 반환 두리스트

(define short 
    (lambda (list1 list2) 
    (if (<= (length list1) (length list2)) 
     list1 
     list2))) 

> (short '(a b c) '(1 2 3 4 5 6 7)) 

의 비교에 사용되는 경우.

그러나이 방법은 한 목록이 다른 목록보다 훨씬 길 때 특히 효과적이지 않습니다. 두 목록을 반복하여 짧게 반환하기 전에이 목록을 반복합니다.

나는 아래에보다 효과적인 방법이 있습니다. 그러나 두 목록의 끝을 확인하지 않고 더 짧은 길이를 얻는 데 더 효율적인/대체 방법이 있는지 궁금합니다. 아마도 car/cdr과 함께 목록을 재귀 적으로 거쳐 더 짧은 목록이 먼저 끝날 때까지.

(define shorter? 
    (lambda (list1 list2) 
    (and (not (null? list2)) 
     (or (null? list1) 
      (shorter? (cdr list1) (cdr list2)))))) 

(define shorter 
    (lambda (list1 list2) 
    (if (shorter? list2 list1) 
     list2 
     list1))) 

Answer 1

귀하의 shorter? 절차는 가능한 한 이미 효율적이다 and 특별 서식의 경우). 따라서 목록 중 하나가 null에 도달하면 재귀가 중지됩니다.

(define shorter? 
    (lambda (list1 list2) 
    (cond ((null? list2) #f) 
      ((null? list1) #t) 
      (else (shorter? (cdr list1) (cdr list2)))))) 

당신이 사용하는 하나의 과정 안에 두 절차를 넣을 수 있습니다 더 컴팩트 한 솔루션을 원하는 경우 명명 된 let (다른 답변에서 설명 등) 또는 : 귀하의 shorter? 구현은이 같은에 해당하고 효율적입니다 내부 헬퍼 프로 시저, 둘 다 동일합니다. 나중에 접근법을 보여 드리겠습니다 :

(define (shorter lst1 lst2) 
    (define (shorter-list list1 list2) 
    (cond ((null? list2) lst2) 
      ((null? list1) lst1) 
      (else (shorter-list (cdr list1) (cdr list2))))) 
    (shorter-list lst1 lst2)) 

Answer 2

I는 다음과 같이 시작하는 것이 좋습니다 :

(define (shorter list-1 list-2) (shorter-loop list-1 list-2 list-1 list-2)) 

다음 도우미 함수 짧은 루프가 동시에 목록-1 및 목록-2를 재귀

(define (shorter-loop list-1 list-2 result-1 result-2) 
    ;; 
) 

. list-1이 널 (null)이되면 result-1을 리턴하고, list-2가 널을 리턴하면 결과 - 2를 리턴합니다. (모두 and 및 or 특별한 형태의 단락 회로 및 중지 평가 식의 값이합니다 ( or 특별한 양식) true 때 또는 false -

Answer 3

'명명 된하자'방법은 쉽게 쉽게 계산할 수있는 코드를 제공합니다. 설명은 설명을 제공합니다 :

(define (shorter l1 l2) 
    (let loop ((al l2)   ; start with both full lists 
      (bl l2)) 
    (cond 
     [(empty? al) l1]  ; if al finishes, return l1 and end; 
     [(empty? bl) l2]  ; if bl finishes, return l2 and end; 
     [else 
     (loop (cdr al) (cdr bl))] ; else loop again with cdr of lists; 
    ))) 

이 기능은 해안가 목록이 완료되면 끝나며 더 이상 긴 목록이 끝날 때까지 계속됩니다.