Chế độ tìm kiếm nhị phân XLOOKUP và XMATCH trong Delphi

HotXLS, component bảng tính Delphi và C++Builder bản địa, đánh giá XLOOKUP và XMATCH qua một lõi tra cứu dùng chung. Lõi đó chấp nhận bốn chế độ khớp (-1, 0, 1, 2) và bốn chế độ tìm kiếm (-2, -1, 1, 2), chạy một phép giảm nhị phân logarit bất cứ khi nào giá trị tuyệt đối của chế độ tìm kiếm là 2, và từ chối mọi tổ hợp khác với một lỗi công thức

Báo cáo lỗi đưa bạn đến đây không bao giờ nói "search mode". Nó nói workbook được sinh trên server hiển thị một con số khác với cùng file mở trong Excel, trên có thể bốn hàng trong chín nghìn. Bốn hàng đó luôn có điểm chung: một khóa tra cứu bị trùng lặp, hoặc một khớp gần đúng phải chọn một hàng xóm, hoặc một cột tra cứu ai đó đã sắp xếp theo một cột khác tuần trước. Hàm tra cứu là nơi một engine công thức ngừng là số học và bắt đầu là một hợp đồng, và hợp đồng đó có những điều khoản mà hầu hết bên gọi chưa bao giờ đọc

XLOOKUP thực sự chấp nhận những con số chế độ nào?

Đúng bốn cho mỗi loại, và không gì khác. HotXLS xác thực match_mode so với -1, 0, 1 và 2 và search_mode so với -2, -1, 1 và 2 trước khi nó chạm vào một ô nào, và bất kỳ giá trị nào khác trả về #VALUE! thay vì bị kẹp vào chế độ hợp lệ gần nhất. Bốn chế độ khớp là 0 cho khớp chính xác, -1 cho khớp chính xác hoặc giá trị nhỏ hơn kế tiếp, 1 cho khớp chính xác hoặc giá trị lớn hơn kế tiếp, và 2 cho wildcard; bốn chế độ tìm kiếm là 1 cho quét tuyến tính thuận, -1 cho quét tuyến tính ngược, 2 cho tìm kiếm nhị phân trên dữ liệu tăng dần, và -2 cho tìm kiếm nhị phân trên dữ liệu giảm dần. Bỏ qua chúng sẽ chọn chế độ khớp 0 và chế độ tìm kiếm 1, cặp mà hầu hết công thức thực tế dùng. Số lượng tham số cũng được kiểm soát tương tự: XLOOKUP nhận ba đến sáu tham số và XMATCH nhận hai đến bốn, và bất cứ gì ngoài các phạm vi đó là một #VALUE! trước khi việc đánh giá bắt đầu

// Shared by XLOOKUP and XMATCH, before any cell is read
if ((RequestedMatchMode <> -1) and (RequestedMatchMode <> 0) and
    (RequestedMatchMode <> 1) and (RequestedMatchMode <> 2)) or
   ((RequestedSearchMode <> -2) and (RequestedSearchMode <> -1) and
    (RequestedSearchMode <> 1) and (RequestedSearchMode <> 2)) then
begin
  Result := lxErrorValue;          // #VALUE!
  Exit;
end;

if Abs(RequestedSearchMode) = 2 then
begin
  if RequestedMatchMode = 2 then   // wildcards cannot ride a binary descent
  begin
    Result := lxErrorValue;
    Exit;
  end;
  // ... O(log n) descent over the lookup vector
end;

Một bước sớm hơn có một phép kiểm tra âm thầm hơn đáng để biết. Các tham số chế độ đến như các biểu thức worksheet, nên HotXLS ép chúng thành một số, từ chối NaN và vô cực, rồi yêu cầu số đó bằng chính giá trị đã làm tròn của nó. XLOOKUP(x, A:A, B:B, "none", 0, 1.5) là một #VALUE!, không phải một chế độ tìm kiếm 2 trá hình. Điều đó quan trọng khi chế độ đến từ một ô mà một phép tính nặng làm tròn đã tạo ra, phổ biến hơn trong các workbook được sinh tự động so với các workbook viết tay

Vì sao search_mode 2 cho ra câu trả lời sai trên dữ liệu chưa sắp xếp?

Vì nó đang làm chính xác điều bạn đã yêu cầu. Chế độ tìm kiếm 2 báo cho engine rằng vector tra cứu đã ở thứ tự tăng dần rồi, và một tìm kiếm nhị phân không thể xác minh khẳng định đó mà không cần một lượt O(n) sẽ phá hủy lý do dùng nó. Vì vậy HotXLS tin bên gọi, chia đôi khoảng, và trả về bất cứ gì phép giảm dừng lại tại đó. Trên đầu vào chưa sắp xếp, câu trả lời không phải một lỗi, nó âm thầm sai, và đây là một vi phạm hợp đồng chứ không phải một khiếm khuyết trong engine

Microsoft ghi nhận cùng sự bất đối xứng đó cho XLOOKUP và XMATCH: các chế độ nhị phân yêu cầu dữ liệu đã sắp xếp và tạo ra kết quả không hợp lệ nếu không. ISO 29500-1 mục 18.17, định nghĩa ngữ pháp công thức SpreadsheetML, mang mô tả LOOKUP và VLOOKUP cũ hơn với yêu cầu thứ tự tăng dần của riêng chúng, và XLOOKUP cùng XMATCH ra đời sau văn bản đó đủ xa để chúng di chuyển trong file dưới dạng _xlfn.XLOOKUP và _xlfn.XMATCH theo quy ước hàm tương lai. Thế hệ khác nhau, cùng một thỏa thuận: bên gọi cung cấp bất biến về thứ tự, engine cung cấp logarit

var
  Book: TXLSXWorkbook;
  Sheet: TXLSXWorksheet;
begin
  Book := TXLSXWorkbook.Create;
  try
    Sheet := Book.Sheets.Add('Rates');
    Sheet.Cells[1, 1].Value := 40;  Sheet.Cells[1, 2].Value := 0.10;
    Sheet.Cells[2, 1].Value := 10;  Sheet.Cells[2, 2].Value := 0.25;
    Sheet.Cells[3, 1].Value := 30;  Sheet.Cells[3, 2].Value := 0.15;

    // Forward linear scan: finds key 40 wherever it sits
    Sheet.Cells[5, 1].Formula := 'XLOOKUP(40,A1:A3,B1:B3,"missing",0,1)';
    // Binary ascending: the promise was broken, the key is never visited
    Sheet.Cells[6, 1].Formula := 'XLOOKUP(40,A1:A3,B1:B3,"missing",0,2)';

    Book.SaveAs('lookup-modes.xlsx');
  finally
    Book.Free;
  end;
end;

Truy vết công thức thứ hai và thất bại hoàn toàn máy móc. Phép giảm dò ô giữa, đọc 10, quyết định 10 nhỏ hơn 40, loại bỏ nửa trái bao gồm cả hàng thực sự giữ 40, dò 30, loại bỏ lần nữa, và hết khoảng. Excel hành xử y hệt, đó chính là mấu chốt: tái tạo lại câu trả lời sai là một yêu cầu tương thích, không phải một phép lịch sự. Tiền đề về thứ tự cũng nghiêm ngặt hơn "các số tăng dần", vì bộ so sánh xếp hạng giá trị theo loại trước, theo thứ tự số, rồi văn bản, rồi boolean, rồi giá trị lỗi, rồi ô trống, và chỉ so sánh trong cùng một loại sau đó. Một cột mã số phần có ba ô lưu văn bản thay vì số không phải là tăng dần theo bộ so sánh đó dù nó trông thế nào trên màn hình, và các chế độ nhị phân sẽ vui vẻ đọc sai nó

Khóa trùng lặp rơi vào đâu?

Vào một đầu xác định của dãy trùng lặp, và đầu nào phụ thuộc vào chế độ tìm kiếm chứ không phải may rủi. Khi phép giảm nhị phân gặp một khóa bằng nhau dưới chế độ tìm kiếm 2, nó ghi lại vị trí rồi tiếp tục thu hẹp về bên trái, nên kết quả là chỉ số thấp nhất của dãy; dưới chế độ tìm kiếm -2, trên dữ liệu giảm dần, nó ghi lại vị trí và thu hẹp về bên phải, nên kết quả là chỉ số cao nhất. Các chế độ tuyến tính đơn giản hơn: chế độ tìm kiếm 1 trả về lần khớp đầu tiên đi thuận, chế độ tìm kiếm -1 lần khớp đầu tiên đi ngược. Đây là chi tiết tạo ra sự khác biệt bốn hàng ở đoạn mở đầu, vì một workbook mà khóa của nó là duy nhất cho ra câu trả lời giống hệt nhau dưới cả bốn chế độ tìm kiếm và che giấu sự khác biệt qua mọi test bạn từng viết từ một file mẫu sạch. Thêm một mã khách hàng trùng lặp vào dữ liệu sản xuất và các chế độ bắt đầu bất đồng đúng ở những hàng đã trùng lặp: không gì thay đổi trong engine, đầu vào chỉ đơn giản là ngừng là một tập hợp và trở thành một đa tập hợp

// A1:A7 holds 1, 3, 5, 5, 5, 7, 9 - ascending, with a run of three
Sheet.Cells[1, 3].Formula := 'XMATCH(5,A1:A7,0,1)';   // 3, first forward hit
Sheet.Cells[2, 3].Formula := 'XMATCH(5,A1:A7,0,-1)';  // 5, first reverse hit
Sheet.Cells[3, 3].Formula := 'XMATCH(5,A1:A7,0,2)';   // 3, lowest index of the run

// B1:B7 holds 9, 7, 5, 5, 5, 3, 1 - descending
Sheet.Cells[4, 3].Formula := 'XMATCH(5,B1:B7,0,-2)';  // 5, highest index of the run

Khớp gần đúng chọn ứng viên á quân như thế nào?

Bằng cách giữ một ứng viên tốt nhất song song với việc tìm kiếm khớp chính xác và chỉ trả về nó nếu không có khớp chính xác nào xuất hiện. HotXLS coi match_mode -1 là "giá trị lớn nhất không lớn hơn mục tiêu" và match_mode 1 là "giá trị nhỏ nhất không nhỏ hơn", và cả hai được giải quyết trên toàn bộ vùng đã quét thay vì dừng lại ở hàng xóm chấp nhận được đầu tiên. Trên đường nhị phân, cùng ý tưởng đó rơi ra miễn phí từ phép giảm: mỗi bước vượt quá hoặc chưa tới đều cập nhật ứng viên, nên ứng viên cuối cùng là phần tử biên kế bên vị trí mà khóa lẽ ra đã được chèn vào

// Linear path: refine the candidate only on a strict improvement
if (RequestedMatchMode = -1) or (RequestedMatchMode = 1) then
begin
  CompareResult := CompareDynamicValues(CurrentValue, RequestedValue);
  if ((RequestedMatchMode = -1) and (CompareResult <= 0) and
      ((CandidateIndex < 0) or
       (CompareDynamicValues(CurrentValue, CandidateValue) > 0))) or
     ((RequestedMatchMode = 1) and (CompareResult >= 0) and
      ((CandidateIndex < 0) or
       (CompareDynamicValues(CurrentValue, CandidateValue) < 0))) then
  begin
    CandidateIndex := ScanIndex;
    CandidateValue := CurrentValue;
  end;
end;

Đọc kỹ điều kiện bên trong, vì phần phá vỡ hòa nằm ở đó. Một ô mới chỉ thay thế ứng viên đang giữ khi nó tốt hơn một cách nghiêm ngặt, không bao giờ khi nó chỉ đơn thuần bằng nhau, nên trong số nhiều ô giữ cùng một giá trị á quân, ô được giữ lại là ô gặp đầu tiên theo thứ tự quét: chỉ số thấp nhất dưới quét thuận, cao nhất dưới quét ngược. Nếu XLOOKUP và XMATCH không tìm thấy cả khớp chính xác lẫn hàng xóm chấp nhận được, XLOOKUP rơi về tham số if_not_found của nó khi có cung cấp và về #N/A khi không có, còn XMATCH luôn cho ra #N/A

Vì sao wildcard và tìm kiếm nhị phân không thể cùng tồn tại

Vì một mẫu wildcard không phải một vị trí trong một thứ tự. Chế độ khớp 2 hỏi liệu một ô có khớp với một mặt nạ hay không, và việc khớp mặt nạ trả lời có hoặc không; một phép giảm nhị phân cần một câu trả lời ba chiều cho nó biết nên giữ nửa nào. Không có cách nào biện minh được để hỏi liệu ACME-* nằm bên trái hay bên phải một ô cho trước, nên HotXLS từ chối match_mode 2 kết hợp với search_mode 2 hoặc -2 ngay từ đầu với #VALUE! thay vì đoán một thứ tự và tạo ra thứ vô nghĩa trông có vẻ hợp lý. Hai đường đi cũng so sánh giá trị khác nhau, điều này củng cố sự tách biệt: quét tuyến tính quyết định sự bằng nhau bằng một phép so sánh văn bản không phân biệt hoa thường, hoặc bằng khớp mặt nạ khi wildcard được bật, trong khi phép giảm nhị phân quyết định sự bằng nhau bằng cách hỏi bộ so sánh thứ tự trả về không. Đó là có chủ đích chứ không phải một tai nạn của việc phân lớp, vì đường nhị phân chỉ được dùng quan hệ mà nó thực sự đang định vị theo. Nếu bạn cần wildcard, hãy dùng chế độ tìm kiếm 1 hoặc -1 và chấp nhận chi phí tuyến tính, đó chính là sự đánh đổi mà việc theo dõi phụ thuộc đứng sau tính toán lại gia tăng được thiết kế để giữ ngoài đường tới hạn của bạn

Lỗi hình dạng: range hai chiều và vector trả về không khớp

Cả hai hàm đều yêu cầu một range tra cứu thực sự một chiều. Nếu range được cung cấp trải trên nhiều hơn một hàng và nhiều hơn một cột cùng lúc, HotXLS trả về #VALUE! thay vì tự chọn một trục thay bạn, và một range một hàng hoặc một cột được đọc theo trục dài của nó. XLOOKUP thêm một quy tắc hình dạng thứ hai: range trả về phải dài đúng bằng range tra cứu dọc theo trục khớp, nên một tra cứu dọc trên 500 hàng ghép với một range trả về 499 hàng là một lỗi, không phải một sai lệch một-đơn-vị được âm thầm giải quyết ở hàng cuối. Khi range trả về rộng hơn một cột cho một tra cứu dọc, hoặc cao hơn một hàng cho một tra cứu ngang, XLOOKUP trả lại toàn bộ lát đã khớp như một mảng và nó tràn vào các ô lân cận theo cùng quy tắc như các hàm mảng động khác, được mô tả trong bài về range tràn và mảng động. Điều đó thực sự hữu ích để kéo cả một bản ghi ra khỏi một bảng bằng một công thức, và cũng là cách nhanh nhất để ghi đè một cột bạn định giữ lại

Chọn một chế độ khi không có ai đang nhìn màn hình

Việc sinh phía server xứng đáng một chính sách nghiêm ngặt hơn so với dùng tương tác, vì không có con người nào để nhận ra một tổng trông có vẻ sai. Mặc định biện minh được là chế độ tìm kiếm 1 với chế độ khớp 0: tuyến tính, chính xác, không phụ thuộc thứ tự, và không thể vô hiệu hóa bằng cách sắp xếp lại một sheet. Chỉ dùng chế độ tìm kiếm 2 khi cùng một đường code cũng đã tạo ra thứ tự đó, trong cùng một lượt chạy, trên cùng một cột, và ghi lại sự phụ thuộc đó kế bên công thức, vì một tìm kiếm nhị phân trên một cột được sắp xếp theo một khóa khác là cách rẻ nhất có thể để tính ra một con số sai đầy tự tin. Khi việc tra cứu thực sự nóng và dữ liệu thực sự đã sắp xếp, phần thưởng là thật: phép giảm đọc theo bậc log n ô thay vì n, và mỗi lần đọc trong số đó đi qua một lần phân giải ô workbook đầy đủ, nên phần tiết kiệm lớn hơn số lượng chỉ thị gợi ý

Nếu hình dạng của vấn đề gần với một quy tắc miền hơn là một tra cứu, một callback vào code Pascal của riêng bạn, như được trình bày trong bài về hàm worksheet tùy chỉnh, thường sẽ vượt trội hơn bất kỳ sự sắp xếp khéo léo nào của các hàm dựng sẵn. Các triển khai XLOOKUP và XMATCH được thảo luận ở đây đi kèm trong component bảng tính Delphi HotXLS tiêu chuẩn, trang sản phẩm của nó mang tài liệu tham chiếu hàm được hỗ trợ đầy đủ cho Delphi và C++Builder