3

我有一个包含几个单词的列表。我想过滤掉其中一些与特定模式不匹配的。将所有匹配项添加到临时列表并随后将此列表复制到主列表中是否更快？或者从主列表中删除所有不匹配是否更快？我要尽可能快地过滤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.

4

3 回答 3

1

假设一个List<T>那么你将不得不考虑以下几点：

  • 如果 Count 小于 Capacity，则该Add方法是 O(1) 操作。如果需要增加容量来容纳新元素，这个方法就变成了O(n)操作，其中n是Count；
  • 该RemoveAt方法是一个 O(n) 操作，其中 n 是 (Count - index)。

如果您创建列表以保存初始容量设置为总字数的匹配项，那么Add将始终为 O(1) 并且更快。但是，您需要考虑创建这个容量设置为总字数的新列表的开销。

最重要的是，您需要对其进行测试，看看哪种方法更适合您的特定场景。

于 2012-06-26T17:02:08.823 回答
0

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

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();
    }
}
于 2012-06-26T17:44:44.500 回答
0

整体

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

我不会担心将临时列表复制回初始列表。您已经定义它填充它，继续使用它。

于 2012-06-26T19:10:06.677 回答