c# - 关于执行效率的问题
本文介绍了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屋!
查看全文