링크 된 목록은 열망한 기능 언어로 실제적인 성능 이점을 갖고 있습니까?

Question

게으른 함수형 언어에서 링크 된 목록은 생성기와 유사한 의미를 가지며 최적화 컴파일러에서는 실제로 저장소에 사용되지 않을 때 오버 헤드를 완전히 제거 할 수 있다는 것을 알고 있습니다.

그러나 열정적 인 기능 언어에서는 사용이 덜 어려워 보이지만 최적화는 더 어려워 보입니다. Scheme과 같은 언어가 기본 배열 표현으로 플랫 배열을 사용하는 좋은 성능의 이유가 있습니까?

단일 링크 된 목록을 사용하는 것이 명백한 시간 복잡성의 영향을 알고 있습니다. 필자는 열심히 단일 링크 된 목록을 기본 시퀀스 표현으로 사용하여 컴파일러 최적화를 고려한 실제 성능 결과에 대해 더 생각하고 있습니다.

Answer 1

TL; DR : 성능 이점 없음!

첫 번째 Lisp는 데이터 구조로 cons (연결된 목록 셀)을 가지며 모든 용도로 사용되었습니다. Common Lisp와 Scheme은 오늘날 벡터를 가지고 있지만 기능적 스타일을 위해서는 좋은 일치는 아닙니다. 연결된 목록에는 누적 기 앞에 0 개 이상의 요소를 추가하는 재귀 적 단계가 하나있을 수 있으며 결국에는 반복 사이에 공유 된 목록이 있습니다. 이 연산은 하나 이상의 재귀를 수행하여 여러 버전이 모두 꼬리를 공유하게 만듭니다. 나는 공유가 링크드리스트의 가장 중요한 측면이라고 말한다. 미니 맥스 알고리즘을 만들어 연결 목록에 상태를 저장하면 상태의 변경되지 않은 부분을 복사하지 않고 상태를 변경할 수 있습니다.

작성자의 C++ Bjarne Stroustrup은 데이터 구조가 복잡하고 링크 된 목록에서 크기가 두 배가되는 페널티가 데이터 구조의 요소 절반을 이동해야하는 경우에도 쉽게 수행 할 수 있다고 언급했습니다. 이들은 이중으로 연결된 목록과 돌연변이 삽입물을 기억하고 있지만 대부분의 시간은 포인터를 선형 적으로 따라 가면서 모든 CPU 캐시가 누락되어 올바른 지점을 찾고 따라서 정렬 된 모든 O (n) 검색에 대해 언급합니다. 벡터를 더 잘 나열 할 수 있습니다.

목록에없는 목록에 많은 삽입을하는 프로그램이있는 경우 cons으로 CL 및 Scheme에서 할 수있는 트리가 더 좋은 선택 일 수 있습니다. 사실 Chris Okasaki의 모든 기능적 데이터 구조는 cons으로 구현할 수 있습니다. 하스켈에서 "변경 가능한"구조체는 대부분 비슷하게 구현됩니다.

Scheme에서 성능 문제가 발생하고 프로파일 링 한 후에 연결된 목록 작업을 배열로 대체하려고 시도하면 찾을 수없는 경우가 있습니다. 결국 모든 알고리즘 선택에는 장단점이 있습니다. 어떤 언어에서도 어려운 계산이 어렵습니다.