Cách nhanh nhất để xác định số không tối thiểu khác

Question

Có một mảng ví dụ 4 số nguyên làm cách nào một số có thể xác định số không tối thiểu khác - theo cách nhanh nhất?

Answer 1

Có một giải pháp song song cho vấn đề này, nhưng có lẽ nó không đáng để thử.

tiên chúng ta xác định một hoạt động xchg(m, n) trên một mảng một:

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n]) 

Thao tác này phân loại hai yếu tố 'm' và 'n' thứ tự tăng dần nếu cả hai đều chứa các giá trị khác không, hoặc hoán đổi chúng nếu giá trị trong phần tử 'm' bằng không.

Tiếp theo chúng ta thực hiện một bộ năm hoạt động như sau:

xchg(0,2) xchg(1,3) 
xchg(0,1) xchg(2,3) 
xchg(1,2) 

Các cặp xchg hoạt động có thể được thực hiện song song, giảm chi phí thời gian bằng 40% so với một thực hiện đúng tuần tự. Khi chúng ta kết thúc, bất kỳ phần tử nào khác trong mảng sẽ được sắp xếp theo thứ tự tăng dần. Phần tử có giá trị nhỏ nhất sẽ nằm trong [0]. Nếu giá trị đó bằng không, không có giá trị khác 0 trong mảng.

giải pháp này có ưu điểm của xử lý song song vốn được cung cấp bởi mạng lưới phân loại (http://en.wikipedia.org/wiki/Sorting_network), nhưng quá trình quét tuần tự của 4 yếu tố còn sử dụng không quá ba hoạt động so sánh, và điều quan trọng đòi hỏi phải có một nửa số lượng lưu trữ viết trung bình:

quét tuần tự

int v = a[0] 
for (n = 1; n < 4; n++) { 
    if ((a[n] < v && a[n] != 0) || v == 0) v = a[n] 
} 

Answer 2

Phụ thuộc vào đầu vào. Nếu mảng không được sắp xếp, thì bạn sẽ phải lặp qua toàn bộ mảng. Nếu mảng được sắp xếp, thì bạn chỉ cần lặp lại cho đến khi bạn tìm thấy thứ gì đó không bằng 0 - ngắn hơn nhiều.

Answer 3

Trừ khi bạn giữ giá trị tối thiểu khi các phần tử được thêm vào mảng hoặc bạn giữ mảng theo thứ tự sắp xếp - tôi không thấy giải pháp nào khác ngoài việc lặp lại mọi thành viên để xác định giá trị tối thiểu.

Không có cách nào 'nhanh' để kiểm tra từng thành viên.

Nói chung tôi khuyên bạn không nên tối ưu hóa thứ gì đó trừ khi nó thực sự chứng tỏ là chậm. Quy tắc cũ của chương trình dành 90% thời gian của nó trong 10% mã nói chung là đúng. Vì vậy, các quy tắc mà các lập trình viên có khả năng tối ưu hóa 99,99% mã không nằm trong 10% đó.

hồ sơ mã của bạn - mã số hồ sơ của bạn - mã số hồ sơ của bạn

Answer 4

Vâng cách nhanh nhất để mã hóa nó là std::min({a,b,c,d}). Trên một lưu ý nghiêm trọng hơn: Nếu ứng dụng của bạn đang thắt cổ chai trên thứ gì đó như lấy tối thiểu nhiều giá trị, một giải pháp tốt hơn có thể là tìm cách chia nhiệm vụ tìm kiếm tối thiểu đó thành các phần và gửi tới GPU (hoặc nhiều chủ đề), sau đó có thể vận hành nhiều tính toán tìm kiếm tối thiểu cùng một lúc.

Song song có lẽ sẽ giúp nhiều hơn là cố gắng viết một hàm tối thiểu trong hội đồng.

Answer 5

Nếu chúng ta đang nghĩ đến tối ưu hóa vi mô, thì có thể nhanh hơn để tính min(min(a,b),min(c,d)) thay vì min(min(min(a,b),c),d) trên bộ xử lý đơn đặt hàng hiện đại, vì ít phụ thuộc tuần tự hơn: trước đây bộ xử lý có thể tính min(a,b) và min(c,d) độc lập song song, nếu có đủ đơn vị thực thi. Điều này giả định rằng bộ xử lý có lệnh di chuyển có điều kiện, do đó máy tính min không yêu cầu phân nhánh.