Tôi tò mò nếu có ai có thể giải thích việc triển khai tìm kiếm nhị phân không nhánh cho tôi. Tôi thấy nó được đề cập trong một question gần đây nhưng tôi không thể tưởng tượng nó sẽ được thực hiện như thế nào. Tôi cho rằng nó có thể hữu ích để tránh các nhánh nếu số lượng các mục là khá lớn.Tìm kiếm nhị phân không phân nhánh
Tôi sẽ giả định bạn đang nói về câu "Tạo một mảng static const của tất cả các ô vuông hoàn hảo trong miền bạn muốn hỗ trợ và thực hiện tìm kiếm nhị phân nhanh không nhánh trên đó." được tìm thấy trong this answer.
Tìm kiếm nhị phân "không nhánh" về cơ bản chỉ là vòng lặp tìm kiếm nhị phân chưa được kiểm soát. Điều này chỉ hoạt động nếu bạn biết trước số lượng mục trong mảng bạn đang tìm kiếm (như bạn sẽ làm nếu đó là static const). Bạn có thể viết một chương trình để viết mã chưa được kiểm soát nếu nó quá dài để làm bằng tay.
Sau đó, bạn phải điểm chuẩn giải pháp của mình để xem liệu giải pháp đó có thực sự nhanh hơn vòng lặp hay không. Nếu mã không có nhánh của bạn quá lớn, nó sẽ không vừa với bộ nhớ cache nhanh của CPU và sẽ mất nhiều thời gian để chạy hơn vòng lặp tương đương.
Nếu có chức năng trả về +1, -1 hoặc 0 dựa trên vị trí của mục chính xác so với mục hiện tại, có thể khởi tạo vị trí thành kích thước danh sách/2 và bước thành vị trí/2 và sau đó sau mỗi lần so sánh làm vị trí + = hướng * bước; stepsize = stepsize/2. Lặp lại cho đến khi bước là số không.
"Lặp lại cho đến khi bước là số không." Làm thế nào là nó không nhánh là bạn đang làm một chi nhánh không bằng không? – rlibby
Nếu ai biết giá trị bắt đầu, người ta có thể bỏ vòng lặp số lần yêu cầu. Ngoài ra, một số nền tảng phần cứng (đặc biệt là DSP) hỗ trợ vòng lặp "DO" kiểu Fortran trong phần cứng; khi một lệnh được lấy từ một địa chỉ phù hợp với địa chỉ đầu cuối vòng lặp, bộ đếm vòng lặp sẽ giảm và bộ đếm chương trình sẽ được nạp với địa chỉ bắt đầu vòng lặp. Zero chu kỳ trên không cho vòng lặp. – supercat
chi nhánh được tính toán vẫn là nhánh. Loop unrolling là không phân nhánh (hoặc ít nhất nó có thể được), nhưng nó không sử dụng bất kỳ điều kiện nào như "cho đến khi bước là số không." – rlibby
Ah okay tôi nhận được ngay bây giờ cảm ơn. Tôi giả sử có một số bit kỳ lạ twiddling để tránh các báo cáo nếu bên trong vòng lặp. – GWW
+1 bởi vì đây thực sự là một cách hữu ích để loại bỏ các nhánh vòng lặp, mặc dù từ một nhận xét sau đó về câu hỏi đó dường như R. dự định "bit xoắn để tránh các nhánh có điều kiện". Bằng cách làm cả hai bạn có thể trong thực tế tránh * tất cả * chi nhánh. –
Tìm kiếm không có nhánh "không phân nhánh" được trình bày trong "Lập trình viên ngọc trai" của Bentley, IIRC, nơi ông giải thích kỹ thuật này một cách triệt để –