나는 그것을 검색 할 수있는 가장 빠른 방법을 찾기 위해 수백만 개가 넘는 객체 목록을 가지고 있습니다.

Question

나는 그 안에있는 100 만 개가 넘는 객체를 저장하는리스트를 가지고 있습니다. 목록을 살펴보고 아래 쿼리를 통해 찾은 개체를 최대한 효율적으로 업데이트해야합니다.

사전 또는 HashSet을 사용하려고 생각했지만 비교적 C#에 익숙하지 않아 이러한 두 가지 방법을 구현하는 방법을 알 수 없었습니다. 현재 코드는 IList를 통해 검색하는 LINQ 문일뿐입니다.

public IList<LandObject> landObjects = new List<LandObject>();  

var lObjsToUpdate = from obj in landObjects 
         where 
      obj.position.x >= land.x - size.x && 
      obj.position.x <= land.x + size.x && 
      obj.position.y >= land.y - size.y && 
      obj.position.y <= land.y + size.y 
        select obj; 

foreach(var item in lObjsToUpdate) 
{ 
    //do what I need to do with records I've found 
} 

아무도 내가 어떻게 효율적으로 접근 할 수 있는지 제안 할 수 있습니까?

Answer 1

실제 답변에는 성능 테스트 및 비교가 포함되어야하며 런타임 환경 (메모리 대 CPU 등)에 따라 달라집니다.

내가 시도 할 첫번째 일은

, land 및 size가 일정하기 때문에, 당신은 (목록에 추가 또는 모든 객체하거나 다른 모든 개체 집합) 기준에 맞는 객체의 간단한 HashSet<LandObject>을 유지할 수 있습니다. 새 오브젝트가 추가 될 때마다 기준에 맞는 지 확인하고, 기준에 맞는다면 그 오브젝트 세트에 추가하십시오. 객체 참조로 작업 할 때 충돌을 피할 때 HashSet이 얼마나 좋은지 모르지만 측정하려고 시도 할 수 있습니다.

자세히 알아 보려면 HashSet<int>의 메모리 제한을 설명하는 related question이 도움이 될 수 있습니다. .NET < 4.5를 사용하면 HashSet은 몇 백만 항목까지 확인해야합니다. 내가 이해하는 바에 따르면, 몇 가지 설정으로 .NET 4.5는 2GB의 최대 객체 크기의 한계를 없애고 64 비트 머신을 가지고 있다고 가정하면 미칠 수 있습니다.

Answer 2

많은 반복을하는 데 도움이되는 것은 계산을 한 번 수행하고 쿼리 내에서 다른 변수를 사용하는 것입니다. 또한 그것은 일부는 각 끝에 1 범위를 증가 및 동등 검사 제거하는 데 도움이 될 것입니다

당신이를 찾기 위해 모든 하나 하나를 테스트 할 필요가 없도록 이상적으로

public IList<LandObject> landObjects = new List<LandObject>();  
float xmax = land.x + size.x + 1; 
float xmin = land.x - size.x - 1; 
float ymax = land.y + size.y + 1; 
float ymin = land.y - size.y - 1; 

var lObjsToUpdate = from obj in landObjects 
         where 
      obj.position.x > xmin && 
      obj.position.x < xmax && 
      obj.position.y > ymin && 
      obj.position.y < ymax 
        select obj; 

Answer 3

당신은 요소를 분할하는 방법이 필요합니다 맞는 것들과 버려야 할 것들. 파티션하는 방법은 항목이 얼마나 빽빽하게 있는지에 따라 달라집니다. 예를 들어 X 좌표의 정수 부분을 분할하는 것만 큼 간단하거나 좌표의 적절한 크기 조정 된 값으로 간단하게 지정할 수 있습니다. 당신이 첫 번째 패스로 상당히 빨리 좌표 X에 필터링 할 수 있습니다 X 좌표를 취하고 그것을 위해 파티션 값을 반환하는 방법 (의 지금은 Partition를 호출하자)을 감안할 때

노드의 수를 줄이기 위해 당신 확인해야합니다. 파티션 기능을 사용하여 올바른 배포를 얻으려면 약간의 노력이 필요할 수 있습니다.

예를 들어 부동 소수점 좌표가 -100 < X <= 100이고 1,000,000 개가이 범위에 균등하게 분산되어 있다고 가정 해 보겠습니다. 이는 정수 값이 X 인 경우 목록을 (평균적으로) 5000 개의 항목으로 구성된 200 개의 파티션으로 나눕니다. 즉, 검색 범위의 X 차원에있는 모든 정수 단계에 대해 테스트 할 수있는 항목은 ~ 5,000 개뿐입니다.

public interface IPosition2F 
{ 
    float X { get; } 
    float Y { get; } 
} 

public class CoordMap<T> where T : IPosition2F 
{ 
    SortedDictionary<int, List<T>> map = new SortedDictionary<int,List<T>>(); 
    readonly Func<float, int> xPartition = (x) => (int)Math.Floor(x); 

    public void Add(T entry) 
    { 
     int xpart = xPartition(entry.X); 
     List<T> col; 
     if (!map.TryGetValue(xpart, out col)) 
     { 
      col = new List<T>(); 
      map[xpart] = col; 
     } 
     col.Add(entry); 
    } 

    public T[] ExtractRange(float left, float top, float right, float bottom) 
    { 
     var rngLeft = xPartition(left) - 1; 
     var rngRight = xPartition(right) + 1; 

     var cols = 
      from keyval in map 
      where keyval.Key >= rngLeft && keyval.Key <= rngRight 
      select keyval.Value; 

     var cells = 
      from cell in cols.SelectMany(c => c) 
      where cell.X >= left && cell.X <= right && 
       cell.Y >= top && cell.Y <= bottom 
      select cell; 

     return cells.ToArray(); 
    } 

    public CoordMap() 
    { } 

    // Create instance with custom partition function 
    public CoordMap(Func<float, int> partfunc) 
    { 
     xPartition = partfunc; 
    } 
} 

최종 검색 공간을 줄일 좌표 X에 분할됩니다

는 여기에 몇 가지 코드입니다.만약 당신이 한걸음 더 나아가고 싶다면 Y 좌표에서 파티션을 나눌 수도 있습니다. 독자의 연습 문제로 남겨 둘 것입니다 :

당신의 parition 함수가 매우 정교하고 파티션의 다수가 추가 유용 할 수 있습니다 ColumnRange 기능과 유사에 : 나는 모든 편의를 위해 SortedDictionary을 사용

public T[] ExtractRange(float left, float top, float right, float bottom) 
    { 
     var rngLeft = xPartition(left) - 1; 
     var rngRight = xPartition(right) + 1; 

     var cells = 
      from cell in ColumnRange(rngLeft, rngRight).SelectMany(c => c) 
      where cell.X >= left && cell.X <= right && 
       cell.Y >= top && cell.Y <= bottom 
      select cell; 

     return cells.ToArray(); 
    } 

:

이

public IEnumerable<List<T>> ColumnRange(int left, int right) 
    { 
     using (var mapenum = map.GetEnumerator()) 
     { 
      bool finished = mapenum.MoveNext(); 
      while (!finished && mapenum.Current.Key < left) 
       finished = mapenum.MoveNext(); 

      while (!finished && mapenum.Current.Key <= right) 
      { 
       yield return mapenum.Current.Value; 
       finished = mapenum.MoveNext(); 
      } 

     } 
    } 

ExtractRange 방법은 다음과 같이 그것을 사용할 수 있습니다 ce, 그리고 가능한 한 빨리 ExtractRange 메소드를 수행 할 수 있기 때문입니다. 작업에 더 적합한 다른 컨테이너 유형이 있습니다.