HotXLS Bağımlılık Grafiği: Dizi Formül Çıktısı İndeksleme

Delphi ve C++Builder için yerli Excel kütüphanesi HotXLS 2.383.1, formula bağımlılık kenarlarını bir çıktı-aralık indeksiyle kuruyor: formula düğümleri çapa hücreye göre sıralı kalıyor ve her alt ağacın en büyük çıktı satırını (OutRow2) taşıyan segment tree, TXLSDepGraph.BuildEdges'in başvurulan bir aralığa ulaşamayacak formül bloklarının tamamını atlamasına izin veriyor. Yaklaşık 100.000 formüllük bir Win32 çalışma kitabında zorunlu yeniden hesaplama 18,488 saniyeden 102–109 milisaniyeye indi

Bir saniye süren toplu iş yirmi saniye sürmeye başlayana kadar kimse bağımlılık grafiğini profillemez. Grafik, formula topolojisi her değiştiğinde yeniden kurulur — çalışma kitabı yüklendikten ya da üretildikten sonraki ilk Recalculate, ya da grafik geçersiz kılındıktan sonraki her geçiş — ve düzeltme öncesi izde yalnızca o ilk geçiş 16,074 ms tuttu. Değerlendirme hiç sorun olmadı; kimin kime bağımlı olduğuna karar vermek sorundu

100.000 formülü yeniden hesaplamak neden 18 saniye tuttu?

Eski kenar kurucu, bir sayfadaki formül sayısına göre kareseldi. Her bağımlılık aralığı için BuildEdges aday düğümlerden oluşan bir pencereyi ikili aramayla buluyor, sonra her birini RangeIntersectsOutput ile test ediyordu ve o pencere, başvurulan sayfanın en tepesinden başlıyordu. Düğüm anahtarları XLSDepMakeKey'ten gelir; sheet indeksini 34. bitten yukarı, satırı 14–33. bitlere, sütunu 0–13. bitlere paketler, dolayısıyla (Sheet1, 0, 0) alt sınırı "başvurulan aralığın dibine kadar 1. satırdan aşağı her formül" demekti

// 2.383.1 öncesi - TXLSDepGraph.BuildEdges, d düğümünün r bağımlılık aralığı için
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // sayfanın tepesi
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...FNodeOrder üzerinde iki ikili arama [i, Lo) penceresini üretir...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge ya da LookupScan edge, EdgeStamp / ScanStamp ile tekilleştirilir
  end;
  Inc(i);
end;

Bunu açığa çıkaran performans düzeneği sıradan bir kademeli modeldir: A2:A50000 her biri üstteki hücreye bir ekler, B1:B50000 her biri A sütunundaki komşuyu ikiye katlar. r. satıra bir başvuru bu yüzden dikdörtgen testinden yaklaşık 2r aday geçiriyordu; tek bir grafik kurulumu beş milyar mertebesinde kesişim kontrolü yapıyordu — kâğıt üstü bir kestirme ama kronometredeki 18,5 saniyeyle örtüşüyor. Her kontrol "hayır" diyordu, bir-iki tanesi hariç

Kenar kurucu aramayı neden başvurulan satırdan başlatamıyor?

Çünkü bir aralığın üstüne demirlenmiş bir dizi formülü, o aralığın içindeki hücrelere sahip olabilir. Her TXLSDepNode, çapasından (Row, Col) (OutRow2, OutCol2)'ye uzanan bir çıktı dikdörtgeni tanımlar ve bir CSE dizi formülü tüm dikdörtgeni için tek düğüm alır — artımlı yeniden hesaplama ve bağımlılık grafiği makalesinin anlattığı gibi. A1:A10'u dolduran, A1'e demirli bir kök, yalnızca A5 okuyan bir formülden kenar almak zorundadır; ikili aramayı 5. satırdan başlatın o kenar sessizce kaybolur, bu da yavaş bir rapor yerine dağıtılmış raporda bayat önbellek değeri demektir. Sorgu aslında iki yanlıdır — çapa Row2'de ya da öncesinde, çıktı en az Row1'e ulaşıyor — ve tek bir sıralama düzeni iki yarıyı birden cevaplayamaz. Çok hücreli sonuçlar modern çalışma kitaplarında da karşınıza çıkar; dynamic array spill formülleri makalesi spilled aralıkların HotXLS'te nasıl davrandığını anlatıyor

En büyük çıktı satırlarından bir segment tree

HotXLS üst sınır için çapa sıralamasını koruyor ve alt sınır için zenginleştirilmiş bir segment tree ekliyor. BuildNodeIndex FNodeOrder'ı her zamanki gibi düğüm anahtarına göre sıralıyor, sonra BuildMaxOutRowTree FNodeMaxOutRow2'yi (düğüm başına dört girdi ayrılmış) her alt ağaç altında bulunan en büyük OutRow2 ile dolduruyor. QueryNodeTree yalnızca anahtar penceresinin içinde iniyor ve maksimum çıktı satırı FRanges[r].Row1'in üstünde kalan her alt ağacı terk ediyor, çünkü içindeki hiçbir formül başvurulan satırlara ulaşamıyor. Hayatta kalan yapraklar yine tam RangeIntersectsOutput testinden geçiyor; sheet kapsamları ve sütunlar eskisi gibi denetleniyor

// TXLSDepGraph.BuildNodeIndex / BuildEdges, 2.383.1'den beri (hafifçe yoğunlaştırıldı)
procedure BuildMaxOutRowTree(ATreeIndex, ALeft, ARight: Integer);
var
  Mid: Integer;
begin
  if ALeft = ARight then
  begin
    FNodeMaxOutRow2[ATreeIndex] := FNodes[FNodeOrder[ALeft]].OutRow2;
    Exit;
  end;
  Mid := (ALeft + ARight) shr 1;
  BuildMaxOutRowTree(ATreeIndex * 2, ALeft, Mid);
  BuildMaxOutRowTree(ATreeIndex * 2 + 1, Mid + 1, ARight);
  FNodeMaxOutRow2[ATreeIndex] := Max(FNodeMaxOutRow2[ATreeIndex * 2],
    FNodeMaxOutRow2[ATreeIndex * 2 + 1]);
end;

procedure QueryNodeTree(ATreeIndex, ALeft, ARight, ALower, AUpper: Integer);
var
  Split: Integer;
begin
  // anahtar penceresinin dışında, ya da bu alt ağaçta Row1'e ulaşan çıktı yok
  if (ARight < ALower) or (ALeft >= AUpper) or
     (FNodeMaxOutRow2[ATreeIndex] < FRanges[r].Row1) then
    Exit;
  if ALeft = ARight then
  begin
    Inc(FEdgeCandidateChecks);
    if RangeIntersectsOutput(FRanges[r], FNodes[FNodeOrder[ALeft]]) then
    begin
      // değişmedi: EdgeStamp / ScanStamp baskılaması, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // önce sol alt ağaç
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // eski sırayı korur
end;

Soldan-sağa özyineleme bir stil tercihi değil. Hayatta kalan yapraklar, eski while döngüsünün ziyaret ettiği sıranın tıpatıp aynısıyla ziyaret ediliyor; böylece Dependents ve Precedents dizileri aynı sırayla doluyor ve topolojik düzen deterministik kalıyor. Aynı şey iki kenar türü için de geçerli: önce kaydedilen bir hard edge, aynı çift için sonraki bir LookupScan kenarını yine baskılıyor; hard'dan önce kaydedilen bir scan edge ise yerini koruyor — lookup aralıklarının sahte döngüsel referanslar üretmesini önleyen ayrım bu. Başvuru başına maliyet, pencere büyüklüğünden O((k + 1) log n)'e düşüyor; k, çıktısı başvurulan satırlara gerçekten ulaşan formül sayısı

Çıktı indeksi neyi garanti ediyor ve nasıl doğrulanıyor?

TXLSDepGraph aynı kenarları eskisiyle aynı sırada üretiyor ve yeni EdgeCandidateChecks özelliği en son kurulumun gerçekte kaç çıktı dikdörtgeni test ettiğini sayıyor; iddia retorik değil, ölçülebilir. EdgeBuildDeepChainsCheckOneCandidatePerDependency regresyon testi, uzamsal sıralamayı zorlamak için ters sırada eklenen 1.024 ve 100.000 düğümlük nokta-başvuru zincirleri kuruyor ve tam olarak N − 1 kontrol — uzun zincir için 99.999 — artı her düğüm için beklenen precedent, dependent ve topolojik düzeni doğruluyor. Eşlik eden testler, sheet kapsamları arasında düzensiz eklenen dizi köklerini, yinelenen hard ve lookup-scan başvurularını (yukarıdaki baskılama kurallarıyla 10 kontrol) ve AddNode sonrası yeniden kurulumu kapsıyor; bu, sıralama bayrağını temizler, böylece sonraki BuildEdges ya da NodeIndexOf ağacı yeniden kurar ve sayacı biriktirmek yerine sıfırlar

Ölçülen sonuçlar: 18,5 saniyeden yaklaşık 0,1 saniyeye

Düzeltme öncesi Win32 izi — sürüm 2.383.0 için proje performans taban çizgisinde saklı — 18,488 ms ve 19,578 ms'lik iki zorunlu yeniden hesaplama kaydetti. İndekslemeden sonra mimari başına üç seri odaklı çalıştırma Win32'de 102,332–109,429 ms, Win64'te 116,990–133,995 ms ölçtü; Win32'de kabaca 170 ila 180 kat daha hızlı. Düzeltme öncesi Win64 taban çizgisi kaydedilmediği için Win64 hızlandırma iddiası yok. Aynı çalıştırmalar, salt-okunur yeniden hesaplama denetimini zorunlu yeniden hesaplamanın 1,35 katı içinde tutan mevcut eşiği geçti. Mutlak sayılar makineye ve yüküne bağlı; onları alıntılamadan önce iş yükünü kendi donanımınızda yeniden üretin

uses
  System.SysUtils, System.Diagnostics, lxHandle;

procedure TimeChainRecalc;
var
  Wb: TXLSWorkbook;
  Sh: TXLSWorksheet;
  I, Failed: Integer;
  Watch: TStopwatch;
begin
  Wb := TXLSWorkbook.Create;
  try
    Sh := Wb.Sheets.Add;
    Sh.Cells[1, 1].Value := 1;
    for I := 2 to 50000 do                     // A sütununda 49.999 halkalı zincir
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // B sütununda 50.000 bağımlı
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // ilk çağrı grafiği kurar
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Çıktı indeksi nerede işe yaramaz hâle gelir?

Ağaç yalnızca satırlar üzerinden budaıyor ve bu, etrafında çok büyük bir model tasarlamadan önce bilmenize değecek birkaç dürüst sınır bırakıyor

• Sütun ıskaları yapraklarda ödenmeye devam eder: A100:Z200'ü dolduran 2.626 formülün tamamı 100. satıra ulaşıyor; AA100:AA200'e bir başvuru onları reddetmeden önce her birini test ediyor
• Tüm sütun aralıkları gibi geniş başvuruların gerçekten çok precedenti vardır; indeks boşa giden kontrolleri kaldırır, gerçek kenarları değil, o kenarları kurmak yine sayılarıyla orantılıdır
• Birkaç sheet'e yayılan başvurular için saklanan maksimum sheet'i yok sayar; derin çıktılı ara sheet'lerdeki formüller yaprak testine ulaşır. Sonuçlar doğru kalır, yalnızca budama zayıflar
• Ağaç formula düğümü başına dört tam sayı tutar — 100.000 düğüm için yaklaşık 1,6 MB — ve her AddNode onu geçersiz kılar; topoloji değişiklikleri bir sonraki kenar kurulumunda tam bir O(n log n) yeniden sıralama artı O(n) ağaç kurulumu öder

Rapor bandı adı klonlamada aynı karesel şekil

Sürüm 2.383.2, TXLSXDefinedNames.UniqueCloneName içindeki akraba bir sorunu düzeltti: kopyalanan her defined name sonek aramasını _2'den yeniden başlatıyordu, tekrarlanan rapor bandı kopyaları isim aramalarında karesel büyüyordu. Kapsamlı isim indeksi artık taban adı ve kapsam başına bir sonek ipucu tutuyor ve döndürdüğü son adayı yeniden kontrol ediyor, çünkü çağıran onu gerçekte eklemeyebilir; bir adı silmek, yeniden adlandırmak ya da yeniden kapsamlandırmak indeksi geçersiz kılar ve ilk-müsait adlandırma geri gelir. Regresyon paketinde 1.024 ardışık klon 5.088 aday araması, dört dönüşümlü taban adı 5.039 aramasına ihtiyaç duyarken rapor benchmark minimumları kabaca 240 ms'den 18–20 ms'ye indi. Rapor bandı zamanlama eşiği kendisi hâlâ kararlı değil — düzeltme sonrası ilk denemede altı çalıştırmanın üçü 1,05 oranını aştı — ve performans geçmişi, eşiği geçene kadar ayarlamak yerine o başarısızlıkları kayıtta tutuyor

Delphi ya da C++Builder uygulamanız büyük Excel çalışma kitapları üretiyor ya da yeniden hesaplıyorsa, Delphi ve C++Builder için HotXLS Excel component bu indekslenmiş bağımlılık grafiğini, hem classic hem XLSX çalışma kitabı sınıflarının yeniden hesaplama motorunda taşıyor