Có thể làm nhanh hơn tìm kiếm nhị phân

 (lemire.me)
3 điểm bởi GN⁺ 2026-05-01 | 1 bình luận | Chia sẻ qua WhatsApp
  • Tìm kiếm nhị phân thường được dùng để tìm giá trị trong mảng đã sắp xếp, nhưng nó chỉ so sánh một giá trị mỗi lần, trong khi CPU hiện đại có thể so sánh nhiều giá trị đồng thời trong một lệnh, nên nếu tận dụng khả năng này thì có thể tăng tốc độ tìm kiếm đáng kể
  • SIMD Quad là một thuật toán tìm kiếm phân cấp: chia mảng thành các khối 16 phần tử, nhanh chóng thu hẹp vị trí khối bằng tìm kiếm nội suy bậc 4, rồi dùng lệnh SIMD để so sánh đồng thời 16 phần tử trong khối
  • Trong benchmark, trên Intel với warm cache thuật toán này cho hiệu năng nhanh hơn hơn 2 lần so với tìm kiếm nhị phân; trên Apple với cold cache cũng nhanh hơn hơn 2 lần, và ở mọi điều kiện đo đều tốt hơn std::binary_search
  • Thay vì chia đôi như tìm kiếm nhị phân, nếu chia thành 4 phần thì số lệnh có tăng nhẹ, nhưng trên các mảng lớn của Intel nó tận dụng memory-level parallelism tốt hơn nên hiệu năng cold cache được cải thiện
  • Các thuật toán giáo khoa được thiết kế mà không giả định data parallelism và memory parallelism của CPU ngày nay, nên việc thiết kế lại để phản ánh đặc tính phần cứng có thể mang lại cải thiện hiệu năng thực tế

Ý tưởng cốt lõi

  • Tìm kiếm nhị phân có cấu trúc chỉ so sánh một giá trị tại mỗi thời điểm, nhưng các bộ xử lý ARM 64-bit và x64 hiện đại có thể so sánh đồng thời 8 số nguyên 16-bit trong một lệnh
  • Nếu tận dụng khả năng phần cứng này, có thể chuyển đơn vị tìm kiếm từ từng phần tử riêng lẻ sang theo khối, qua đó giảm mạnh số lần so sánh
  • Thay vì chia mảng làm hai, nếu chia làm 4 (tìm kiếm bậc 4) thì số lệnh có thể tăng nhẹ, nhưng nút thắt có thể không nằm ở số lệnh, đồng thời còn tận dụng memory-level parallelism tốt hơn

Cách cơ bản để kiểm tra phần tử trong mảng đã sắp xếp

  • Cách đơn giản nhất để kiểm tra sự tồn tại của một giá trị trong mảng đã sắp xếp là tìm kiếm tuyến tính, duyệt từng giá trị một; trong C++ có thể đạt hiệu quả tương tự bằng std::find
  • Với mảng lớn, tìm kiếm nhị phân nhanh hơn, lặp lại quá trình loại bỏ nửa trên hoặc nửa dưới dựa trên giá trị ở giữa đoạn tìm kiếm
  • std::binary_search của C++ trả về giá trị boolean cho biết phần tử có tồn tại hay không
  • Định dạng Roaring Bitmap dùng các mảng số nguyên 16-bit có kích thước từ 1 đến 4096 và sử dụng tìm kiếm nhị phân để kiểm tra sự tồn tại của giá trị

Cấu trúc thuật toán SIMD Quad

  • Chia mảng đã sắp xếp của các số nguyên không dấu 16-bit thành các khối kích thước cố định gồm 16 phần tử
  • Dùng phần tử cuối của mỗi khối làm khóa nội suy để thu hẹp phạm vi xuống một khối duy nhất có khả năng chứa giá trị đích, sau đó kiểm tra đồng thời 16 phần tử trong khối đó bằng SIMD
  • Các bước hoạt động:
    • Nếu số phần tử nhỏ hơn 16 thì tìm kiếm tuyến tính trên toàn bộ mảng
    • Chia mảng thành các khối liên tiếp 16 phần tử, số khối tổng cộng là num_blocks = cardinality / 16
    • Dùng phần tử cuối khối làm khóa, so sánh các điểm 1/4 trong phạm vi tìm kiếm hiện tại với giá trị đích rồi điều chỉnh base
    • Nếu là khối hợp lệ thì trên ARM dùng NEON, còn trên x64 dùng SSE2 để nạp 16 phần tử và thực hiện so sánh bằng nhau song song
    • Các phần tử còn lại không nằm trong khối đầy đủ sẽ được tìm tuyến tính
    Quảng cáo

Cách benchmark

  • Với mỗi kích thước mảng từ 2 đến 4096, tạo 100.000 mảng đã sắp xếp của số nguyên không dấu 16-bit
  • Với mỗi kích thước, thực hiện 10 triệu truy vấn kiểm tra phần tử theo hai chế độ
    • chế độ cold: mỗi truy vấn tìm trên một mảng khác nhau để mô phỏng cache miss
    • chế độ warm: tìm trên cùng một mảng 100 lần liên tiếp để mô phỏng cache hit
  • Chỉ số đo là thời gian truy vấn trung bình; các đối tượng so sánh là tìm kiếm tuyến tính (std::find), tìm kiếm nhị phân (std::binary_search) và SIMD Quad
  • Hệ thống đo là Apple M4 (Apple LLVM) và Intel Emerald Rapids (GCC)
Quảng cáo

Kết quả đo

  • Khi mảng lớn hơn, tìm kiếm nhị phân thắng rõ rệt so với tìm kiếm tuyến tính; trong cold cache, tìm kiếm tuyến tính càng bất lợi hơn vì phải truy cập nhiều dữ liệu hơn
  • Nền tảng Intel: trong warm cache, SIMD Quad nhanh hơn hơn 2 lần so với tìm kiếm nhị phân; trong cold cache, mức lợi ích nhỏ hơn
  • Nền tảng Apple: trong cold cache, SIMD Quad nhanh hơn hơn 2 lần; trong warm cache, mức lợi ích bị giới hạn hơn
  • Trong mọi trường hợp, SIMD Quad đều nhanh hơn std::binary_search
  • Phần SIMD giảm lượng công việc bằng các lệnh chuyên dụng, đồng thời ít lệnh và ít nhánh hơn, nên nguyên nhân cải thiện tốc độ khá rõ ràng

Hiệu quả của tìm kiếm bậc 4

  • Ngoài ra còn so sánh với phiên bản SIMD binary, giữ nguyên tối ưu SIMD nhưng thay tìm kiếm nội suy bậc 4 bằng tìm kiếm nhị phân
  • Trên nền tảng Apple, hiệu quả của cách tiếp cận bậc 4 là không lớn
  • Trên nền tảng Intel, trong tình huống cold cache với mảng lớn, cách tiếp cận bậc 4 là một tối ưu hóa có ý nghĩa
  • Trên máy chủ Intel, tìm kiếm bậc 4 tận dụng memory-level parallelism tốt hơn

Các điểm chính trong triển khai

  • Hàm simd_quad nhận mảng uint16_t, số phần tử cardinality, giá trị cần tìm pos, và trả về boolean
  • gap được cố định là 16; nếu cardinality < gap thì dùng vòng lặp đơn giản để tìm
  • Vòng lặp tìm khối, khi n > 3, sẽ đọc và so sánh giá trị cuối khối tại các điểm 1/4, 2/4, 3/4, rồi di chuyển base theo tổng của ba kết quả so sánh
  • Khối được chọn sẽ được so sánh song song 16 phần tử theo hai cụm bằng vceqq_u16 của ARM NEON hoặc _mm_cmpeq_epi16 của x64 SSE2
  • Với đoạn phần tử còn lại, hàm trả về kết quả v == pos tại điểm đầu tiên thỏa v >= pos

Kết luận

  • Tìm kiếm nhị phân kiểu giáo khoa là một thuật toán ổn, nhưng hoàn toàn có thể làm nhanh hơn theo cách có ý nghĩa trong hiệu năng thực tế
  • Nhiều thuật toán chuẩn vốn không được thiết kế với giả định về mức độ song song rất cao của máy tính hiện đại
  • SIMD Quad là một cách tiếp cận nhằm tận dụng cả memory-level parallelism lẫn data parallelism
  • Có thể vẫn còn những thuật toán tốt hơn, và cần các cách tiếp cận sáng tạo hơn
  • Mã nguồn
  • Faster intersections between sorted arrays with shotgun

Bài viết liên quan

1 bình luận

 
GN⁺ 2026-05-01
Ý kiến trên Hacker News

  • Tách biệt với câu chuyện tối ưu phần cứng mức thấp mà Daniel Lemire nói tới, tìm kiếm nhị phân hay các biến thể triển khai của nó chỉ là tốt nhất khi ta không biết gì ngoài việc dữ liệu đã được sắp xếp/đơn điệu
    Nếu có thông tin trước về phân bố dữ liệu thì có thể dùng nó để tạo ra thuật toán nhanh hơn rất nhiều. Ví dụ là cách con người lật từ điển giấy đến một cụm trang phù hợp nhanh hơn so với tìm kiếm nhị phân thuần túy
    Về mặt toán học, tìm kiếm trên danh sách đã sắp xếp gần với việc dùng một thuật toán điều khiển vòng kín để tìm hàm nghịch đảo của một hàm đơn điệu, và ta thậm chí có thể xây dựng hàm chi phí rồi dùng gradient descent hoặc các biến thể tăng tốc. Nói rộng hơn, thay vì lấy lời giải từ một mô tả bị trừu tượng hóa quá mức, việc tận dụng thêm thông tin về bài toán cụ thể luôn hiệu quả hơn, và có thể đem lại cải thiện tốc độ có khả năng mở rộng lớn hơn nhiều so với các cải thiện hệ số hằng số nhờ tận dụng phần cứng tốt hơn

    • Tôi đã suy nghĩ khá nhiều về tìm kiếm nhị phân nhưng vẫn chưa tìm ra thứ gì tốt hơn cách cài đặt này: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
      1. Kiểm tra O(1) xem có phải danh sách dày đặc không
      2. Kiểm tra cận trên
      3. Tìm kiếm nhị phân với số vòng lặp cố định
        Số vòng lặp cố định tốt cho bộ dự đoán nhánh, và vòng lặp lõi cũng được tối ưu rất chặt cho phần cứng đích, chẳng hạn tránh phép nhân. Mọi nỗ lực làm cho nó “thông minh” hơn đều khiến vòng lặp tệ đi và không mang lại lợi ích. Định dạng mảng struct có kích thước 12, và thường thì N nhỏ nên lại càng khó
    • Tôi nhớ đã từng đọc một bài về treap, trong đó thay vì cân bằng cây, người ta dùng trọng số để điều chỉnh độ sâu tìm kiếm giống như mã hóa Huffman, nhằm giảm thời gian truy cập trung bình khi tần suất truy cập khác nhau
      Tôi đã không bookmark lại nên khoảng mỗi năm hai lần lại đi tìm lại. Theo truyền thuyết thì tôi vẫn còn đang tìm
    • Đúng, nhưng mấu chốt là nhiều khi bạn không thể biết thêm gì về dữ liệu
      Đó là lý do B-tree là tiêu chuẩn trong cơ sở dữ liệu. Dữ liệu có thể là bất cứ thứ gì, và nếu bạn nạp vào cả đống dòng mới thì đặc tính của nó có thể thay đổi mạnh bất cứ lúc nào
      Bạn có thể xây dựng thuật toán tăng tốc truy vấn bằng thứ gì đó như gradient descent, nhưng B-tree vốn đã rất nhanh rồi, lại còn có nhiều ưu điểm như hiệu năng tệ nhất có thể dự đoán được, nhu cầu I/O dễ đoán, quét theo khoảng, duyệt theo thứ tự đã sắp xếp, hỗ trợ điều kiện tiền tố
      Có thể tạo ra thuật toán truy vấn hiệu quả hơn cho một số phân bố dữ liệu nhất định, nhưng thường phải đánh đổi mất các thuộc tính quan trọng. Một thuật toán khác có thể đưa ra ước lượng ban đầu gần hơn, nhưng lại chậm khi tìm tới phần tử cuối cùng; hoặc trung bình nhanh hơn nhưng hiệu năng tệ nhất quá tệ nên không dùng được
      Ngay cả với từ điển giấy, sau ước lượng đầu tiên thì bạn gần như cũng dùng tìm kiếm nhị phân. Số bước được cắt giảm nhờ ước lượng ban đầu chỉ là vài lần. Khi đã tới đúng cụm trang thì người ta lại lướt tuyến tính nhiều hơn mức cần thiết; dùng tìm kiếm nhị phân nghiêm ngặt có thể nhanh hơn, nhưng còn phải cân bằng với thời gian lật trang
    • Câu “tận dụng thêm thông tin về bài toán cụ thể sẽ hiệu quả hơn” vừa hiển nhiên vừa sâu sắc. Bạn càng có nhiều thông tin sẵn thì đúng là bạn càng có nhiều thông tin sẵn
    • Fritz Henglein đã có vài công trình thú vị về sắp xếp/nhóm nhanh. Bài báo cốt lõi có vẻ là Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
      Ed Kmett sau đó đã phát triển ý tưởng đó thành thư viện Haskell discrimination[2], và bài nói chuyện kỹ thuật liên quan[3] cũng rất thú vị
      [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
      [2]: https://hackage.haskell.org/package/discrimination
      [3]: https://www.youtube.com/watch?v=cB8DapKQz-I

  • “Tìm kiếm tứ phân” rốt cuộc chẳng phải chỉ là bung một bước của vòng lặp tìm kiếm nhị phân sao? Để tìm khoảng có chứa phần tử, số phép so sánh có vẻ xấp xỉ nhau, chỉ là trông giống như xử lý 4 nhánh một lần thay vì 2. Có vẻ bung vòng lặp cũng cho hiệu quả tương tự

    • Còn rắc rối hơn thế. Bộ xử lý hiện đại có thực thi suy đoán, nên nó sẽ đoán kết quả so sánh và tiếp tục đi sâu theo một nhánh cho tới khi biết là đoán sai hoặc chạm giới hạn nội bộ. Nếu sai, nó bỏ phần công việc suy đoán, chịu phạt vài chu kỳ rồi khởi động lại từ điểm khác
      Xét theo góc nhìn của bộ xử lý thì mọi vòng lặp thực ra đều đã được bung ở một mức nào đó, chỉ còn lại phần overhead nhỏ của bản thân vòng lặp. Trong tìm kiếm nhị phân, chi phí chính là lấy dữ liệu từ bộ nhớ hoặc cache, nên cuộc chiến thực sự là làm sao yêu cầu dữ liệu sẽ cần về sau càng sớm càng tốt để phải chờ ít hơn
      Khác biệt của thuật toán như tìm kiếm tứ phân là thay vì chỉ nạp trước thật sâu một phía của mỗi nhánh, nó prefetch nông cho mọi khả năng có thể xảy ra. Cuối cùng thì prefetch sẽ cần đến chắc chắn được phát ra, và lượng băng thông bị dùng cho dữ liệu không nằm trên đường thực thi thực tế cũng ít hơn đôi chút
      Nếu muốn dự đoán hiệu năng thực tế của thuật toán tìm kiếm thì “số phép so sánh” gần như là thước đo vô dụng. Nút thắt không phải là bạn làm được bao nhiêu phép so sánh, mà là bạn tận dụng băng thông bộ nhớ và cache tốt đến đâu. Nếu tính cả cách nhánh hoạt động bên trong CPU hiện đại thì cũng có thể xem đây là một dạng bung vòng lặp
    • Có thể xem nó là bung vòng lặp một chút. Lý do hiệu năng tốt hơn không phải vì giảm mạnh số lệnh hay số lần đọc bộ nhớ, mà vì nó nới lỏng phụ thuộc dữ liệu để tránh thực thi hoàn toàn tuần tự. Cũng có thể xem nó giống như suy đoán thực thi cả hai phía của một nhánh
    • Tìm kiếm tứ phân về cơ bản thực hiện phép so sánh của vòng lặp hiện tại đồng thời với hai phép so sánh có thể xảy ra ở vòng tiếp theo. Nó phức tạp hơn một chút so với bung vòng lặp đơn thuần
      Dù sao thì cả hai vẫn đều là O(log N) với hệ số hằng số khác nhau. Trong lớp học thuật toán, các hệ số hằng số không mấy quan trọng, nhưng ngoài đời chúng có thể tác động khá lớn
    • Đúng ở một mức độ nào đó, nhưng nó cũng loại bỏ phụ thuộc dữ liệu giữa các bước đã bung
    • Vì bộ xử lý không hoạt động theo cách ngây thơ mà ta thường tưởng tượng

  • Gần đây tôi cũng viết một bài[1] về tìm kiếm mũ[2]. Đây là thuật toán dùng khi phải lặp đi lặp lại việc tìm kiếm nhị phân trong một mảng mà chính các phần tử cần tìm cũng đã được sắp xếp, và trong workload của chúng tôi nó cho mức tăng tốc 8x
    [1] https://lalitm.com/post/exponential-search/
    [2] https://en.wikipedia.org/wiki/Exponential_search

    • Tìm kiếm mũ hữu ích với REST API đánh địa chỉ tài nguyên bằng ID tuần tự, khi bạn cần ID cuối cùng nhưng không có endpoint chuyên dụng
      HEAD /users/1 -> 200 OK
      HEAD /users/2 -> 200 OK
      HEAD /users/4 -> 200 OK
      ...
      HEAD /users/2048 -> 200 OK
      HEAD /users/4096 -> 404 Not Found
      Sau đó chỉ cần tìm kiếm nhị phân giữa 2048 và 4096 là có thể tìm ra người dùng mới nhất và tiện thể biết luôn số lượng người dùng. Đây là thông tin hữu ích nếu bạn đang nghiên cứu một công ty SaaS cạnh tranh

  • CPU luôn truy cập cả cache line, thường là 64 byte, trong một lần, nên có vẻ sẽ tốt hơn nếu tìm kiếm trên cả cache line. Khi dữ liệu đã nằm trong CPU thì gần như miễn phí
    Vì vậy tôi muốn thử cách trong tìm kiếm “nhị phân”, ta kiểm tra mọi giá trị của cache line ở giữa, nếu không có giá trị khớp thì đi sang trái/phải. Việc tìm trong cache line có thể làm bằng một lệnh SIMD 512 bit. Một cache line 64 byte tương đương 32 số nguyên 16 bit, nên có thể nhanh hơn gần 32 lần so với tìm kiếm nhị phân đơn giản, hoặc ít nhất là giảm 32 lần truy cập bộ nhớ, thứ sẽ chi phối trong hầu hết chương trình thực tế

    • Xác suất tìm thấy giá trị đích ở các cache line phía trên của cây tìm kiếm nhị phân, tức một vector đã sắp xếp, là thấp. Tốt hơn là dùng dữ liệu bổ sung trong line để thu hẹp phạm vi tìm kiếm, và như vậy sẽ dẫn đến B-tree hoặc B+ tree
      Nếu dùng khóa 4 byte và con trỏ con 4 byte, hoặc chỉ số mảng, thì một nút nội bộ có thể chứa 7 khóa, 8 con trỏ con và 1 con trỏ tiếp theo, vừa khít một cache line 64 byte. Với 1 triệu phần tử, độ sâu cây giảm từ khoảng 20 xuống khoảng 7, và vài tầng trên cùng nhiều khả năng sẽ nằm sẵn trong cache
      Nếu chịu khó thêm một chút thì có thể dùng SIMD để tăng tốc tìm kiếm bên trong nút B-tree, nhưng phụ thuộc dữ liệu rất lớn

  • Với mảng nhỏ hơn, tìm kiếm tuyến tính có giá trị sentinel ở cuối vốn đã rất khó bị đánh bại. Tuy vậy, lý do nhận định này hơi mơ hồ là vì điều kiện “nhỏ” quá mơ hồ nên khó cảm nhận

    • Điều đó không đúng. Xem benchmark rất hay trong bài này thì tìm kiếm tuyến tính bắt đầu thua ở đâu đó quanh 200~400 phần tử
      Nhìn chung tôi rất thích bài này. Nó đào rất sâu vào một câu hỏi mà tôi vẫn hay thắc mắc, lại còn kèm các thí nghiệm loại trừ rất hữu ích
    • Bài này không bàn về chuyện đó

  • Tôi từng làm vài thử nghiệm tìm kiếm trên mảng nhỏ, khoảng 16~32 phần tử, và tìm kiếm nhị phân là một trong những cách tệ nhất vì có quá nhiều nhánh. Cách nhanh nhất cho mảng nhỏ là tìm kiếm tuyến tính không nhánh
    Tức là không thoát vòng lặp giữa chừng mà quét qua toàn bộ phần tử. Ví dụ nếu muốn biết một số có trong mảng hay không thì gộp kết quả kiểm tra của mọi phần tử bằng phép OR logic. Tôi không dùng SIMD, nhưng với mảng nhỏ thì nhánh rất đắt nên cứ kiểm tra hết mọi phần tử mà không rẽ nhánh lại nhanh hơn

    • Không rõ có phải nhanh hơn vì đây là kiểu truy cập mà prefetcher thích không

  • Phần giải thích thuật toán hơi khiến tôi bối rối
    Phần SIMD chỉ được dùng ở bước cuối, tức khi tìm trong 16 phần tử cuối cùng
    Phần tìm kiếm tứ phân là kiểm tra 3 điểm để tạo ra 4 nhánh, nhưng mục tiêu là tìm đúng block chứ không chỉ đúng key
    Chi tiết này khá thú vị: tác giả dùng phần tử cuối cùng của mỗi block cho bước tìm kiếm tứ phân. Tôi tò mò không biết thuật toán sẽ thay đổi thế nào nếu dùng phần tử đầu tiên hoặc một phần tử tùy ý

  • Trực giác cốt lõi ở đây là so sánh đa điểm bằng SIMD có vẻ còn dùng được ở quy mô lớn hơn bước cuối
    Đại ý là: a) dùng gather để lấy nhiều phần tử tại 16 vị trí cách đều nhau b) so sánh song song bằng lệnh SIMD c) tập trung vào block đúng d) nếu block đủ nhỏ thì chuyển sang tìm kiếm tuyến tính, còn không thì lặp lại chu kỳ gather/so sánh
    Lệnh gather đọc từ bộ nhớ không liên tục, và với tìm kiếm nhị phân thì đúng là nó đọc nhiều hơn mức cần thiết. Dù vậy, nếu đổi lại được khả năng so sánh đa hướng và gộp 4 bước tìm kiếm nhị phân thành 1 thì có lẽ sẽ thắng trên bảng lớn
    Cũng không phải mọi kiểu dữ liệu đều hỗ trợ so sánh đủ 16 hướng. Tìm kiếm float64 ngay cả với AVX-512 cũng chỉ giới hạn ở 8 hướng, còn int32 và float32 thì có thể 16 hướng

    • gather cực kỳ chậm. Ai thực sự quan tâm đến hiệu quả sẽ tránh gather
      Tôi nghĩ tìm kiếm nhị phân thực tế nhiều khả năng còn nhanh hơn cách dựa trên gather

  • Các thuật toán khoa học máy tính cổ điển thực chất được “thiết kế” cho CPU gần như không có tính song song. Không có nhiều lõi, không có Hyper-threading, không có lệnh SIMD; mọi lần truy cập bộ nhớ đều có cùng độ trễ nên cũng không có khái niệm trễ cache L1/L2/L3; và giả định dữ liệu là tổng quát/ngẫu nhiên
    Chỉ cần rời khỏi một trong các giả định đó là đã có rất nhiều tinh chỉnh giúp tăng hiệu năng
    Các thuật toán cổ điển là điểm xuất phát rất tốt để sau đó phát triển lời giải tối ưu hơn khi ta biết thêm về dạng dữ liệu cụ thể hoặc tính chất/tính năng của CPU cụ thể
    Khi đi tới đầu nhọn của tối ưu hóa thì thường bạn sẽ nhìn vào cách dữ liệu được lưu trong bộ nhớ và được truy cập ra sao, cũng như liệu thay đổi để cải thiện chỗ này có làm hại các bước sau hay không. Ở một công ty cũ của tôi từng có người tối ưu một đoạn mã quá lâu, và kết quả là tối ưu đó làm đẩy nhiều thông tin cần cho phần sau ra khỏi cache, khiến toàn bộ ứng dụng chậm đi
    Điều này có lẽ gần với quy tắc lập trình thứ 5 của Rob Pike, tức một cách diễn đạt lại điều Fred Brooks đã nói trong The Mythical Man Month. Tham khảo: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...

  • Hồi tuổi teen, tôi từng dành cả cuối tuần nghĩ rằng nếu tìm kiếm nhị phân tốt vì mỗi bước giảm không gian tìm kiếm đi một nửa, thì tìm kiếm tam phân hẳn còn tốt hơn vì giảm xuống còn một phần ba
    Thay vì chỉ so sánh một giá trị ở giữa, ta so sánh giá trị ở mốc 1/3, và nếu còn quá thấp thì lại so sánh giá trị ở mốc 2/3
    Nhưng rồi tôi nghĩ rằng mỗi bước tuy giảm theo 1/3 thay vì 1/2 như tìm kiếm nhị phân, nhưng số phép so sánh trung bình lại là 3/2 lần, nên rốt cuộc là như nhau
    Sửa: xem câu trả lời của zamadatix thì thực ra trong 2/3 trường hợp phải so sánh 2 lần, nên trung bình là 5/3 lần

    • Cách tiếp cận tam phân này thực ra không có số phép so sánh trung bình mỗi bước là 3/2
      Phần ba đầu: 1 lần so sánh
      Phần ba thứ hai: 2 lần so sánh
      Phần ba thứ ba: 2 lần so sánh
      (1+2+2)/3 = trung bình 5/3 lần so sánh. Cảm giác “so sánh 1 hoặc 2 lần” dễ khiến người ta tưởng là 50%, nhưng thực tế xác suất dừng ở phép đầu là 1/3, còn phải so sánh 2 lần là 2/3
      Vì vậy có thể chỉ ra rằng tổng số phép so sánh trung bình khiến tìm kiếm tam phân tệ hơn một chút: 5/3*Log_3[n] = 1.052... * Log_2[n]
      Tức là số bước ít hơn, nhưng để đi hết thì trung bình lại cần nhiều phép so sánh hơn. Điều này nhìn chung đúng với mọi kiểu tìm kiếm dạng này, tức khi số nhánh phân chia lớn hơn 2. Tất nhiên còn có vài giả định như giá trị cần tìm phân bố đều và chi phí phép toán được lý tưởng hóa, và đây chính là điểm mà bài viết gốc bắt đầu đi vào
    • Hóa ra ý nghĩ thời niên thiếu đó cũng có chút cơ sở
      Chỉ là không phải dưới dạng tam phân của thuật toán tìm kiếm nhị phân. Thứ đó thực ra không phải tìm kiếm tam phân thật, mà gần giống một kiểu tìm kiếm nhị phân lệch. So sánh vốn có bản chất nhị phân, nên mọi thuật toán tìm kiếm dựa trên so sánh đều là một dạng tìm kiếm nhị phân, và việc chọn điểm không phải phần tử giữa sẽ kém hiệu quả hơn về độ phức tạp thuật toán. Tuy vậy trên phần cứng thực tế, trong một số điều kiện nào đó nó vẫn có thể tốt hơn. Để có tam phân thật sự thì phép toán cơ bản phải là so sánh 3 hướng
      Điểm trở nên thú vị là khi xét tới “hiệu quả cơ số”[1]. Lựa chọn tốt nhất là số tự nhiên gần e nhất, tức 3. Nó cũng liên quan đến tìm kiếm trên cây, nơi cây tam phân có thể tốt hơn cây nhị phân
      [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
    • Ở những nơi không thể tìm nhanh, như trên đĩa chẳng hạn, ta có thể dùng ví dụ B-tree 128 nhánh. Chi phí lấy 128 khóa không đắt hơn lấy 1 khóa bao nhiêu, nhưng đổi lại giảm được thêm 7 lần truy xuất
    • Rồi sau đó bạn có tưởng tượng ra CPU có bộ so sánh tam phân không?
    • Từ sau thời tuổi teen của bạn, CPU đã mở rộng đáng kể cả về độ rộng thực thi lẫn khả năng vector. Khi throughput tăng lên, cán cân dịch chuyển theo hướng đốt thêm phép toán để giảm chuỗi phụ thuộc
      Nên có thể ý tưởng đó không khả thi trên CPU thời ấy, nhưng lại có tiềm năng hơn trên CPU ngày nay