Оптимизация объединения двух списков ключ-значение в Delphi: торговля памятью за скорость

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

Оптимизации

Я попробовал несколько вещей, измеряя производительность с помощью функции QueryPerformanceCounter Windows API. Оказалось, что даже с небольшим количеством ключей (два или три), поддержание отсортированного словаря дает почти такую же производительность. Сравнение ключей с помощью функции CompareString из Windows API было намного slower, чем извлечение ключей как строк и сравнение их с помощью CompareStr из SysUtils. Я предполагаю, что это происходит из-за более медленной реализации CompareString. Есть ли другой способ сравнить строки, который принимает указатели и длину в качестве входных данных? Я не нашел такой.

Чтобы сохранить словарь отсортированным, я использую алгоритм сортировки из Classes.TStringList, который, как я понимаю, является быстрой сортировкой. Есть ли другой алгоритм сортировки, лучше подходящий для этой ситуации?

Альтернативный ответ

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

Наше приложение написано на Delphi, но, я думаю, эта проблема может быть интересной независимо от используемого языка. Входные списки ключей-значений представлены в виде указателей на массивы символов. Например, 'Key1=Value1'#13#10'Key2=Value2'#10'Key3=Value3'#13#10#10'Key4=Value4'. Каждое значение ключа-значения разделено символом '=' и может быть разделено любым сочетанием символов #13 и #10. В выходном списке ключи-значения всегда разделены #13#10. Порядок ключей-значений в выходном списке не имеет значения. Если один из входных списков содержит дубликат ключа, это не проблема, но мы также можем оставить только один ключ, так как дубликаты не должны присутствовать в списке изначально. Если оригинальный и обновленный списки содержат одинаковый ключ, значение из обновленного списка должно быть сохранено. Мы работаем только с символами ASCII.

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

Для каждого входного списка ключей-значений мы выполняем следующие действия:

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

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

Я попробовал несколько вещей, измеряя производительность с помощью функции QueryPerformanceCounter Windows API. Оказалось, что даже с небольшим количеством ключей (два или три), поддержание отсортированного словаря дает почти такую же производительность. Сравнение ключей с помощью функции CompareString из Windows API было намного slower, чем извлечение ключей как строк и сравнение их с помощью CompareStr из SysUtils. Я предполагаю, что это происходит из-за более медленной реализации CompareString. Есть ли другой способ сравнить строки, который принимает указатели и длину в качестве входных данных? Я не нашел такой.

Чтобы сохранить словарь отсортированным, я использую алгоритм сортировки из Classes.TStringList, который, как я понимаю, является быстрой сортировкой. Есть ли другой алгоритм сортировки, лучше подходящий для этой ситуации?

Подтвержденный ответ

На данный момент ваше решение кажется хорошим и сложно будет его улучшить. Единственное предложение, которое я могу сделать, — использовать хеширование для словаря вместо отсортированного списка ключей и бинарного поиска. Вы можете использовать Delphi's `` TDictionary

Создано по материалам из источника по ссылке.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Сортировка и Фильтр ::