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++ 中重新实现您的代码，或者，如果您愿意，可以尝试将 Mono 与 AOT（提前编译器）一起使用：它会大大提高性能

 mono --aot=full YourProgram.exe

现在更多关于基准和最优性：您是否将您的结果与其他人进行了比较？您是否在同一硬件上运行了其他集合覆盖算法，或者您能否将您的硬件与运行相同算法的其他硬件进行比较？

并且......您的解决方案与最佳解决方案有多接近？你能给[你自己]一个估计吗？关键在于 LINQ，我讨厌它，因为您为了代码的简单性而失去了对代码的控制。LINQ 的复杂性是什么？如果每个 LINQ 是 O(n)，那么你的算法是 O(n^3) 但我可能会建议你替换

remaining.Any()

和

remaining.Count > 0

以获得一定程度的复杂性。

我的只是建议，希望对你有帮助

于 2010-10-10T00:17:47.703 回答