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

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

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

Требования

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

Мое решение

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

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

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

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

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

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

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

string,algorithm,delphi,optimization,sorting,

4

Ответов: 2


1 принят

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

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

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


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

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

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

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

строка, алгоритм, Дельфы, оптимизация, сортировка,
Похожие вопросы