Trong bài viết này, mình sẽ nói về tìm kiếm xấp xỉ. Hiểu được cách Excel thực hiện việc tìm kiếm này, các bạn sẽ biết thêm cách để tối ưu hóa tốc độ file.

Khi sử dụng Excel, ta đã quá quen thuộc với những hàm tìm kiếm như VLOOKUP, HLOOKUP, INDEX/MATCH. Mới hơn nữa ta có XLOOKUP, XMATCH. Lâu đời hơn cả là LOOKUP. Các bạn có để ý rằng trong những hàm này đều có một tham số tùy chọn giữa “Exact” - Tìm chính xác và “Approximate” - Tìm xấp xỉ không?

Giới thiệu về tìm kiếm với hàm MATCH

Chúng ta sẽ đến với một hàm rất quen thuộc: MATCH.

=MATCH(lookup_value,lookup_array,[match_type])

MATCH sẽ trả về vị trí của một giá trị trong một mảng. Chẳng hạn ta có mảng:

["a","c","b","z","e","f","g"]

Ở đây, khi nhập hàm MATCH để tìm kiếm “b”, ta sẽ viết:

=MATCH("b",mảng_trên,0)

Kết quả trả về là 2, vì phần tử “b” ở vị trí thứ 2 từ trái sang.

Tại sao match_type bắt buộc lại là 0? Bởi vì theo như tài liệu của Microsoft cũng như theo “kinh nghiệm dân gian”, nếu bỏ trống hoặc điền 1/-1 thì kết quả trả về sẽ sai hoặc lỗi.

Giờ hãy đến với ví dụ tiếp theo.

Một ví dụ khác, ta có mảng:

[5,10,15,20,25,30]

Khi thực hiện tìm kiếm số 15 với MATCH, ta hoàn toàn có thể viết:

=MATCH(15,mảng_trên,0)

hoặc

=MATCH(15,mảng_trên)

hoặc

=MATCH(15,mảng_trên,1)

Cả 3 công thức trên đều trả về kết quả 3, chính là vị trí của số 15 trong mảng. Vậy tại sao trong trường hợp này lại có thể dùng match_type = 1?

Chúng ta đã biết rằng nếu để mặc định thì match_type sẽ được ngầm hiểu là 1, và theo như tài liệu của Microsoft, nếu tiến hành tìm kiếm “xấp xỉ” với tham số 1, mảng cần phải được sắp xếp theo thứ tự.

Quả vậy, nếu mảng của ta đổi thành [10,5,30,25,20,15] hoặc sắp xếp theo một thứ tự khác, thì tìm kiếm xấp xỉ sẽ bị sai.

Vì sao khi tìm kiếm xấp xỉ, ta cần phải sắp xếp dữ liệu từ nhỏ tới lớn hoặc từ lớn tới nhỏ?

Mình đã đi hỏi những người “trong ngành” và biết được một điều rằng, việc chọn match_type (cũng như lookup_type) giống như trigger một cái công tắc về lựa chọn thuật toán tìm kiếm.

Với type = 0, Excel sẽ sử dụng Linear Search.

Với type = 1, Excel sẽ sử dụng Binary Search.

Với các hàm như MATCH, XLOOKUP, XMATCH, ta có thêm tùy chọn -1, cũng vẫn là Binary Search với mảng được xếp ngược lại.

Các bạn có thể google 2 từ khóa trên để hiểu.

Và chính vì Binary Search chỉ hoạt động đúng khi mảng được sắp xếp từ nhỏ tới lớn, nên trong các tài liệu của Excel luôn yêu cầu ta phải sắp xếp như vậy để kết quả không sai.

Cách mà Binary search hoạt động trong Excel

Trước hết, mình sẽ đặt một câu hỏi cho các bạn. Liệu với một mảng không được sắp xếp, ta có biết được kết quả trả về sẽ “sai” như thế nào không?

Một mảng ví dụ cho các bạn:

[10,5,30,25,20,15]

Yêu cầu là ta cần tìm vị trí “sai” của số 15 với hàm =MATCH(15,mảng_trên,1)

Đáp án ở đây là 2, và tại sao lại như vậy? Các bạn hãy nhớ nguyên tắc của Binary Search nhé.

Các bước cụ thể:

Đầu tiên, Excel sẽ đánh số thứ tự các phần tử trong mảng

Và bởi Binary Search sẽ bắt đầu với vị trí ở giữa hoặc làm tròn xuống, ta có vị trí bắt đầu là vị trí số 3. Tại đây, Excel sẽ chèn giá trị tìm kiếm vào ngay sau vị trí tìm kiếm:

Bởi 15 < 30, Binary Search sẽ tiếp tục ở bên mảng trái. Và bởi (2+1)/2 làm tròn xuống = 1, giá trị được so sánh sẽ nằm ở vị trí thứ nhất, giá trị tìm kiếm đặt ở sau.

Bởi 10 < 15, nên Binary Search sẽ tìm về bên phải. Lúc này giá trị tìm kiếm sẽ di chuyển sang bên phải. Lúc này ta chỉ còn 1 cột ở vị trí 2:

Bởi 5 < 15 và không còn nơi nào để di chuyển, giá trị trả về sẽ là 2.

Trong trường hợp ta thay 5 tại vị trí 2 bằng một số bất kỳ lớn hơn 15, chẳng hạn 100, kết quả trả về sẽ là 1. Bởi khi đó, 10 sẽ là số nhỏ hơn gần nhất với 15.

Áp dụng vào trong Excel, giờ mình có một ảnh như này, các bạn đã hiểu tại sao kết quả của hàm MATCH lại trả về như vậy chưa nào?

Tại sao tìm kiếm lại trả về giá trị cuối cùng?

Các bạn có biết ứng dụng kinh điển này của hàm LOOKUP không?

=LOOKUP(2,1/(điều kiện), mảng kết quả)

Hồi trước, ta sẽ hiểu đơn giản là hàm này sẽ lấy giá trị ở vị trí cuối cùng, so sang mảng kết quả rồi trả về giá trị tương ứng. Còn giờ hãy đào sâu hơn với câu hỏi, tại sao lại là giá trị cuối?

Hãy bắt đầu với 1/(điều kiện). Kết quả ở đây sẽ trả về một mảng bao gồm 2 giá trị: #DIV/0! và 1. Ví dụ:

{1;1;1;1;#DIV/0!;1;1;#DIV/0!;1}

Khi đưa vào hàm LOOKUP, ta sẽ viết lại công thức như sau:

=LOOKUP(2,{1;1;1;1;#DIV/0!;1;1;#DIV/0!;1},mảng kết quả)

Trước khi đọc tiếp, có một điều mình sẽ nói mà bỏ qua bước chứng minh: LOOKUP (và các hàm tìm kiếm sử dụng xấp xỉ) sẽ bỏ qua lỗi. Các bạn có thể tìm hiểu thông tin này trên các diễn đàn Excel, hoặc tự test xem nhé.

Vậy thì công thức trên sẽ được viết lại:

=LOOKUP(2,{1;1;1;1;1;1;1},mảng kết quả rút gọn theo)

hoặc

=LOOKUP(2,{1;1;1;1;<bỏ qua>;1;1;<bỏ qua>;1},mảng kết quả)

hoặc một logic nào đó khác

Tại sao lại “hoặc”? Bởi vì mình không biết cụ thể Microsoft thiết kế theo đường nào. Có rất nhiều cách để đạt được kết quả. Tuy vậy, nhìn chung chúng ta chỉ cần xử lý mảng bao gồm toàn số 1. Và bởi giá trị LOOKUP của chúng ta là 2, Binary Search sẽ liên tục duyệt tìm về nửa phải cho đến cuối và trả về giá trị ở vị trí cuối cùng. Các bạn có thể xem ảnh minh họa sau:

Nếu chúng ta tìm một số khác thì sao? – Miễn là số lớn hơn 1, ta sẽ luôn lấy được giá trị cuối cùng.

Vậy là, các bạn đã hiểu nguyên lý hoạt động case kinh điển với hàm LOOKUP trên rồi đúng không?

Tuy nhiên, có một điều rất thú vị ở đây, đó là với lookup_value = 1, hàm LOOKUP vẫn trả về vị trí cuối cùng.

Cách xử lý nếu kết quả tìm kiếm trong mảng khớp với nhiều giá trị trùng lặp?

Tiếp tục với bài toán trên. Bây giờ, ta sẽ viết lại logic công thức:

=LOOKUP(1,{1;1;1;1;1;1;1},mảng tương ứng)

Hoặc, để dễ minh họa hơn, ta sẽ dùng MATCH trong trường hợp này:

=MATCH(1,{1;1;1;1;1;1;1},1)

Bạn nghĩ kết quả của hàm MATCH trên có phải là 4 (vị trí ở giữa theo quy tắc của Binary Search) không?

Câu trả lời là Không. Kết quả là 7, vị trí cuối cùng.

Tại sao lại là cuối cùng? Có phải nó rất mâu thuẫn với Binary Search?

Để làm rõ hơn, giờ ta sẽ có 1 mảng như này:

[1,1,1,1,1,0,1]

Khi thực hiện tìm kiếm với Binary Search, kết quả trả về là 5 (ngay bên trái số 0) thay vì 7 là giá trị cuối cùng. Bây giờ, thay vị trí trung tâm của mảng thành 2:

[1,1,1,2,1,0,1]

Kết quả trả về là 3, nằm ngay bên trái số 2.

Và khi thay vị trí trung tâm của mảng thành 0:

[1,1,1,0,1,0,1]

Kết quả là 7, vị trí cuối cùng.

Tại sao lại như vậy? Dưới đây sẽ là kết luận:

Mình đã đi hỏi rất nhiều bên, cả những moderator của Excel community cũng nói rằng phải xem xét vấn đề này vì nó thực sự không dễ để vừa trả lời vừa giữ bí mật về cách viết hàm. Tuy nhiên thì mình cũng có một assumption khá chính xác như sau:

Khi giá trị được tìm thấy trong mảng, công thức sẽ không dừng lại và trả ngay ra giá trị đó. Bởi mảng được sắp xếp sẽ có 1 tính chất đó là các giá trị trùng lặp nhau chắc chắn sẽ nằm cạnh nhau, nên công thức sẽ tiếp tục duyệt về bên phải để tìm các giá trị trùng lặp khác. Khi gặp một giá trị khác với giá trị đã tìm được, khi đó công thức sẽ trả về giá trị nằm gần nhất về bên trái.

Hình ảnh minh họa như sau:

Và đó là cách tìm kiếm xấp xỉ hoạt động. Các bạn đã rõ hơn chưa nào?

Tối ưu hóa tốc độ

Quên mất, còn lời khuyên. Mình có một số thứ rút ra như sau:

1. Bởi Binary Search là thuật toán tìm kiếm nhanh hơn Linear Search, nên nếu dữ liệu của bạn có thể sắp xếp được và bạn kiểm soát được việc đó, hãy tìm kiếm xấp xỉ để đạt được tốc độ cao. Còn nếu bạn không thể kiểm soát được, hãy tiếp tục tìm kiếm chính xác (và có thể là cả nâng cấp phần cứng máy tính).
2. Mình từng thấy một số bên sử dụng LOOKUP(1,1/…) thay vì LOOKUP(2,1/…). Lời khuyên của mình là dù cả hai cùng trả về kết quả ở vị trí cuối, hãy chọn phương án thứ hai, bởi vì trong 1 set dữ liệu lớn thì phương án 2 sẽ nhanh hơn phương án 1 đấy. Tại sao? Các bạn thử coi mỗi lần lặp là 1s, cho 1 triệu dòng dữ liệu, tính xem 2 phương án sẽ trả kết quả lần lượt trong bao nhiêu giây nào?