c# - 关于执行效率的问题

问题描述

问 题

leetcode上一道计算质数的题目Count Primes

这两种写法效率差异有点看不懂

public int CountPrimes(int n) {
         bool[] isPrime = new bool[n];
            for (int i = 2; i < n; i++)
            {
                isPrime[i] = true;
            }
            for (int i = 2; i * i < n; i++)
            {
                if (!isPrime[i]) continue;
                for (int j = i * i; j < n; j += i)
                {
                    isPrime[j] = false;
                }
            }
            int count = 0;
            for (int i = 2; i < n; i++)
            {
                if (isPrime[i]) count++;
            }
            return count;
    }

运行时间：69 ms

public int CountPrimes(int n) {
         bool[] isPrime = new bool[n];
            for (int i = 2; i * i < n; i++)
            {
                if (isPrime[i]) continue;
                for (int j = i * i; j < n; j += i)
                {
                    isPrime[j] = true;
                }
            }
            int count = 0;
            for (int i = 2; i < n; i++)
            {
                if (!isPrime[i]) count++;
            }
            return count;
    }

运行时间：83 ms

少走一遍for，为什么运行反而变慢了？内部发生了什么？leetcode时间计算有误？初学者，对底层的东西不是很了解

解决方案

应该是最后统计数量的时候做了取反的操作导致的吧

for (int i = 2; i < n; i++)
{
    if (!isPrime[i]) count++;
}

---

上面说的好像不大对 仔细看了下 第一种的第二个循环也有一个取反操作

---

把上面的代码放到VS里试了一下，代码及结果如下：

using System;

namespace CountPrimes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 1000000000;
            DateTime dtStart = DateTime.Now;

            Console.WriteLine($"in {n} have {CountPrimes1(n)} primes (cost {(DateTime.Now - dtStart).TotalSeconds} seconds)");

            dtStart = DateTime.Now;
            Console.WriteLine($"in {n} have {CountPrimes2(n)} primes (cost {(DateTime.Now - dtStart).TotalSeconds} seconds)");

            Console.ReadLine();
        }

        public static int CountPrimes1(int n)
        {
            bool[] isPrime = new bool[n];
            for (int i = 2; i < n; i++)
            {
                isPrime[i] = true;
            }
            for (int i = 2; i * i < n; i++)
            {
                if (!isPrime[i]) continue;
                for (int j = i * i; j < n; j += i)
                {
                    isPrime[j] = false;
                }
            }
            int count = 0;
            for (int i = 2; i < n; i++)
            {
                if (isPrime[i]) count++;
            }
            return count;
        }

        public static int CountPrimes2(int n)
        {
            bool[] isPrime = new bool[n];
            for (int i = 2; i * i < n; i++)
            {
                if (isPrime[i]) continue;
                for (int j = i * i; j < n; j += i)
                {
                    isPrime[j] = true;
                }
            }
            int count = 0;
            for (int i = 2; i < n; i++)
            {
                if (!isPrime[i]) count++;
            }
            return count;
        }
    }
}

结果:

in 1000000000 have 50847534 primes (cost 28.0662532 seconds)

in 1000000000 have 50847534 primes (cost 24.9906462 seconds)

看结果还是第二种方法的效率高

这篇关于c# - 关于执行效率的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！