โหมด Binary Search ของ XLOOKUP กับ XMATCH ใน Delphi

HotXLS spreadsheet component เนทีฟสำหรับ Delphi และ C++Builder ประเมิน XLOOKUP และ XMATCH ผ่าน lookup core เดียวที่ใช้ร่วมกัน core นั้นรับโหมด match สี่แบบ (-1, 0, 1, 2) และโหมด search สี่แบบ (-2, -1, 1, 2) รันการเดินแบบ binary logarithmic ทุกครั้งที่โหมด search แบบสัมบูรณ์เป็น 2 และปฏิเสธทุกชุดผสมอื่นด้วย formula error

รายงานบั๊กที่ทำให้คุณมาอ่านตรงนี้ไม่เคยพูดว่า "search mode" มันบอกว่า workbook ที่เซิร์ฟเวอร์สร้างขึ้นแสดงตัวเลขต่างจากไฟล์เดียวกันที่เปิดใน Excel ในราวสี่แถวจากเก้าพันแถว สี่แถวนั้นมักมีจุดร่วมบางอย่างเสมอ คือ lookup key ที่ซ้ำกัน หรือ approximate match ที่ต้องเลือกเพื่อนบ้าน หรือคอลัมน์ lookup ที่มีใครเรียงลำดับด้วยคอลัมน์อื่นเมื่อสัปดาห์ที่แล้ว ฟังก์ชัน lookup คือจุดที่ formula engine หยุดเป็นแค่เลขคณิตและเริ่มเป็นสัญญา และสัญญานั้นมีข้อกำหนดที่คนเรียกใช้ส่วนใหญ่ไม่เคยอ่าน

XLOOKUP ยอมรับตัวเลขโหมดอะไรบ้างจริง ๆ

เจาะจงสี่ตัวของแต่ละอย่าง ไม่มีอื่นเลย HotXLS ตรวจสอบ match_mode เทียบกับ -1, 0, 1 และ 2 และ search_mode เทียบกับ -2, -1, 1 และ 2 ก่อนแตะเซลล์แม้แต่ตัวเดียว และค่าอื่นใดจะคืน #VALUE! แทนที่จะถูกบีบให้เข้าโหมดที่ถูกต้องใกล้เคียงที่สุด โหมด match ทั้งสี่คือ 0 สำหรับตรงเป๊ะ, -1 สำหรับตรงเป๊ะหรือค่าเล็กกว่าถัดไป, 1 สำหรับตรงเป๊ะหรือค่าใหญ่กว่าถัดไป และ 2 สำหรับ wildcard โหมด search ทั้งสี่คือ 1 สำหรับการสแกนเชิงเส้นไปข้างหน้า, -1 สำหรับการสแกนเชิงเส้นย้อนกลับ, 2 สำหรับ binary search เหนือข้อมูลเรียงขึ้น และ -2 สำหรับ binary search เหนือข้อมูลเรียงลง การไม่ระบุจะเลือกโหมด match 0 และโหมด search 1 ซึ่งเป็นคู่ที่สูตรจริงเกือบทุกตัวใช้ จำนวนอาร์กิวเมนต์ถูกควบคุมแบบเดียวกัน XLOOKUP รับสามถึงหกอาร์กิวเมนต์ และ XMATCH รับสองถึงสี่ และค่านอกช่วงเหล่านั้นคือ #VALUE! ก่อนการประเมินจะเริ่มด้วยซ้ำ

// 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;

มีการตรวจสอบที่เงียบกว่าอีกขั้นก่อนหน้านั้นที่ควรรู้ไว้ อาร์กิวเมนต์โหมดมาถึงในรูปแบบสูตร worksheet ดังนั้น HotXLS จะแปลงให้เป็นตัวเลข ปฏิเสธ NaN และ infinity แล้วเรียกร้องให้ตัวเลขนั้นเท่ากับค่าที่ปัดกลมของตัวมันเอง XLOOKUP(x, A:A, B:B, "none", 0, 1.5) คือ #VALUE! ไม่ใช่ search mode 2 แบบปลอมตัว เรื่องนี้สำคัญเมื่อโหมดมาจากเซลล์ที่การคำนวณหนักเรื่องการปัดเศษสร้างขึ้น ซึ่งพบได้บ่อยใน workbook ที่สร้างขึ้นอัตโนมัติมากกว่าที่เขียนด้วยมือ

ทำไม search_mode 2 ให้คำตอบผิดกับข้อมูลที่ไม่ได้เรียงลำดับ

เพราะมันทำตามสิ่งที่คุณขอเป๊ะ ๆ search mode 2 บอก engine ว่า lookup vector เรียงลำดับขึ้นอยู่แล้ว และ binary search ไม่สามารถตรวจสอบข้อกล่าวอ้างนั้นได้โดยไม่ผ่าน O(n) ที่จะทำลายเหตุผลของการใช้มันตั้งแต่แรก ดังนั้น HotXLS จึงเชื่อผู้เรียก แบ่งครึ่งช่วง แล้วคืนสิ่งที่การเดินไปตกลง บนข้อมูลที่ไม่ได้เรียงลำดับ คำตอบไม่ใช่ error มันผิดอย่างเงียบ ๆ และนี่คือการละเมิดสัญญามากกว่าจะเป็นข้อบกพร่องใน engine

Microsoft บันทึกความไม่สมมาตรแบบเดียวกันไว้สำหรับ XLOOKUP และ XMATCH โหมด binary ต้องการข้อมูลที่เรียงลำดับแล้วและให้ผลลัพธ์ที่ไม่ถูกต้องหากไม่เป็นเช่นนั้น ISO 29500-1 ข้อ 18.17 ซึ่งกำหนดไวยากรณ์สูตร SpreadsheetML พก คำอธิบาย LOOKUP และ VLOOKUP รุ่นเก่าพร้อมข้อกำหนดการเรียงลำดับขึ้นของตัวเอง และ XLOOKUP กับ XMATCH เกิดขึ้นทีหลังข้อความนั้นไกลพอที่จะเดินทางในไฟล์เป็น _xlfn.XLOOKUP และ _xlfn.XMATCH ภายใต้ convention future-function รุ่นต่างกัน แต่ข้อตกลงเดียวกัน ผู้เรียกจัดหา invariant ของการเรียงลำดับ engine จัดหาลอการิทึม

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;

ไล่ตามสูตรที่สองแล้วความล้มเหลวคือกลไกล้วน ๆ การเดินตรวจสอบเซลล์กึ่งกลาง อ่านค่า 10 ตัดสินว่า 10 น้อยกว่า 40 ทิ้งครึ่งซ้ายรวมถึงแถวที่มี 40 อยู่จริง ตรวจสอบ 30 ทิ้งอีกครั้ง แล้วช่วงก็หมด Excel ทำงานแบบเดียวกัน ซึ่งเป็นประเด็นสำคัญ การสร้างคำตอบผิดซ้ำเป็นข้อกำหนดความเข้ากันได้ ไม่ใช่มารยาท ข้อกำหนดการเรียงลำดับยังเข้มงวดกว่า "ตัวเลขเรียงขึ้น" เพราะตัวเปรียบเทียบจัดอันดับค่าตามประเภทก่อน ตามลำดับ ตัวเลข แล้วข้อความ แล้ว boolean แล้ว error value แล้วค่าว่าง และเปรียบเทียบภายในประเภทเดียวกันหลังจากนั้นเท่านั้น คอลัมน์รหัสชิ้นส่วนแบบตัวเลขที่มีสามเซลล์เก็บข้อความแทนไม่ใช่การเรียงขึ้นภายใต้ตัวเปรียบเทียบนั้น ไม่ว่ามันจะดูเรียงลำดับบนหน้าจอแค่ไหนก็ตาม และโหมด binary จะอ่านมันผิดอย่างยินดี

Duplicate key ไปตกที่ไหน

ที่ปลายด้านหนึ่งของ duplicate run ที่กำหนดแน่นอน และปลายไหนขึ้นอยู่กับ search mode ไม่ใช่โชค เมื่อการเดินแบบ binary เจอ key ที่เท่ากันภายใต้ search mode 2 มันจะบันทึกตำแหน่งแล้วยังคงแคบเข้าไปทางซ้าย ดังนั้นผลลัพธ์คือดัชนีต่ำสุดของ run ภายใต้ search mode -2 บนข้อมูลเรียงลง มันบันทึกตำแหน่งแล้วแคบเข้าไปทางขวา ดังนั้นผลลัพธ์คือดัชนีสูงสุด โหมดเชิงเส้นง่ายกว่านั้น search mode 1 คืนการชนครั้งแรกที่เจอไปข้างหน้า search mode -1 คือการชนครั้งแรกที่เจอย้อนกลับ นี่คือรายละเอียดที่สร้างความคลาดเคลื่อนสี่แถวจากย่อหน้าเปิดบทความ เพราะ workbook ที่ key ของมันไม่ซ้ำกันเลยจะให้คำตอบเหมือนกันทุกโหมด search และซ่อนความต่างไว้ผ่านทุกการทดสอบที่คุณเขียนจากไฟล์ตัวอย่างสะอาด เพิ่มรหัสลูกค้าที่ซ้ำกันหนึ่งตัวเข้าไปในข้อมูลจริงแล้วโหมดต่าง ๆ จะเริ่มไม่ตรงกันเป๊ะ ๆ ที่แถวที่ซ้ำ ไม่มีอะไรเปลี่ยนใน engine เลย ข้อมูลนำเข้าแค่หยุดเป็นเซตและกลายเป็น multiset

// 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

Approximate match เลือกตัวรองอย่างไร

ด้วยการเก็บตัวเลือกที่ดีที่สุดควบคู่ไปกับการค้นหาแบบ exact-match และคืนมันก็ต่อเมื่อไม่มีการชนแบบเป๊ะปรากฏขึ้น HotXLS ถือว่า match_mode -1 คือ "ค่าที่ใหญ่ที่สุดที่ไม่เกินเป้าหมาย" และ match_mode 1 คือ "ค่าที่เล็กที่สุดที่ไม่เล็กกว่า" และทั้งสองถูกคำนวณเหนือพื้นที่ที่สแกนทั้งหมด ไม่ใช่หยุดที่เพื่อนบ้านที่ยอมรับได้ตัวแรก ในเส้นทาง binary แนวคิดเดียวกันตกออกมาจากการเดินโดยอัตโนมัติ ทุกขั้นตอนที่เกินหรือขาดจะอัปเดตตัวเลือก ดังนั้นตัวเลือกสุดท้ายคือ element ขอบเขตที่อยู่ติดกับตำแหน่งที่ key ควรถูกแทรก

// 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;

อ่านเงื่อนไขด้านในให้ละเอียด เพราะการตัดสิน tie อยู่ตรงนั้น เซลล์ใหม่จะแทนที่ตัวเลือกปัจจุบันก็ต่อเมื่อมันดีกว่าอย่างเคร่งครัดเท่านั้น ไม่เคยแทนที่เมื่อแค่เท่ากัน ดังนั้นในบรรดาหลายเซลล์ที่มีค่าตัวรองเดียวกัน ตัวที่ถูกเก็บไว้คือตัวแรกที่เจอในลำดับการสแกน คือดัชนีต่ำสุดในการสแกนไปข้างหน้า ดัชนีสูงสุดในการสแกนย้อนกลับ ถ้า XLOOKUP และ XMATCH ไม่พบทั้งการชนแบบเป๊ะและเพื่อนบ้านที่ยอมรับได้ XLOOKUP จะถอยกลับไปใช้อาร์กิวเมนต์ if_not_found ของมันเมื่อมีการระบุไว้ และไปที่ #N/A เมื่อไม่มี ในขณะที่ XMATCH ให้ #N/A เสมอ

ทำไม wildcard กับ binary search ถึงอยู่ร่วมกันไม่ได้

เพราะรูปแบบ wildcard ไม่ใช่ตำแหน่งในลำดับ Match mode 2 ถามว่าเซลล์ตรงกับ mask หรือไม่ และการจับคู่ mask ตอบแค่ใช่หรือไม่ใช่ การเดินแบบ binary ต้องการคำตอบสามทางที่บอกได้ว่าควรเก็บครึ่งไหน ไม่มีวิธีที่สมเหตุสมผลในการถามว่า ACME-* อยู่ทางซ้ายหรือขวาของเซลล์ที่กำหนด ดังนั้น HotXLS จึงปฏิเสธ match_mode 2 ที่ผสมกับ search_mode 2 หรือ -2 ตั้งแต่ต้นด้วย #VALUE! แทนที่จะเดาการเรียงลำดับแล้วสร้างเรื่องไร้สาระที่ดูสมเหตุสมผล ทั้งสองเส้นทางยังเปรียบเทียบค่าต่างกันด้วย ซึ่งเสริมการแยกนั้นให้ชัดขึ้น การสแกนเชิงเส้นตัดสินความเท่ากันด้วยการเปรียบเทียบข้อความแบบไม่สนตัวพิมพ์เล็กใหญ่ หรือด้วยการจับคู่ mask เมื่อเปิด wildcard ในขณะที่การเดินแบบ binary ตัดสินความเท่ากันด้วยการถามตัวเปรียบเทียบลำดับหาค่าศูนย์ นั่นตั้งใจ ไม่ใช่อุบัติเหตุของการวางชั้น เพราะเส้นทาง binary อาจใช้แค่ความสัมพันธ์ที่มันกำลังนำทางอยู่จริง ๆ เท่านั้น ถ้าคุณต้องการ wildcard ให้ใช้ search mode 1 หรือ -1 และยอมรับต้นทุนเชิงเส้น ซึ่งเป็นการแลกเปลี่ยนแบบเดียวกับที่การติดตาม dependency เบื้องหลัง การคำนวณใหม่แบบ incremental ถูกออกแบบมาเพื่อกันออกจาก critical path ของคุณ

Error รูปทรง: ช่วงสองมิติและ return vector ที่ไม่ตรงกัน

ทั้งสองฟังก์ชันต้องการช่วง lookup ที่เป็นมิติเดียวจริง ๆ ถ้าช่วงที่ระบุครอบคลุมมากกว่าหนึ่งแถวและมากกว่าหนึ่งคอลัมน์พร้อมกัน HotXLS จะคืน #VALUE! แทนที่จะเลือกแกนให้คุณเอง และช่วงแถวเดียวหรือคอลัมน์เดียวจะถูกอ่านตามแกนยาวของมัน XLOOKUP เพิ่มกฎรูปทรงข้อที่สอง ช่วง return ต้องยาวเท่ากับช่วง lookup ตามแกนที่ match เป๊ะ ดังนั้น lookup แนวตั้ง 500 แถวคู่กับช่วง return 499 แถวคือ error ไม่ใช่การขาดหนึ่งที่ถูกแก้อย่างเงียบ ๆ ที่แถวสุดท้าย เมื่อช่วง return กว้างกว่าหนึ่งคอลัมน์สำหรับ lookup แนวตั้ง หรือสูงกว่าหนึ่งแถวสำหรับแนวนอน XLOOKUP จะส่งคืนชิ้นที่ match ทั้งหมดเป็น array และมันจะ spill เข้าไปในเซลล์ข้างเคียงภายใต้กฎเดียวกับฟังก์ชัน dynamic array อื่น ๆ อธิบายไว้ในบทความเรื่อง spill range และ dynamic array นั่นมีประโยชน์จริงสำหรับการดึง record ทั้งตัวออกจากตารางด้วยสูตรเดียว และมันก็เป็นวิธีเร็วที่สุดในการเขียนทับคอลัมน์ที่คุณตั้งใจจะเก็บไว้ด้วย

การเลือกโหมดเมื่อไม่มีใครดูหน้าจอ

การสร้างข้อมูลฝั่งเซิร์ฟเวอร์ควรมีนโยบายที่เข้มงวดกว่าการใช้งานแบบโต้ตอบ เพราะไม่มีมนุษย์คอยสังเกตว่ายอดรวมดูผิด ค่าเริ่มต้นที่ปลอดภัยคือ search mode 1 กับ match mode 0 คือแบบเชิงเส้น ตรงเป๊ะ ไม่ขึ้นกับลำดับ และไม่มีทางทำให้เสียหายด้วยการเรียงลำดับ sheet ใหม่ เอื้อมมือไปใช้ search mode 2 เฉพาะที่ code path เดียวกันสร้างการเรียงลำดับด้วย ในการรันเดียวกัน เหนือคอลัมน์เดียวกัน และเขียนความสัมพันธ์นั้นไว้ข้างสูตร เพราะ binary search บนคอลัมน์ที่เรียงลำดับด้วยคีย์ต่างกันคือวิธีที่ถูกที่สุดในการคำนวณตัวเลขผิดแบบมั่นใจ เมื่อ lookup นั้นร้อนแรงจริง ๆ และข้อมูลเรียงลำดับจริง ๆ ผลตอบแทนก็เป็นจริง การเดินอ่านเซลล์ในระดับ log n แทนที่จะเป็น n และแต่ละการอ่านนั้นผ่านการคำนวณเซลล์ workbook เต็มรูปแบบ ดังนั้นการประหยัดจึงมากกว่าที่จำนวนคำสั่งบอกไว้

ถ้ารูปร่างของปัญหาใกล้เคียงกับกฎโดเมนมากกว่า lookup callback เข้าไปยัง Pascal code ของคุณเอง ตามที่กล่าวไว้ในบทความเรื่อง ฟังก์ชัน worksheet แบบกำหนดเอง มักจะเอาชนะการจัดเรียงฟังก์ชันในตัวที่ฉลาดใด ๆ ได้ การทำงานของ XLOOKUP และ XMATCH ที่กล่าวถึงในบทความนี้มาพร้อมกับ HotXLS Delphi spreadsheet component มาตรฐาน ที่หน้าผลิตภัณฑ์มีเอกสารอ้างอิงฟังก์ชันที่รองรับฉบับเต็มสำหรับ Delphi และ C++Builder