从字符串数组中删除列表中存在的元素

Question

我有一个字符串数组x和一个列表y，我想从列表x中删除所有y的数据，怎样才能以最快的方式完成？

例如： X: 1) "aaa.bbb.ccc" 2) "ddd.eee.fff" 3) "ggg.hhh.jjj"

Y: 1) "bbb" 2) "fff"

结果应该是一个新的列表，只包含3)，因为X.1被Y.1删除，X.2被Y.2删除。

如何做到这一点？

我知道我可以在列表X上使用foreach，并检查列表Y中的每个元素，但这是最快的方法吗？

- PassionateDeveloper

---

你的意思是要从x中删除所有包含y中任何元素作为子字符串的元素吗？另外，你说“Array”，是指“List”吗？ - Matthew Watson

如果Y1只是“bb”，那么是否应该删除X1？ - Corak

是的，它应该是交叉引用。 - PassionateDeveloper

@Kovu 你的意思是“是的，如果要删除的内容是“bb”，那么应该删除“aaa.bbb.ccc”这一项吗？”（即使“bb”只是“bbb”的子集） - Matthew Watson

Answer 1

最方便的方式是:

var Z = X.Where(x => !x.Split('.').Intersect(Y).Any()).ToList();

这并不是“最快”的意思。可能做到最快（运行时间）的方法是使用令牌搜索，例如：

public static bool ContainsToken(string value, string token, char delimiter = '.')
{
    if (string.IsNullOrEmpty(token)) return false;
    if (string.IsNullOrEmpty(value)) return false;

    int lastIndex = -1, idx, endIndex = value.Length - token.Length, tokenLength = token.Length;
    while ((idx = value.IndexOf(token, lastIndex + 1)) > lastIndex)
    {
        lastIndex = idx;
        if ((idx == 0 || (value[idx - 1] == delimiter))
            && (idx == endIndex || (value[idx + tokenLength] == delimiter)))
        {
            return true;
        }
    }
    return false;
}

然后大致如下：

var list = new List<string>(X.Length);
foreach(var x in X)
{
    bool found = false;
    foreach(var y in Y)
    {
        if(ContainsToken(x, y, '.'))
        {
            found = true;
            break;
        }
    }
    if (!found) list.Add(x);
}

以下内容：

• 不分配数组（例如用于Split的输出或Split的params char[]参数）
• 不创建任何新的string实例（例如Split的输出）
• 不使用委托抽象层
• 没有捕获的作用域
• 使用List<T>的结构自定义迭代器，而非IEnumerable<T>的类迭代器
• 将新的List<T>以适当的最坏情况大小启动，以避免重新分配空间

- Marc Gravell

---

+1。很有趣看到你的代码在令牌搜索方面，我以前没有见过这样的。 - user1017882

@DeeMac，这段代码实际上是我昨天写的一些stackoverflow.com代码，用于替换查找形式为“abc;def;ghij”的匹配项的代码。旧代码使用了Split，我们看到了大量重复字符串（和数组）缓慢填充内存的开销 - 也就是说，每个请求都会导致额外的“abc”、“def”、“ghij”和一个新的string[3]。在stackoverflow.com上，这很快就会填满... - Marc Gravell

根据你的 ContainsToken() 函数，我认为你可以使用它从列表中删除所有匹配项，如下所示：x.RemoveAll(s1 => y.Any(s2 => ContainsToken(s1, s2, '.')));（如果你想修改原始列表）。 - Matthew Watson

@MatthewWatson 好的，问题中提到了“新列表”；此外，我试图避免任何不可见的分配（例如捕获上下文）- 但是：这是RemoveAll的一个很好的用法。 - Marc Gravell

@Corak 是的，如果 bb 会导致 aaa.bbb.ccc 被删除，你可以使用字符串包含检查；在我看来，原始问题不太清楚。 - Marc Gravell

Answer 2

如果您有这个Contains约束条件，那么在X和Y上进行迭代确实是最快的选项。我真的没有看到其他方法。

但不应该使用foreach在X上进行迭代，因为您不能使用foreach修改您迭代的集合。

因此，一个选项可能是：

for (int counterX = 0; counterX < X.Length; counterX++)
{
    for(int counterY = 0; counterY < Y.Length; counterY++)
    {
        if (X[counterX].Contains(Y[counterY]))
        {
            X.RemoveAt(counterX--);
            counterY = Y.Length;
        }
    }
}

这应该可以解决问题（但要注意，此代码未经测试）。

- Roy Dictus

---

我提出了同样的答案，但为什么会被踩呢？非常赞同你的答案，这是我认为最好的方法。 - user1017882

Answer 3

我认为一个相当快的方法是使用List内置的RemoveAll()方法:

List<string> x = new List<string>
{
    "aaa.bbb.ccc",
    "ddd.eee.fff",
    "ggg.hhh.jjj"
};

List<string> y = new List<string>
{
    "bbb",
    "fff"
};

x.RemoveAll(s => y.Any(s.Contains));

（请注意，我假设您有两个列表x和y。您的OP提到了一个字符串数组，但接下来谈到了“List X”和“List Y”，因此我忽略了字符串数组部分。）

- Matthew Watson

---

这里的包含是不可靠的，因为“aaa.bbbb.ccc”包含“bbb”，但我不认为这是一个“匹配”。 - Marc Gravell

@MarcGravell 在这方面上，原帖不够明确。正如你所看到的，我已经要求澄清。 - Matthew Watson

Answer 4

尝试使用Aggregate函数，如下：

    var xArr = new string[] { "aaa.bbb.ccc", "ddd.eee.fff", "ggg.hhh.jjj" };
    var yList = new List<string> { "bbb", "fff" };

    var result = xArr.Aggregate(new List<string> { }, (acc, next) =>
    {
        var elems = next.Split('.');
        foreach (var y in yList)
            if (elems.Contains(y))
                return acc;
        acc.Add(next);
        return acc;
    });

- Esteban Elverdin

---

这是很多Split...如果目的是方便，可以在一行中完成；如果目的是性能，那么有更好的方法。 - Marc Gravell

@MarcGravell，谢谢，我改进了答案，每次迭代只做一次分割。 - Esteban Elverdin

Answer 5

如果你有一个相对较小的列表，性能影响并不会太大。这是我能想到的最简单的foreach解决方案。

List<string> ListZ = ListX.ToList();

foreach (string x in ListX)
{
    foreach (string y in ListY)
    {
        if (x.Contains(y))
            ListZ.Remove(x);
    }
}

- tnw

---

这有点棘手 - 如果Y有"bbb"，那会导致"aaa.bbbbb.ccc"被移除吗？嗯，它会 - 但是应该吗？（这或许更适合问提问者） - Marc Gravell