Excel / SharedStrings 的排序算法

Question

在 Excel 中，它们将字符串“压缩”为数字映射（尽管我不确定在这种情况下 compress 这个词是否正确）。下面是一个示例：

虽然这有助于减少整体文件大小和内存占用，但 Excel 如何对字符串字段进行排序？是否每个字符串都需要通过查找映射：如果是这样，那不会大大增加/减慢对字符串字段进行排序的成本（如果有 1M 个值，1M 键查找将不会是琐碎的）。关于这个的两个问题：

1. 共享字符串是在 Excel 应用程序本身中使用，还是仅在保存数据时使用？
2. 那么在场上排序的示例算法是什么？任何语言都可以（c、c#、c++、python）。

Answer 1

我无法找到 ExcelSharedStringTable在运行时如何在内存中存储带有元素的单元格，但将它们存储为项目的索引SharedStringTable只需要一次额外的取消引用即可访问它们，假设元素存储为数组。所以我的猜测是它是这样完成的。这是最简单的方法，也是使其更快的唯一方法是拥有SharedStringTable已按元素排序的运行时表示。在这种情况下，按索引排序相当于按值排序。然而，这种方法使得插入操作成本高昂，因为当将新字符串插入到表的中间时，所有大于它应增加的索引都会增加，并且文档中此类单元格的数量可能非常大，最多可达所有索引。细胞指的是SharedStringTable.

如果单元格包含与文件中相同的索引，则以下是如何columnValue根据它们指向存储在向量中的字符串对由sharedStrings向量表示的单元格进行排序（在 C++ 中，因为你说没有区别），成本为 2每个比较操作的额外取消引用：

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

它不在OP中，但反向SharedStringTable查找操作很慢，将元素缓存到字典中会有所帮助。