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:
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:
- Werden gemeinsam genutzte Zeichenfolgen in der Excel-Anwendung selbst oder nur beim Speichern der Daten verwendet?
- Was wäre dann ein Beispielalgorithmus, um auf dem Feld zu sortieren? Jede Sprache ist in Ordnung (c, c #, c ++, Python).
excel
algorithm
performance
sorting
compression
David542
quelle
quelle
Antworten:
Ich kann nicht herausfinden, wie genau Excel Zellen mit
SharedStringTable
Elementen im Speicher zur Laufzeit speichert, aber das Speichern als Index des Elements inSharedStringTable
erfordert 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 vonSharedStringTable
bereits 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 beziehenSharedStringTable
.Wenn die Zellen dieselben Indizes wie in der Datei enthalten, sortieren Sie die durch den
columnValue
Vektor dargestellten Zellen anhand der Zeichenfolgen, auf die sie zeigen, imsharedStrings
Vektor (in C ++, da Sie angegeben haben, dass es keinen Unterschied gibt) zu einem Preis von 2 zusätzliche Dereferenzen pro Vergleichsoperation:Es war nicht im OP, aber die Reverse-
SharedStringTable
Lookup-Operation ist langsam und das Zwischenspeichern von Elementen in ein Wörterbuch hilft.quelle
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
- -
quelle