.NETで文字列配列を効率的にマージし、異なる値を保持します
https://stackoverflow.com/questions/146358
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
.NET 3.5を使用しています。 2つの文字列配列があり、1つ以上の値を共有できます。
string[] list1 = new string[] { "apple", "orange", "banana" };
string[] list2 = new string[] { "banana", "pear", "grape" };
重複する値のない1つの配列にそれらをマージする方法が欲しい：
{ "apple", "orange", "banana", "pear", "grape" }
LINQでこれを行うことができます：
string[] result = list1.Concat(list2).Distinct().ToArray();
しかし、それは大きな配列にはあまり効率的ではないと思います。
もっと良い方法はありますか？
解決
string[] result = list1.Union(list2).ToArray();
from msdn ：＆quot;このメソッドは、リターンから重複を除外しますセット。これは、重複を含む入力シーケンス内のすべての要素を返すConcat（TSource）メソッドとは異なる動作です。
他のヒント
なぜ非効率的だと思いますか？私の知る限り、ConcatとDistinctはどちらも遅延評価され、Distinctの背後でHashSetを使用して、既に返された要素を追跡します。
一般的な方法よりも効率的にする方法がわからない：）
EDIT：Distinctは実際にはHashSetの代わりにSet（内部クラス）を使用しますが、要旨は依然として正しいです。これは、LINQがいかに優れているかを示す非常に良い例です。最も単純な答えは、ドメインの知識がなくても達成できるのと同じくらい効率的です。
効果は次のものと同等です：
public static IEnumerable<T> DistinctConcat<T>(IEnumerable<T> first, IEnumerable<T> second)
{
HashSet<T> returned = new HashSet<T>();
foreach (T element in first)
{
if (returned.Add(element))
{
yield return element;
}
}
foreach (T element in second)
{
if (returned.Add(element))
{
yield return element;
}
}
}
.NET 3.5では、これを実行できるHashSetクラスが導入されました。
IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);
パフォーマンスはわかりませんが、指定したLinqの例に勝るものです。
編集： 私は訂正します。 ConcatとDistinctのレイジーな実装には、重要なメモリと速度の利点があります。 Concat / Distinctは約10％高速で、データの複数のコピーを保存します。
コードで確認しました：
Setting up arrays of 3000000 strings overlapping by 300000
Starting Hashset...
HashSet: 00:00:02.8237616
Starting Concat/Distinct...
Concat/Distinct: 00:00:02.5629681
の出力：
int num = 3000000;
int num10Pct = (int)(num / 10);
Console.WriteLine(String.Format("Setting up arrays of {0} strings overlapping by {1}", num, num10Pct));
string[] list1 = Enumerable.Range(1, num).Select((a) => a.ToString()).ToArray();
string[] list2 = Enumerable.Range(num - num10Pct, num + num10Pct).Select((a) => a.ToString()).ToArray();
Console.WriteLine("Starting Hashset...");
Stopwatch sw = new Stopwatch();
sw.Start();
string[] merged = new HashSet<string>(list1).Union(list2).ToArray();
sw.Stop();
Console.WriteLine("HashSet: " + sw.Elapsed);
Console.WriteLine("Starting Concat/Distinct...");
sw.Reset();
sw.Start();
string[] merged2 = list1.Concat(list2).Distinct().ToArray();
sw.Stop();
Console.WriteLine("Concat/Distinct: " + sw.Elapsed);
免責事項これは時期尚早な最適化です。サンプル配列には、3.5拡張メソッドを使用します。この地域でパフォーマンスの問題があることがわかるまで、ライブラリコードを使用する必要があります。
配列をソートできる場合、またはコード内のそのポイントに到達したときに配列がソートされている場合は、次のメソッドを使用できます。
これらは両方から1つのアイテムを取得し、「最低」を生成します。次に、両方のソースが使い果たされるまで、対応するソースから新しいアイテムを取得します。 2つのソースからフェッチされた現在のアイテムが等しい場合、最初のソースからアイテムを生成し、両方のソースでそれらをスキップします。
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2)
{
return Merge(source1, source2, Comparer<T>.Default);
}
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2, IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source1))
throw new ArgumentNullException("source1");
if (Object.ReferenceEquals(null, source2))
throw new ArgumentNullException("source2");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T>
enumerator1 = source1.GetEnumerator(),
enumerator2 = source2.GetEnumerator())
{
Boolean more1 = enumerator1.MoveNext();
Boolean more2 = enumerator2.MoveNext();
while (more1 && more2)
{
Int32 comparisonResult = comparer.Compare(
enumerator1.Current,
enumerator2.Current);
if (comparisonResult < 0)
{
// enumerator 1 has the "lowest" item
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
else if (comparisonResult > 0)
{
// enumerator 2 has the "lowest" item
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
else
{
// they're considered equivalent, only yield it once
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
more2 = enumerator2.MoveNext();
}
}
// Yield rest of values from non-exhausted source
while (more1)
{
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
while (more2)
{
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
}
}
ソースの1つに重複が含まれている場合、出力に重複が表示される場合があることに注意してください。すでに並べ替えられているリストからこれらの重複を削除する場合は、次の方法を使用します。
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source)
{
return CheapDistinct<T>(source, Comparer<T>.Default);
}
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source,
IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source))
throw new ArgumentNullException("source");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T> enumerator = source.GetEnumerator())
{
if (enumerator.MoveNext())
{
T item = enumerator.Current;
// scan until different item found, then produce
// the previous distinct item
while (enumerator.MoveNext())
{
if (comparer.Compare(item, enumerator.Current) != 0)
{
yield return item;
item = enumerator.Current;
}
}
// produce last item that is left over from above loop
yield return item;
}
}
}
これらはいずれも、データ構造を使用してデータのコピーを保持するものではないため、入力がソートされている場合は安価になります。保証できない、または保証しない場合は、すでに見つかった3.5拡張メソッドを使用する必要があります。
上記のメソッドを呼び出すサンプルコードを次に示します。
String[] list_1 = { "apple", "orange", "apple", "banana" };
String[] list_2 = { "banana", "pear", "grape" };
Array.Sort(list_1);
Array.Sort(list_2);
IEnumerable<String> items = Merge(
CheapDistinct(list_1),
CheapDistinct(list_2));
foreach (String item in items)
Console.Out.WriteLine(item);
キーとして値を持つハッシュテーブルを作成し（まだ存在しないもののみを追加）、キーを配列に変換することが実行可能な解決策になる可能性があります。
測定するまで、どちらのアプローチが速いかわかりません。 LINQの方法はエレガントで理解しやすいです。
別の方法は、セットをハッシュ配列（Dictionary）として実装し、両方の配列のすべての要素をセットに追加することです。次に、set.Keys.ToArray（）メソッドを使用して、結果の配列を作成します。
