Sortieralgorithmus für Excel / SharedStrings

10

In Excel "komprimieren" sie Zeichenfolgen zu einer numerischen Zuordnung (obwohl ich nicht sicher bin, ob das Wort "Komprimieren" in diesem Fall korrekt ist). Hier ist ein Beispiel, das unten gezeigt wird:

Geben Sie hier die Bildbeschreibung ein

Dies hilft zwar dabei, die Gesamtgröße der Dateien und den Speicherbedarf zu verringern, aber wie sortiert Excel dann nach einem Zeichenfolgenfeld? Würde jede einzelne Zeichenfolge die Lookup-Zuordnung durchlaufen müssen? Und wenn ja, würde dies nicht die Kosten für eine Sortierung in einem String-Feld erheblich erhöhen / verlangsamen (was wäre, wenn es 1M-Werte gäbe, wären es 1M-Key-Lookups nicht trivial). Zwei Fragen dazu:

  1. Werden gemeinsam genutzte Zeichenfolgen in der Excel-Anwendung selbst oder nur beim Speichern der Daten verwendet?
  2. Was wäre dann ein Beispielalgorithmus, um auf dem Feld zu sortieren? Jede Sprache ist in Ordnung (c, c #, c ++, Python).
David542
quelle
Ich werde auch an einer sachkundigen Antwort darauf interessiert sein. Ich kann nur vermuten, dass es etwas mit Speicher-Caching zu tun hat, aber leicht falsch sein kann.
PeterT
Ich denke, dass die Tatsache, dass diese Zuordnung in der physischen XML-Darstellung eines Dokuments vorhanden ist, unabhängig davon ist, wie Excel die Daten zur Laufzeit intern darstellt. Ich würde glauben, dass es rechnerisch effizienter ist, Datenspalten auf rohe Weise darzustellen (obwohl dies auf viele Arten geschehen kann).
Alxrcs
@alxrcs Gibt es Dokumente oder Bücher, die in die Interna von Excel aufgenommen werden, ähnlich wie bei SQLServer? amazon.com/Pro-Server-Internals-Dmitri-Korotkevitch/dp/… , oder ist es im Grunde eine Black Box außerhalb des MS-Teams?
David542
Ich bin mir nicht sicher, sorry. Sie können online einige Spezifikationen für die Dateiformate finden, aber ich denke nicht, dass Details zu Excel-Laufzeit-Interna so einfach zu finden sind.
Alxrcs
Wie auch immer, von Ihrer zweiten Frage aus vermute ich, dass Sie mehr an der Theorie als an den Excel-Besonderheiten interessiert sind, stimmt das?
Alxrcs

Antworten:

0

Ich kann nicht herausfinden, wie genau Excel Zellen mit SharedStringTableElementen im Speicher zur Laufzeit speichert, aber das Speichern als Index des Elements in SharedStringTableerfordert nur eine zusätzliche Dereferenzierung, um darauf zuzugreifen, vorausgesetzt, die Elemente werden als Array gespeichert. Ich vermute also, dass dies so gemacht wird. Dies ist der einfachste und einzige Weg, um es schneller zu machen, ist die Laufzeitdarstellung von SharedStringTablebereits nach Elementen sortierten. In diesem Fall entspricht das Sortieren nach einem Index dem Sortieren nach dem Wert. Dieser Ansatz macht den Einfügevorgang jedoch kostspielig, da beim Einfügen einer neuen Zeichenfolge in die Mitte der Tabelle alle Indizes größer sind, als sie inkrementiert werden sollten, und die Anzahl solcher Zellen im Dokument bis zu allen sehr groß sein kann Zellen, die sich auf beziehen SharedStringTable.

Wenn die Zellen dieselben Indizes wie in der Datei enthalten, sortieren Sie die durch den columnValueVektor dargestellten Zellen anhand der Zeichenfolgen, auf die sie zeigen, im sharedStringsVektor (in C ++, da Sie angegeben haben, dass es keinen Unterschied gibt) zu einem Preis von 2 zusätzliche Dereferenzen pro Vergleichsoperation:

// sort indexes from columnValue based on comparing values in sharedStrings
sort(columnValue.begin(), columnValue.end(), 
     [&sharedStrings](size_t i1, size_t i2){return sharedStrings[i1] < sharedStrings[i2];});

Es war nicht im OP, aber die Reverse- SharedStringTableLookup-Operation ist langsam und das Zwischenspeichern von Elementen in ein Wörterbuch hilft.

isp-zax
quelle
0

Microsoft Excel Shared Strings-Tabelle

Die Tabelle für gemeinsam genutzte Zeichenfolgen ist ein Open XML-Standard, wie er durch den ISO-Standard definiert ist - ISO / IEC 29500-1: 2016 (E)

Offizielle Definition von Shared Strings (zitiert aus dem ISO-Dokument)

Shared String Table

Zeichenfolgenwerte können direkt in Tabellenzellenelementen gespeichert werden. Das Speichern des gleichen Werts in mehreren Zellenelementen kann jedoch zu sehr großen Arbeitsblattteilen führen, was möglicherweise zu Leistungseinbußen führen kann. Die Tabelle für gemeinsam genutzte Zeichenfolgen ist eine indizierte Liste von Zeichenfolgenwerten, die in der gesamten Arbeitsmappe verwendet werden. Dadurch können Implementierungen Werte nur einmal speichern.

Der ISO-Standard für Shared Strings kann von heruntergeladen werden

https://standards.iso.org/ittf/PubliclyAvailableStandards/c071691_ISO_IEC_29500-1_2016.zip

Antworten auf die Fragen zu diesem Thema

Frage 1: Werden gemeinsam genutzte Zeichenfolgen in der Excel-Anwendung selbst oder nur beim Speichern der Daten verwendet?

Antwort: Freigegebene Zeichenfolgen werden von Excel nur zum Zeitpunkt des Speicherns des Dokuments IE verwendet, nur um die Tabelle als Datei im Speicher zu speichern.

Wenn die Datei jedoch zur Anzeige geöffnet wird, werden die Zellen mit tatsächlichen Zeichenfolgenwerten gefüllt, die aus der Tabelle der gemeinsam genutzten Zeichenfolgen abgerufen werden.

- -

Frage 2: Was wäre dann ein Beispielalgorithmus, um auf dem Feld zu sortieren? Jede Sprache ist in Ordnung (c, c #, c ++, Python).

Antwort: Für eine Anwendung wie Excel ist eine spezielle proprietäre Variante der Schnellsortierung wahrscheinlich der wahrscheinlichste Algorithmus, der zum Sortieren nach Zeichenfolgenwerten verwendet wird.

Excel hat ein Limit von 1.048.576 Zeilen. Für diese Größe ist Quick Sort definitiv ein Gewinner. Eine schnelle Sortierung kann zu einem sehr effizienten Ergebnis für einen Datensatz dieser Größenordnung führen.

Hier ist der Link zur Implementierung von Quick Sort in C ++ zum Sortieren von Zeichenfolgen:

http://www.cplusplus.com/forum/beginner/101599/

Gopinath
quelle
2
Eine schnelle Sortierung würde sich auf der Zeichenfolge selbst befinden. Sie müssten jedoch einen Zeiger dereferenzieren oder eine Lookup-Map millionenfach erstellen, nein? Ich denke, diese Antwort sagt im Grunde nur "Ja, es macht Shared Strings. Hier erfahren Sie, wie Sie eine Sortierung ohne Shared Strings durchführen."
David542
2
Die Tabelle mit gemeinsam genutzten Zeichenfolgen wird nur zum Speichern des Dateiinhalts auf der Festplatte verwendet. Der ISO-Standard legt nicht fest, wie die Zellen beim Öffnen der Anwendung ausgefüllt werden müssen. Wenn Zellen mit einer Kopie des Zeichenfolgenwerts gefüllt sind, der aus der Tabelle der gemeinsam genutzten Zeichenfolgen extrahiert wurde, kann die Dereferenzierung vermieden werden.
Gopinath
1
Aha. Ja, mein Hauptinteresse hier war, wie es im Speicher behandelt wird, außerhalb des Aspekts von / nach Speicher. Haben Sie einen Einblick in diesen Teil davon?
David542
Bei der Excel-Sortierung muss der Benutzer die Sortierreihenfolge als Liste von Spalten angeben (Beispiel: Sortieren nach Spalte A, dann nach B, dann nach C, dann nach D). Angenommen, die Spalte A enthält doppelte Zeichenfolgen. Während des Sortierens werden alle Zeilen mit demselben Wert für Spalte A nach Werten von 'Spalte B' sortiert. Wenn Zellen von B auch doppelte Werte enthalten, erfolgt die Sortierung in Spalte C usw., bis die Spalte mit eindeutigen Werten gefunden wird. Wenn keine der Spalten eindeutige Werte hat, werden die Zeilen übersprungen.
Gopinath