5

リストから重複する値を削除するための最良のアルゴリズムは何ですか？私はこれを試しました：

for (int i = 0; i < AuthorCounter-1; i++)
{
    for (int j = 0; j < AuthorCounter-1; j++)
    {
        if (i != j)
        {
            if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[j].Text)
            {
                AuthorGroupNode.Nodes[j].Remove();
                AuthorCounter--;
            }

        }
    }
}

AuthorGroupNodesこれがノードのリストです。それはある程度正しいことをしましたが、完璧ではありませんでした。誰もがより良い解決策を持っています???

4

4 に答える 4

6

現在のアルゴリズムはO（N-squared）であり、大きなリストではパフォーマンスが非常に低くなります。

スペースが問題にならない場合はHashSet<int>、ノードのハッシュを保持できます。リストを1回トラバースします。ノードのハッシュがHashSetにある場合、これは重複ノードであることがわかります。スキップしてください。ハッシュがHashSetにない場合は、このノードを新しいリストに追加し、ノードのハッシュをHashSetに追加します。

これはO（N）を実行し、元のリスト、リストのコピーから重複を除いたもの、およびHashSet用のメモリを必要とします。アルゴリズムは非破壊的です。

Linqを使用できる場合は、

var distinctList = originalList.Distinct().ToList();

アップデート

それが、JonSkeetがDistinctを再実装した方法とほぼ同じであることを発見しました。

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    return source.Distinct(EqualityComparer<TSource>.Default); 
} 

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    if (source == null)  
    { 
        throw new ArgumentNullException("source"); 
    } 
    return DistinctImpl(source, comparer ?? EqualityComparer<TSource>.Default); 
} 

private static IEnumerable<TSource> DistinctImpl<TSource>( 
    IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    HashSet<TSource> seenElements = new HashSet<TSource>(comparer); 
    foreach (TSource item in source) 
    { 
        if (seenElements.Add(item)) 
        { 
            yield return item; 
        } 
    } 
}

https://codeblog.jonskeet.uk/2010/12/30/reimplementing-linq-to-objects-part-14-distinct/

于 2012-07-17T04:28:02.577 に答える
4

これは御馳走のように機能します：

var xs = new []
{
    2, 3, 2, 4, 3, 3, 5, 6,
};

var ys = xs
    .ToLookup(z => z, z => z)
    .Select(x => x.First());

コードの場合、次のようになります。

var nodes = AuthorGroupNode.Nodes
    .ToLookup(z => z.Text, z => z)
    .Select(x => x.First())
    .ToArray();

それよりもはるかに単純にすることはできません。:-)

于 2012-07-17T04:52:01.330 に答える
3

Eric J.の答えを後回しにする...EqualityComparerを実装して、個別のアイテムの識別方法を完全に制御する必要があります。

class Program
{
    static void Main(string[] args)
    {
        var list = new List<SampleClass>();
        // add some items

        var distinctItems = list.Distinct(new SampleClass());
    }
}

public class SampleClass : EqualityComparer<SampleClass>
{
    public string Text { get; set; }

    public override bool Equals(SampleClass x, SampleClass y)
    {
        if (x == null || y == null) return false;
        return x.Text == y.Text;
    }

    public override int GetHashCode(SampleClass obj)
    {
        if (obj == null) return 0;
        if (obj.Text == null) return 0;
        return obj.Text.GetHashCode();
    }
}

詳細：http：//msdn.microsoft.com/en-us/library/bb338049

于 2012-07-17T04:34:50.570 に答える
2

リストの最後の要素をチェックすることはありません。2番目の for を機能させるには、次のように変更する必要があります。

for (int j = 0; j < AuthorCounter; j++)

ノードの各ペアを 2 回チェックしています。最初に i = 0 および j = 1 の場合を確認し、次に i = 1 および j = 0 の場合を確認します。j を i の前または i と同じで開始する必要はありません。i = 0 の場合、内側のループはその要素のすべての重複を削除するため、一意であることがわかりますAuthorGroupNodes.Nodes[0]。次回外側のループを通過すると、それAuthorGroupNodes.Nodes[1]が一意であることを確認できます。したがって、i + 1 に等しい j から始めて、i == j のチェックを外すことができます。また、ノードを削除しても、j は次のノードまで増加します。これにより、削除したノードの次の j にある新しいノードがスキップされるため、j をデクリメントするか、ノードを削除しない場合は単に j をインクリメントする必要があります。

for (int j = i + 1; j < AuthorCounter;)
{
    if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[j].Text)
    {
        AuthorGroupNode.Nodes[j].Remove();
        AuthorCounter--;
    }
    else
    {
        j++;
    }
}

あなたはそれが機能するが完全ではないと言っているので、標準のリストを使用しておらず、ノードが Remove() メソッドを使用してリストからの独自の削除を処理していると仮定しています。

リストが比較しているフィールドでソートされている場合は、内側の for ループを完全に削除し、別の要素が見つかるまで現在の要素の重複を削除できます。

for (int i = 0; i < AuthorCounter-1;)
{
    if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[i + 1].Text)
    {
        AuthorGroupNode.Nodes[i].Remove();
        AuthorCounter--;
    }
    else
    {
        i++;
    }
}
于 2012-07-17T04:42:26.577 に答える