(Lisp 또는 Scheme에서) 유용한 순환 목록은 무엇입니까?

Question

Scheme과 Lisp (내가 생각하기에)는 순환리스트를 지원하며, C/C++에서 순환리스트를 사용하여 요소의 삽입과 삭제를 '단순화'하고 있지만 무엇이 유용할까요?

Scheme은 구성 및 처리가 가능하지만 무엇을 위해서입니까?

원형 또는 꼬리 원형이 필요한 '킬러'데이터 구조가 있습니까?

Answer 1

'원형 목록'을 지원한다고 말하면 조금 큽니다. Lisp에서 원형 데이터 구조의 모든 종류를 만들 수 있습니다. 많은 프로그래밍 언어 에서처럼. Lisp에 관해서는 특별한 점이 많지 않습니다. 일반적인 "알고리즘 및 데이터 구조"책을 가지고 순환 데이터 구조를 구현하십시오 : 그래프, 링, ... 어떤 Lisps가 제공하는 것은 순환 데이터 구조를 인쇄하고 읽을 수 있다는 것입니다. 일반적인 Lisp 프로그래밍 도메인에서는 원형 데이터 구조가 일반적이기 때문에 파서, 관계형, 단어 네트워크, 계획 네트워크 등이 공통적으로 사용됩니다.

데이터 구조에 사이클이 포함되어있는 것이 일반적입니다. 실제 '순환 목록'은 자주 사용되는 것이 아닙니다. 예를 들어 작업을 실행하는 작업 스케줄러에 대해 생각해보고 다음 시간으로 전환합니다. 작업 목록은 원형이어서 '마지막'작업 후에 스케줄러가 '첫 번째'작업을 수행 할 수 있습니다. 사실 '마지막'과 '처음'은 없습니다. 이것은 단지 순환 목록의 작업이며 스케줄러는 끝내지 않고 실행합니다. 또한 창 시스템에 창 목록을 가질 수 있으며 다음 창으로 전환 할 수있는 몇 가지 핵심 명령이 있습니다. 창의 목록은 원형 일 수 있습니다.

목록은 값싼 다음 작업이 필요하고 데이터 구조의 크기를 미리 알 수없는 경우에 유용합니다. 언제나 다른 노드를 목록에 추가하거나 목록에서 노드를 제거 할 수 있습니다. 목록의 일반적인 구현은 다음 노드를 가져오고 항목을 추가/제거하는 것을 저렴하게 만듭니다. 배열에서 다음 요소를 가져 오는 것도 상대적으로 간단합니다 (마지막 인덱스가 첫 번째 인덱스로 이동하면 인덱스가 증가합니다). 그러나 요소를 추가/제거하는 것은 일반적으로 더 비싼 시프트 연산이 필요합니다.

또한 순환 데이터 구조를 작성하기가 쉽기 때문에 대화 형 프로그래밍 중에이를 수행 할 수도 있습니다. 그런 다음 내장 루틴을 사용하여 원형 데이터 구조를 인쇄하면 프린터가 처리 할 수 ​​있다면 좋은 생각이 될 것입니다. 그렇지 않으면 원형 목록이 영원히 인쇄 될 수 있기 때문입니다 ...

Answer 2

예를 들어 이중 링크 목록 데이터 구조는 Scheme/LISP 관점에서 "원형"입니다. 즉, cons-structure를 인쇄하려고하면 역 참조, 즉 "순환"이 발생합니다. 따라서 실제로는 "링"처럼 보이는 데이터 구조가 아니라 Scheme/LISP 관점에서 어떤 종류의 백 포인터가있는 모든 데이터 구조가 "순환"합니다.

"일반"LISP 목록은 단일 링크입니다. 즉, 목록 내부에서 항목을 제거하기위한 파괴적인 변형은 O (n) 연산입니다. 이중 연결된 목록의 경우 O (1)입니다. 이는 Scheme/LISP 컨텍스트에서 "순환"인 이중 연결 목록의 "킬러 기능"입니다.

Answer 3

Monopoly를 사용한 적이 있습니까?

카운터 및 모듈로 게임을하지 않고 게임의 컴퓨터 구현에서 모노 폴리 보드를 어떻게 표현 하시겠습니까? 순환 목록은 자연적입니다.

Answer 4

목록의 시작 부분에 요소를 추가하고 제거하는 것은 저렴합니다. 목록 끝에 요소를 추가하거나 제거하려면 전체 목록 을 트래버스해야합니다.

순환 목록을 사용하면 일종의 고정 길이 대기열을 가질 수 있습니다.

설치 길이 (5)의 원형 목록 :

> (import (srfi :1 lists)) 
> (define q (circular-list 1 2 3 4 5)) 

하는의이 목록에 번호를 추가하자

> (set-car! q 6) 

이제

는 만들자 그리스트의 마지막 요소 :

> (set! q (cdr q)) 

목록 표시 :

> (take q 5) 
(2 3 4 5 6) 

따라서 목록에서 요소가 입력되고 머리에서 제거되는 대기열로 볼 수 있습니다.

가의 목록에 7을 추가하자

가 어쨌든, 이것이 내가 원형 목록을 사용했던 방법 중 하나입니다

> (set-car! q 7) 
> (set!  q (cdr q)) 
> (take q 5) 
(3 4 5 6 7) 

등 ....

나는이 기술을 에서 사용하는데,이 기술은 Processing book의 예제에서 이식되었습니다. 원형리스트의

에드

Answer 5

한 사용은 맵의 srfi-1 버전을 사용하는 경우 값을 "반복"하는 것입니다. 예를 들어, lst의 각 요소에 val을 추가, 우리는 쓸 수 :

(map + (circular-list 10) (list 0 1 2 3 4 5)) 

반환 : 예를 들어

(map + (circular-list val) lst) 

물론

(10 11 12 13 14 15) 

, 당신은이 작업을 수행 할 수 +을 (lambda (x) (+ x val))으로 대체하지만 때로는 위의 관용구를 더 쉽게 사용할 수 있습니다. 이는 srfi-1 버전의지도에서만 작동하며 크기가 다른 목록을 허용 할 수 있습니다.