配列[5, 2, 4, 6, 1, 3]を深いコピーをしたい

Question

やりたいこと・疑問点

挿入ソートを実装しています。
並べ替える過程を追いたくて、@resultに過程をpushしています。
同じ位置で

p ary
@result << ary

を書いているのに@resultには、ソート済みの配列が入っているのはなぜでしょうか？

該当のソースコード

N=gets.to_i
A=gets.split.map(&:to_i)

@result = []
def insertionSort(tmp, n)
  # ary=tmp.clone　←変更前
  ary = Marshal.load(Marshal.dump(tmp))
  p [tmp.object_id, ary.object_id]
  p [tmp[0].object_id, ary[0].object_id]

  (1...n).each{|i|
    p ary
    @result << ary

    v = ary[i]
    j = i - 1

    while j >= 0 && ary[j] > v do
      ary[j+1] = ary[j]
      j -= 1
    end
    ary[j+1] = v
  }
end

insertionSort(A, N)
p @result

入力

6
5 2 4 6 1 3

出力

[13220980, 13220860]　# 異なる
[11, 11] # 同じ
[5, 2, 4, 6, 1, 3]
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]

Comments

[gemmaro]

インスタンス変数 `@result` はどのような意図でしょうか．このコードはクラス定義の内部から抜粋したものですか？

[m.ts10806]

＞Rubyでわからないことがあります
タイトルには要件を。
https://teratail.com/help/question-tips#questionTips3-1

[moon_light]

すみませんm(__)m
修正しました。

Answer 1

ソートが配列aryを直接書き換えることで行われているため、同じオブジェクトであるaryを@resultに入れても、そちらも変化し続けます。

Comments

[moon_light]

回答ありがとうございます。
↑のgemmaroさんへの回答を参考に、回答していただけるとありがたいです。m(__)m

Answer 2

Rubyのドキュメントによると， ary = tmp.clone の箇所で使っている clone は， Array -> Object -> Kernel のように辿って， Kernel#clone [1] のことですね．これは

Produces a shallow copy of ...

とあるように，所謂深いコピーではないです．
ただ，この箇所が直接の問題ではなさそうで，注目すべきは result << ary のところです． result に何度か追加されたとしても， ary は shallow copy されたものなので，その正体はどれも同じですし， ary に対する最後の変更は result に含まれる他全ての要素に波及します．
質問文の出力で result の要素が 全て同じかつ整列された ary の可視化結果になっているのも頷けます．

参考

• [1] “module Kernel - Documentation for Ruby master.” (accessed Feb. 20, 2021).

Comments

[moon_light]

回答ありがとうございます。
回答していただいたことを調べたところ、参照・浅いコピー・深いコピーがあることを知りました。
そこで、深いコピーをすれば自分の望む出力が得られるのではないかと考え、
ary=tmp.clone
ではなく
ary = Marshal.load(Marshal.dump(tmp))
でコピーを行ってみたところ、出力の通りtmpとaryのobject_idは異なるのですが、
tmpとaryのそれぞれの要素のobject_idが同じになっていました。
これは、配列の要素が整数で、整数は Immutableだからということがわかりました。
ではtmpのような要素が整数(Immutable)の配列に対して、深いコピーを行うにはどのような方法を用いたら良いのでしょうか？

長いうえに分かりづらい文章で恐縮ですが回答いただけると幸いです。(__)

[maisumakun]

> tmpとaryのそれぞれの要素のobject_idが同じになっていました。

小さな整数については、同じ値のobject_idは必ず「同じ」です。整数オブジェクト自体はImmutableなので、これによる問題はありません。