更に Ruby の Matrix と Numo::NArray で pagepank をやってみた

はじめに

前回の記事を投稿後、Rubyの元標準ライブラリのMatrixと外部ライブラリのNumo::NArrayがあったので、更にやってみた。

問題の整理[再掲]

ノード数Nの有向グラフがある。
高橋くんはノード1からスタートして100回ランダムな遷移を行います。
遷移後、高橋くんがどのノードにいるかを答えてください。

入力
N M
A1 B1
.
.
.
Am Bm

入力例
5 7
1 2
1 3
2 4
3 4
3 5
4 5
5 1

Ruby Matrix版

matrix.rb

require 'matrix'

n, x = gets.split.map(&:to_i)
m = Matrix.zero(n)
x.times do
  a, b = gets.split.map(&:to_i)
  m[b - 1, a - 1] += 1
end
s = m.column_vectors.map{ _1.sum.to_f }
n.times do |i|
  n.times do |j|
    m[i, j] /= s[j]
  end
end
v = Matrix.column_vector([1.0 / n] * n)
100.times do
  v = m * v * 0.85
  v += Matrix.column_vector([(1 - 0.85) / n] * n)
end
puts v

# output
Matrix[[0.2541917802460697], [0.13803150660856423], [0.13803150660856423], [0.20599017093683208], [0.2637550355999698]]

普段Matrixを使用していないので、もう少しきれいに書きたかったです。

Numo::NArray

narray.rb

require 'numo/narray'

n, x = gets.split.map(&:to_i)
m = Numo::DFloat.zeros(n, n)
x.times do
  a, b = gets.split.map(&:to_i)
  m[b - 1, a - 1] += 1
end
n.times do |i|
  s = m[true, i].sum
  n.times do |j|
    m[j, i] /= s
  end
end
v = Numo::DFloat.new(n).fill 1.0 / n
100.times do
  v = m.dot v * 0.85
  v += Numo::DFloat.new(n).fill (1 - 0.85) / n
end
p v

# output
[0.254192, 0.138032, 0.138032, 0.20599, 0.263755]

はじめて？使用したので、怪しいところがあるかもしれませんが。

benchmark

benchmark.rb

require 'numo/narray'
require 'benchmark'
require_relative 'lib/networkx'
require 'matrix'

@n = 300
Benchmark.bm 10 do |r|
  r.report "networkX" do
    g = NetworkX::DiGraph.new
    @n.times do |i|
      g.add_edge(i, (i + 1) % @n)
    end
    NetworkX.pagerank(g)
  end

  r.report "matrix" do
    m = Matrix.zero(@n)
    @n.times do |i|
      m[(i + 1) % @n, i] += 1
    end
    s = m.column_vectors.map{ _1.sum.to_f }
    @n.times do |i|
      @n.times do |j|
        m[i, j] /= s[j]
      end
    end
    v = Matrix.column_vector([1.0/@n] * @n)
    @n.times do
      v = m * v * 0.85
      v += Matrix.column_vector([(1 - 0.85) / @n] * @n)
    end
  end

  r.report "narray" do
    m = Numo::DFloat.zeros(@n, @n)
    @n.times do |i|
      m[(i + 1) % @n, i] += 1
    end
    @n.times do |i|
      s = m[true, i].sum
      @n.times do |j|
        m[j, i] /= s
      end
    end
    v = Numo::DFloat.new(@n).fill 1.0 / @n
    @n.times do
      v = m.dot v * 0.85
      v += Numo::DFloat.new(@n).fill (1 - 0.85) / @n
    end
  end
end

# output
                 user     system      total        real
networkX   107.812000   0.046000 107.858000 (108.873295)
matrix       2.282000   0.000000   2.282000 (  2.311542)
narray       0.062000   0.000000   0.062000 (  0.058779)

とりあえず、ベンチマークを取ってみました。
networkXより、即席で作成したMatrix版の方が成績が良くて、困ったものです。

それにしても、Numo::NArrayは爆速ですね。

まとめ

• pegerank に更に詳しくなった