데이터 구조는 lisp로

Question

나는 간단한 문제가있다 : 객체를리스트로 수집하고이리스트를 거꾸로 횡단한다. 꽤 쉽지만이 코드는 고부하 계산의 일부입니다. cons를 사용하는 것은 자연 스럽다. 왜냐하면 새로운 요소를 추가하거나 순차적 접근에 O (1)이 필요하기 때문이다. 하지만 양방향으로 쉽게 트래버스하기위한 효과적인 이중 연결 목록이 필요한 경우 어떻게해야합니까? (역방향) 사용 하시겠습니까? 그것은 O (n) 메모리와 시간이 걸리므로 실제로는 (O (n^2)) (이것은 정말로 나쁩니다). (마지막) 또는 (추가)를 사용 하시겠습니까? 같은 이야기 : O (n). 나는 표준 라이브러리 함수의 계산상의 복잡성에 대한 정보를 (소스 코드 제외) 어디에서 찾을 수 있을지 정말로 이해하지 못한다. 그것은 구현에 의존 하는가? 다양한 표준 데이터 구조를 구현하려면 무엇을해야합니까? conses를 효과적으로 사용하는 가이드가 있습니까?

Answer 1

커먼 리스프를 사용하는 경우 벡터를 대신 사용할 수 있습니다. 벡터는 채우기 포인터를 가질 수 있으며 조절할 수 있습니다. 따라서 vector-push를 사용하여 요소를 벡터에 추가 할 수 있습니다. 채우기 포인터가 커집니다. 벡터가 조절 가능하면 필요한 경우 더 크게됩니다. 벡터는 1 차원 배열이므로 원하는대로 색인을 사용하여 요소에 액세스 할 수 있습니다.

그런 벡터를 만들려면 MAKE-ARRAY 옵션을 참조하십시오.

VECTOR-PUSH 및 VECTOR-PUSH-EXTEND는 요소를 추가하는 함수입니다.

Answer 2

(reverse)을 한 번 실행 한 다음 역순으로 순차적으로 이동하면 합계는 O (2n) 시간 (설정은 O (n), 그 다음 다른 O (n)은 통과해야 함) 및 O (n) 메모리.

이중 연결 목록은 그리 복잡하지 않습니다. 아시다시피, 목록은 cons 셀로 구성되며, car가 객체를 가리키고 cdr은리스트의 다음 cons 셀을 가리 킵니다. 이중 링크 목록을 할

한 가지 방법은 대신 CDR 포인트 목록의 다음 단점 셀에 누구의 차 지점 이전의 단점 셀에 다른 죄수 셀에 CDR 점을 가지고있다 그 목록. 그런 다음 cddr을 사용하여 앞으로 이동하고 cdar을 사용하여 뒤로 이동하십시오.

나는 표준 라이브러리 함수는 어떤 보장 복잡성을 가지고 있음을 알 수 없습니다. 명세가 명세하지 않는 한, 그것은 구현 - 정의 될 것이다.