Cách nhanh nhất để tính toán phân phối tần số cho mảng trong C# là gì?

Question

Tôi chỉ tự hỏi phương pháp tốt nhất cho phép tính đó là gì. Giả sử tôi có một mảng đầu vào của các giá trị và mảng các ranh giới - tôi muốn tính toán/phân bổ tần số phân bổ cho từng phân đoạn trong mảng ranh giới.

Ý tưởng hay là sử dụng tìm kiếm nhóm cho điều đó?

Trên thực tế tôi thấy rằng câu hỏi Calculating frequency distribution of a collection with .Net/C#

Nhưng tôi không hiểu làm thế nào để sử dụng xô cho mục đích đó gây ra kích thước của mỗi thùng có thể khác nhau trong hoàn cảnh của tôi.

EDIT: Sau tất cả các cuộc thảo luận tôi có giải pháp vòng lặp bên trong/bên ngoài, nhưng tôi vẫn muốn loại bỏ vòng lặp bên trong bằng từ điển để có hiệu suất O (n) trong trường hợp đó. giá trị vào chỉ mục nhóm. Vì vậy, chúng ta cần một số loại hàm băm với O (1) phức tạp? Có ý tưởng nào để làm nó không không?

Answer 1

Sắp xếp nhóm đã là trường hợp xấu nhất O (n^2), vì vậy tôi chỉ làm một vòng lặp bên trong/bên ngoài đơn giản tại đây. Vì mảng nhóm của bạn nhất thiết phải ngắn hơn mảng đầu vào của bạn, hãy giữ nó trong vòng lặp bên trong. Vì bạn đang sử dụng kích thước nhóm tùy chỉnh, thực sự không có thủ thuật toán học nào có thể loại bỏ vòng lặp bên trong đó.

int[] freq = new int[buckets.length - 1]; 
foreach(int d in input) 
{ 
    for(int i = 0; i < buckets.length - 1; i++) 
    { 
     if(d >= buckets[i] && d < buckets[i+1]) 
     { 
      freq[i]++; 
      break; 
     } 
    } 
} 

Đây cũng là trường hợp xấu nhất O (n^2) nhưng bạn không thể đánh bại sự đơn giản của mã. Tôi sẽ không lo lắng về việc tối ưu hóa cho đến khi nó trở thành một vấn đề thực sự. Nếu bạn có một mảng nhóm lớn hơn, bạn có thể sử dụng tìm kiếm nhị phân của một số loại. Nhưng, vì các bản phân phối tần số thường là < 100 yếu tố, tôi nghi ngờ bạn sẽ thấy rất nhiều lợi ích hiệu suất thực tế.

Answer 2

Nếu mảng đầu vào của bạn đại diện cho dữ liệu thế giới thực (với mô hình của nó) và mảng ranh giới là lớn để lặp lại một lần nữa và một lần nữa trong vòng lặp bên trong, bạn có thể xem xét các phương pháp sau đây:

• Trước hết loại mảng đầu vào của bạn. Nếu bạn làm việc với dữ liệu trong thế giới thực Tôi khuyên bạn nên xem xét Timsort - Wiki cho việc này. Nó cung cấp đảm bảo hiệu suất rất tốt cho một mẫu có thể được nhìn thấy trong dữ liệu trong thế giới thực.

• Traverse qua mảng được sắp xếp và so sánh nó với giá trị đầu tiên trong mảng ranh giới:

  • Nếu giá trị trong mảng đầu vào là ít sau đó ranh giới - tần số tăng truy cập cho ranh giới này
  • Nếu giá trị trong mảng đầu vào lớn hơn sau đó là ranh giới - đi tới giá trị tiếp theo trong mảng các ranh giới và tăng bộ đếm cho ranh giới mới.

Trong một mã nó có thể trông như thế này:

Timsort(myArray); 
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>() 

for (int i = 0; i<myArray.Lenght; i++) { 
    if (myArray[i]<boundaries[boundPos]) { 
    boundaries[boubdPos]++; 
    } 
    else { 
    boundPos++; 
    boundaries[boubdPos]++; 
    } 
}