0

私が書いた構造体の配列（またはリスト）を提供し、重複した要素を削除して返す最適化されたアルゴリズムを探しています。
O（n ^ 2）の複雑さを持つ単純なアルゴリズムでそれを行うことができることを私は知っています。しかし、より良いアルゴリズムが必要です。

どんな助けでも大歓迎です。

4

4 に答える 4

3

実際の使用では、LINQDistinctが最も簡単なソリューションです。これは、おそらく次のアルゴリズムと非常によく似た、ハッシュテーブル ベースのアプローチを使用します。

そのようなアルゴリズムがどのように見えるかに興味がある場合:

IEnumerable<T> Distinct(IEnumerable<T> sequence)
{
    var alreadySeen=new HashSet<T>();
    foreach(T item in sequence)
    {
        if(alreadySeen.Add(item))// Add returns false if item was already in set
            yield return;
    }
}

d個別の要素と合計要素がある場合n、このアルゴリズムにはO(d)メモリとO(n)時間がかかります。

このアルゴリズムはハッシュセットを使用するため、O(n)ランタイムを実現するには十分に分散されたハッシュが必要です。ハッシュがうまくいかない場合、ランタイムは次のように劣化する可能性がありますO(n*d)

于 2013-07-04T08:34:42.953 に答える
3

これは O(N) 時間近くで実行されます。

var result = items.Distinct().ToList();

[編集]

O(N) 時間であるという Microsoft からの文書化された証拠がないため、次のコードを使用していくつかのタイミングを計りました。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Demo
{
    class Program
    {
        private void run()
        {
            test(1000);
            test(10000);
            test(100000);
        }

        private void test(int n)
        {
            var items = Enumerable.Range(0, n);
            new Action(() => items.Distinct().Count())
                .TimeThis("Distinct() with n == " + n + ": ", 10000);
        }

        static void Main()
        {
            new Program().run();
        }
    }

    static class DemoUtil
    {
        public static void TimeThis(this Action action, string title, int count = 1)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                action();

            Console.WriteLine("Calling {0} {1} times took {2}",  title, count, sw.Elapsed);
        }
    }
}

結果は次のとおりです。

Calling Distinct() with n == 1000:   10000 times took 00:00:00.5008792
Calling Distinct() with n == 10000:  10000 times took 00:00:06.1388296
Calling Distinct() with n == 100000: 10000 times took 00:00:58.5542259

n時間は、少なくともこの特定のテストではほぼ直線的に増加しており、O(N) アルゴリズムが使用されていることを示しています。

于 2013-07-04T08:10:43.580 に答える
2

O(N) の複雑さで HashSet を使用できます。

List<int> RemoveDuplicates(List<int> input)
{
    var result = new HashSet<int>(input);
    return result.ToList();
}

ただし、メモリ使用量が増加します。

于 2013-07-04T08:09:32.150 に答える