string - 从字符数组合并键值列表的有效方法

Question

在我们的一个应用程序的核心，我们必须合并键值列表。因为这个合并函数一直被调用，所以它必须尽可能快。以内存换取额外速度是可以接受的。

我们的应用程序是用 Delphi 编写的，因此我将引用一些 Delphi 特定的例程，但我想这个问题可能与用于解决它的语言无关。

要求

• 两个输入键值列表(“原始”和“更新”)作为指向字符数组的指针传入，例如'Key1=Value1'#13#10'Key2=Value2'#10'Key3=Value3'#13#10#10'Key4=Value4'。请注意，键和值由“=”分隔，键值对可以由字符 #13 和 #10 的任意组合分隔。
• 在输出中，键值对将始终由 #13#10 分隔。
• 输出中键值对的顺序无关紧要。
• 如果其中一个输入包含重复键，可以保留副本。然而，只保留一个键也是可以接受的，因为一开始就不应该有重复项。如果原始和更新包含相同的键，则更新的值将被保留。
• 我只处理 ASCII 字符。

我的解决方案

我的解决方案的核心是一个字典，它将一个键(字符串)映射到一个指针和包含该值的内存块的长度。此 map 按键排序。它可以在使用前重置并在合并例程的多次调用之间共享，因此我们节省了映射及其条目的内存分配和释放。 对每个输入键值列表执行以下操作:

• 遍历输入中的每个字符。
• 遇到键值分隔符时，提取键并向前扫描到值的末尾。
• 如果key存在于map中，更新我们通过提前扫描确定的值指针和长度。
• 跳过值后的所有 #13 和 #10 字符以到达下一个键的开头。
• 重复直到输入结束。

填充 map 后，通过遍历 map 、连接键、键值分隔符、基于给定位置和长度的值的副本以及每个条目的“\r\n”来构建输出字符串.不要忘记最后的空终止符。

优化思路

我尝试了以下操作，使用 QueryPerformanceCounter Windows API 函数测量性能。

• 我最初认为，当键的数量很少时，保持 map 排序的工作量太大了。然而，事实证明，即使只有两个或三个键，保持 map 排序也会产生几乎相同的性能。
• 映射包含作为字符串的键，这意味着我必须从字符数组中提取键并使用 Delphi 的 SetString 例程从中创建一个字符串。我的理解方式Delphi strings ，这必须涉及内存复制，我想避免这种情况。但是，仅存储 key 的指针和长度，然后使用 CompareString routine from the Windows unit 比较它们比将键提取为字符串并使用 SysUtils 中的 CompareStr 进行比较要慢得多。我认为这是因为 CompareString 实现速度较慢。是否可能有不同的例程来比较接受指针和长度作为其输入的字符串？不过我还没有找到。
• 为了保持 map 排序，我使用了 Classes.TStringList 中的排序算法，如果我没记错的话，这是一种快速排序。是否有更适合这种情况的不同排序算法？

您还能想到哪些其他优化甚至完全不同的算法？

Answer 1

据我所知，您的解决方案很好，很难改进。

我唯一的建议是对字典使用散列而不是排序的键列表和二进制搜索。您可以使用 Delphi 的 TDictionary<TKey,TValue>假设其表现是合理的。对于 TKey您将使用自定义记录来实现您的 map (位置和长度)。同样对于 TValue .您必须实现自己的比较器，这可以很容易地完成，而不会产生堆分配。

说了这么多，您是否 100% 确定堆分配对于这个应用程序来说就像您认为的那样邪恶？您应该使用 TDictionary<string,string> 尝试一个简单的实现并对应用程序进行概要分析以证明它在字典代码中花费了大量时间。这种方法的另一个好处是，如果堆分配确实是一个问题，您可以使用 string基于版本作为测试目的的引用实现。您的基于指针偏移量+长度的版本肯定是错误工厂。