cách nhanh nhất để có được n thấp nhất từ ​​mảng

Question

Tôi cần phải tìm n thấp nhất (mà không phải là 0) từ mảng các đôi (chúng ta hãy gọi mảng mẫu). Tôi cần phải làm điều này nhiều lần trong một vòng lặp, do đó tốc độ thực hiện là rất quan trọng. Tôi đã cố gắng đầu tiên phân loại các mảng và sau đó lấy 10 giá trị đầu tiên (mà không phải là 0), tuy nhiên, mặc dù Array.Sort được cho là nhanh, nó đã trở thành nút cổ chai:

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(); 
} 

Vì vậy, tôi đã thử một khác nhau, nhưng giải pháp ít sạch, bằng cách đọc thứ nhất trong các giá trị n đầu tiên, phân loại chúng, sau đó lặp qua tất cả các giá trị khác trong mẫu kiểm tra nếu giá trị nhỏ hơn giá trị cuối cùng trong sắp xếp lowestSamples mảng. Nếu giá trị thấp hơn thì thay thế nó bằng giá trị trong mảng và sắp xếp lại mảng. Điều này hóa ra nhanh hơn khoảng 5 lần:

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(); 
     } 
    } 
} 

Mặc dù điều này hoạt động tương đối nhanh, tôi muốn thách thức bất kỳ ai đưa ra giải pháp nhanh hơn và tốt hơn.

Answer 1

Thay vì liên tục sắp xếp lowestSamples, chỉ cần chèn mẫu nơi mà nó sẽ ngồi:

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]; 
    } 
} 

Bây giờ, nếu numLowestSamples cần phải được khá lớn (gần kích thước của mẫu.đếm) thì bạn có thể muốn sử dụng hàng đợi ưu tiên có thể nhanh hơn (thường sẽ là O (logn) để chèn mẫu mới thay vì O (n/2) trong đó n là numLowestSamples). Hàng đợi ưu tiên sẽ có thể chèn giá trị mới một cách hiệu quả và loại bỏ giá trị lớn nhất trên thời gian O (logn).

Với numLowestSố mẫu ở 10, thực sự không cần thiết - đặc biệt vì bạn chỉ xử lý gấp đôi và không phải là cấu trúc dữ liệu phức tạp. Với một numLowestSamples heap và nhỏ, chi phí cấp phát bộ nhớ cho các nút heap (các hàng đợi ưu tiên nhất sử dụng đống) có thể lớn hơn bất kỳ hiệu quả tìm kiếm/chèn nào (thử nghiệm là quan trọng).

Answer 2

Tôi nghĩ bạn có thể muốn thử việc duy trì một min-heap và đo lường sự khác biệt hiệu suất. Đây là một cấu trúc dữ liệu được gọi là vùng đệm Fibonacci mà tôi đang làm việc. Nó có thể có thể sử dụng một chút công việc nhưng bạn ít nhất có thể kiểm tra giả thuyết của tôi.

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

Lý tưởng nhất, bạn chỉ muốn thực hiện một lần vượt qua bộ sưu tập, vì vậy giải pháp của bạn khá mượt mà. Tuy nhiên, bạn đang sử dụng toàn bộ danh sách phụ với mỗi lần chèn khi bạn chỉ cần quảng bá các con số phía trước. Tuy nhiên, việc phân loại 10 yếu tố gần như không đáng kể và nâng cao điều này sẽ không thực sự mang lại cho bạn nhiều. trường hợp xấu nhất (về hiệu suất bị lãng phí) cho giải pháp của bạn là nếu bạn có 9 con số thấp nhất từ ​​đầu, như vậy với mỗi số tiếp theo bạn thấy rằng là < lowestSamples[numLowestSamples - 1], bạn sẽ được sắp xếp một danh sách đã được sắp xếp (đó là điều tồi tệ nhất trường hợp kịch bản cho QuickSort).

Tóm lại, kể từ khi bạn đang sử dụng quá ít số, không có nhiều cải thiện toán học bạn có thể làm cho các nguyên cần thiết của việc sử dụng một ngôn ngữ được quản lý để làm điều này.

Kudos trên thuật toán mát mẻ!

Answer 4

Đây được gọi là Thuật toán lựa chọn.

Có một số giải pháp tổng thể về trang Wiki này:

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

(nhưng bạn phải làm một chút công việc để chuyển sang C#)

Bạn có thể sử dụng một thuật toán QuickSelect để tìm phần tử thấp nhất thứ n, và sau đó lặp qua mảng để nhận được từng phần tử < = một phần tử đó.

Có một ví dụ QuickSelect trong C# ở đây: http://dpatrickcaldwell.blogspot.co.uk/2009/03/more-ilist-extension-methods.html

Answer 5

Hai ý tưởng khác nhau:

1. Thay vì sắp xếp mảng, chỉ cần thực hiện một single Insertion Sort vượt qua trên đó. Bạn đã biết mục mới được thêm vào sẽ là mục duy nhất không có thứ tự, vì vậy hãy sử dụng kiến ​​thức đó.
2. Hãy xem Heap Sort. Nó xây dựng một heap tối đa nhị phân (nếu bạn muốn sắp xếp nhỏ nhất thành lớn nhất), sau đó bắt đầu loại bỏ các phần tử khỏi heap bằng cách hoán đổi phần tử max ở chỉ mục 0 với phần tử cuối cùng vẫn là một phần của heap. Bây giờ nếu bạn giả vờ sắp xếp mảng từ phần tử lớn nhất đến nhỏ nhất, bạn có thể dừng sắp xếp sau khi đã sắp xếp 10 phần tử. 10 phần tử ở cuối mảng sẽ là nhỏ nhất, mảng còn lại vẫn là một đống nhị phân trong biểu diễn mảng. Tôi không chắc nó sẽ so sánh như thế nào với Quicksort-based selection algorithm on Wikipedia. Việc xây dựng heap sẽ luôn được thực hiện cho toàn bộ mảng, bất kể bạn muốn chọn bao nhiêu phần tử.

Answer 6

Tôi nghĩ ý tưởng của bạn là chính xác. Tức là, một người vượt qua và giữ một cấu trúc dữ liệu được sắp xếp có kích thước tối thiểu là nói chung, nhanh nhất. Cải thiện hiệu suất của bạn cho điều này là tối ưu hóa.

Tối ưu hóa của bạn sẽ là: 1) bạn sắp xếp các kết quả của mình mỗi lần đi qua. Điều này có thể là nhanh nhất cho các kích thước nhỏ, nó không phải là nhanh nhất cho các bộ lớn hơn. Hãy xem xét có thể hai thuật toán, một cho dưới một ngưỡng nhất định và một (giống như một loại đống) cho trên ngưỡng. 2) theo dõi bất kỳ giá trị nào phải được xóa khỏi tập hợp tối thiểu của bạn (bạn hiện đang thực hiện bằng cách xem phần tử cuối cùng). Bạn có thể bỏ qua chèn và sắp xếp bất kỳ giá trị nào lớn hơn hoặc bằng bất kỳ giá trị nào bị loại bỏ.