حالت‌های جستجوی باینری XLOOKUP و XMATCH در Delphi

HotXLS، کامپوننت بومی صفحه‌گسترده Delphi و C++Builder، XLOOKUP و XMATCH را از طریق یک هسته جستجوی مشترک ارزیابی می‌کند. آن هسته چهار match mode (-1، 0، 1، 2) و چهار search mode (-2، -1، 1، 2) را می‌پذیرد، هر وقت مقدار مطلق search mode برابر ۲ باشد یک نزول باینری لگاریتمی اجرا می‌کند، و هر ترکیب دیگر را با یک خطای فرمول رد می‌کند

گزارش باگی که شما را اینجا می‌فرستد هرگز نمی‌گوید "search mode". می‌گوید workbook تولیدشده توسط سرور عددی متفاوت از همان فایل باز شده در Excel نشان می‌دهد، شاید در چهار ردیف از نه‌هزار. آن چهار ردیف همیشه چیزی مشترک دارند: یک کلید جستجوی تکراری، یا یک تطبیق تقریبی که مجبور بوده یک همسایه انتخاب کند، یا یک ستون جستجو که کسی هفته پیش با ستون دیگری مرتب کرده. توابع جستجو جایی هستند که یک موتور فرمول از حساب بودن دست می‌کشد و به یک قرارداد تبدیل می‌شود، و آن قرارداد بندهایی دارد که اغلب فراخوانندگان هرگز نمی‌خوانند

XLOOKUP واقعاً کدام اعداد mode را می‌پذیرد؟

دقیقاً چهار تا از هر کدام، و هیچ‌چیز دیگر. HotXLS match_mode را در برابر -1، 0، 1 و 2 و search_mode را در برابر -2، -1، 1 و 2 پیش از دست‌زدن به یک سلول واحد اعتبارسنجی می‌کند، و هر مقدار دیگری #VALUE! برمی‌گرداند به‌جای اینکه به نزدیک‌ترین mode مجاز clamp شود. چهار match mode عبارتند از 0 برای دقیق، -1 برای دقیق یا کوچک‌تر بعدی، 1 برای دقیق یا بزرگ‌تر بعدی، و 2 برای wildcard؛ چهار search mode عبارتند از 1 برای یک اسکن خطی رو‌به‌جلو، -1 برای یک اسکن خطی معکوس، 2 برای یک جستجوی باینری روی داده صعودی، و -2 برای یک جستجوی باینری روی داده نزولی. حذف کردن آن‌ها match mode 0 و search mode 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;

یک گام زودتر یک بررسی آرام‌تر وجود دارد که ارزش دانستن دارد. آرگومان‌های mode به‌عنوان عبارات کاربرگ می‌رسند، پس HotXLS آن‌ها را به یک عدد coerce می‌کند، NaN و infinity را رد می‌کند، و سپس مطالبه می‌کند عدد برابر مقدار گرد‌شده خودش باشد. XLOOKUP(x, A:A, B:B, "none", 0, 1.5) یک #VALUE! است، نه یک search mode 2 پنهان. این وقتی اهمیت دارد که mode از سلولی می‌آید که یک محاسبه سنگین‌گرد تولیدش کرده، که در workbookهای تولیدشده رایج‌تر از workbookهای دستی است

چرا search_mode 2 روی داده مرتب‌نشده پاسخ اشتباه می‌دهد؟

چون دقیقاً همان کاری را می‌کند که خواسته‌اید. search mode 2 به موتور می‌گوید بردار جستجو از قبل به ترتیب صعودی است، و یک جستجوی باینری نمی‌تواند آن ادعا را بدون یک پاس O(n) که کل دلیل استفاده از آن را نابود می‌کند تأیید کند. HotXLS بنابراین به فراخواننده اعتماد می‌کند، بازه را نصف می‌کند، و هرچه نزول به آن فرود بیاید برمی‌گرداند. روی ورودی مرتب‌نشده پاسخ یک خطا نیست، خاموش اشتباه است، و این یک نقض قرارداد است نه یک نقص در موتور

Microsoft همان نامتقارنی را برای XLOOKUP و XMATCH مستند می‌کند: حالت‌های باینری به داده مرتب‌شده نیاز دارند و در غیر این صورت نتایج نامعتبر تولید می‌کنند. ISO 29500-1 بند 18.17، که گرامر فرمول SpreadsheetML را تعریف می‌کند، توصیف‌های قدیمی‌تر LOOKUP و VLOOKUP را با نیازمندی ترتیب صعودی خودشان حمل می‌کند، و XLOOKUP و XMATCH آن‌قدر پس از آن متن آمده‌اند که در فایل به‌عنوان _xlfn.XLOOKUP و _xlfn.XMATCH تحت قرارداد future-function سفر می‌کنند. نسل متفاوت، همان معامله: فراخواننده invariant ترتیب را تأمین می‌کند، موتور لگاریتم را تأمین می‌کند

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;

فرمول دوم را ردیابی کنید و شکست کاملاً مکانیکی است. نزول سلول میانی را کاوش می‌کند، ۱۰ را می‌خواند، تصمیم می‌گیرد ۱۰ کوچک‌تر از ۴۰ است، نیمه چپ شامل ردیفی که واقعاً ۴۰ را نگه داشته را دور می‌ریزد، ۳۰ را کاوش می‌کند، دوباره دور می‌ریزد، و از بازه تمام می‌شود. Excel به همان روش رفتار می‌کند، که همان نکته است: بازتولید پاسخ اشتباه یک نیازمندی سازگاری است، نه یک لطف. فرض ترتیب همچنین از "اعداد صعودی" سخت‌گیرانه‌تر است، چون comparator ابتدا مقادیر را بر اساس نوع رتبه‌بندی می‌کند، به ترتیب اعداد، سپس متن، سپس booleanها، سپس مقادیر خطا، سپس خالی‌ها، و فقط پس از آن درون یک نوع مقایسه می‌کند. یک ستون کدهای بخش عددی که سه سلول به‌جای عدد متن ذخیره می‌کند تحت آن comparator صعودی نیست هرچقدر هم روی صفحه به‌نظر برسد، و حالت‌های باینری با خوشحالی آن را غلط می‌خوانند

کلیدهای تکراری کجا فرود می‌آیند؟

روی یک انتهای قطعی از دنباله تکراری، و اینکه کدام انتها به search mode بستگی دارد نه به شانس. وقتی نزول باینری زیر search mode 2 به یک کلید برابر برخورد می‌کند موقعیت را ثبت می‌کند و سپس به باریک‌شدن به چپ ادامه می‌دهد، پس نتیجه پایین‌ترین اندیس دنباله است؛ زیر search mode -2، روی داده نزولی، موقعیت را ثبت می‌کند و به راست باریک می‌شود، پس نتیجه بالاترین اندیس است. حالت‌های خطی ساده‌تراند: search mode 1 اولین برخورد رو‌به‌جلو را برمی‌گرداند، search mode -1 اولین برخورد رو‌به‌عقب را. این همان جزئیاتی است که اختلاف چهار-ردیفی پاراگراف آغازین را تولید می‌کند، چون یک workbook که کلیدهای آن یکتا هستند پاسخ‌های یکسانی زیر هر چهار search mode می‌دهد و تفاوت را در سراسر هر تستی که از یک فایل نمونه پاک نوشته‌اید پنهان می‌کند. یک کد مشتری تکراری به داده تولید اضافه کنید و حالت‌ها دقیقاً روی ردیف‌هایی که تکراری شده شروع به اختلاف می‌کنند: هیچ‌چیز در موتور تغییر نکرده، ورودی صرفاً از یک set بودن دست کشیده و به یک 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

تطبیق تقریبی چگونه نامزد دوم را انتخاب می‌کند؟

با نگه داشتن یک بهترین نامزد در کنار جستجوی تطبیق‌دقیق و بازگرداندن آن فقط اگر هیچ برخورد دقیقی ظاهر نشود. 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 می‌دهد

چرا wildcardها و جستجوی باینری نمی‌توانند همزیستی کنند

چون یک الگوی wildcard یک موقعیت در یک ترتیب نیست. match mode 2 می‌پرسد آیا یک سلول با یک ماسک مطابقت دارد، و تطبیق ماسک بله یا خیر پاسخ می‌دهد؛ یک نزول باینری به یک پاسخ سه‌طرفه نیاز دارد که به آن بگوید کدام نیمه را نگه دارد. هیچ راه قابل‌دفاعی برای پرسیدن اینکه آیا ACME-* چپ یا راست یک سلول مشخص می‌افتد وجود ندارد، پس HotXLS از ابتدا match_mode 2 ترکیب‌شده با search_mode 2 یا -2 را با #VALUE! رد می‌کند به‌جای حدس زدن یک ترتیب و تولید یک مزخرف قابل‌قبول‌به‌نظر. دو مسیر همچنین مقادیر را متفاوت مقایسه می‌کنند، که تقسیم را تقویت می‌کند: اسکن خطی برابری را با یک مقایسه متن غیرحساس‌به‌بزرگ‌کوچکی، یا با تطبیق ماسک وقتی wildcardها روشن‌اند تصمیم می‌گیرد، درحالی‌که نزول باینری برابری را با پرسیدن یک صفر از comparator ترتیب تصمیم می‌گیرد. این عمدی است نه یک تصادف از لایه‌بندی، چون مسیر باینری فقط ممکن است از رابطه‌ای استفاده کند که واقعاً با آن ناوبری می‌کند. اگر به wildcard نیاز دارید، search mode 1 یا -1 استفاده کنید و هزینه خطی را بپذیرید، که همان معامله‌ای است که ردیابی وابستگی پشت بازمحاسبه افزایشی طراحی شده تا از مسیر بحرانی شما دور نگه دارد

خطاهای شکل: بازه‌های دوبعدی و بردارهای بازگشتی نامنطبق

هر دو تابع به یک بازه جستجوی واقعاً یک‌بعدی نیاز دارند. اگر بازه تأمین‌شده همزمان بیش از یک ردیف و بیش از یک ستون را در بر بگیرد، HotXLS به‌جای انتخاب یک محور از طرف شما #VALUE! برمی‌گرداند، و یک بازه تک‌ردیفی یا تک‌ستونی در امتداد محور بلندش خوانده می‌شود. XLOOKUP یک قانون شکل دوم اضافه می‌کند: بازه بازگشتی باید دقیقاً به همان طولی باشد که بازه جستجو در امتداد محور تطبیقی است، پس یک جستجوی عمودی روی ۵۰۰ ردیف جفت‌شده با یک بازه بازگشتی ۴۹۹ردیفی یک خطاست، نه یک off-by-one که خاموش در آخرین ردیف حل شود. وقتی بازه بازگشتی برای یک جستجوی عمودی از یک ستون پهن‌تر باشد، یا برای یک جستجوی افقی از یک ردیف بلندتر باشد، XLOOKUP کل برش تطبیق‌یافته را به‌عنوان یک آرایه برمی‌گرداند و به سلول‌های همسایه با همان قوانین سایر توابع آرایه پویا سرریز می‌کند، شرح‌داده‌شده در مقاله بازه‌های spill و آرایه‌های پویا. این برای بیرون کشیدن یک رکورد کامل از یک جدول با یک فرمول واقعاً مفید است، و همچنین سریع‌ترین راه برای رونویسی ستونی است که قصد داشتید نگه دارید

انتخاب یک mode وقتی کسی صفحه را تماشا نمی‌کند

تولید سمت‌سرور سزاوار خط‌مشی سخت‌گیرانه‌تری از استفاده تعاملی است، چون هیچ انسانی نیست که متوجه شود یک مجموع اشتباه به‌نظر می‌رسد. پیش‌فرض قابل‌دفاع search mode 1 با match mode 0 است: خطی، دقیق، مستقل از ترتیب، و غیرقابل‌ابطال با مرتب‌سازی مجدد یک صفحه. فقط جایی به search mode 2 دست بزنید که همان مسیر کد همچنین ترتیب را در همان اجرا، روی همان ستون تولید کرده، و آن وابستگی را کنار فرمول بنویسید، چون یک جستجوی باینری روی ستونی مرتب‌شده با کلیدی متفاوت ارزان‌ترین راه ممکن برای محاسبه یک عدد اشتباه با اعتماد‌به‌نفس است. وقتی جستجو واقعاً داغ و داده واقعاً مرتب است پاداش واقعی است: نزول در حدود log n سلول را می‌خواند به‌جای n، و هر یک از آن خوانده‌ها از یک حل سلول کامل workbook عبور می‌کند، پس صرفه‌جویی بزرگ‌تر از چیزی است که تعداد instruction نشان می‌دهد

اگر شکل مسئله به یک قانون دامنه نزدیک‌تر باشد تا یک جستجو، یک callback به کد Pascal خودتان، همان‌طور که در مقاله توابع سفارشی کاربرگ پوشش داده شده، معمولاً از هر ترتیب هوشمندانه توابع built-in پیشی می‌گیرد. پیاده‌سازی‌های XLOOKUP و XMATCH که اینجا بحث شد همراه با نسخه استاندارد کامپوننت صفحه‌گسترده HotXLS Delphi عرضه می‌شوند، که صفحه محصولش مرجع کامل توابع پشتیبانی‌شده برای Delphi و C++Builder را حمل می‌کند