为什么我的C#计算时间可能是非确定性的？

Question

我正在运行一个搜索算法,它在一开始就用一个种子提供.从这一点开始,我希望算法能够以确定的方式运行,而这在很大程度上也是如此.通过查看第10,000步,20,000步并看到它们是相同的,我可以在很大程度上验证这一点.我看到的不同之处是用于到达同一位置的线程处理器时间的长度(采用相同的路径).我正在使用ProcessThread.TotalProcessorTime测量线程时间.

为了量化这个,我已经为你做了一些测试.我改变了运行时间并测量了在此时间内评估的解决方案的数量

---

    30s         60s          120s        120s
473,962     948,800     1,890,668   1,961,532
477,287     954,335     1,888,955   1,936,974
473,441     953,049     1,895,727   1,960,875
475,606     953,576     1,905,271   1,941,511
473,283     951,390     1,946,729   1,949,231
474,846     954,307     1,840,893   1,939,160
475,052     952,949     1,848,938   1,934,243
476,797     957,179     1,945,426   1,951,542

475,034     476,599       473,831     486,721
  1,478       2,426        23,922      11,108

我重复了8次测试.底部两行显示在30秒期间评估的平均解决方案,然后是标准偏差.我重复了120s测试,因为标准偏差第一次如此之高,第二次低得多.

如果我的算法做了同样的工作,那么什么可能导致相同的工作花费不同的时间？什么是随机元素？

澄清几点:

1. 我说的是线程处理器时间而不是时钟时间
2. 该算法在单个线程上运行,没有与其他线程的显式交互
3. 这个环境是Windows XP .Net C#双处理器
4. 它是一个控制台应用程序
5. 该算法使用处理器和内存,只有在完成后才会将结果打印到屏幕上.

最好的祝福

Answer 1

优化,内存管理(GC,分配,分页等)和及时编译.

Answer 2

在处理器级别，缓存未命中和不正确的分支预测都会影响从一次运行到另一次运行可能花费的处理器时间。在框架层面，JITing 和 GC 也会影响它。后者比前者更容易被观察到。