書き方で変わる消費メモリ with Ruby #Ruby

書き方を変えるだけで消費メモリは変わるらしい

今回は、書き方を変えれば消費メモリは変わるよっていう記事です。今後、要因がわかり次第追記予定です。

メモリとは

データ・プログラムの一時保存を行うメモリーメモリーとは、データを記憶する部品のことです。

考えるべきメモリ領域

メモリ領域には3つの種類があります。メモリ領域には、静的領域、ヒープ領域、スタック領域と3種類あります。

ヒープ領域とは

ヒープ領域とは、プログラムの実行時に動的に確保するためのメモリ領域です。
プログラム実行時に逐次メモリの割り当てが要求されるような動的処理、動的なオブジェクトの定義の際にメモリ領域を割り当てる役割を担っています。割り当ては、プログラム実行時にアプリケーションから必要なサイズのメモリを要求される事により、ヒープ領域から割り当てられます。また、この領域は、まとまった空き領域をなるべく大きくしてメモリの有効活用をはかることや、複数スレッドから同時に割り当て要求が来た場合でも整合性を保つ制御が必要なため、OSや仮想マシンが提供してくれます。割り当てや、不要なメモリの解放処理はこの管理機能を介して行います。
ヒープ領域は限られているので余分なメモリの確保や不要なメモリの解放を忘れてしまう事によるメモリリークも存在する事を把握しておきましょう。

競プロ問題で発見した消費メモリを減らした書き方

Rubyのような動的型づけ言語では、プログラム実行時にかなりのヒープ領域を消費します。但し、書き方によっては、消費メモリーを減らす事もできるという事を現在やっているAtCorderで気づきました。では、解説していきたいと思います。
(githubでAtCorderの自分のAnswerも公開しています!)→https://github.com/fujisawaryohei/AtCorder

今回の問題は、こちらです。
https://atcoder.jp/contests/abs/tasks/abc085_b

かなり優しい問題ではありますが、自分はこのような解答をしました。

arr = readlines.map{|x| x.chomp.to_i}
mochiLength = Array.new
(0..arr[0]-1).to_a.each_index do |idx|
   mochiLength[idx] = arr[idx+1]
end
print mochiLength.uniq.length

簡単に処理の流れを説明すると、まずは標準入力で受け取った複数行の数字の文字列の改行文字省きつつ、数値型に変換しました。この時、問題のSample入力の１行目が要素数であったので、その要素数を省いた配列を作りたかったため、その後、空配列を定義して、イテレーターで生成しました。その配列の中から被っている値を省いて、その要素数を出力して終了です。

この時の実行時間と消費メモリはこのようになりました。一番右が消費メモリです。右から2番目が実行時間です。

こちらをこのように書き直してみました。

arr = readlines.map{|x| x.chomp.to_i}
mochiLength = Array.new
(0..arr[0]-1).to_a.each_index{|idx| mochiLength[idx] = arr[idx+1]}
print mochiLength.uniq.length

この時の実行時間と消費メモリはこのようになりました。実行時間が早くなり、消費メモリが減りました。

今後要因がわかり次第追記予定

下記の要因がわかり次第追記予定ですが、今回は、少し書き方を変えれば消費メモリが変わるよっていう記事でした。
おそらくヒープ領域のポインタ格納メモリとRubyのオブジェクト領域のメモリについてより深く知る事ができると、何故なのかがわかると思うのですので、要因がわかり次第追記していく予定です。

下記の記事を参照しつつ、使って検証していきます。
http://yoskmr.hatenablog.com/entry/2015/12/08/031234
https://techracho.bpsinc.jp/hachi8833/2017_11_30/48130