2

セットカバー問題を「解決」するのにどれくらいの時間がかかるかをテストするために、このプログラムを書きました。

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

namespace SetCover
{
    class Program
    {
        const int maxNumItems = 10000;
        const int numSets = 5000;
        const int maxItemsPerSet = 300;

        static void Main(string[] args)
        {
            var rand = new Random();
            var sets = new List<HashSet<int>>(numSets);
            var cover = new List<HashSet<int>>(numSets);
            var universe = new HashSet<int>();
            HashSet<int> remaining;
            var watch = new Stopwatch();


            Console.Write("Generating sets...");
            for (int i = 0; i < numSets; ++i)
            {
                int numItemsInSet = rand.Next(1, maxItemsPerSet);
                sets.Add(new HashSet<int>());

                for (int j = 0; j < numItemsInSet; ++j)
                {
                    sets[i].Add(rand.Next(maxNumItems));
                }
            }
            Console.WriteLine("Done!");

            Console.Write("Computing universe...");
            foreach (var set in sets)
                foreach (var item in set)
                    universe.Add(item);
            Console.WriteLine("Found {0} items.", universe.Count);

            watch.Start();

            //Console.Write("Removing subsets...");
            //int numSetsRemoved = sets.RemoveAll(subset => sets.Any(superset => subset != superset && subset.IsSubsetOf(superset)));
            //Console.WriteLine("Removed {0} subsets.", numSetsRemoved);


            //Console.Write("Sorting sets...");
            //sets = sets.OrderByDescending(s => s.Count).ToList();
            //Console.WriteLine("{0} elements in largest set.", sets[0].Count);


            Console.WriteLine("Computing cover...");
            remaining = universe.ToHashSet();
            while (remaining.Any())
            {
                Console.Write("  Finding set {0}...", cover.Count + 1);
                var nextSet = sets.MaxBy(s => s.Intersect(remaining).Count());
                remaining.ExceptWith(nextSet);
                cover.Add(nextSet);
                Console.WriteLine("{0} elements remaining.", remaining.Count);
            }
            Console.WriteLine("{0} sets in cover.", cover.Count);

            watch.Stop();

            Console.WriteLine("Computed cover in {0} seconds.", watch.Elapsed.TotalSeconds);

            Console.ReadLine();
        }
    }

    public static class Extensions
    {
        public static HashSet<TValue> Clone<TValue>(this HashSet<TValue> set)
        {
            var tmp = new TValue[set.Count];
            set.CopyTo(tmp, 0);
            return new HashSet<TValue>(tmp);
        }

        public static HashSet<TSource> ToHashSet<TSource>(this IEnumerable<TSource> source)
        {
            return new HashSet<TSource>(source);
        }
    }
}

これは貪欲な次善のソリューションですが、それでも実行に 147 秒かかりました。ただし、このソリューションは最適にかなり近いはずなので、私の目的には十分であると思います。どうすれば高速化できますか？

良いことよりも悪いことの方が多いので、いくつかの行をコメントアウトしました。編集：宇宙の計算は、実際にはタイミングから離れるべきではありません...それは事前に知ることができます。

4

1 に答える 1

2

コード/アルゴリズムの詳細については深く掘り下げていませんが、いくつかの理論を使用してアドバイスします。Henk がコメントしたように、「良い」ベンチマークを実行するには、不要なコードをすべて削除し、コマンドラインから完全に最適化されたリリース モードでプログラムを実行する必要があります。

次に、マネージ コードを実行していることを思い出してください。C# (および Java) は、パフォーマンスではなく相互運用性のために設計されていますが、どちらも優れたプラットフォームです。パフォーマンスが必要な場合は C++ でコードを再実装するか、必要に応じて AOT (事前コンパイラ) で Mono を使用してみてください。パフォーマンスが大幅に向上します。

 mono --aot=full YourProgram.exe

ベンチマークと最適性についてさらに詳しく: 自分の結果を他のユーザーと比較しましたか? 同じハードウェアで他のセット カバー アルゴリズムを実行しましたか? または、同じアルゴリズムを実行した他のハードウェアとハ​​ードウェアを比較できますか?

そして...あなたの解は最適にどれくらい近いですか? [自分で] 見積もりを出してもらえますか? 鍵は LINQ にあり、コードを単純化するためにコードを制御できなくなるため、私はこれを嫌います。LINQ の複雑さはどのくらいですか? 各LINQがO（n）の場合、アルゴリズムはO（n ^ 3）ですが、置き換えることをお勧めします

remaining.Any()

と

remaining.Count > 0

複雑さの大きさを得るために。

私は単なるアドバイスです。役に立てば幸いです

于 2010-10-10T00:17:47.703 に答える