Trung bình nhanh mà không có phân chia

Question

Tôi có một vòng lặp tìm kiếm nhị phân được nhấn nhiều lần trong đường dẫn thực hiện.

Một hồ sơ cho thấy rằng phần bộ phận của tìm kiếm (tìm kiếm các chỉ số trung đưa các chỉ số cao và thấp của phạm vi tìm kiếm) thực sự là một phần tốn kém nhất của việc tìm kiếm, bởi một yếu tố của khoảng 4.

(Tôi nghĩ) nó không phải là quan trọng cho tìm kiếm nhị phân hiệu quả để tìm giá trị trung bình chính xác, chỉ là một giá trị gần giữa mà không có thiên vị trong hai hướng.

Có thuật toán bit-twiddling để thay thế mid = (low + high)/2 bằng thứ gì đó nhanh hơn nhiều không?

Chỉnh sửa: Ngôn ngữ là C#, nhưng hoạt động bit tương đương có hiệu lực ở bất kỳ ngôn ngữ nào (mặc dù nó không có lợi ích hiệu suất), đó là lý do tôi để thẻ C# tắt.

Answer 1

int mid = (low + high) >>> 1; 

Lưu ý rằng sử dụng "(thấp + cao)/2" để tính toán điểm giữa won't work correctly khi tràn số nguyên trở thành vấn đề.

Answer 2

Bạn có thể dùng chút thay đổi và cũng khắc phục một vấn đề tràn có thể:

low + ((high-low) >> 1) 

Tuy nhiên tôi phải thừa nhận tôi mong đợi các trình biên dịch hiện đại và thông dịch viên để làm phân chia bởi 2 (hoặc phân chia bởi bất cứ quyền lực liên tục khác 2) như chuyển dịch bit, do đó, không chắc chắn nếu nó thực sự sẽ giúp đỡ - hãy thử nó ra.

Answer 3

Nếu tôi nhớ chính xác, có một số trường hợp sử dụng chính xác giữa mảng có thể thực sự chậm hơn. Giải pháp là để ngẫu nhiên lựa chọn chỉ mục mà bạn chia đôi mảng. Tương tự với thuật toán để xác định trung vị của một mảng.

Tôi không thể nhớ lại các chi tiết chính xác, nhưng tôi nhớ đã nghe trong bài 6 của số MIT algorithms series trên iTunes.

Answer 4

Đây là một phiên bản bit-hack của tỷ lệ trung bình mà không gặp phải vấn đề tràn:

unsigned int average (unsigned int x, unsigned int y) 
{ 
    return (x&y)+((x^y)>>1); 
} 

Answer 5

Tiếp tục mở rộng trên Nils' câu trả lời Richard Schroeppel phát minh này.

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

ITEM 23 (Schroeppel):

(A và B) + (A HOẶC B) = A + B = (A XOR B) + 2 (A và B).

(A + B)/2 = ((A XOR B) + 2(A AND B))/2 
      = (A XOR B)/2 + (A AND B) 
      = (A XOR B)>>1 + (A AND B) 


avg(x,y){return((x^y)>>1)+(x&y);} 

(A AND B) + (A OR B) = A + B vì A AND B cho tổng các chia sẻ (giữa A và B), quyền hạn của hai, A OR B mang đến cho cả hai những chia sẻ và những người không được, do đó:

(A AND B) + (A OR B) = 
    (sum of shared powers of two) + 
    ((sum of shared powers of two) + (sum of unshared powers of two)) = 
    (sum of shared powers of two) + 
    ((sum of shared powers of two) + (sum of powers of two of A only) + 
    (sum of powers of two of B only)) = 
     ((sum of shared powers of two) + (sum of powers of two of A only)) + 
     ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

A XOR B đưa ra một bản đồ các bit khác nhau giữa A và B.Do đó,

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only). 

Và như sau:

2(A AND B) + (A XOR B) = 
     ((sum of shared powers of two) + (sum of powers of two of A only)) + 
     ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

Answer 6

Hãy thử thấp + ((cao - thấp)/2)). Điều này sẽ hiệu quả vì bạn chỉ lấy trung bình của hai số. Điều này sẽ làm giảm lượng thời gian thuật toán được thực hiện nếu danh sách tìm kiếm nhị phân là khá lớn, vì cao - thấp là nhỏ hơn nhiều so với cao + thấp.