使用Ruby线程，但没有看到加速

eni9jsuy 于 2023-01-30 发布在 Ruby

关注(0)|答案(4)|浏览(332)

我尝试为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

ruby

来源：https://stackoverflow.com/questions/20713881/using-ruby-threads-but-not-seeing-a-speed-up

4条答案

按热度按时间

bybem2ql1#

据我所知，大多数ruby实现都不使用真实的的线程（OS级别），或者只使用某种锁，因此这样的实现无法从多核/处理器线程中获益（参见http://en.wikibooks.org/wiki/Ruby_Programming/Reference/Objects/Thread）。
如果你的应用程序是CPU绑定的，那么这会有效地阻止你从线程中获得好处。另一方面，如果它是IO绑定的，那么线程可能会有所帮助。（这样，当一个绿色线程等待IO时，其他绿色线程可以使用你分配的CPU时间。然而，物理上，仍然只有一个CPU核心被使用）。

赞(0）回复(0）举报 2023-01-30

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。例如：

class CollatzSequence

  def initialize
    @lengths = Hash.new { |h, n| cache_length(h, n) }
  end

  def length(n)
    @lengths[n]
  end

private

  def cache_length(h, n)
    if n <= 1
      h[n] = 1
    else
      next_in_seqence = n.even? ? (n / 2) : (n * 3 + 1)
      h[n] = 1 + h[next_in_seqence]
    end
  end

end

require 'benchmark'
sequencer = CollatzSequence.new

Benchmark.bm(10) do |bm| 
  bm.report('not cached')  { sequencer.length(837799)     } 
  bm.report('cache hit 1') { sequencer.length(837799)     } 
  bm.report('cache hit 2') { sequencer.length(837799 * 2) } 
end

#                  user     system      total        real
# not cached   0.000000   0.000000   0.000000 (  0.001489)
# cache hit 1  0.000000   0.000000   0.000000 (  0.000007)
# cache hit 2  0.000000   0.000000   0.000000 (  0.000011)

赞(0）回复(0）举报 2023-01-30

agyaoht73#

你所需要的只是一个进程从小于1000000的奇数开始寻找最长的Collatz链，另一个进程从小于1000000的偶数开始寻找最长的Collatz链。如果你都是手动启动的话，在不同的内核中运行一个脚本的多个示例并不太困难。这很便宜，也很脏，但是它是有效的：-）但是它们不能只是一个进程中的线程，它们必须是独立的进程。（我认为我所说的“进程”就是ThorX 89所说的“操作系统线程”。）

赞(0）回复(0）举报 2023-01-30

xv8emn3q4#

除了线程化之外，还有其他方法可以加快速度。
我好像记得Ruby是一种特别慢的语言，由一个不关心性能的人设计的。也许你可以使用一种不同的语言。
更重要的是：你用的是一种很简单的方法，它确实有效，但是很多计算要重复很多次，例如，你得到了下面的Collatz序列：

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
                11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

序列中的大多数步骤（例如，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亿...

赞(0）回复(0）举报 2023-01-30

我来回答

使用Ruby线程，但没有看到加速

4条答案

相关问题

热门标签

最新问答