Эффективный способ объединения списков значений ключей из символьных массивов

Question

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

Наше приложение написано на 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» для каждой записи.Не забывайте последний нулевой терминатор.

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Обновлено: исправлен предзаказ на заказ