c# - 如何组合 List 中的项目以高效地创建新项目

Question

我有一个例子，我有一个对象的名称和一堆文件名。我需要将正确的文件名与对象匹配。文件名可以包含数字和单词，由连字符 (-) 或下划线 (_) 分隔。我无法控制文件名或对象名。例如:

10-11-12_001_002_003_13001_13002_this_is_an_example.svg

本例中的对象名称只是一个字符串，代表一个数字

10001

如果文件名与对象名匹配，我需要返回 true 或 false。文件名的不同段可以单独匹配，也可以任意组合两个段。在上面的示例中，它应该适用于以下情况(不是每个真实情况，只是示例):

10001
10002
10003
11001
11002
11003
12001
12002
12003
13001
13002

而且，对于这种情况(以及其他)，我们应该返回 false:

13003

到目前为止我想出的是:

public bool IsMatch(string filename, string objectname)
{
    var namesegments = GetNameSegments(filename);
    var match = namesegments.Contains(objectname);
    return match;
}

public static List<string> GetNameSegments(string filename)
{
    var segments = filename.Split('_', '-').ToList();

    var newSegments = new List<string>();
    foreach (var segment in segments)
    {
        foreach (var segment2 in segments)
        {
            if (segment == segment2)
                continue;

            var newToken = segment + segment2;
            newSegments.Add(newToken);
        }
    }

    return segments.Concat(newSegments).ToList();
}

一个或两个片段组合起来就可以匹配，这就足够了。不应考虑三个或更多段的组合。

到目前为止这确实有效，但是否有更好的方法来做到这一点，或许无需嵌套 foreach 循环？

Answer 1

首先:不要无缘无故地更改调试过的、有效的、足够高效的代码。您的解决方案看起来不错。

但是，我们可以对您的解决方案进行一些改进。

public static List<string> GetNameSegments(string filename)

将输出设为列表会对调用者不需要的实现施加限制。应该是IEnumerable<String> .特别是因为在这种情况下调用者只关心第一个匹配项。

var segments = filename.Split('_', '-').ToList();

为什么 ToList ？列表是数组支持的。你已经有了一个数组。只需使用数组即可。

由于不再需要构建列表，我们可以将您的双循环解决方案转换为迭代器 block :

public static IEnumerable<string> GetNameSegments(string filename)
{
  var segments = filename.Split('_', '-');
  foreach (var segment in segments)
    yield return segment;
  foreach (var s1 in segments)
    foreach (var s2 in segments)
      if (s1 != s2)
        yield return s1 + s2; 
}

好多了。或者我们可以注意到它具有查询的结构并简单地返回查询:

public static IEnumerable<string> GetNameSegments(string filename)
{
  var q1= filename.Split('_', '-');
  var q2 = from s1 in q1
           from s2 in q1
           where s1 != s2
           select s1 + s2;
  return q1.Concat(q2);
}

同样，这种形式更好。

现在让我们谈谈效率。通常情况下，我们可以以增加复杂性为代价来提高效率。 这段代码看起来应该足够快。您的示例有九个片段。让我们假设九或十是典型的。到目前为止，我们的解决方案首先考虑十个左右的单例，然后是一百个左右的组合。没什么;这段代码可能没问题。但是，如果我们有数千 段并正在考虑数百万 的可能性怎么办？

在那种情况下，我们应该重构算法。一种可能性是这种通用解决方案:

public bool IsMatch(HashSet<string> segments, string name)
{
  if (segments.Contains(name))
    return true;
  var q = from s1 in segments
          where name.StartsWith(s1)
          let s2 = name.Substring(s1.Length)
          where s1 != s2
          where segments.Contains(s2)
          select 1; // Dummy. All we care about is if there is one.
  return q.Any();
}

您的原始解决方案是分段数的二次方。这个是线性的；我们依靠常量顺序包含操作。 (这当然假设字符串操作是常数时间的，因为字符串很短。如果这不是真的，那么我们还有另外一锅鱼要炸。)

在渐近情况下，我们还能如何提取胜利？

• 如果我们碰巧拥有集合不是哈希集而是排序列表的属性，那么我们可以做得更好；我们可以对列表进行二进制搜索以找到可能的前缀匹配范围的开始和结束，然后将列表倒入哈希集中以进行后缀匹配。这仍然是线性的，但可以有一个更小的常数因子。

• 如果我们碰巧知道目标字符串与段数相比较小，我们可以从另一端解决问题。 生成目标字符串分区的所有可能组合，并检查两半是否都在段集中。这个解决方案的问题是它在内存使用上是字符串大小的二次方。所以我们想要做的是在字符序列上构造一个特殊的散列并使用它来填充散列表，而不是标准的字符串散列。我相信您可以从那里看到解决方案是如何进行的；我不会详细说明。