Блог

В основе одного из наших приложений лежит необходимость объединения списков значений ключей. Поскольку эта функция слияния вызывается постоянно, она должна выполняться как можно быстрее. Допустимо использовать память для увеличения скорости.

Наше приложение написано на Delphi, поэтому я буду ссылаться на некоторые специфические процедуры Delphi, но я полагаю, что эта проблема может представлять интерес независимо от языка, используемого для ее решения.

Требования

• Два входных списка значений ключей («оригинал» и «обновление») передаются как указатели на символьные массивы, например 'Key1=Value1'#13#10'Key2=Value2'#10'Key3=Value3'#13#10#10'Key4=Value4' . Обратите внимание, что ключ и значение разделяются символом ‘=’, а пары значений ключей могут быть разделены любой комбинацией символов #13 и #10 .
• В выходных данных пары значений ключей всегда будут разделены #13#10 символом .
• Порядок пар значений ключей в выходных данных не имеет значения.
• Если один из входных данных содержит дубликат ключа, можно сохранить дубликат. Однако сохранение только одного ключа также приемлемо, поскольку дубликатов не должно быть там в первую очередь. Если оригинал и обновление содержат один и тот же ключ, значение из обновления должно быть сохранено.
• Я имею дело только с символами ASCII.

Мое решение

В основе моего решения лежит словарь, который сопоставляет ключ (строку) с указателем и длиной блока памяти, содержащего значение. Эта карта сортируется по ключам. Его можно сбросить перед использованием и использовать совместно для нескольких вызовов процедуры слияния, поэтому мы экономим на выделении и освобождении памяти для карты и ее записей. Выполните следующие действия для каждого списка входных значений ключей:

• Выполните итерацию по каждому символу во входных данных.
• При обнаружении разделителя значений ключей извлеките ключ и выполните сканирование до конца значения.
• Если ключ существует в карте, обновите указатель значения и длину, которые мы определили путем предварительного сканирования.
• Пропустите все #13 #10 символы и после значения, чтобы перейти к началу следующего ключа.
• Повторяйте до конца ввода.

После заполнения карты создайте выходную строку, выполнив итерацию по карте, объединив ключ, разделитель значений ключа, копию значения на основе заданной позиции и длины и » r n» для каждой записи. Не забывайте о конечном нулевом терминаторе.

Идеи для оптимизации

Я пробовал следующие действия, измеряя производительность с помощью функции API Windows QueryPerformanceCounter.

• Изначально я думал, что сохранение отсортированной карты — это слишком много работы, когда количество ключей невелико. Однако, как оказалось, даже при использовании только двух или трех ключей сортировка карты привела к практически одинаковой производительности.
• Карта содержит ключ в виде строки, что означает, что я должен извлечь ключ из массива символов и создать из него строку, используя процедуру setString Delphi. Насколько я понимаю строки Delphi, это должно включать копирование в память, чего я хотел бы избежать. Однако сохранение только указателя и длины ключа и последующее их сравнение с использованием процедуры CompareString из модуля Windows было намного медленнее, чем извлечение ключей в виде строк и сравнение их с использованием CompareStr из SysUtils. Я предполагаю, что это связано с тем, что реализация CompareString выполняется медленнее. Может быть, существует другая процедура сравнения строк, которая принимает указатели и длину в качестве входных данных? Однако я его не нашел.
• Чтобы сохранить сортировку карты, я использую алгоритм сортировки по классам.TStringList, который является быстрой сортировкой, если я не ошибаюсь. Может быть, есть другой алгоритм сортировки, который лучше подходит для этого сценария?

Какие другие оптимизации или даже совершенно другие алгоритмы вы могли бы придумать?

Насколько я могу судить, ваше решение хорошее, и его будет сложно улучшить.

Единственное предложение, которое я бы сделал, это использовать хеширование для словаря, а не отсортированного списка ключей и двоичного поиска. Вы могли бы использовать Delphi TDictionary<TKey,TValue> , предполагая, что его производительность была разумной. Для TKey вас будет использоваться пользовательская запись, реализующая вашу карту (позиция и длина). Аналогично для TValue . Вам пришлось бы реализовать свой собственный компаратор, который можно было бы сделать достаточно легко, не требуя выделения кучи.

Сказав все это, вы на 100% уверены, что распределение кучи так же плохо, как вы думаете, для этого приложения? Вы должны попробовать наивную реализацию с использованием TDictionary<string,string> и профилировать приложение, чтобы доказать, что оно тратит значительное время на код словаря. Другим преимуществом такого подхода было бы то, что, если действительно выделение кучи было проблемой, вы могли бы использовать string базовую версию в качестве эталонной реализации для целей тестирования. Ваша версия, основанная на смещении указателя длине, обязательно будет фабрикой ошибок.

Предложение «Эта карта сортируется по ключам» и фраза «сохранение отсортированной карты» и прочее, указывающее на указатели и длины, звучит так, как будто вы сортируете массив указателей после каждой вставки в массив. Если это так, вы можете обнаружить, что Timsort выполняется быстрее, чем Quicksort.

Поддержание сбалансированного дерева поиска, вероятно, было бы лучшим подходом. Дерево формата АА легко кодируется и имеет производительность, аналогичную красно-черному дереву, т. Е. O (ln n) вставок, поисков и удалений. Если вы действительно сортируете массив после каждой вставки, использование дерева поиска сократит время вставки с O (n ln n) до O (ln n).

Чтобы считывать ключи по порядку, используйте обход по порядку, который выполняется в наихудшем случае времени O (n ln n).

Обновлено: исправлен предварительный заказ на порядок