계획에 푸시 앤 팝을 작성하려면 어떻게해야합니까?

StackOverflow https://stackoverflow.com/questions/1041603

  •  22-07-2019
  •  | 
  •  

문제

지금은 가지고 있습니다

(define (push x a-list)
  (set! a-list (cons a-list x)))

(define (pop a-list)
  (let ((result (first a-list)))
    (set! a-list  (rest a-list))
    result))

그러나 나는이 결과를 얻는다 :

Welcome to DrScheme, version 4.2 [3m].
Language: Module; memory limit: 256 megabytes.
> (define my-list (list 1 2 3))
> (push 4 my-list)
> my-list
(1 2 3)
> (pop my-list)
1
> my-list
(1 2 3)

내가 뭘 잘못하고 있죠? 요소가 첫 번째로부터 삭제되도록 요소가 끝나고 팝되도록 푸시를 쓰는 더 좋은 방법이 있습니까?

도움이 되었습니까?

해결책

이것은 코드에서 돌연변이를 사용하는 것에 대한 요점입니다.이를 위해 매크로로 점프 할 필요가 없습니다. 나는 지금 스택 작업을 가정 할 것입니다 : 당신이 전달하고 돌연변이 할 수있는 간단한 값을 얻으려면, 당신이 필요한 것은 목록 주위의 래퍼 만 있으면되며 나머지 코드는 동일하게 유지됩니다 (음, 사소한 변화가있어 스택 작업을 제대로 수행합니다). PLT 체계에서 이것은 정확히 상자의 것입니다.

(define (push x a-list)
  (set-box! a-list (cons x (unbox a-list))))

(define (pop a-list)
  (let ((result (first (unbox a-list))))
    (set-box! a-list (rest (unbox a-list)))
    result))

또한 사용할 수 있습니다 begin0 대신 let:

(define (pop a-list)
  (begin0 (first (unbox a-list))
    (set-box! a-list (rest (unbox a-list)))))

그것을 큐로 바꾸는 것은 위의 방법 중 하나를 사용할 수 있지만 Jonas가 쓴 마지막 버전을 제외하고 솔루션은 매우 비효율적입니다. 예를 들어, SEV가 제안한 작업을 수행하면 다음과 같습니다.

(set-box! queue (append (unbox queue) (list x)))

그런 다음 이것은 복사합니다 전부의 큐 - 이는 큐에 항목을 추가하는 루프가 각 추가에 따라 모든 것을 복사하여 GC에 대한 많은 쓰레기를 생성 함을 의미합니다 (루프의 문자열 끝에 문자를 추가하는 것에 대해 생각하십시오). "Unknown (Google)"솔루션은 목록을 수정하고 마지막에 포인터를 추가하므로 수집 할 쓰레기를 생성하지 않지만 여전히 비효율적입니다.

Jonas가 쓴 솔루션은이 작업을 수행하는 일반적인 방법입니다. 목록의 끝에 대한 포인터를 유지합니다. 그러나 PLT 구성표로 수행하려면 Mutable Pairs를 사용해야합니다. mcons, mcar, mcdr, set-mcar!, set-mcdr!. PLT의 일반적인 쌍은 버전 4.0이 나왔기 때문에 불변입니다.

다른 팁

  1. 당신은 그냥 어휘 변수에 바인딩되는 것을 설정하고 있습니다. a-list. 이 변수는 함수가 종료 된 후에 더 이상 존재하지 않습니다.

  2. cons 새로운 단점 셀을 만듭니다. 단점 셀은 두 부분으로 구성되며 car 그리고 cdr. 목록은 각 차량에 약간의 값이있는 일련의 단점 셀이며, 각 CDR은 각각의 다음 셀을 가리키며, 마지막 CDR은 NIL을 가리키고 있습니다. 당신이 쓸 때 (cons a-list x), 이것은 a-list 차에서 x CDR에서는 원하는 것이 아닐 것입니다.

  3. push 그리고 pop 일반적으로 대칭 작업으로 이해됩니다. 목록에 무언가를 밀면 (스택으로 기능), 나중에이 목록을 팝하면 다시 돌아올 것으로 예상됩니다. 목록은 항상 처음에 참조되므로 (cons x a-list).

  4. IANAS (나는 체계가 아니다)하지만, 당신이 원하는 것을 얻는 가장 쉬운 방법은 push 매크로 (사용 define-syntax) 확장됩니다 (set! <lst> (cons <obj> <lst>)). 그렇지 않으면 통과해야합니다 참조 당신의 목록에 push 기능. 비슷한 보류 pop. 참조를 전달하면 다른 목록으로 감을 수 있습니다.

Svante는 정확합니다. 매크로를 사용하는 것이 관용적 인 방법입니다.

다음은 매크로가없는 방법이 있지만 아래쪽에는 일반 목록을 대기열로 사용할 수 없습니다. R5RS와의 작업은 최소한 올바른 라이브러리를 가져온 후 R6R에서 작동해야합니다.

(define (push x queue)
  (let loop ((l (car queue)))
    (if (null? (cdr l))
      (set-cdr! l (list x))
      (loop (cdr l)))))

 (define (pop queue)
   (let ((tmp (car (car queue))))
     (set-car! queue (cdr (car queue)))
     tmp))

(define make-queue (lambda args (list args)))

(define q (make-queue 1 2 3))

(push 4 q)
q
; ((1 2 3 4))
(pop a)
; ((2 3 4))
q

나는 당신이 a를 구현하려고한다고 생각합니다 대기줄. 이것은 여러 가지 방법으로 수행 할 수 있지만 인서트와 제거 작업을 일정한 시간에 수행하려면 O (1)을 모두 참조해야합니다. 앞면과 등 대기열의.

이 참조를 a에서 유지할 수 있습니다 단점 셀 또는 내 예에서와 같이 폐쇄로 싸여 있습니다.

용어 push 그리고 pop 일반적으로 스택을 처리 할 때 사용되므로이를 변경했습니다. enqueue 그리고 dequeue 아래 코드에서.

(define (make-queue)
  (let ((front '())
        (back '()))
    (lambda (msg . obj)
      (cond ((eq? msg 'empty?) (null? front))
            ((eq? msg 'enqueue!) 
             (if (null? front)
                 (begin 
                   (set! front obj)
                   (set! back obj))
                 (begin
                   (set-cdr! back obj)
                   (set! back obj))))
            ((eq? msg 'dequeue!) 
             (begin
               (let ((val (car front)))
                 (set! front (cdr front))
                 val)))
            ((eq? msg 'queue->list) front)))))

make-queue 변수에서 대기열의 상태를 감싸는 절차를 반환합니다. front 그리고 back. 이 절차는 큐 데이터 구조의 절차를 수행하는 다른 메시지를 수용합니다.

이 절차는 다음과 같이 사용할 수 있습니다. 

> (define q (make-queue))
> (q 'empty?)
#t
> (q 'enqueue! 4)
> (q 'empty?)
#f
> (q 'enqueue! 9)
> (q 'queue->list)
(4 9)
> (q 'dequeue!)
4
> (q 'queue->list)
(9)

이것은 체계에서 거의 객체 지향 프로그래밍입니다! 당신은 생각할 수 있습니다 front 그리고 back 대기열 클래스의 개인 구성원 및 메시지로서 메소드로.

전화 규칙은 약간 뒤로되지만 더 좋은 API에서 대기열을 감싸는 것은 쉽습니다. 

(define (enqueue! queue x)
   (queue 'enqueue! x))

(define (dequeue! queue)
  (queue 'dequeue!))

(define (empty-queue? queue)
  (queue 'empty?))

(define (queue->list queue)
  (queue 'queue->list))

편집하다:

처럼 엘리 지적, 쌍이 있습니다 불변 PLT 체계에서 기본적으로 set-car! 그리고 set-cdr!. 코드가 PLT 체계에서 작동하려면 사용해야합니다. 돌연변이 가능한 쌍 대신에. 표준 체계 (R4RS, R5RS 또는 R6RS)에서 코드는 수정되지 않아야합니다.

당신이하는 일은 "큐"를 로컬로만 수정하는 것이므로 결과는 정의 범위 외부에서 사용할 수 없습니다. 이는 체계에서 모든 것이 참조가 아니라 가치별로 전달되기 때문에 발생합니다. 계획 구조는 불변입니다.

(define queue '()) ;; globally set

(define (push item)
  (set! queue (append queue (list item))))

(define (pop)
  (if (null? queue)
      '()
      (let ((pop (car queue)))
        (set! queue (cdr queue))
        pop)))

;; some testing
(push 1)
queue
(push 2)
queue
(push 3)
queue
(pop)
queue
(pop)
queue
(pop)

문제는 체계에서 데이터와 조작을 따르는 문제에 의존합니다. 부작용 규칙이 없습니다

따라서 진정한 대기열의 경우, 우리는 우리가 가지고 있지 않은 돌연변이를 원할 것입니다. 그래서 우리는 그것을 시도하고 우회해야합니다.

모든 것이 있기 때문에 가치로 통과했습니다 제도에서, 참조와는 달리, 상황은 현지 상태로 유지되며 변경되지 않은 상태로 남아 있습니다. 부작용이 없습니다. 그러므로 나는 글로벌 큐를 만들기로 결정했습니다. 글로벌 큐를 만들기로 선택했습니다.이 대기열은 전 세계적으로 구조에 대한 변경 사항을 적용하여 아무것도 전달하지 않고이를 우회하는 방법입니다.

어쨌든, 1 큐가 필요한 경우,이 방법은 메모리 집약적이지만 구조를 수정할 때마다 새 객체를 만들므로 메모리 집약적이지만 잘 작동합니다.

더 나은 결과를 얻으려면 매크로를 사용하여 대기열 생성을 자동화 할 수 있습니다.

목록에서 작동하는 푸시 및 팝 매크로는 Emacs LISP, Gauche Scheme, Common LISP, Chicken Scheme (Miscmacros Egg), 아크 등 많은 Lispy 언어로 발견됩니다.

Welcome to Racket v6.1.1.
> (define-syntax pop!
  (syntax-rules ()
    [(pop! xs)
     (begin0 (car xs) (set! xs (cdr xs)))]))
> (define-syntax push!
  (syntax-rules ()
    [(push! item xs)
     (set! xs (cons item xs))]))
> (define xs '(3 4 5 6))
> (define ys xs)
> (pop! xs)
3
> (pop! xs)
4
> (push! 9000 xs)
> xs
'(9000 5 6)
> ys  ;; Note that this is unchanged.
'(3 4 5 6)

이 목록은 라켓에서 불변이지만 작동합니다. 포인터를 조정하여 항목은 단순히 목록에서 "팝 핑"됩니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top