我尝试为Project Euler的问题14编写一个多线程解决方案,但我并没有看到真正的速度提升。没有任何共享资源,也没有使用互斥锁......我的代码是因为上下文切换而变慢吗?我没有正确理解线程的好处吗?
http://projecteuler.net/problem=14
require 'benchmark'
benchmark_results = Benchmark.measure do
threads = []
num_threads = 10
num_threads.times do |thread_num|
threads << Thread.new(thread_num + 1) do |thread_num|
Thread.current["max_length"] = 0
(thread_num..1000000).step(num_threads).each do |i|
next if i.even?
current = i
length = 0
until current == 1
if current.even?
current = current / 2
else
current = current * 3 + 1
end
length += 1
end
if length > Thread.current["max_length"]
Thread.current["max_length"] = length
Thread.current["max_i"] = i
end
end
end
end
threads.each { |thread| thread.join; print "#{thread['max_i']} -> #{thread['max_length']}\n" }
end
puts benchmark_results
4条答案
按热度按时间bybem2ql1#
据我所知,大多数ruby实现都不使用真实的的线程(OS级别),或者只使用某种锁,因此这样的实现无法从多核/处理器线程中获益(参见http://en.wikibooks.org/wiki/Ruby_Programming/Reference/Objects/Thread)。
如果你的应用程序是CPU绑定的,那么这会有效地阻止你从线程中获得好处。另一方面,如果它是IO绑定的,那么线程可能会有所帮助。(这样,当一个绿色线程等待IO时,其他绿色线程可以使用你分配的CPU时间。然而,物理上,仍然只有一个CPU核心被使用)。
t8e9dugd2#
Ruby有许多不同的实现,最常用的是MRI(参见:other question.
MRI有线程,但不幸的是一次只使用一个CPU核心。这意味着:此时实际上只有一个线程在运行。
如果你的线程必须等待IO发生,那么速度可能会提高。因为如果一个线程必须等待,另一个线程可以赶上。但是你的问题总是需要CPU。
我建议研究另一个Ruby实现,比如JRuby来解决这类问题。JRuby有真正的线程。
如果你改变你的实现,也许你会有一个更大的速度。在你一遍又一遍地重新计算每个
max_length
的时候。例如:n = 4
的序列长度为3
,如果计算n = 8
的length
,只需执行一个步骤(n / 2
),即可得到4
的current
,并且已经知道n = 4
具有length = 3
:因此length(8) = 1 + length(4) = 1 + 4 = 5
。例如:agyaoht73#
你所需要的只是一个进程从小于1000000的奇数开始寻找最长的Collatz链,另一个进程从小于1000000的偶数开始寻找最长的Collatz链。如果你都是手动启动的话,在不同的内核中运行一个脚本的多个示例并不太困难。这很便宜,也很脏,但是它是有效的:-)但是它们不能只是一个进程中的线程,它们必须是独立的进程。(我认为我所说的“进程”就是ThorX 89所说的“操作系统线程”。)
xv8emn3q4#
除了线程化之外,还有其他方法可以加快速度。
我好像记得Ruby是一种特别慢的语言,由一个不关心性能的人设计的。也许你可以使用一种不同的语言。
更重要的是:你用的是一种很简单的方法,它确实有效,但是很多计算要重复很多次,例如,你得到了下面的Collatz序列:
序列中的大多数步骤(例如,52-〉26)被计算了不止一次。这里显然有某种优化的空间。通过忽略以偶数开头的序列,您已经做了一些优化(顺便说一句,你在整理结果的时候忘记了纠正这个错误)。我发现了一个更快的方法,并将其与原始方法进行了比较。对于前10个,000个数字而不是第一个1,000,000,该简单方法花费63秒;忽略偶数的简单方法花费35秒;我的方法花了5秒钟。对于100万个完整的数字,我的算法花了9分钟;我没有试着运行其他的代码(所有这些代码都是用Perl编写的)。如果您不想了解我是如何做到的更多细节,请现在就把目光移开!
我不是只计算每个结果然后就忘记它,而是在计算过程中创建了一个结果数组。现在,假设您已经计算了所有Collatz序列的长度,直到12为止。要计算从13开始的序列的长度,您可以从13开始,一直计算到小于13的数字。该序列的长度为13、40、20、10.你看了数组中的元素10,发现从10到1有6步,你知道从13到10有3步,因为你刚刚完成了这些步骤,所以从13到1有9步,所以你把9设置为数组中的元素13.
没有明显的/好的方法可以用线程来做这件事。我认为如果你真的想做的话,有可能想出一些东西,但这不值得努力。也许如果他们说10亿...