如何组合List <string>中的项目以有效地创建新项目

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？列表是由阵列支持的.你已经掌握了一个阵列.只需使用数组.

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

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();
}

您的原始解决方案是段数的二次方.这个是线性的; 我们依赖于常量顺序包含操作.(这当然假设字符串操作是恒定的时间,因为字符串很短.如果那不是真的那么我们还有另外一条鱼来煎炸.)

我们还能如何在渐近情形中提取胜利？

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

• 如果我们碰巧知道目标字符串与段数相比较小,我们可以从另一端攻击问题. 生成目标字符串的所有可能的分区组合,并检查两个半部是否在段集中.这个解决方案的问题在于它在字符串大小方面的内存使用量是二次的.所以我们想要做的就是在字符序列上构造一个特殊的哈希,并使用它来填充哈希表,而不是标准的字符串哈希.我相信你可以看到解决方案是如何从那里出发的; 我不会详细说明.

Answer 2

效率在很大程度上取决于您试图解决的业务问题。如果不了解完整的上下文/用法，就很难定义最有效的解决方案。适用于一种情况的方法并不总是适用于其他情况。

我总是提倡编写工作代码，然后稍后解决任何性能问题（或者在问题上投入更多锡，因为它通常更便宜！）如果您遇到特定的性能问题，请告诉我们更多信息...

我要冒险地说（希望）每次执行时您只会将文件名与对象名匹配一次。如果是这样的话，我认为这种方法将是最快的。在您将单个文件名与多个对象名称进行匹配的情况下，显而易见的选择是建立一个索引并按照您已经做的那样进行匹配，尽管我会根据您的预期考虑不同类型的集合执行/使用。

public static bool IsMatch(string filename, string objectName)
{
    var segments = filename.Split('-', '_');

    for (int i = 0; i < segments.Length; i++)
    {
        if (string.Equals(segments[i], objectName)) return true;

        for (int ii = 0; ii < segments.Length; ii++)
        {
            if (ii == i) continue;
            if (string.Equals($"{segments[i]}{segments[ii]}", objectName)) return true;
        }
    }

    return false;
}