LISP (또는 autolisp) 사용 연관성 목록은 성능이 얼마나 좋습니까?

Question

긴 연관 구조를 사용하여 무거운 기하학적 처리를 수행하는 Autolisp 프로젝트를 수행하고 있습니다. 따라서 연관 목록 강렬한 사용 타이밍 결과에 대해 궁금합니다. 구현은 얼마나 단순/복잡한가요? 일부 데이터 구조 또는 정상적인 점 목록 목록을 사용합니까? B- 트리의 연장이 있습니까?

Answer 1

공동 LISP 및 EMACS LISP 협회 목록은 링크 된 목록이므로 선형 검색 시간이 있습니다. autolisp가 동일하다고 가정하면 (그렇지 않은 경우, "연관 목록"이라는 용어의 사용이 오도의 소지가 있다고 가정하면) 모든 작업이 목록 길이에서 선형이라고 가정 할 수 있습니다. 예를 들어, 100 개의 요소가있는 Alist는 평균적으로 50 개의 액세스가 필요합니다.

Answer 2

ALIST와 ID 기반 해시 타이블 사이의 최근 X86 하드웨어에서 SBCL의 전환점은 액세스의 분포를 가정 할 때 약 30-40 요소입니다.

Answer 3

물론, 대부분의 체계 구현 (또는 사양에있을 수 있습니까?)은 대부분 동일한 API를 사용하는 해시블이 있습니다. 그러나 투명하지 않습니다. Alist를 요청하면 쌍 목록을 얻습니다. 해시 가능을 원한다면 요청하십시오.

즉, 선형 알고리즘이 느리지 않다는 것을 기억하는 것이 중요합니다. 그들은 '비정질'입니다. 적은 수의 요소의 경우 더 복잡한 '영리한'알고리즘보다 성능이 우수합니다. 'n'이 얼마나 큰지, 알고리즘에 크게 달라지고, 큰 캐시를 사용하는 빠른 프로세서이지만 느린 RAM은 계속 밀어 붙입니다. 또한, 일부 LISP에서 사용 가능한 것과 같은 무거운 최적화 컴파일러가 생성됩니다. 매우 단단한 선형 코드.

Answer 4

나는 약 10 년 동안 Autolisp와 함께 일하지 않았지만 협회 목록 조작과 관련된 실제 성능 문제를 찾지 못했습니다. 그리고 나는 상당한 양의 협회 목록 조작을 수행 할 코드를 작성했습니다.

VBA 또는 Objectarx에서 작업하면 성능 이점이있을 수 있지만 비교 테스트를 실행하여 실제로 더 나은지 확인해야 할 것입니다.

Answer 5

내가 아는 B-Tree의 확장은 없지만 Visual LISP를 사용하면 ActiveX 객체를 사용하여 대부분의 유형의 데이터베이스에 액세스 할 수 있습니다.