我有两个字符串列表，一个是源列表，一个是目标列表。源列表中的项在目标列表中可能有0到n次匹配，但不会有重复匹配。
考虑到两个列表都已排序，如何在性能方面最有效地进行匹配。
例如：
source = {"1", "2", "A", "B", ...}
target = {"1 - new music", "1 / classic", "1 | pop", "2 edit", "2 no edit", "A - sing", "B (listen)", ...}
MatchName的方法。如果您将要进行更多优化的搜索，可以使用新函数NameMatch，它只比较两个字符串并返回一个布尔值。我不确定这值得尝试进行深度优化。你可以使用二分查找实现，但其效果会受到相当大的限制。我们讨论的元素数量有多少？
假设列表已经排序，并且在target中不存在不能与source匹配的元素：
static List<string>[] FindMatches(string[] source, string[] target)
{
// Initialize array to hold results
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)
{
// Initialize array to hold results
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)
{
// Whatever comparison you need here, this one is really basic :)
return target[0] - source[0];
}
两种算法本质上是相同的。如您所见，当不再找到匹配项时，您只需一次循环遍历目标元素并将索引前移至源数组。
如果源元素数量有限，则可能值得进行更智能的搜索。如果源元素数量也很大，则这样做的所谓好处会减少。
另一方面，在我的机器上，第一个算法在Debug模式下使用100万个目标元素仅需0.18秒。第二个算法甚至更快（0.03秒），但这是因为执行了更简单的比较。如果您需要比较所有内容直到第一个空格字符，那么速度会明显变慢。
NameMatch 签名。你需要一个完整的比较器(小于、等于、大于)，就像你的例子一样。 - Thorarin已编辑，重写，未经测试，应具有O（源+目标）性能。
使用方式为MatchMaker.Match（source，target）。ToList（）;
public static class MatchMaker
{
public class Source
{
char Term { get; set; }
IEnumerable<string> Results { get; set; }
}
public static IEnumerable<Source> Match(IEnumerable<string> source, IEnumerable<string> target)
{
int currentIndex = 0;
var matches = from term in source
select new Source
{
Term = term[0],
Result = from result in target.FromIndex(currentIndex)
.TakeWhile((r, i) => {
currentIndex = i;
return r[0] == term[0];
})
select result
};
}
public static IEnumerable<T> FromIndex<T>(this IList<T> subject, int index)
{
while (index < subject.Count) {
yield return subject[index++];
}
}
}
var matches = from result in target
from term in source
where result[0] == term[0]
select new {
Term: term,
Result: result
};
我反对过早优化。
string[] source = {"1", "2", "A", "B" };
string[] target = { "1 - new music", "1 / classic", "1 | pop", "2 edit", "2 no edit", "A - sing", "B (listen)" };
List<string>[] matches = new List<string>[source.Length];
int targetIdx = 0;
for (int sourceIdx = 0; sourceIdx < source.Length; sourceIdx++) {
matches[sourceIdx] = new List<string>();
while (targetIdx < target.Length && NameMatch(source[sourceIdx], target[targetIdx])) {
matches[sourceIdx].Add(target[targetIdx]);
targetIdx++;
}
}
for循环有一些优化，并且目标元素的数量大于源元素的数量。无论如何，差异非常小，你的版本可能更容易理解，因为它没有使用负逻辑。 - Thorarin这里有一个答案，只循环一次遍历两个列表，利用它们都已排序的逻辑作为优化。像大多数人说的那样，我不会太担心优化，因为任何这些答案都可能足够快，我会选择最易读和可维护的解决方案。
话虽如此，我需要做点什么来消磨时间，所以给你看看。以下代码的一个优点是它允许目标列表中有源列表中没有匹配项，尽管我不确定您是否需要该功能。
class Program
{
public class Source
{
private readonly string key;
public string Key { get { return key;}}
private readonly List<string> matches = new List<string>();
public List<string> Matches { get { return matches;} }
public Source(string key)
{
this.key = key;
}
}
static void Main(string[] args)
{
var sources = new List<Source> {new Source("A"), new Source("C"), new Source("D")};
var targets = new List<string> { "A1", "A2", "B1", "C1", "C2", "C3", "D1", "D2", "D3", "E1" };
var ixSource = 0;
var currentSource = sources[ixSource++];
foreach (var target in targets)
{
var compare = CompareSourceAndTarget(currentSource, target);
if (compare > 0)
continue;
// Try and increment the source till we have one that matches
if (compare < 0)
{
while ((ixSource < sources.Count) && (compare < 0))
{
currentSource = sources[ixSource++];
compare = CompareSourceAndTarget(currentSource, target);
}
}
if (compare == 0)
{
currentSource.Matches.Add(target);
}
// no more sources to match against
if ((ixSource > sources.Count))
break;
}
foreach (var source in sources)
{
Console.WriteLine("source {0} had matches {1}", source.Key, String.Join(" ", source.Matches.ToArray()));
}
}
private static int CompareSourceAndTarget(Source source, string target)
{
return String.Compare(source.Key, target.Substring(0, source.Key.Length), StringComparison.OrdinalIgnoreCase);
}
}
t--来抵消for循环中的前进，但另一种选择是使用while循环和一些糟糕的continue用法:P - Thorarin既然它们已经排序，那么这不就是一个基本的O(N)合并循环吗？
ia = ib = 0;
while(ia < na && ib < nb){
if (A[ia] < B[ib]){
// A[ia] is unmatched
ia++;
}
else if (B[ib] < A[ia]){
// B[ib] is unmatched
ib++;
}
else {
// A[ia] matches B[ib]
ia++;
ib++;
}
}
while(ia < na){
// A[ia] is unmatched
ia++;
}
while(ib < nb){
// B[ib] is unmatched
ib++;
}
我认为最好的方法是准备一个索引。就像这样（Javascript）
index = [];
index["1"] = [0,1,2];
index["2"] = [3,4];
在这种情况下，不需要非常排序的列表。
<*,*<*>>，我会给你+1。 - Kobi当你超过当前源前缀时，显然你需要停止遍历目标列表。在这种情况下，你最好使用前缀方法而不是匹配方法，这样你就可以知道当前的前缀是什么，并且如果你超过了它，就可以停止搜索目标。