מצבי חיפוש בינארי XLOOKUP ו-XMATCH בדלפי

HotXLS, רכיב הגיליון האלקטרוני הילידי של דלפי ו-C++Builder, מעריך XLOOKUP ו-XMATCH דרך ליבת חיפוש משותפת אחת. הליבה הזו מקבלת ארבעה מצבי התאמה (-1, 0, 1, 2) וארבעה מצבי חיפוש (-2, -1, 1, 2), מריצה ירידה בינארית לוגריתמית בכל פעם שמצב החיפוש המוחלט הוא 2, ודוחה כל צירוף אחר עם שגיאת נוסחה

דוח הבאג ששולח אותך לכאן אף פעם לא אומר "search mode". הוא אומר שחוברת העבודה שנוצרה בשרת מציגה מספר שונה מאשר אותו קובץ פתוח באקסל, על אולי ארבע שורות מתוך תשעת אלפים. לארבע השורות האלה תמיד יש משהו במשותף: מפתח חיפוש כפול, או התאמה קירובית שהייתה צריכה לבחור שכן, או עמודת חיפוש שמישהו מיין לפי עמודה אחרת בשבוע שעבר. פונקציות חיפוש הן המקום שבו מנוע נוסחאות מפסיק להיות אריתמטיקה ומתחיל להיות חוזה, ולחוזה יש סעיפים שרוב הקוראים אף פעם לא קוראים

אילו מספרי מצב XLOOKUP בעצם מקבל?

בדיוק ארבעה מכל, ושום דבר אחר. HotXLS מאמתת את match_mode כנגד -1, 0, 1 ו-2 ואת search_mode כנגד -2, -1, 1 ו-2 לפני שהיא נוגעת בתא בודד, וכל ערך אחר מחזיר #VALUE! במקום להיהדק למצב חוקי הקרוב ביותר. ארבעת מצבי ההתאמה הם 0 עבור מדויק, -1 עבור מדויק או הקטן-הבא, 1 עבור מדויק או הגדול-הבא, ו-2 עבור תו כללי; ארבעת מצבי החיפוש הם 1 עבור סריקה ליניארית קדימה, -1 עבור סריקה ליניארית אחורה, 2 עבור חיפוש בינארי על נתונים עולים, ו-2- עבור חיפוש בינארי על נתונים יורדים. השמטתם בוחרת מצב התאמה 0 ומצב חיפוש 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;

צעד אחד קודם יש בדיקה שקטה יותר ששווה להכיר. ארגומנטי המצב מגיעים כביטויי גיליון-עבודה, כך ש-HotXLS כופה אותם למספר, מסרבת ל-NaN ואינסוף, ואז דורשת שהמספר יהיה שווה לערכו המעוגל שלו עצמו. XLOOKUP(x, A:A, B:B, "none", 0, 1.5) הוא #VALUE!, לא מצב חיפוש 2 במסווה. זה חשוב כשהמצב מגיע מתא שחישוב כבד-עיגול הפיק, שנפוץ יותר בחוברות עבודה שנוצרות מאשר בכתובות-ביד

למה search_mode 2 נותן תשובה שגויה על נתונים לא-ממוינים?

מפני שהוא עושה בדיוק את מה שביקשת. מצב חיפוש 2 אומר למנוע שוקטור החיפוש כבר בסדר עולה, וחיפוש בינארי לא יכול לאמת את הטענה הזו בלי מעבר O(n) שהיה הורס את הסיבה להשתמש בו. HotXLS לכן סומכת על הקורא, חוצה את המרווח, ומחזירה כל מה שהירידה נוחתת עליה. על קלט לא-ממוין התשובה אינה שגיאה, היא שגויה בשקט, וזו הפרת חוזה ולא פגם במנוע

מיקרוסופט מתעדת את אותה אסימטריה עבור XLOOKUP ו-XMATCH: המצבים הבינאריים דורשים נתונים ממוינים ומפיקים תוצאות לא-תקינות אחרת. תקן ISO 29500-1 סעיף 18.17, שמגדיר את דקדוק הנוסחה SpreadsheetML, נושא את התיאורים הישנים יותר של LOOKUP ו-VLOOKUP עם דרישת הסדר-העולה שלהם, ו-XLOOKUP ו-XMATCH מגיעים מאוחר יותר מספיק שהם נוסעים בקובץ כ-_xlfn.XLOOKUP ו-_xlfn.XMATCH תחת המוסכמה של פונקציה-עתידית. יצירה שונה, אותה עסקה: הקורא מספק את שינוי-הסדר, המנוע מספק את הלוגריתם

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, זורקת שוב, ונגמר לה המרווח. אקסל מתנהג באותה דרך, וזה כל העניין: שחזור התשובה השגויה הוא דרישת תאימות, לא נימוס. הנחת הסדר גם קפדנית יותר מ"מספרים עולים", כי המשווה מדרג ערכים לפי סוג תחילה, בסדר מספרים, ואז טקסט, ואז בוליאנים, ואז ערכי שגיאה, ואז ריקים, ורק משווה בתוך סוג אחרי זה. עמודת קודי חלק מספריים שבה שלושה תאים מאחסנים טקסט במקום זאת אינה עולה תחת המשווה הזה לא משנה איך היא נראית על המסך, והמצבים הבינאריים ישמחו לקרוא אותה שגוי

איפה מפתחות כפולים נוחתים?

בקצה דטרמיניסטי של ריצת הכפילות, והקצה תלוי במצב החיפוש ולא במזל. כשהירידה הבינארית פוגעת במפתח שווה תחת מצב חיפוש 2 היא רושמת את המיקום ואז ממשיכה לצמצם שמאלה, כך שהתוצאה היא האינדקס הנמוך ביותר של הריצה; תחת מצב חיפוש 2-, על נתונים יורדים, היא רושמת את המיקום ומצמצמת ימינה, כך שהתוצאה היא האינדקס הגבוה ביותר. המצבים הליניאריים פשוטים יותר: מצב חיפוש 1 מחזיר את הפגיעה הראשונה קדימה, מצב חיפוש 1- את הפגיעה הראשונה אחורה. זה הפרט שמפיק את הפער בן ארבע-השורות מהפסקה הפותחת, כי חוברת עבודה שהמפתחות שלה ייחודיים נותנת תשובות זהות תחת כל ארבעת מצבי החיפוש ומסתירה את ההבדל דרך כל בדיקה שכתבת מקובץ דוגמה נקי. הוסף קוד לקוח כפול אחד לנתוני ייצור והמצבים מתחילים לחלוק דעות בדיוק על השורות שהוכפלו: שום דבר לא השתנה במנוע, הקלט פשוט הפסיק להיות סט והפך למולטי-סט

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

איך התאמה קירובית בוחרת את המתמודד השני?

על ידי שמירת מועמד מיטבי לצד חיפוש ההתאמה-המדויקת ומחזירה אותו רק אם אין פגיעה מדויקת. HotXLS מתייחסת ל-match_mode -1 כ"הערך הגדול ביותר שאינו גדול מהיעד" ול-match_mode 1 כ"הקטן ביותר שאינו קטן", ושניהם נפתרים על פני כל האזור שנסרק ולא על ידי עצירה בשכן הראשון הקביל. בנתיב הבינארי אותו רעיון נופל מהירידה בחינם: כל צעד שחורג מלמעלה או מלמטה מעדכן את המועמד, כך שהמועמד הסופי הוא אלמנט הגבול הסמוך למיקום שבו המפתח היה מוכנס

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

קרא את התנאי הפנימי בעיון, כי שבירת התיקו חיה שם. תא חדש מחליף את המועמד הקיים רק כשהוא טוב יותר בקפדנות, אף פעם לא כשהוא רק שווה לו, כך שמבין כמה תאים שמחזיקים באותו ערך מקום-שני זה שנשמר הוא הראשון שנפגש בסדר הסריקה: האינדקס הנמוך ביותר תחת סריקה קדימה, הגבוה ביותר תחת סריקה אחורה. אם XLOOKUP ו-XMATCH לא מוצאות לא פגיעה מדויקת ולא שכן קביל, XLOOKUP נופלת חזרה לארגומנט if_not_found שלה כשאחד סופק ול-#N/A כשלא, בעוד XMATCH תמיד מניבה #N/A

למה תווים כלליים וחיפוש בינארי לא יכולים לדור יחד

מפני שתבנית תו-כללי אינה מיקום בסדר. מצב התאמה 2 שואל האם תא תואם מסכה, והתאמת מסכה עונה כן או לא; ירידה בינארית צריכה תשובה תלת-כיוונית שאומרת לה איזו מחצית לשמור. אין דרך ניתנת-להגנה לשאול האם ACME-* נמצא משמאל או מימין לתא נתון, כך ש-HotXLS דוחה match_mode 2 בשילוב עם search_mode 2 או 2- מראש עם #VALUE! במקום לנחש סדר ולהפיק שטויות סבירות-למראה. שני הנתיבים גם משווים ערכים אחרת, מה שמחזק את הפיצול: הסריקה הליניארית מחליטה שוויון עם השוואת טקסט לא-תלוית-רישיות, או עם התאמת מסכה כשתווים כלליים פועלים, בעוד הירידה הבינארית מחליטה שוויון על ידי שאילת המשווה הסדרתי לאפס. זה מכוון ולא תאונה של שכבות, כיוון שהנתיב הבינארי מותר לו להשתמש רק ביחס שהוא בעצם מנווט לפיו. אם אתה זקוק לתווים כלליים, השתמש במצב חיפוש 1 או 1- וקבל את העלות הליניארית, שהיא אותה עסקה שמעקב התלות מאחורי חישוב מחדש incremental מיועד לשמור מחוץ לנתיב הקריטי שלך

שגיאות צורה: טווחים דו-ממדיים ווקטורי החזרה לא-תואמים

שתי הפונקציות דורשות טווח חיפוש חד-ממדי באמת. אם הטווח שסופק פורש יותר משורה אחת ויותר מעמודה אחת בו-זמנית, HotXLS מחזירה #VALUE! במקום לבחור ציר בשמך, וטווח שורה-בודדת או עמודה-בודדת נקרא לאורך הציר הארוך שלו. XLOOKUP מוסיפה כלל צורה שני: טווח ההחזרה חייב להיות בדיוק באותו אורך כמו טווח החיפוש לאורך הציר המתאים, כך שחיפוש אנכי על פני 500 שורות מזווג עם טווח החזרה בן 499 שורות הוא שגיאה, לא סטייה-באחד שנפתרת בשקט בשורה האחרונה. כשטווח ההחזרה רחב יותר מעמודה אחת לחיפוש אנכי, או גבוה יותר משורה אחת לאופקי, XLOOKUP מחזירה את כל הפרוסה שהותאמה כמערך והיא נשפכת לתאים השכנים תחת אותם כללים כמו פונקציות המערך הדינמי האחרות, מתואר במאמר על טווחי שפיכה ומערכים דינמיים. זה שימושי באמת לחילוץ רשומה שלמה מטבלה בנוסחה אחת, וזו גם הדרך המהירה ביותר לדרוס עמודה שהתכוונת לשמור

בחירת מצב כשאף אחד לא צופה במסך

יצירה בצד השרת ראויה למדיניות קפדנית יותר משימוש אינטראקטיבי, כי אין בן-אדם שישים לב שסכום נראה שגוי. ברירת המחדל הניתנת-להגנה היא מצב חיפוש 1 עם מצב התאמה 0: ליניארי, מדויק, בלתי-תלוי-בסדר, ובלתי-אפשרי לבטל על ידי מיון מחדש של גיליון. הושט יד למצב חיפוש 2 רק במקום שבו אותו נתיב קוד גם הפיק את הסדר, באותה ריצה, על אותה עמודה, וכתוב את התלות הזו ליד הנוסחה, כי חיפוש בינארי על עמודה שמוינה לפי מפתח אחר הוא הדרך הזולה ביותר לחשב מספר שגוי בביטחון. כשהחיפוש באמת חם והנתונים באמת ממוינים הרווח אמיתי: הירידה קוראת בסדר גודל של log n תאים במקום n, וכל אחת מהקריאות האלה עוברת דרך פתרון תא חוברת-עבודה מלא, כך שהחיסכון גדול יותר ממה שספירת ההוראות מרמזת

אם צורת הבעיה קרובה יותר לכלל תחום מאשר לחיפוש, callback לקוד הפסקל שלך עצמך, כמכוסה במאמר על פונקציות גיליון-עבודה מותאמות אישית, בדרך כלל ינצח כל סידור פיקח של המובנות. המימושים של XLOOKUP ו-XMATCH הנדונים כאן משתלבים עם רכיב הגיליון האלקטרוני HotXLS Delphi הסטנדרטי, שעמוד המוצר שלו נושא את הפניית הפונקציות הנתמכות המלאה עבור דלפי ו-C++Builder