LoginSignup
13
5

More than 1 year has passed since last update.

@HMMNRST

AtCoderでRubyの数値配列 Numo::NArray を利用…する前の基礎勉強

Last updated at Posted at 2020-04-18

2020年4月12日開催の AtCoder Beginner Contest 162 から、正式に Ruby 2.7 が使えるようになった。

お知らせ

  • 本コンテストから、使用可能言語が変更となります。
  • 使用可能な言語は、このページの下部をご確認ください。

詳細情報を見てみると、個人的にRubyのバージョンより気になる記載があった。

項目 値
言語 Ruby
実装 CRuby
バージョン 2.7.1
コンパイルコマンド ruby -w -c {dirname}/{basename}
実行コマンド RUBY_THREAD_VM_STACK_SIZE=268435456 ruby {dirname}/{basename}
インストール済みライブラリ numo-narray

ライブラリ（RubyGems）として Numo::NArray が使えるようになっていた（たしか今までは無かったはず）。これである種の配列操作はRubyレベルではループを回さず実行可能になる。

とはいえ私は旧版のNArrayを昔に使っていただけなので、AtCoderで実用的に使うにはまだ経験値が足りない。NArrayを使うことで有利になる場面があるのかすらわからない。そこでまずは基本的な使い方を確認していくことにする。

概要

Arrayと比較しながらNArrayの使い方を見ていく。AtCoderで使いそうなものに絞る。

  • データ読み込み
    • Int64.cast(ary) といった感じでArrayから変換するのが簡単かつ高速
    • 一応 Int64.parse(str) でAtCoderの色々な入力形式に対処できる、が遅いのでほぼ利点が無い
    • 1文字単位で配列化するなら Int8.from_binary(str) が超高速
  • 配列操作
    • 多次元配列の扱いが断然楽
    • 部分配列を作っても元の配列と共有される
  • 演算
    • 多くのことがループを回さず演算できる
    • 統計処理も用意されている（が整数型では多くない）
    • 整数型の算術オーバーフローに注意が必要

準備

（環境構築）

手元で試せるよう、AtCoderに合わせたバージョンを用意する。

# rbenv で ruby2.7.1 をインストール
(cd $(rbenv root)/plugins/ruby-build && git pull)
rbenv install 2.7.1

# ruby2.7.1 に numo-narray 0.9.1.6 をインストール
rbenv shell 2.7.1   # このシェルでのみ有効化
gem install numo-narray:0.9.1.6

# irb を起動
irb

ライブラリ読み込み

組み込みライブラリではないので、使うには require する必要がある。慣習的にgem名のハイフンは名前空間の区切りを意味し、 require するときのパス名ではスラッシュ、クラスやモジュールでは :: になる。

Numo::NArray::VERSION #=> NameError (uninitialized constant Numo)

require 'numo/narray'
Numo::NArray::VERSION #=> "0.9.1.6"

毎回 Numo:: を打つのが面倒なら、 include Numo としておけばいい。

データ読み込み

AtCoderによく出てくる入力形式に関して記す。

NArrayは中身の型が決まっているので、基本的に最初から数値型を指定しなければならない。それぞれ NArray のサブクラスとして定義されている。AtCoderならひとまず Int64 （＝64bit符号付き整数）を選んでおけば安心だと思う。

RubyのArrayから変換

クラスメソッド .cast によって簡単にArray（や他のNArrayの型）から変換できる。各入力形式についてNArray専用の方法を覚えるよりこれだけ覚えるほうが導入しやすいうえに、ほとんどの場合に高速。

array = [[1, 2, 3], [4, 5, 6]]

narray = Numo::Int64.cast(array)
#=>
# Numo::Int64#shape=[2,3]
# [[1, 2, 3],
#  [4, 5, 6]]

逆にNArrayをArrayに変換したいときは、インスタンスメソッド #to_a を使う。

文字列を直接変換

文字列からの変換は .parse が良さそうだが、計測したところ明示的にArrayを経由するより10～20倍の時間がかかった。ソースコードによると、内部的には結局Arrayを作って .cast を呼んでいるのに加え、各要素の文字列は eval でRubyオブジェクトに変換している。処理速度よりも柔軟さを重視している感じがする。

というわけでAtCoderで使うことは少なそうなので、参考情報として残しておくだけとする。

入力形式毎の読み込み方法（クリックして詳細を表示）

空白区切りの整数列

.parse は行列を想定したものなので1行でも2次元配列扱いになってしまう。一応そのままでも使える1が、後でハマると嫌なので #reshape!2 で1次元に直しておく。

# 標準入力を模倣する
require "stringio"
line = "1 2 3\n"
$stdin = StringIO.new(line * 10, "r")

array = gets.split.map!(&:to_i)
#=> [1, 2, 3]

narray = Numo::Int64.parse(gets).reshape!(nil)
#=>
# Numo::Int64#shape=[3]
# [1, 2, 3]

2次元配列

1次元化しなくていいぶん簡単…と言いたいが、「標準入力から N 行」という条件だと読み込みに工夫がいる。

# 標準入力を模倣する
require "stringio"
data = <<~EOF
	1 2 3
	4 5 6
EOF
$stdin = StringIO.new(data * 10, "r")

N = 2

array = Array.new(N) { gets.split.map!(&:to_i) }
#=> [[1, 2, 3], [4, 5, 6]]

narray = Numo::Int64.parse($stdin.take(N).join)
#=>
# Numo::Int64#shape=[2,3]
# [[1, 2, 3],
#  [4, 5, 6]]

巨大な整数

64bit整数に収まらない数が与えられるときは、桁毎にバラして配列化することが多い。

この場合は .parse のキーワード引数を使って、1文字ずつ区切る（＝区切りを空文字列にする）よう指定すればいい。型は Int8 で十分だが、後の演算時にオーバーフローしないよう注意。

# 標準入力を模倣する
require "stringio"
line = "3141592653\n"
$stdin = StringIO.new(line * 10, "r")

array = gets.chomp.chars.map!(&:to_i)
#=> [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

narray = Numo::Int8.parse(gets, split1d: '').reshape!(nil)
#=>
# Numo::Int8#shape=[10]
# [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

2値の盤面 方法1

各マスの状態を文字 . # で表した長方形の盤面が与えられることがある。

booleanの2次元配列を作りたければ、型に Bit を使えばいい。文字列の記号を数字 0 1 に置換すれば、「空白の無い行列」とみなせるのでこれまでの方法の組み合わせで読み込める。

# 標準入力を模倣する
require "stringio"
data = <<~EOF
	###
	..#
	.#.
EOF
$stdin = StringIO.new(data * 10, "r")

H, W = 3, 3

array = Array.new(H) { gets.chomp.chars.map! { |c| c == '#' } }
#=> [[true, true, true], [false, false, true], [false, true, false]]

narray = Numo::Bit.parse($stdin.take(H).join.tr('.#', '01'), split1d: '')
#=>
# Numo::Bit#shape=[3,3]
# [[1, 1, 1], 
#  [0, 0, 1], 
#  [0, 1, 0]]

1文字単位で配列化

String#bytes を使っていた箇所なら、 Int8.from_binary に置き換えられる。名前通り本来はバイナリデータを読み込むものなので非常に速い。難点は何をしているのか理解しにくいこと。

逆にバイナリデータを書き出す操作は #to_binary でできる。

文字列のコードポイント

文字列が与えられた際に、Rubyの処理性能向上のため整数配列に変換したいことがある。AtCoderで与えられる文字列はふつうASCIIの範囲内なので、バイト列として読み込めばすぐ変換できる。

# 標準入力を模倣する
require "stringio"
line = "abcxyz\n"
$stdin = StringIO.new(line * 10, "r")

array = gets.chomp.bytes
#=> [97, 98, 99, 120, 121, 122]

narray = Numo::Int8.from_binary(gets.chomp)
#=>
# Numo::Int8#shape=[6]
# [97, 98, 99, 120, 121, 122]

巨大な整数を桁毎にバラす際も、コードポイントから計算すればいい。

# 標準入力を模倣する
require "stringio"
line = "3141592653\n"
$stdin = StringIO.new(line * 10, "r")

array = gets.chomp.bytes.map! { |b| b - 0x30 }
#=> [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

narray = Numo::Int8.from_binary(gets.chomp) - '0'.ord
#=>
# Numo::Int8#shape=[10]
# [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

2値の盤面 方法2

.parse の方法では tr('.#', '01') と置換して読み込んだが、先にNArray化してからbooleanに直すこともできる。改行コードの存在に注意。

# 標準入力を模倣する
require "stringio"
data = <<~EOF
	###
	..#
	.#.
EOF
$stdin = StringIO.new(data * 10, "r")

H, W = 3, 3

array2 = Array.new(H) { gets.chomp.bytes.map! { |b| b == 0x23 } }
#=> [[true, true, true], [false, false, true], [false, true, false]]

# 改行コードが1バイト（CRLFでない）と仮定
narray2 = Numo::Int8.from_binary($stdin.read(H * W.succ), [H, W.succ])[true, 0...W].eq('#'.ord)
#=>
# Numo::Bit#shape=[3,3]
# [[1, 1, 1], 
#  [0, 0, 1], 
#  [0, 1, 0]]

配列の操作

単純な配列の生成

データを読み込むのではなく連番などを作りたいこともある。Arrayによる多次元配列（配列の配列）の場合は同じオブジェクトの参照（浅いコピー）にならないよう注意がいるが、NArrayではその心配は無い。

# 全て同じ値
Array.new(2) { Array.new(3, 7) }
Numo::Int64.new(2, 3).fill(7)

# 連番
(1..).each_slice(3).take(2)
Numo::Int64.new(2, 3).seq(1)

# 繰り返し
array = (0..).each_slice(3).take(2)
array.map { |row| row * 3 } * 2  # 浅いコピーがあることに注意

narray = Numo::Int64.new(2, 3).seq
narray.tile(2, 3)
#=>
# Numo::Int64#shape=[4,9]
# [[0, 1, 2, 0, 1, 2, 0, 1, 2],
#  [3, 4, 5, 3, 4, 5, 3, 4, 5],
#  [0, 1, 2, 0, 1, 2, 0, 1, 2],
#  [3, 4, 5, 3, 4, 5, 3, 4, 5]]

要素の参照と更新

基本はArrayによる多次元配列（配列の配列）の添字ルールと同じ。

  • 右側の添字が早く回る3
  • 0始まりで、負の数を入れれば逆順に参照できる
  • 「配列の配列」ではなく、ひとつの [] に複数の添字を並べる
    • Array#dig の引数と同様
    • Array#[] にあった「開始位置と長さを指定する方法」はNArrayには無い

加えて、NArrayは形状を無視して1次元配列としてもアクセスできる。

# 4x3x2の3次元配列に、先頭から順番に 0, 1, 2, … と値を入れておく
array = (0..).each_slice(2).each_slice(3).take(4)
narray = Numo::Int64.new(4, 3, 2).seq

# 以下は全て 13 を返す
array[2][0][-1]
array.dig(2, 0, -1)

narray[2, 0, -1]
narray[13]

[]= を使えば、その要素の値を変更できる。

部分配列

多次元配列でも操作しやすいという特徴のほか、「ビュー」という概念が重要になる。

1次元の場合

Rangeで範囲指定して取り出せる。Arrayと同じに結果に見えるが、異なる動作をしている。

array = [*0...5]
narray = Numo::Int64.new(5).seq

sub_array = array[1...-1]
sub_array[0..1] = [9, 8]
sub_array #=> [9, 8, 3]
array     #=> [0, 1, 2, 3, 4]

sub_narray = narray[1...-1]
sub_narray[0..1] = [9, 8]
sub_narray #=> Numo::Int64(view)#shape=[3] [9, 8, 3]
narray     #=> Numo::Int64#shape=[5] [0, 9, 8, 3, 4]

Arrayでは各要素をコピーした新しい配列が作られる。NArrayでは元の配列の「ビュー」（窓）を取得でき、ビューの要素を変更すると元の配列にも反映される。巨大な配列を切り出すときは有利かもしれない。

ビューをやめて新しいNArrayを作りたければ、ビューに対して #copy を呼び出せばいい。

2次元の場合

例えば「それぞれの配列から3番目（添字2）の要素のみを抜き出す」という操作を考える。Arrayなら #map で個々に抽出するか #transpose してから選択する必要がある。NArrayでは各次元にRangeと整数を指定するだけでいい。

array = (0..).each_slice(7).take(5)
narray = Numo::Int64.new(5, 7).seq

array.map { |a| a[2] } #=> [2, 9, 16, 23, 30]
array.transpose[2]     # 同上

narray[0..-1, 2] #=> Numo::Int64(view)#shape=[5] [2, 9, 16, 23, 30]
narray[true, 2]  # 0..-1 なら true と指定してもいい

また、1次元の例と同様に範囲を絞れば、矩形領域さえも簡単に抜き出せる。

narray[1..2, 3..6]
#=> 
# Numo::Int64(view)#shape=[2,4]
# [[10, 11, 12, 13], 
#  [17, 18, 19, 20]]

3次元以上の場合

これ以降はArrayでは複雑すぎてやらないと思う。部分配列が必要なときは、配列定義時の添字の順序を変えて処理が単純にならないか検討したい。

NArrayでは2次元と同様に、各次元でRangeか整数を指定すれば簡単に切り出せる。整数を指定した分だけ、結果の配列の次元は小さくなる。

形状の取得と変更

多次元配列の形状は #shape で取得できる。また、大きさが同じ別形状の配列を作るときは #reshape を使う。

narray1 = Numo::Int64.new(24).seq  #=> Numo::Int64#shape=[24] [...]
narray2 = narray1.reshape(4, 6)    #=> Numo::Int64#shape=[4,6] [...]
narray3 = narray2.reshape(2, 3, 4) #=> Numo::Int64#shape=[2,3,4] [...]

narray3.shape #=> [2, 3, 4]

転置 #transpose は多次元配列版として「添字順序の並べ替え」になっている。引数なしなら順序を反転させることになる（→2次元配列ならArrayと同じ動作）。

narray3
#=>
# Numo::Int64#shape=[2,3,4]
# [[[0, 1, 2, 3],
#   [4, 5, 6, 7],
#   [8, 9, 10, 11]],
#  [[12, 13, 14, 15],
#   [16, 17, 18, 19],
#   [20, 21, 22, 23]]]

narray3.transpose(2, 0, 1)
#=>
# Numo::Int64(view)#shape=[4,2,3]
# [[[0, 4, 8], [12, 16, 20]],
#  [[1, 5, 9], [13, 17, 21]],
#  [[2, 6, 10], [14, 18, 22]],
#  [[3, 7, 11], [15, 19, 23]]]

narray3.transpose
#=> Numo::Int64(view)#shape=[4,3,2] [...]

条件抽出

Arrayなら #select などを使って各要素をひとつずつ評価していく。

NArrayでは単純な条件なら、配列のまま評価して Bit の配列を作ることで抽出などの操作が可能になる。

array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
narray = Numo::Int64.cast(array)
#=> Numo::Int64#shape=[10] [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

# 配列のなかで5以上の要素とその添字
array.select { |x| x >= 5 } #=> [5, 9, 6, 5]
array.each_index.select { |i| array[i] >= 5 } #=> [4, 5, 7, 8]

mask = (narray >= 5) #=> Numo::Bit#shape=[10] [0, 0, 0, 0, 1, 1, 0, 1, 1, 0]
narray[mask] #=> Numo::Int64(view)#shape=[4] [5, 9, 6, 5]
mask.where #=> Numo::Int32#shape=[4] [4, 5, 7, 8]

== など一部の比較演算子はオブジェクトの比較（booleanを返す）になってしまうので、要素の比較（boolean配列を返す）には代わりに #eq などを使う必要がある。

ループ（イテレーター）

NArrayではいかにループを使用しないかが重要なので出番は少ない。Arrayと大きく異なる点は Enumerable をincludeしていないこと。 ※ただし同名のメソッドがいくつか用意されている（集計の節を参照）

ループ用のメソッドは #each, #each_with_index, #map, #map_with_index がある。indexは可変長引数で渡ってくるので、ブロックの仮引数を |x, i, j| などとしてもいいし |x, *idx| と配列化してもいい。

narray = Numo::Int64.new(2, 3).seq

narray.each_with_index { |x, *idx| puts "narray[#{idx * ','}] = #{x}" }
narray.map_with_index  { |x, *idx| idx.inject(x, :*) }

破壊的メソッドの Array#map! 相当に関しては発展編を参照。

演算

「Rubyレベルでループを回さず計算する」という利点を活かすには必須。

（整数型の注意点）

  • Ruby組み込みの Integer クラスは任意長の整数を扱えるが、 NArray の整数型は上限があるため、算術オーバーフローに注意しなければならない
  • 除算 / と剰余 % は負の数が絡むと結果が異なる場合がある（余り付き除算の定義がC言語とRubyで異なるため）

要素毎の演算

多くの単項・2項演算子が使える。基本的には2種類の使い方を覚えておけばいい。

  • NArrayと通常の数値の演算
  • 同じ形状のNArray同士の演算
    • 形状が異なっていても計算できるパターンについては発展編で触れる
narray1 = Numo::Int64.new(2, 3).seq(1)
narray2 = Numo::Int64.new(2, 3).seq(1)

# NArray と 通常の数値 の演算（順序はどちらも可能）
10 - narray1
#=>
# Numo::Int64#shape=[2,3]
# [[9, 8, 7], 
#  [6, 5, 4]]

# 同じ形状の NArray 同士の演算
narray1 * narray2
#=>
# Numo::Int64#shape=[2,3]
# [[1, 4, 9],
#  [16, 25, 36]]

部分配列を用いることでより幅広い計算が可能になる。

# 三角数の数列 a_n = n(n+1)/2
narray = Numo::Int64.new(12).seq
narray[0..-2] * narray[1..-1] / 2
#=>
# Numo::Int64#shape=[11]
# [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

集計

#sum, #minmax など、 Enumerable にあるようなメソッドが存在する。NArray版の特徴は、ある次元に沿った集計もできる（戻り値がNArray）ということ。

narray = Numo::Int64.new(4, 3, 2).seq

narray.sum       #=> 276
narray.sum(0)    #=> Numo::Int64#shape=[3,2] [...]
narray.sum(0, 2) #=> Numo::Int64#shape=[3] [...]
narray.sum(-1)   #=> Numo::Int64#shape=[4,3] [...]

浮動小数点数であれば、平均 #mean, 分散 #var, 標準偏差 #stddev といった統計処理も使える。

Bit はboolean配列なので、 #sum などは無いが #all?, #any?, #count4 などが使える。

累積和

累積和 #cumsum は地味に便利。

narray = Numo::Int64.new(5).seq * 2 + 1
#=> Numo::Int64#shape=[5] [1, 3, 5, 7, 9]

narray.cumsum
#=> Numo::Int64#shape=[5] [1, 4, 9, 16, 25]

# 同じことをArrayでする場合
array = narray.to_a
tmp = 0; array.map { |x| tmp += x } #=> [1, 4, 9, 16, 25]

多次元の累積和は、処理する次元を指定して narray.cumsum(0).cumsum(1) という感じで繰り返す必要がある。

数学関数

Ruby組み込みに Math 、標準添付ライブラリbigdecimalに BigMath があるように、NArrayには Numo::NMath がある。整数を与えた場合は浮動小数点数に変換される。

Numo::NMath.log2(8 ** Numo::Int64.new(4).seq)
#=> Numo::DFloat#shape=[4] [0, 3, 6, 9]

発展編

難易度と利用頻度を考えると飛ばしてよさそうな話。ここまでしなくてもAtCoderは解けるはず。

形状の異なるNArray同士の計算規則

  1. 配列でない数は「0次元配列」とみなす
  2. 次元が異なる場合は、次元の小さいNArrayに大きさ 1 の次元を追加して揃える
  3. 同じ次元の大きさが片方が 1 でもう片方が 2 以上なら、 1 のほうは内容をコピーしてもう片方の大きさに揃える（「単純な配列の生成」で扱った NArray#tile を想像すればいい）
  4. 添字の同じ要素同士で演算する

例えば九九の2次元配列は以下のように作れる。

narray1 = Numo::Int64.new(9).seq(1) #=> Numo::Int64#shape=[  9]
narray2 = narray.reshape(nil, 1)    #=> Numo::Int64#shape=[9,1]
narray1 * narray2                   #=> Numo::Int64#shape=[9,9]
  • narray1 のほうが次元が小さいので、 shape=[1,9] として次元を揃える
  • narray1 と narray2 どちらも大きさ 1 の次元があるので、 shape=[9,9] として揃える

破壊的メソッドとinplace演算

NArrayのメソッドにも、自身のオブジェクトを書き換える「破壊的メソッド」がある。それに加えて、オブジェクトの inplace フラグによって破壊的操作を試みるメソッドが存在する。これをうまく使えば、新しいオブジェクトが作られるオーバーヘッドを減らせる。

narray = Numo::Int64[3, 1, 4, 1, 5, 9]

# 新しい配列を作るので narray は変わらない
narray + 1
narray.map { |x| 10 - x }
narray.sort
narray #=> Numo::Int64#shape=[6] [3, 1, 4, 1, 5, 9]

# inplaceフラグを立てる
narray.inplace!

# 自身を書き換える
narray + 1
narray.map { |x| 10 - x }
narray.sort
narray #=> Numo::Int64#shape=[6] [0, 4, 5, 6, 8, 8]

# inplaceフラグを下ろす
narray.out_of_place!

純粋な破壊的メソッドと異なり、inplace演算が適切でないときは新しいオブジェクトを作るので、利用するときは毎回結果を同じ変数に代入するほうが安全。 narray += 1 といった自己代入演算子も使える。

Rubyオブジェクトの配列

64bitを超える整数や、分数、 nil などを使いたいとなれば、Rubyのオブジェクトを要素とする配列を作ればいい。ただし、配列のまま使える演算子やメソッドはかなり限られ、NoMethodErrorどころか期待と異なる結果になる場合すらある。

# 余り付き除算の定義がC言語とRubyで異なるという話（※この結果は期待通り）
dividends = [8,  8, -8, -8]
divisors  = [3, -3,  3, -3]

Numo::Int64.cast(dividends) % Numo::Int64.cast(divisors)
#=> Numo::Int64#shape=[4] [2, 2, -2, -2]
Numo::RObject.cast(dividends) % Numo::RObject.cast(divisors)
#=> Numo::RObject#shape=[4] [2, -1, 1, -2]

参考

  1. 内部的には連続した1次元配列であり、多次元配列であっても1次元として参照できる。 ↩

  2. 引数に各次元の大きさを与えるが、大きさに true または nil を1ヶ所だけ指定すると、他の次元の大きさから自動決定してくれる。 ↩

  3. 旧版のNArrayは、Fortranと同じで左側の添字が早く回る。 ↩

  4. Bit#count はtrueの個数を返す。 ↩

13
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
13
5