배열의 인덱스를 가지고있는 것보다 더 빨리 찾을 수 있습니까?

Question

목록에 정점을 유지하고 있는데, 정점을 아직 포함하지 않은 경우에만 정점을 목록에 추가하려고합니다. 그것이 포함되어 있지 않으면 목록에 추가 한 다음 tris라는 목록에 색인을 추가합니다. 그러나 목록에 이미 정점이 포함되어 있으면 해당 위치의 색인을 찾아야하며 그 색인을 트리스 목록에 추가하면됩니다. 여기에 내가 알아 낸 가장 빠른 방법이 있습니다. 더 빠른 방법이 있습니까?

Hashtable vertIndexes; 
List<Vector3> verts; 
List<int> tris; 

foreach (var vert in vertsOutput) 
{ 
    Vector3 p = point + vert; 
    if(!vertIndexes.Contains(p)) 
    { 
     vertIndexes.Add(p, verts.Count); 
     tris.Add(verts.Count); 
     verts.Add(p); 
    } 
    else 
    { 
     tris.Add((int)vertIndexes[p]); 
    } 
} 

Answer 1

현재 항목 당 2 개의 해시 테이블 작업을 수행하고 있습니다. 다음 중 하나를 저장할 수 있습니다 :

Dictionary<Vector3, int> vertIndexes; 
... 

int index; 
if(vertIndexes.TryGetValue(p, out index)) 
//present at given index 
else 
//not present 

TryGetValue 동시에 존재 여부를 테스트하고 저장된 값을 반환합니다.

사용자 지정 해시 테이블을 사용하면 더 빨라질 수 있습니다. Dictionary에는 일반적으로 필요한 오버 헤드가 있으며 필요하지 않습니다. 예를 들어, 모듈러스 연산자는 놀랍게도 비싸고 좋은 해시 코드에서는 불필요합니다. 그러나이 답변의 범위를 벗어납니다.

Answer 2

많은 종류의 컨테이너가 있으며 성능, 리소스 및 활용 특성이 모두 다릅니다.

목록이 검색을위한 가장 빠른 컨테이너가 아닙니다. 사전이나 Hashset이 더 좋을 수도 있습니다. 하지만 사용 방법에 따라 다릅니다.

키로 정점을 검색해야하는 경우 사전을 사용하십시오. 꼭짓점 자체가 키이면 해시 테이블을 사용하십시오. 그런 다음 인덱스에 대해 별도의 해시 테이블이 필요하지 않습니다.

실제로 카운트해야합니까? 그렇지 않다면 정점에 해시 테이블을 사용하십시오. 개수가 필요하면 정점에 키가있는 사전을 사용하십시오. Dictionary<Vertex3,int>