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

Answer 1

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

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

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

Answer 2

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

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

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

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