hiệu suất tìm kiếm nhị phân so với hiệu quả tìm kiếm tuyến tính trong fortran

Question

Câu hỏi này là về hiệu quả của tìm kiếm tuyến tính so với hiệu quả tìm kiếm nhị phân cho mảng được sắp xếp trước trong bộ nhớ tiếp giáp ...

Tôi có một ứng dụng được viết bằng fortran (77!). Một hoạt động thường xuyên đối với phần của tôi là tìm chỉ mục trong một mảng sao cho gx(i) <= xin < gx(i+1). Tôi hiện đã thực hiện điều này như một binary search - xin lỗi vì các nhãn tuyên bố và goto - Tôi đã nhận xét những gì statments tương đương sẽ được sử dụng fortran 90 ...

 i=1 
     ih=nx/2 
201  continue !do while (.true.) 
      if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then !found what we want 
       ilow=i+1; ihigh=i 
       s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow)) 
       s2=1.0-s1 
       return 
      endif 
      if(i.ge.ih)then 
       goto 202 !exit 
      endif 
      if(xin.le.(gx(ih))then !xin is in second half of array 
       i=ih 
       ih=nx-(nx-ih)/2 
      else !xin is in first half of array 
       i=i+1 
       ih=i+(ih-i)/2 
      endif 
     goto 201 !enddo 

Tuy nhiên, hôm nay, tôi đã được đọc trên Wikipedia về tìm kiếm nhị phân và tôi đi qua này:

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a 
linear search may have superior performance simply because 
it exhibits better locality of reference. 

tôi không hoàn toàn hiểu tuyên bố này - ấn tượng của tôi là fetches bộ nhớ cache được thu thập trong (ish) khối lớn tại một thời điểm, vì vậy nếu chúng ta bắt đầu ở đầu mảng, tôi nghĩ rằng hầu hết các mảng sẽ có trong bộ nhớ cache đã có (ít nhất là nhiều như nó sẽ được cho một tìm kiếm tuyến tính), vì vậy tôi đã không nghĩ rằng đó sẽ là vấn đề.

Vì vậy, câu hỏi của tôi là, có cách nào để cho biết thuật toán nào sẽ hoạt động tốt hơn (tìm kiếm tuyến tính hoặc nhị phân?) Có ranh giới kích thước mảng không? Tôi hiện đang sử dụng mảng có kích thước khoảng 100 phần tử ...

Answer 1

Đối với mảng nhỏ, sự cố không phải là bộ nhớ cache. Bạn nói đúng: Một mảng nhỏ có thể được lưu trữ nhanh chóng.

Vấn đề là dự đoán nhánh có khả năng thất bại cho tìm kiếm nhị phân vì các nhánh được lấy hoặc bỏ qua ngẫu nhiên theo cách phụ thuộc vào dữ liệu. Chi nhánh dự đoán bỏ lỡ ngăn chặn đường ống CPU.

Hiệu ứng này có thể nghiêm trọng. Bạn có thể dễ dàng tìm kiếm 3 đến 8 phần tử tuyến tính trong cùng một thời gian để thực hiện một nhánh tìm kiếm nhị phân đơn (và bạn cần thực hiện nhiều nhánh tìm kiếm nhị phân). Chính xác điểm hòa vốn cần được đo.

Việc trì hoãn đường ống CPU cực kỳ tốn kém. Core i7 có thể rút ngắn tối đa 4 hướng dẫn cho mỗi chu kỳ đồng hồ (12 giga-instructions/giây ở 3 GHz!). Nhưng chỉ, nếu bạn không bị đình trệ.

Có các thuật toán không có nhánh thực hiện tìm kiếm nhị phân bằng cách sử dụng các chỉ lệnh CPU có điều kiện di chuyển. Các thuật toán này về cơ bản mở ra 32 bước tìm kiếm và sử dụng CMOV trong mỗi bước (32 bước là mức tối đa theo lý thuyết). Chúng không có nhánh nhưng không có gian hàng miễn phí: Mỗi bước tiếp theo phụ thuộc 100% vào phiên bản trước để CPU không thể sạc trước trong luồng lệnh. Nó phải chờ mọi lúc. Vì vậy, họ không giải quyết vấn đề này, chỉ cải thiện nó một chút.