벡터에 대한 교차 함수가 있습니까?

매우 자주 목록은 consing 및 추가 gc 단계로 인해 벡터와 비교할 때 성능상의 단점이 있으며 일부 기능은 목록 및 벡터를 허용하는 일반 시퀀스에서 작동한다는 진술을 찾습니다.벡터에 대한 교차 함수가 있습니까?

그러나 intersection과 같은 일부 기능에는 두 개의 목록이 필요합니다. 벡터에 대한 대안을 제공하는 라이브러리가 있습니까?

나는 이런 식으로 시작했지만 좀 더 성숙한 해결책이 있어야한다고 생각합니다.

(defun vec-intersec (vec-1 vec-2 &aux (result (make-array 0 :adjustable t :fill-pointer 0))) 
    "A simple implementation of intersection for vectors instead of lists." 
    (loop :for v1 :across vec-1 
     :if (find v1 vec-2 :test #'equal) 
      :do (vector-push-extend v1 result)) 
    result)

출처

2017-12-08 Martin Buchmann

귀하의 작업은 2 차입니다. 성능을 고려하는 경우 해시 테이블을 사용하십시오. 그렇지 않으면 목록으로 변환합니다. – sds

"해시 테이블 사용"에 대해 자세히 설명해 주시겠습니까? 벡터 대신 또는'find'를 피하기위한 중간 구조로서? –

HT 멤버십 테스트에는 일정한 비용이 있으므로 세트를 나타내는 데 사용하면 의미가 있습니다. '찾기 '는 선형이기 때문에 항상 최적이 아닙니다. 사용 패턴에 따라 트리/정렬 된 목록 (로그 액세스) 또는 HT 중 하나를 사용하는 방법이 있습니다. 집합을 자주 수정합니까? – sds

항상 컬렉션의 크기와 함께하고 싶은 작업에 따라 다릅니다.

약 20 ~ 50 개 이하의 요소는 임의로 액세스 할 때도 목록을 완벽하게 사용할 수 있습니다 (내부 루프가 빡빡하지 않거나 많이 사용하지 않는 경우).

이미 벡터가있는 경우 순진한 선형 패턴 대신 이진 검색을 수행 할 수 있도록 벡터 중 하나를 정렬하는 것이 가장 편리 할 수 있습니다. 그만큼 충분하지 않고 컬렉션이 커지면 요소를 해시 테이블 (적절한 키가있는 :test)에 넣으면 더 빨리 (상각 된) 조회를 할 수 있습니다.

아주 오래 걸릴 것입니다. 이와 같이 간단한 방법으로 해결할 수없는 문제를 확인한 경우 고급 데이터 구조를 지원하는 FSet 또는 CL-Containers을 조사하는 것이 좋습니다.

출처

2017-12-08 22:10:05 Svante

또는 해시 테이블에 그 중 하나의 요소 (더 짧은 것, 아마도 차이가있을 경우)를 슬래핑 한 다음 빠른 존재 확인을 위해 해시 테이블을 사용하십시오. – Vatine

@Vatine : 예, 세 번째 단락의 두 번째 부분의 요지입니다. – Svante

벡터에 대한 교차 함수가 있습니까?

답변

관련 문제