Algorytm sortowania dla Excel / SharedStrings

W programie Excel „kompresują” ciągi do odwzorowania numerycznego (choć nie jestem pewien, czy w tym przypadku słowo kompresja jest poprawne). Oto przykład pokazany poniżej:

Chociaż pomaga to zmniejszyć całkowity rozmiar pliku i wielkość pamięci, w jaki sposób program Excel sortuje według pola ciągu? Czy każdy ciąg musiałby przejść przez mapowanie odnośników: a jeśli tak, to nie zwiększyłoby to znacznie kosztu / spowolnienia podczas sortowania na polu ciągów (co gdyby były wartości 1M, wyszukiwania kluczy 1M nie byłyby trywialny). Dwa pytania na ten temat:

1. Czy w samej aplikacji Excel używane są wspólne ciągi, czy tylko podczas zapisywania danych?
2. Jaki byłby wówczas przykładowy algorytm do sortowania na polu? Każdy język jest w porządku (c, c #, c ++, python).

Nie mogę znaleźć, jak dokładnie Excel przechowuje komórki z SharedStringTableelementami w pamięci w czasie wykonywania, ale przechowywanie ich jako indeksu elementu SharedStringTablewymaga tylko jednej dodatkowej dereferencji, aby uzyskać do nich dostęp, przy założeniu, że elementy są przechowywane jako tablica. Domyślam się, że tak to się robi. Jest to najprostszy sposób, a jedynym sposobem na przyspieszenie jest przedstawienie w czasie wykonywania reprezentacji SharedStringTablejuż posortowanych według elementów. W takim przypadku sortowanie według indeksu jest równoważne sortowaniu według wartości. Takie podejście powoduje jednak, że operacja wstawiania jest kosztowna, ponieważ gdy nowy ciąg jest wstawiany do środka tabeli, wszystkie indeksy większe niż powinny być zwiększane, a liczba takich komórek w dokumencie może być bardzo duża, aż do wszystkich komórki odnoszące się do SharedStringTable.

Jeśli komórki zawierają indeksy takie same jak w pliku, oto jak posortować komórki reprezentowane przez columnValuewektor na podstawie ciągów, które wskazują na przechowywane w sharedStringswektorze (w C ++, ponieważ powiedziałeś, że nie ma różnicy) kosztem 2 dodatkowe dereferencje na operację porównania:

// 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];});

Nie było go w OP, ale SharedStringTableoperacja wyszukiwania wstecznego jest powolna i pomaga buforowanie elementów w słowniku.

Tabela wspólnych ciągów Microsoft Excel

Tabela wspólnych ciągów jest zgodna ze standardem Open XML, zgodnie z definicją normy ISO - ISO / IEC 29500-1: 2016 (E)

Oficjalna definicja wspólnych ciągów (cytowana z dokumentu ISO)

Wspólna tabela ciągów

Wartości ciągów mogą być przechowywane bezpośrednio w elementach komórki arkusza kalkulacyjnego; jednak przechowywanie tej samej wartości w wielu elementach komórki może skutkować bardzo dużymi częściami arkusza roboczego, co może skutkować pogorszeniem wydajności. Shared String Table to zindeksowana lista wartości ciągów, wspólna dla skoroszytu, która umożliwia implementacjom przechowywanie wartości tylko raz.

Standard ISO dotyczący wspólnych ciągów można pobrać z

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

Odpowiedzi na pytania na ten temat

Pytanie 1: Czy współużytkowane ciągi są używane w samej aplikacji Excel, czy tylko podczas zapisywania danych?

Odpowiedź: Udostępnione ciągi są używane przez program Excel tylko podczas zapisywania dokumentu, IE, tylko w celu przechowywania arkusza kalkulacyjnego jako pliku na dysku.

Jednak po otwarciu pliku do wyświetlenia komórki zapełniane są rzeczywistymi wartościami ciągów pobranymi z tabeli wspólnych ciągów.

-

Pytanie 2: Jaki byłby wówczas przykładowy algorytm do sortowania na polu? Każdy język jest w porządku (c, c #, c ++, python).

Odpowiedź: W przypadku aplikacji takich jak Excel wydaje mi się, że specjalna zastrzeżona odmiana szybkiego sortowania jest najbardziej prawdopodobnym algorytmem do sortowania według wartości ciągu.

Program Excel ma limit 1 048 576 wierszy. W przypadku tego rozmiaru szybkie sortowanie jest zdecydowanie zwycięzcą. Szybkie sortowanie może dać bardzo wydajny wynik dla zestawu danych tej wielkości.

Oto link do implementacji szybkiego sortowania w C ++ do sortowania ciągów:

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