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 はカウントです。
  • このRemoveAtメソッドは O(n) 操作です。ここで、n は (カウント - インデックス) です。

初期容量を総単語数に設定して一致を保持するリストを作成すると、Add常に O(1) になり、高速になります。ただし、総単語数に設定された容量でこの新しいリストを作成するオーバーヘッドを考慮する必要があります。

要するに、それをテストして、特定のシナリオで何がうまく機能するかを確認する必要があります。

于 2012-06-26T17:02:08.823 に答える
0

全体

文字.IndexOf（word [0]）> -1

私には少し馴染みがなかったので、将来のプログラマーのためにもっと読みやすく、保守しやすいものを探しました。リスト内の各文字列の最初の文字をチェックして、{a A、B、C、a、b、c}の範囲で一致するものを探していることを理解するのに1分かかりました。それは機能しますが、私には少し謎めいたものでした。私はそれを読むのに時間をかけ始めています、しかし私はこのようにそれをします：

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

一時リストを最初のリストにコピーして戻すことについて心配する必要はありません。あなたはすでにそれがそれを埋めたと定義されています、先に進んでそれを使用してください。

于 2012-06-26T19:10:06.677 に答える
0

これは、メソッドの時間を計る方法についてまとめた例です。これを行うには多くの方法があり、いくつか試してみる必要があると思います。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();
    }
}
于 2012-06-26T17:44:44.500 に答える