세트 또는 멀티 세트에 <Object A, Relation R, Object B> 유형의 서로 다른 릴레이션을 (약 100-1000) 저장하고 싶습니다. A 및 (A,R)을 검색 할 수 있지만 (A,R,B)은 검색 할 수 없으며 동일한 A 및 R과 약간의 (< 5) 개의 관계가 있으므로 선형 검색을 사용하는 것이 좋습니다.세트 대 멀티 세트
그것이 집합의 관계를 저장하는 것이 좋습니다 (A, R 및 B으로 정렬) 또는 A 및 R에 의해 주문한 MULTISET에 저장할?
편집 : 해시 테이블을 살펴 보았지만 반복이 설정된 반복만큼 빠르지 않으며 패턴 일치도 많은 반복이 필요합니다. 은 (는 반복의 시작을 찾기 위해 한 번 검색 한 후 같은 객체 A를 모든 관계가 완료 될 때까지 반복해야합니다.) 당신이 가지고 수집 한 의견에서
감사합니다, 라그나
을 A 또는 쌍 (A, R)에 대한 정확한 일치를 조회하는 것.
이것이 맞을 때 가장 좋은 방법은 두 개의 해시 테이블을 사용하는 것입니다. 하나는 A를 키로 사용하고 다른 하나는 (A, R)을 키로 사용하는 것입니다. 릴레이션 자체는 정렬되지 않은 벡터에 저장 될 수 있으며 인덱스는 두 해시 테이블에 삽입됩니다. 이것이 조회 작업을위한 O (1) 복잡성을 얻는 유일한 방법입니다.
두 개의 독립적 인 색인 구조가있는 성능은 매우 중요합니다. A 만 키로 사용하면 (A, R) 키를 찾을 때 적합한 R을 검색해야하는 개체 목록을 얻게됩니다. 쌍. 반대의 경우, (A, R) 키만 있으면 O (1) 시간 동안 특정 A 만 볼 수 없습니다.
이전에는 해시 테이블을 사용한 적이 없지만 O (1) 조회가 프로그램 속도를 높이기 때문에 무언가를 배우는 데 많은 도움이 될 것입니다. – Ragnar
(A, R) 키만 사용하고 A로 정렬 한 다음 (열거 형) R로 오름차순으로 정렬하고 (A, 0) 및 (A, 255)를 검색 할 수 있습니까? – Ragnar
아니요, 존재하지 않는 (A, R) 쌍에 대한 위치를 검색 할 수 있어야하므로 O (1) 시간에는 가능하지 않습니다. 그리고 해시 테이블로는이 작업을 수행 할 수 없습니다. 이진 트리 또는 정렬 된 배열의 이진 검색과 같은 다른 인덱스 구조에서도 가능하지만 O (log N) 시간 복잡도를 의미합니다. – cmaster
벡터에 저장하는 것은 어떻습니까? 1000 가지 요소의 경우, 가장 빠른 구현이라는 사실을 알게되었습니다. –
프로그램은 집합/벡터를 매우 자주 검색 할 것입니다. 다른 관계에서 많은 패턴 일치를해야하기 때문입니다 (프로그램은 기하학 문제 해결 자이며 특정 정리를 적용 할 수있는 상황을 찾아야합니다) – Ragnar
@Ragnar : 질문은 실제로 검색이 얼마나 자주 수행되어야하는지가 아니라 맵의 복잡한 구조가 단순한 벡터 구조에 대해 보상하는 경우입니다. 맵을 사용하기 전에 지불해야하는 요소의 수는 사람들이 기대하는 것보다 훨씬 높습니다. –