我不确定这值得尝试进行深度优化。你可以使用二分查找实现,但其效果会受到相当大的限制。我们讨论的元素数量有多少?
目标列表中没有无法匹配的元素
假设列表已经排序,并且在target
中不存在不能与source
匹配的元素:
static List<string>[] FindMatches(string[] source, string[] target)
{
List<string>[] matches = new List<string>[source.Length];
for (int i = 0; i < matches.Length; i++)
matches[i] = new List<string>();
int s = 0;
for (int t = 0; t < target.Length; t++)
{
while (!MatchName(source[s], target[t]))
{
s++;
if (s >= source.Length)
return matches;
}
matches[s].Add(target[t]);
}
return matches;
}
存在不匹配元素
如果在target
中存在没有与source
匹配的元素,上述方法将会失效(如果这些元素不在target的末尾)。为了解决这个问题,最好采用不同的比较实现方式。我们需要它返回“小于”、“等于”或“大于”,就像排序时使用的Comparer一样,而不是一个布尔值:
static List<string>[] FindMatches(string[] source, string[] target)
{
List<string>[] matches = new List<string>[source.Length];
for (int i = 0; i < matches.Length; i++)
matches[i] = new List<string>();
int s = 0;
for (int t = 0; t < target.Length; t++)
{
int m = CompareName(source[s], target[t]);
if (m == 0)
{
matches[s].Add(target[t]);
}
else if (m > 0)
{
s++;
if (s >= source.Length)
return matches;
t--;
}
}
return matches;
}
static int CompareName(string source, string target)
{
return target[0] - source[0];
}
两种算法本质上是相同的。如您所见,当不再找到匹配项时,您只需一次循环遍历目标元素并将索引前移至源数组。
如果源元素数量有限,则可能值得进行更智能的搜索。如果源元素数量也很大,则这样做的所谓好处会减少。
另一方面,在我的机器上,第一个算法在Debug模式下使用100万个目标元素仅需0.18秒。第二个算法甚至更快(0.03秒),但这是因为执行了更简单的比较。如果您需要比较所有内容直到第一个空格字符,那么速度会明显变慢。