배열에서 가장 낮은 n을 얻는 가장 빠른 방법

Question

배열을 두 배로 배열 한 다음 n을 가장 낮게 (0이 아닌) 찾습니다 (배열 을이라고 부름). 루프를 여러 번 반복해야하므로 실행 속도가 중요합니다. ,

const int numLowestSamples = 10; 

double[] samples; 

double[] lowestSamples = new double[numLowestSamples]; 

for (int count = 0; count < iterations; count++) // iterations typically around 2600000 
{ 
    samples = whatever; 
    Array.Sort(samples); 
    lowestSamples = samples.SkipWhile(x => x == 0).Take(numLowestSamples).ToArray(); 
} 

따라서 I 다른 시도 : I 먼저 배열을 정렬 한 후 처음 10 개 개의 값 (0이되지 않는)에 Array.sort 빠른 것으로 알려져 있지만, 그러나, 병목되었다 복용 시도 첫 번째 n 값을 먼저 읽고 값을 정렬 한 다음 다른 모든 값을 샘플으로 반복하여 값이 정렬 된 마지막 값인 lowestSamples 배열보다 작 ​​으면 검사합니다. 값이 낮 으면 배열의 값으로 바꾸고 배열을 다시 정렬합니다. 이 약 5 배 빠른 것으로 밝혀졌다 :

const int numLowestSamples = 10; 

double[] samples; 

List<double> lowestSamples = new List<double>(); 

for (int count = 0; count < iterations; count++) // iterations typically around 2600000 
{ 
    samples = whatever; 

    lowestSamples.Clear(); 

    // Read first n values 
    int i = 0; 
    do 
    { 
     if (samples[i] > 0) 
      lowestSamples.Add(samples[i]); 

     i++; 
    } while (lowestSamples.Count < numLowestSamples) 

    // Sort the array 
    lowestSamples.Sort(); 

    for (int j = numLowestSamples; j < samples.Count; j++) // samples.Count is typically 3600 
    { 
     // if value is larger than 0, but lower than last/highest value in lowestSamples 
     // write value to array (replacing the last/highest value), then sort array so 
     // last value in array still is the highest 
     if (samples[j] > 0 && samples[j] < lowestSamples[numLowestSamples - 1]) 
     { 
      lowestSamples[numLowestSamples - 1] = samples[j]; 
      lowestSamples.Sort(); 
     } 
    } 
} 

이 상대적으로 빠른 작동하지만, 내가 더 빠르고 더 나은 해결책을 마련하기 위해 사람을 도전하고 싶었다.

Answer 1

대신 반복 lowestSamples, 그냥 앉아 것 샘플 삽입 정렬 :

int samplesCount = samples.Count; 

for (int j = numLowestSamples; j < samplesCount; j++) 
{ 
    double sample = samples[j]; 

    if (sample > 0 && sample < currentMax) 
    { 
     int k; 

     for (k = 0; k < numLowestSamples; k++) 
     { 
      if (sample < lowestSamples[k]) 
      { 
       Array.Copy(lowestSamples, k, lowestSamples, k + 1, numLowestSamples - k - 1); 
       lowestSamples[k] = sample; 

       break; 
      } 
     } 

     if (k == numLowestSamples) 
     { 
      lowestSamples[numLowestSamples - 1] = sample; 
     } 

     currentMax = lowestSamples[numLowestSamples - 1]; 
    } 
} 

을 이제 numLowestSamples이 상당히 크다고 할 필요가있는 경우를 (접근 샘플의 크기.count)를 사용하면 O (n/2)가 아닌 numLowestSamples 인 새 샘플을 삽입하는 데 더 빠른 (일반적으로 O (logn)이 될 수있는 우선 순위 대기열을 사용할 수 있습니다. 우선 순위 큐는 새로운 값을 효율적으로 삽입하고 O (logn) 시간에 가장 큰 값을 제거 할 수 있습니다.

numLowestSamples가 10 인 경우 실제로는 필요하지 않습니다. 특히 복소수 만 다루고 복잡한 데이터 구조는 다루지 않기 때문에 특히 그렇습니다. 힙이 있고 numLowestSamples가 작은 경우 힙 노드 (대부분의 우선 순위 대기열에서 힙을 사용)에 대한 메모리 할당의 오버 헤드는 검색/삽입 효율성 향상 (테스트가 중요 함)보다 클 수 있습니다.

Answer 2

최소 힙을 유지하고 성능 차이를 측정 해보십시오. 다음은 피보나치 힙 (fibonacci heap)이라고 불리는 데이터 구조입니다. 아마 약간의 작업을 할 수는 있지만 적어도 내 가설을 테스트 할 수는 있습니다.

public sealed class FibonacciHeap<TKey, TValue> 
{ 
    readonly List<Node> _root = new List<Node>(); 
    int _count; 
    Node _min; 

    public void Push(TKey key, TValue value) 
    { 
     Insert(new Node { 
      Key = key, 
      Value = value 
     }); 
    }  

    public KeyValuePair<TKey, TValue> Peek() 
    { 
     if (_min == null) 
      throw new InvalidOperationException(); 
     return new KeyValuePair<TKey,TValue>(_min.Key, _min.Value); 
    }  

    public KeyValuePair<TKey, TValue> Pop() 
    { 
     if (_min == null) 
      throw new InvalidOperationException(); 
     var min = ExtractMin(); 
     return new KeyValuePair<TKey,TValue>(min.Key, min.Value); 
    } 

    void Insert(Node node) 
    { 
     _count++; 
     _root.Add(node); 
     if (_min == null) 
     { 
      _min = node; 
     } 
     else if (Comparer<TKey>.Default.Compare(node.Key, _min.Key) < 0) 
     { 
      _min = node; 
     } 
    } 

    Node ExtractMin() 
    { 
     var result = _min; 
     if (result == null) 
      return null; 
     foreach (var child in result.Children) 
     { 
      child.Parent = null; 
      _root.Add(child); 
     } 
     _root.Remove(result); 
     if (_root.Count == 0) 
     { 
      _min = null; 
     } 
     else 
     { 
      _min = _root[0]; 
      Consolidate(); 
     } 
     _count--; 
     return result; 
    } 

    void Consolidate() 
    { 
     var a = new Node[UpperBound()]; 
     for (int i = 0; i < _root.Count; i++) 
     { 
      var x = _root[i]; 
      var d = x.Children.Count; 
      while (true) 
      { 
       var y = a[d]; 
       if (y == null) 
        break;     
       if (Comparer<TKey>.Default.Compare(x.Key, y.Key) > 0) 
       { 
        var t = x; 
        x = y; 
        y = t; 
       } 
       _root.Remove(y); 
       i--; 
       x.AddChild(y); 
       y.Mark = false; 
       a[d] = null; 
       d++; 
      } 
      a[d] = x; 
     } 
     _min = null; 
     for (int i = 0; i < a.Length; i++) 
     { 
      var n = a[i]; 
      if (n == null) 
       continue; 
      if (_min == null) 
      { 
       _root.Clear(); 
       _min = n; 
      } 
      else 
      { 
       if (Comparer<TKey>.Default.Compare(n.Key, _min.Key) < 0) 
       { 
        _min = n; 
       } 
      } 
      _root.Add(n); 
     } 
    } 

    int UpperBound() 
    { 
     return (int)Math.Floor(Math.Log(_count, (1.0 + Math.Sqrt(5))/2.0)) + 1; 
    } 

    class Node 
    { 
     public TKey Key; 
     public TValue Value; 
     public Node Parent; 
     public List<Node> Children = new List<Node>(); 
     public bool Mark; 

     public void AddChild(Node child) 
     { 
      child.Parent = this; 
      Children.Add(child); 
     } 

     public override string ToString() 
     { 
      return string.Format("({0},{1})", Key, Value); 
     } 
    } 
} 

Answer 3

이상적으로, 당신은 단지 그렇게 솔루션은 꽤 빠르입니다 컬렉션을 통해 하나 개의 패스를 만들고 싶어 것입니다. 그러나 앞에 삽입 된 숫자를 홍보 할 필요가있을 때마다 모든 하위 목록을 사용합니다. 그러나 10 개의 요소를 정렬하는 것은 거의 무시할 수 있으며이를 향상 시키면 많은 도움이되지는 않습니다. 솔루션에 대한 최악의 시나리오는 처음부터 9 개의 숫자가 낮은 경우입니다. 따라서 후속 숫자가 각각 < lowestSamples[numLowestSamples - 1] 인 경우, 이미 정렬 된 목록을 정렬합니다 (최악의 경우 QuickSort의 경우 시나리오).

결론적으로 소수의 숫자를 사용하고 있기 때문에 관리되는 언어를 사용하여 오버 헤드가 발생하면 많은 수학적 개선 작업을 수행 할 수 없습니다.

멋진 알고리즘의 명성!

Answer 4

선택 알고리즘이라고합니다.

이 위키 페이지에 몇 가지 일반적인 해결책이 있습니다 :

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

당신은 QuickSelect 알고리즘을 사용할 수 있습니다 (하지만 당신은 C#을 변환하기 위해 약간의 작업을해야 할 것입니다) n 번째 가장 낮은 요소를 찾은 다음 배열을 반복하여 각 요소를 얻습니다. < = 그 중 하나. 여기에 C#에서 예 QuickSelect가있다

: http://dpatrickcaldwell.blogspot.co.uk/2009/03/more-ilist-extension-methods.html

Answer 5

두 개의 서로 다른 아이디어 :

이

1. 대신 배열을 정렬로, 단지에 하나의 Insertion Sort 패스를 수행합니다. 새로 추가 된 항목이 순서가없는 유일한 항목이라는 것을 이미 알고 있으므로 해당 지식을 사용하십시오.
2. Heap Sort을 살펴보십시오. 바이너리 max-heap을 빌드하고 (가장 작은 것에서 가장 큰 것을 소트하고 싶다면) 인덱스 0의 max 요소를 여전히 힙의 일부인 마지막 요소와 교체하여 힙에서 요소를 제거하기 시작합니다. 이제 가장 큰 요소에서 가장 작은 요소로 배열을 가장한다면 10 개의 요소를 정렬 한 후에 정렬을 중지 할 수 있습니다. 배열 끝의 10 개 요소가 가장 작을 것이며, 나머지 배열은 여전히 ​​배열 표현의 2 진 힙입니다. 그게 어떻게 Quicksort-based selection algorithm on Wikipedia과 비교 될지 모르겠습니다. 선택할 요소의 수와 관계없이 힙을 빌드하는 작업은 항상 전체 배열에 대해 수행됩니다.

Answer 6

귀하의 아이디어가 정확하다고 생각합니다. 즉, 한 번 통과하고 최소 크기의 정렬 된 데이터 구조를 유지하는 것이 일반적으로 가장 빠릅니다. 성능 향상은 최적화입니다.

귀하의 최적화는 일 것입니다. 1) 귀하는 매순간 결과를 정렬하고 있습니다. 작은 크기의 경우 가장 빠르지 만 더 큰 세트의 경우 가장 빠르지는 않습니다. 어쩌면 두 개의 알고리즘을 고려해보십시오. 하나는 주어진 임계 값 이하이고 다른 하나는 임계 값 이상에 대한 것입니다 (힙 정렬과 같은). 2) 최소 집합에서 제거해야하는 값 (현재 마지막 요소를 보면서 수행 한 값)을 추적합니다. 쫓겨나는 값보다 크거나 같은 값을 삽입하고 정렬하는 작업을 건너 뛸 수 있습니다.