最快的过滤词语列表的方法

Question

我有一个包含多个单词的列表。我想要过滤掉一些不符合特定模式的单词。将所有匹配项添加到临时列表并在之后复制到主列表中是否更快？还是从主列表中删除所有不匹配项更快？

我需要尽快地过滤掉10000个单词，因此我期待每一点速度提升。

string characters = "aAbBcC";
// currentMatches contains all the words from the beginning
List<string> currentMatches = new List<string>();
List<string> newMatches = new List<string>();
foreach (string word in currentMatches)
{
   if (characters.IndexOf(word[0]) > -1)
   // word match
   {
       newMatches.Add(word);
   }
}
currentMatches = newMatches;

foreach循环应该检查word是否以characters中的任一字符开头。在此，我将每个匹配项复制到newMatches，然后再将所有新匹配项复制到currentMatches。

- Stacksatty

---

不，它只需要非常快速，而我不知道我的CPU内部发生了什么。因此，我不知道哪个更快。 - Stacksatty

也许你应该尝试一些方法 - 我建议使用 Linq，因为它非常快速 - 比如像这样的代码：yourList.Where(x => x == someFilterExpression)。你是在优化某些东西吗？你有一些已经很慢的东西需要优化吗？需要让它变得极快的实际原因是什么？ - Charleh

你尝试过什么？ - James Hill

10000个单词并不算很多。我怀疑你无论用什么方法都不会有显著的改进。 - Tudor

这感觉像是过早的优化。当然这只是我的看法。 - s.m.

Answer 1

假设有一个 List<T>，那么您需要考虑以下几点：

• 如果 Count 小于 Capacity，则 Add 方法是 O(1) 操作。如果需要增加容量以容纳新元素，则此方法变为 O(n) 操作，其中 n 是 Count；
• RemoveAt 方法是 O(n) 操作，其中 n 是 (Count - index)。

如果您创建的列表用于保存匹配项，并将初始容量设置为总单词数，则 Add 将始终是 O(1) 并且更快。但是，您需要考虑创建具有设置为总单词数的容量的新列表的开销。

总之，您需要测试并查看哪种方法适用于您的特定情况。

- João Angelo

---

最后一行：说得像个真正的政治家:D - Charleh

Answer 2

这里是我临时拼凑的一个如何计时方法的示例。有很多方法可以做到这一点，我认为你需要尝试一些。你可以使用像João Angelo帖子中提供的信息来帮助你找到好的方法，但这里还有一些方法。此外，如果你愿意花时间，你可以把所有这些放在一个循环中，创建一个新列表，运行所有测试，将TimeSpan结果放入一个集合中，而不是Console.WriteLine它们，然后给你一个测试迭代次数的平均值。这将有助于给你一个平均值。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Test
{
    public class Program
    {
        public static void Main(string[] args)
        {
            List<string> testList = CreateTestList();
            const string filter = "abc";

            TimeNewListMethod(FilterIntoNewListWithLinq, testList, filter);
            TimeInPlaceMethod(FilterInPlaceWithLinq, testList, filter);

            TimeNewListMethod(FilterIntoNewListWithForEach, testList, filter);

            TimeInPlaceMethod(FilterInPlaceWithRemoveAll, testList, filter);

            Console.Read();
        }

        public static void TimeInPlaceMethod(Action<List<string>, string> testMethod, List<string> toFilter, string filter)
        {
            List<string> toFilterCopy = new List<string>(toFilter);
            DateTime time = DateTime.Now;
            testMethod(toFilterCopy, filter);
            Console.WriteLine(DateTime.Now - time);
        }

        public static void TimeNewListMethod(Func<List<string>, string, List<string>> testMethod, List<string> toFilter, string filter)
        {
            List<string> toFilterCopy = new List<string>(toFilter);
            List<string> resultList;
            DateTime time = DateTime.Now;
            resultList = testMethod(toFilterCopy, filter);
            Console.WriteLine(DateTime.Now - time);
        }

        public static List<string> FilterIntoNewListWithLinq(List<string> toFilter, string filter)
        {
            return toFilter.Where(element => element.IndexOf(filter) > -1).ToList();
        }

        public static void FilterInPlaceWithLinq(List<string> toFilter, string filter)
        {
            toFilter = toFilter.Where(element => element.IndexOf(filter) > -1).ToList();
        }

        public static List<string> FilterIntoNewListWithForEach(List<string> toFilter, string filter)
        {
            List<string> returnList = new List<string>(toFilter.Count);
            foreach (string word in toFilter)
            {
                if (word.IndexOf(word[0]) > -1)
                {
                    returnList.Add(word);
                }
            }

            return returnList;
        }

        public static void FilterInPlaceWithRemoveAll(List<string> toFilter, string filter)
        {
            toFilter.RemoveAll(element => element.IndexOf(filter) == -1);
        }

        public static List<string> CreateTestList(int elements = 10000, int wordLength = 6)
        {
            List<string> returnList = new List<string>();
            StringBuilder nextWord = new StringBuilder();

            for (int i = 0; i < elements; i++)
            {
                for (int j = 0; j < wordLength; j++)
                {
                    nextWord.Append(RandomCharacter());
                }
                returnList.Add(nextWord.ToString());
                nextWord.Clear();
            }

            return returnList;
        }

        public static char RandomCharacter()
        {
            return (char)('a' + rand.Next(0, 25));
        }

        public static Random rand = new Random();
    }
}

- Jeremy Pridemore

Answer 3

整个

characters.IndexOf(word[0]) > -1

对我来说有点陌生，因此我会选择更易读和可维护的代码供未来的程序员使用。花了我一分钟才弄清楚你正在检查列表中每个字符串的第一个字符，寻找在 { a A, B, C, a, b, c } 范围内的匹配项。虽然它能够正常工作，但对我来说有点晦涩难懂。现在我已经理解了它，但我会这样做：

        foreach (string word in currentMatches)
        {               
            if (Regex.IsMatch(word, "^([A-Ca-c])"))
            {
                newMatches.Add(word);
            }
        }

不用担心将临时列表复制回初始列表。你已经定义并填充了它，可以直接使用。

- GrayFox374