在我们的一个应用程序的核心，我们必须合并键值列表。因为这个归并函数一直被调用，所以它必须尽可能快。用内存换取额外的速度是可以接受的。
我们的应用程序是用Delphi编写的，所以我将引用一些Delphi特定的例程，但我想这个问题可能与用于解决它的语言无关。
需求- 两个输入键值列表("original"one_answers"update")作为指向字符数组的指针传入，例如
'Key1=Value1'#13#10'Key2=Value2'#10'Key3=Value3'#13#10#10'Key4=Value4'。注意键和值用'='分隔，键值对可以用字符#13和#10的任意组合分隔。 - 在输出中，键值对总是用
#13#10分隔。 - 键值对在输出中的顺序不重要
- 如果其中一个输入包含重复的密钥，则可以保留重复的密钥。但是，只保留一个键也是可以接受的，因为一开始就不应该有重复的键。如果原始密钥和更新的密钥包含相同的密钥，则保留更新的值。
- 我只处理ASCII字符。
我的解决方案的核心是一个字典，它将键(字符串)映射到指向包含该值的内存块的指针和长度。这张地图是按键排序的。它可以在使用之前重置，并在合并例程的多个调用之间共享，因此我们节省了映射及其条目的内存分配和释放。对每个输入键值列表执行以下操作:
- 遍历输入中的每个字符。
- 当遇到键值分隔符时，提取键并向前扫描到值的末尾。
- 如果键在map中存在，则更新我们通过扫描确定的值指针和长度。
- 跳过值后面的所有
#13和#10字符，进入下一个键的开始。 - 重复，直到输入结束
填满映射后，通过遍历映射来构建输出字符串，将键、键值分隔符、基于给定位置和长度的值副本连接起来，并为每个条目设置"rn"。不要忘记最后的空终止符。
优化思路
我尝试了以下事情，使用QueryPerformanceCounter Windows API函数测量性能。
- 我最初认为保持地图排序是太多的工作，当键的数量很少。然而，事实证明，即使只有两个或三个键，保持地图排序也会产生几乎相同的性能。
- 映射包含键作为字符串，这意味着我必须从字符数组中提取键，并使用Delphi的SetString例程从中创建字符串。我理解Delphi字符串的方式，这必须涉及内存副本，这是我想避免的。然而，仅仅存储一个指针和一个键的长度，然后使用来自Windows单元的CompareString例程进行比较，要比从SysUtils中提取键作为字符串并使用CompareStr进行比较慢得多。我认为这是因为CompareString的实现比较慢。有没有可能有一个不同的程序来比较字符串，接受指针和长度作为其输入?但是我还没有找到。
- 保持地图排序，我使用的排序算法从类。TStringList是一个快速排序，如果我没弄错的话。有没有一种不同的排序算法更适合这种情况?
你还能想到什么其他的优化甚至完全不同的算法吗?
就我所知，你的解决方案很好，很难改进。
我唯一的建议是对字典使用哈希，而不是对键的排序列表和二进制搜索。您可以使用Delphi的TDictionary<TKey,TValue>，假设它的性能是合理的。对于TKey，您将使用自定义记录实现您的地图(位置和长度)。TValue也是如此。你必须实现你自己的比较器，这可以很容易地完成，而不会引起堆分配。
说了这么多，你100%确定堆分配像你想象的那样糟糕吗?您应该使用TDictionary<string,string>尝试一个简单的实现，并对应用程序进行分析，以证明它在字典代码中花费了大量时间。这种方法的另一个好处是，如果堆分配确实是一个问题，您可以使用基于string的版本作为测试目的的参考实现。你的指针偏移量+长度为基础的版本肯定是一个bug工厂
句子"This map is sorted on The keys"和短语"keep The map sorted"以及指针和长度之类的东西，听起来像是在每次插入数组之后对指针数组进行排序。如果是这样，您可能会发现Timsort比Quicksort运行得快。
维护一个平衡的搜索树可能是更好的方法。AA树易于编码，并且具有与红黑树相似的性能，即。， 0 (ln n)用于插入、查找和删除。如果你真的在每次插入之后对数组进行排序，使用搜索树可以将插入时间从O(n ln n)减少到O(ln n)。
要按顺序读取键，使用顺序遍历，最坏情况下运行时间为O(n ln n)。
更新:更正预购到订单