Алгоритм сортировки для Excel / SharedStrings

В Excel они «сжимают» строки в числовое отображение (хотя я не уверен, что в этом случае слово сжато правильно). Вот пример, показанный ниже:

Хотя это помогает уменьшить общий размер файла и объем памяти, как тогда Excel выполняет сортировку по строковому полю? Должна ли каждая строка проходить сопоставление поиска: и если это так, не приведет ли это к значительному увеличению / замедлению сортировки строкового поля (что, если бы были значения 1M, поиск ключей 1M не был бы тривиальна). Два вопроса по этому вопросу:

1. Используются ли общие строки в самом приложении Excel или только при сохранении данных?
2. Какой будет пример алгоритма для сортировки по полю тогда? Любой язык в порядке (c, c #, c ++, python).

Я не могу найти, как именно Excel хранит ячейки с SharedStringTable элементами в памяти во время выполнения, но для их сохранения в качестве индекса элемента 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операция обратного поиска медленная и помогает кэширование элементов в словаре.

Таблица общих строк Microsoft Excel

Таблица общих строк соответствует стандарту Open XML, как определено стандартом ISO - ISO ISO / IEC 29500-1: 2016 (E)

Официальное определение общих строк (цитируется по документу ISO)

Таблица общих строк

Строковые значения могут храниться непосредственно внутри элементов ячейки электронной таблицы; однако сохранение одного и того же значения внутри нескольких элементов ячейки может привести к очень большим частям рабочего листа, что может привести к снижению производительности. Shared String Table - это индексированный список строковых значений, общий для всей рабочей книги, который позволяет реализациям сохранять значения только один раз.

Стандарт ISO для общих строк можно загрузить с

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

Ответы на вопросы по этой теме

Вопрос 1. Используются ли общие строки в самом приложении Excel или только при сохранении данных?

Ответ: Общие строки используются Excel только во время сохранения документа, IE, только с целью сохранения электронной таблицы в виде файла в хранилище.

Однако когда файл открывается для отображения, ячейки заполняются фактическими значениями строк, извлеченными из таблицы общих строк.

-

Вопрос 2: Какой будет пример алгоритма для сортировки по полю? Любой язык в порядке (c, c #, c ++, python).

Ответ: Я полагаю, что для такого приложения, как Excel, специальный проприетарный вариант быстрой сортировки является наиболее вероятным алгоритмом для сортировки по строковым значениям.

Excel имеет ограничение в 1 048 576 строк. Для этого размера быстрая сортировка определенно является победителем. Быстрая сортировка может дать очень эффективный результат для набора данных такого масштаба.

Вот ссылка на реализацию быстрой сортировки в C ++ для сортировки строк:

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