Λειτουργίες Binary Search XLOOKUP και XMATCH σε Delphi

Το HotXLS, το εγγενές component υπολογιστικού φύλλου για Delphi και C++Builder, αξιολογεί τα XLOOKUP και XMATCH μέσω ενός κοινού πυρήνα αναζήτησης. Αυτός ο πυρήνας δέχεται τέσσερις λειτουργίες αντιστοίχισης (-1, 0, 1, 2) και τέσσερις λειτουργίες αναζήτησης (-2, -1, 1, 2), τρέχει μια λογαριθμική δυαδική κάθοδο όποτε η απόλυτη λειτουργία αναζήτησης είναι 2, και απορρίπτει κάθε άλλο συνδυασμό με σφάλμα τύπου

Η αναφορά σφάλματος που σας φέρνει εδώ ποτέ δεν λέει «λειτουργία αναζήτησης». Λέει ότι το βιβλίο εργασίας που παράγεται από τον server δείχνει διαφορετικό αριθμό από το ίδιο αρχείο ανοιγμένο στο Excel, σε ίσως τέσσερις γραμμές από εννέα χιλιάδες. Αυτές οι τέσσερις γραμμές έχουν πάντα κάτι κοινό: ένα διπλότυπο κλειδί αναζήτησης, ή μια κατά προσέγγιση αντιστοίχιση που έπρεπε να επιλέξει γείτονα, ή μια στήλη αναζήτησης που κάποιος ταξινόμησε κατά διαφορετική στήλη την προηγούμενη εβδομάδα. Οι συναρτήσεις αναζήτησης είναι εκεί όπου μια μηχανή τύπων σταματά να είναι αριθμητική και αρχίζει να είναι συμβόλαιο, και το συμβόλαιο έχει ρήτρες που οι περισσότεροι καλούντες δεν διαβάζουν ποτέ

Ποιους αριθμούς λειτουργίας δέχεται στην πραγματικότητα το XLOOKUP;

Ακριβώς τέσσερις από κάθε τύπο, και τίποτα άλλο. Το HotXLS επικυρώνει το match_mode έναντι -1, 0, 1 και 2 και το search_mode έναντι -2, -1, 1 και 2 πριν αγγίξει έστω και ένα κελί, και οποιαδήποτε άλλη τιμή επιστρέφει #VALUE! αντί να περιοριστεί στην πλησιέστερη νόμιμη λειτουργία. Οι τέσσερις λειτουργίες αντιστοίχισης είναι 0 για ακριβή, -1 για ακριβή ή τον επόμενο μικρότερο, 1 για ακριβή ή τον επόμενο μεγαλύτερο, και 2 για wildcard· οι τέσσερις λειτουργίες αναζήτησης είναι 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 επομένως εμπιστεύεται τον καλούντα, υποδιπλασιάζει το διάστημα, και επιστρέφει ό,τι κι αν καταλήξει η κάθοδος. Σε μη ταξινομημένη είσοδο η απάντηση δεν είναι σφάλμα, είναι σιωπηλά λάθος, και αυτό είναι παραβίαση συμβολαίου παρά ελάττωμα στη μηχανή

Η Microsoft τεκμηριώνει την ίδια ασυμμετρία για τα 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, απορρίπτει ξανά, και εξαντλεί το διάστημα. Το Excel συμπεριφέρεται με τον ίδιο τρόπο, που είναι το νόημα: η αναπαραγωγή της λάθος απάντησης είναι απαίτηση συμβατότητας, όχι ευγένεια. Η προϋπόθεση διάταξης είναι επίσης αυστηρότερη από «αριθμοί αύξοντες», επειδή ο συγκριτής κατατάσσει τιμές κατά είδος πρώτα, με τη σειρά αριθμοί, μετά κείμενο, μετά booleans, μετά τιμές σφάλματος, μετά κενά, και μόνο συγκρίνει εντός ενός είδους μετά από αυτό. Μια στήλη αριθμητικών κωδικών εξαρτημάτων που έχει τρία κελιά αποθηκευμένα ως κείμενο αντί για αριθμό δεν είναι αύξουσα κάτω από αυτόν τον συγκριτή ανεξάρτητα από το πώς φαίνεται στην οθόνη, και οι δυαδικές λειτουργίες θα το διαβάσουν ευχαρίστως λάθος

Πού καταλήγουν τα διπλότυπα κλειδιά;

Σε ένα ντετερμινιστικό άκρο του τρεξίματος διπλότυπων, και ποιο άκρο εξαρτάται από τη λειτουργία αναζήτησης παρά από τύχη. Όταν η δυαδική κάθοδος πετυχαίνει ένα ίσο κλειδί κάτω από τη λειτουργία αναζήτησης 2, καταγράφει τη θέση και μετά συνεχίζει να στενεύει προς τα αριστερά, οπότε το αποτέλεσμα είναι ο χαμηλότερος δείκτης του τρεξίματος· κάτω από τη λειτουργία αναζήτησης -2, πάνω σε φθίνοντα δεδομένα, καταγράφει τη θέση και στενεύει προς τα δεξιά, οπότε το αποτέλεσμα είναι ο υψηλότερος δείκτης. Οι γραμμικές λειτουργίες είναι απλούστερες: η λειτουργία αναζήτησης 1 επιστρέφει το πρώτο χτύπημα προχωρώντας εμπρός, η λειτουργία αναζήτησης -1 το πρώτο χτύπημα προχωρώντας πίσω. Αυτή είναι η λεπτομέρεια που παράγει την ασυμφωνία τεσσάρων γραμμών από την αρχική παράγραφο, επειδή ένα βιβλίο εργασίας του οποίου τα κλειδιά είναι μοναδικά δίνει πανομοιότυπες απαντήσεις κάτω από όλες τις τέσσερις λειτουργίες αναζήτησης και κρύβει τη διαφορά μέσα από κάθε δοκιμή που γράψατε από ένα καθαρό αρχείο δείγματος. Προσθέστε έναν διπλότυπο κωδικό πελάτη σε δεδομένα παραγωγής και οι λειτουργίες αρχίζουν να διαφωνούν ακριβώς στις γραμμές που διπλασιάστηκαν: τίποτα δεν άλλαξε στη μηχανή, η είσοδος απλώς σταμάτησε να είναι σύνολο και έγινε 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

Γιατί τα wildcards και η δυαδική αναζήτηση δεν μπορούν να συνυπάρξουν

Επειδή ένα μοτίβο wildcard δεν είναι θέση σε μια σειρά. Η λειτουργία αντιστοίχισης 2 ρωτά αν ένα κελί ταιριάζει με μια μάσκα, και η αντιστοίχιση μάσκας απαντά ναι ή όχι· μια δυαδική κάθοδος χρειάζεται μια τριπλή απάντηση που της λέει ποιο μισό να κρατήσει. Δεν υπάρχει υπερασπίσιμος τρόπος να ρωτήσετε αν το ACME-* βρίσκεται αριστερά ή δεξιά από ένα δεδομένο κελί, οπότε το HotXLS απορρίπτει το match_mode 2 σε συνδυασμό με search_mode 2 ή -2 εκ των προτέρων με #VALUE! αντί να μαντέψει μια διάταξη και να παράγει ευλογοφανή ανοησία. Οι δύο διαδρομές συγκρίνουν επίσης τιμές διαφορετικά, που ενισχύει τον διαχωρισμό: η γραμμική σάρωση αποφασίζει ισότητα με σύγκριση κειμένου χωρίς διάκριση πεζών-κεφαλαίων, ή με αντιστοίχιση μάσκας όταν τα wildcards είναι ενεργά, ενώ η δυαδική κάθοδος αποφασίζει ισότητα ρωτώντας τον συγκριτή διάταξης για μηδέν. Αυτό είναι σκόπιμο και όχι ατύχημα στρωματοποίησης, αφού η δυαδική διαδρομή μπορεί να χρησιμοποιήσει μόνο τη σχέση στην οποία στην πραγματικότητα πλοηγείται. Αν χρειάζεστε wildcards, χρησιμοποιήστε λειτουργία αναζήτησης 1 ή -1 και αποδεχτείτε το γραμμικό κόστος, που είναι η ίδια ανταλλαγή που η παρακολούθηση εξαρτήσεων πίσω από την αυξητική επανυπολογισμό έχει σχεδιαστεί να κρατά μακριά από το κρίσιμο μονοπάτι σας

Σφάλματα σχήματος: δισδιάστατα εύρη και ασύμβατα διανύσματα επιστροφής

Και οι δύο συναρτήσεις απαιτούν ένα γνησίως μονοδιάστατο εύρος αναζήτησης. Αν το παρεχόμενο εύρος εκτείνεται σε περισσότερες από μία γραμμή και περισσότερες από μία στήλη ταυτόχρονα, το HotXLS επιστρέφει #VALUE! αντί να επιλέξει έναν άξονα εκ μέρους σας, και ένα εύρος μονής γραμμής ή μονής στήλης διαβάζεται κατά μήκος του μεγάλου άξονά του. Το XLOOKUP προσθέτει έναν δεύτερο κανόνα σχήματος: το εύρος επιστροφής πρέπει να είναι ακριβώς όσο μακρύ είναι το εύρος αναζήτησης κατά μήκος του άξονα αντιστοίχισης, οπότε μια κάθετη αναζήτηση πάνω σε 500 γραμμές συζευγμένη με εύρος επιστροφής 499 γραμμών είναι σφάλμα, όχι ένα off-by-one που επιλύεται σιωπηλά στην τελευταία γραμμή. Όταν το εύρος επιστροφής είναι πλατύτερο από μία στήλη για κάθετη αναζήτηση, ή ψηλότερο από μία γραμμή για οριζόντια, το XLOOKUP επιστρέφει ολόκληρο το αντιστοιχισμένο τμήμα ως πίνακα και ξεχειλίζει στα γειτονικά κελιά κάτω από τους ίδιους κανόνες με τις άλλες δυναμικές συναρτήσεις πίνακα, που περιγράφονται στο άρθρο για τα εύρη ξεχειλίσματος και δυναμικούς πίνακες. Αυτό είναι γνησίως χρήσιμο για την εξαγωγή ολόκληρης εγγραφής από έναν πίνακα με έναν τύπο, και είναι επίσης ο ταχύτερος τρόπος να αντικαταστήσετε μια στήλη που εννοούσατε να κρατήσετε

Επιλογή λειτουργίας όταν κανείς δεν παρακολουθεί την οθόνη

Η παραγωγή στην πλευρά του server αξίζει αυστηρότερη πολιτική από τη διαδραστική χρήση, επειδή δεν υπάρχει άνθρωπος να παρατηρήσει ότι ένα σύνολο φαίνεται λάθος. Η υπερασπίσιμη προεπιλογή είναι λειτουργία αναζήτησης 1 με λειτουργία αντιστοίχισης 0: γραμμική, ακριβής, ανεξάρτητη διάταξης, και αδύνατο να ακυρωθεί με επαναταξινόμηση ενός φύλλου. Απλωθείτε στη λειτουργία αναζήτησης 2 μόνο όπου η ίδια διαδρομή κώδικα παρήγαγε επίσης τη διάταξη, στο ίδιο τρέξιμο, πάνω στην ίδια στήλη, και γράψτε αυτή την εξάρτηση δίπλα στον τύπο, επειδή μια δυαδική αναζήτηση σε μια στήλη ταξινομημένη κατά διαφορετικό κλειδί είναι ο φθηνότερος δυνατός τρόπος να υπολογίσετε έναν σίγουρο λάθος αριθμό. Όταν η αναζήτηση είναι γνησίως καυτή και τα δεδομένα γνησίως ταξινομημένα το κέρδος είναι πραγματικό: η κάθοδος διαβάζει της τάξης του log n κελιά αντί για n, και καθεμιά από αυτές τις αναγνώσεις περνά από πλήρη επίλυση κελιού βιβλίου εργασίας, οπότε η εξοικονόμηση είναι μεγαλύτερη απ' όσο υποδηλώνει ο αριθμός εντολών

Αν το σχήμα του προβλήματος είναι πιο κοντά σε κανόνα τομέα παρά σε αναζήτηση, μια επανάκληση στον δικό σας κώδικα Pascal, όπως καλύπτεται στο άρθρο για τις προσαρμοσμένες συναρτήσεις φύλλου εργασίας, συνήθως θα νικήσει κάθε έξυπνη διάταξη των ενσωματωμένων. Οι υλοποιήσεις XLOOKUP και XMATCH που συζητούνται εδώ διατίθενται με το τυπικό HotXLS Delphi spreadsheet component, του οποίου η σελίδα προϊόντος φέρει την πλήρη αναφορά υποστηριζόμενων συναρτήσεων για Delphi και C++Builder