정렬 된 사전에서 두 키 사이의 지점을 찾는 방법

나는 키/값 쌍으로 측정 된 데이터 포인트를 포함하는 정렬 된 사전을 가지고 있습니다. 측정되지 않은 데이터 포인트의 값을 결정하기 위해 해당 값의 선형 보간법을 사용하여 두 개의 알려진 키 사이에서 값을 외삽하고자합니다. 필자는 측정되지 않은 데이터 포인트를 계산할 때 두 키/값 쌍을 사이에 두는 방법을 이해합니다. 내가 모르는 것은 두 키 사이에있는 키를 찾는 방법입니다. "for"루프 (나는 함수/LINQ 쿼리를 생각하고 있습니다)보다 더 우아한 방법으로 내 데이터 포인트 사이에있는 두 개의 키를 알아낼 수 있습니까?정렬 된 사전에서 두 키 사이의 지점을 찾는 방법

출처

2011-03-14 Joel B

linq와 유사한 솔루션을 찾고있는 경우 http://stackoverflow.com/questions/2768834/how-to-zip-one-ienumerable-with-itself – Douglas

뭔가 작동합니다 :

dic.Keys.Zip(dic.Keys.Skip(1), 
       (a, b) => new { a, b }) 
     .Where(x => x.a <= datapoint && x.b >= datapoint) 
     .FirstOrDefault();

이 주문한 있다는 사실을 이용하여 그들이 키를 통과하고 다음 각 모두 두 개의 키를 비교 다른 순서로 - LINQ는 게이가 처음으로 일치하는 것을 발견하면 트래버스가 중지됩니다.

출처

2011-03-14 16:16:26 BrokenGlass

당신이 다음에 대해 요구하고 가능한이 같은

myDictionary.Keys.Where(w => w > start && w < end)

출처

2011-03-14 16:09:01 Vitaliy

모든 키를 테스트 할 경우 가능한 효율적인 방법입니다. –

일반 루프는 여기에 확인을해야 :

IEnumerable<double> keys = ...; //ordered sequence of keys 
double interpolatedKey = ...; 

// I'm considering here that keys collection doesn't contain interpolatedKey 

double? lowerFoundKey = null; 
double? upperFoundKey = null; 

foreach (double key in keys) 
{ 
    if (key > interpolatedKey) 
    { 
     upperFoundKey = key; 
     break; 
    } 
    else 
     lowerFoundKey = key; 
}

당신은 짧은하지만 덜 효과적 코드와 LINQ와 C#에서 그것을 할 수 있습니다 :

위해

double lowerFoundKey = key.LastOrDefault(k => k < interpolatedKey); 
double upperFoundKey = key.FirstOrDefault(k => k > interpolatedKey);

그것을 효율적으로 LINQ와이 있어야한다 매개 변수 2 인 windowed in F#이라는 메서드. keys 컬렉션에 인접한 쌍 중 IEnumerable을 반환합니다. 이 함수는 LINQ에 없지만 일반 foreach 루프는 정상입니다.

출처

2011-03-14 16:16:46 Snowbear

'Seq.pairwise'는 F # 솔루션에 충분할 것이고,'Seq.windowed'는 더 일반적인 버전 (모든 윈도우 크기)입니다. – BrokenGlass

@BrokenGlass, 감사합니다. 이미 다른 답변에서 얻었습니다. – Snowbear

SortedDictionary에는 반복되는 요소보다 빠르게 필요한 요소 주위의 요소를 찾을 수있는 기능이 없다고 생각합니다. (+1 ~ BrokenGlass 솔루션)

더 빠르게 항목을 찾을 수 있으려면 다른 구조로 전환해야합니다. 나는. SortedList는 비슷한 기능을 제공하지만 Key 컬렉션을 색인화 할 수 있으므로 이진 serach를 사용하여 범위를 찾을 수 있습니다.

출처

2011-03-14 16:30:10

표준 C# 응답은 모두 O (N) 복잡도입니다. 때때로 큰 정렬 된 컬렉션에 작은 하위 집합 만 있으면됩니다. (따라서 모든 키를 반복하지는 않습니다.) 표준 C# 모음은 여기에서 도움이되지 않습니다. 그리고 해결 방법은 다음과 같습니다. http://www.itu.dk/research/c5/ C5 모음 라이브러리의 IntervalHeap을 사용하십시오. 이 클래스는 GetRange() 메서드를 지원하며 O (log N) 복잡도로 시작 키를 검색하고 O (N) 복잡도로 범위를 반복합니다. 성능이 중요한 경우 큰 데이터 세트에 유용합니다. 예 : 게임에서의 공간 분할

출처

2012-10-12 20:50:36 user1190841

정렬 된 사전에서 두 키 사이의 지점을 찾는 방법

답변

관련 문제