Project Euler#23在C#中的低效代码执行时间

本文关键字：代码 执行时间 Euler#23 Project | 更新日期: 2023-09-27 18:25:07

我已经仔细阅读了我的代码，并试图使其尽可能高效。尽管如此，如果不冷冻我的盒子，我还是无法让这个程序一直运行下去。我让它在不结冰的情况下运行的最长时间大约是2个小时。我不敢相信这件事没有在这么长的时间内执行。

是我的电脑出了问题，还是这种暴力解决问题的方法效率很低。

在未来的写作方法中，有哪些方法可以避免这种低效？

private void Form1_Load(object sender, EventArgs e)
    {
        ArrayList listOfAbundantNumbers = new ArrayList();
        ArrayList listOfSums = new ArrayList();
        long total = 0;
        for (int i = 1; i < 20162; i++)
        {
            if (isAbundandt(i))
            {
                listOfAbundantNumbers.Add(i);
            }
            total+=i;
        }
        for (int i = 1; i < listOfAbundantNumbers.Count; i++)
        {
            for (int a = 0; a < listOfAbundantNumbers.Count; a++)
            {
                long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
                long temp2 = Convert.ToInt64(listOfAbundantNumbers[a]);
                long num = temp1 + temp2;
                if(listOfSums.Contains(num) == false)
                {
                    listOfSums.Add(num);
                }
            }
        }
        for (int i = 1; i < listOfAbundantNumbers.Count; i++)
        {
            long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
            total -= temp1;
        }
        printLn(total + "");
    }
    private ArrayList divisorList(long input)
    {
        ArrayList divisors = new ArrayList();
        for (long i = 2; i < Math.Round(Math.Sqrt(input),0,0); i++)
        {
            long temp = input % i;
            if (temp == 0)
            {
                divisors.Add(i);
                divisors.Add(input / i);
            }
        }
        return divisors;
    }
    private Boolean isAbundandt(long input)
    {
        long sum = 0;
        ArrayList divisor = divisorList(input);
        for (int i = 0; i < divisor.Count; i++)
        {
            long temp1 = Convert.ToInt64(divisor[i]);
            sum += temp1;
        }
        sum++;
        if (sum > input)
        {
            return true;
        }
        return false;
    }

Project Euler#23在C#中的低效代码执行时间

避免使用ArrayList，更喜欢像List<Int64>这样的泛型集合，因为转换可能非常昂贵。

程序中有一个部分位于O（n^3）中。它可以很容易地降为O（n^2）。只需替换以下代码（由于List<T>.Contains，O（n））：

if(listOfSums.Contains(num) == false)
{
    listOfSums.Add(num);
}

发件人：

listOfSums.Add(num);

其中listOfSums现在是HashSet<Int64>（它用于具有没有重复的集合）。

此外，您可以将填充listOfSums的时间减少2倍，只需注意，如果您交换i和a，则sum是相同的，那么，两个组合中只有一个会添加到listOfSums。

您可以替换：

for (int i = 1; i < listOfAbundantNumbers.Count; i++)
    for (int a = 0; a < listOfAbundantNumbers.Count; a++)

由；

for (int i = 1; i < listOfAbundantNumbers.Count; i++)
    for (int a = 0; a <= i; a++)

最后的代码是：

private static void Main()
{
    List<Int64> listOfAbundantNumbers = new List<Int64>();
    HashSet<Int64> listOfSums = new HashSet<Int64>();
    long total = 0;
    for (int i = 1; i < 20162; i++)
    {
        if (isAbundandt(i))
        {
            listOfAbundantNumbers.Add(i);
        }
        total += i;
    }
    for (int i = 0; i < listOfAbundantNumbers.Count; i++)
        for (int a = 0; a <= i; a++)
        {
            long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
            long temp2 = Convert.ToInt64(listOfAbundantNumbers[a]);
            long num = temp1 + temp2;
            listOfSums.Add(num);
        }
    for (int i = 1; i < listOfAbundantNumbers.Count; i++)
    {
        long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
        total -= temp1;
    }
    Console.WriteLine(total + "");
}
private static List<Int64> divisorList(long input)
{
    List<Int64> divisors = new List<Int64>();
    for (long i = 2; i < Math.Round(Math.Sqrt(input), 0, 0); i++)
    {
        long temp = input % i;
        if (temp == 0)
        {
            divisors.Add(i);
            divisors.Add(input / i);
        }
    }
    return divisors;
}
private static Boolean isAbundandt(long input)
{
    long sum = 0;
    List<Int64> divisor = divisorList(input);
    for (int i = 0; i < divisor.Count; i++)
    {
        long temp1 = divisor[i];
        sum += temp1;
    }
    sum++;
    if (sum > input)
    {
        return true;
    }
    return false;
}
相关文章：