Java clone()メソッドによる深いコピーの方法
Javaでclone()メソッドの挙動を調べていたがかなり面倒くさいことがわかった。
スクリプト言語なら一行書いて終わりだぞ・・・↓
import copy class Person: def __init__(self, name): self.name = name class Members: def __init__(self, name): self.person = Person(name) def change(self, name): self.person.name = name def show(self): print(self.person.name) if __name__ == '__main__': m1 = Members('taro') m2 = copy.deepcopy(m1) m1.change('jiro') m2.show()
大前提の説明。オブジェクトのコピー法として、
・m2 = m1
・m2 = copy.copy(m1)
・m2 = copy.deepcopy(m1)
の3種類がある。
m2 = m1 は、参照型変数（という呼び方はPythonではあまりしないが、実態として参照型変数、ポインタ変数なのでここではそう書いておく）m2に、参照型変数m1が参照するオブジェクトの参照値を代入するので、
結果的にm2とm1は同じオブジェクトを参照する。
だから、m1を操作すればm2にも変更が及ぶ。
m2 = copy.copy(m1)は、m1の参照するオブジェクトをコピーして、m2にその新しいオブジェクトの参照値を代入する。
それぞれ別のオブジェクトなのだから、m1の変更はm2には及ばないはずである。
だが、オブジェクトm1にはメンバー変数としてm1.personが存在し、この変数にはPerson型オブジェクトへの参照値が代入されている。
コピーの際はこの参照値をコピーするので、m1のメンバー変数m1.personとm2のメンバー変数m2.personは同じオブジェクトを参照する。
なので、m1.personを操作するとm2.personも変わってしまい、見かけ上m1の変更がm2に及んでしまう。
（m1.personが指すオブジェクトを新しいオブジェクトに変更する、なら、m2.personは変わらない）
最後のdeepcopyは完全なコピーであり、m1.personを操作しようとm2.personには影響がない。なので、taroが出力される。
で、Javaでこれを実現するには、clone()メソッドを使って実現するのだが、これがまた面倒くさい。
clone()メソッドはそのままでは浅いコピーしか実現しないので、深いコピーを実現するようにオーバーライドしてやる必要があるというのだ。
// Person.java class Person implements Cloneable { String name; Person(String name) { this.name = name; } @Override public Person clone() { Person clone = null; try { clone = (Person) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return clone; } } // Members.java class Members implements Cloneable { Person p; Members(String name) { this.p = new Person(name); } void change(String name) { this.p.name = name; } void show() { System.out.println("name = " + this.p.name); } @Override public Members clone() { Members clone = null; try { clone = (Members) super.clone(); clone.p = this.p.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return clone; } public static void main(String[] args) { Members m1 = new Members("taro"); Members m2 = m1.clone(); m1.change("jiro"); m2.show(); } }
あらゆるクラスのご先祖クラスであるObjectクラスには、予め浅いコピーを実現するclone()メソッドが定義されている。
clone対象のオブジェクトのクラスはjava.lang.Cloneableインターフェースをimplementsしていなければならない（そうでない場合、検査例外、すなわちtry...catch必須のCloneNotSupportedExceptionが投げられる）。
また、戻り値はObject型で定義されているため、元の型の変数に代入するにはわざわざダウンキャストしてやる必要がある。
深いコピーの実現法としては、まずオブジェクトを浅いコピーしてから、各フィールドのうち参照型変数についても、再度浅いコピーをしてやる。そうすることで全部コピーされるよという理屈。
理屈はわかったし、上のコードで意図した動作にもなったのだが、他に楽な書き方がないのかどうかさっぱりわからない。
そもそもPerson.javaでclone()再定義しないといけないのか？
しなかったらなんかclone()はObjectでprotectedアクセスされますとかいう変なエラーが出るし。はぁ、なんでpublicじゃないんだ？
この言語ほんとただただめんどくさい。
逆ポーランド記法
逆ポーランド記法ってなんやねんって感じだったが（括弧なしではどうやって読めばいいのかわからず困惑していた）、
要するに数を順番にスタックに積んでいって、演算子がスタックに入ったら後に入れたほうから計算していくっていうだけのことなんやな。
難しそうに見えて全然難しくなかった。
逆ポーランド以外の記法はどういうデータ構造で実装すればいいんだろうか。スタックときたら次はキューか？
def calculate(arg): args_list = arg.split(' ') # space区切りの文字列として受け取る stack = [] if len(args_list) == 1: return float(arg) if len(args_list) == 2: return '入力が足りない' calc_dict = { '+': (lambda x, y: x + y), '-': (lambda x, y: x - y), '*': (lambda x, y: x * y), '/': (lambda x, y: x / y) } for str in args_list: if str in ['+', '-', '*', '/']: stack[-2] = calc_dict[str](stack[-2], stack[-1]) del stack[-1] else: stack.append(float(str)) return stack[0] if len(stack) == 1 else '計算途中'
ちなみにこのプログラムは正常な逆ポーランド記法に対しては正常に動作するはずだが、異常入力に対してどうなるかはまともに調べてないので知らない。
おかしな入力でエラーが出て落ちるのは別にいいのだが、おかしな入力からなぜか数字が出てきたりしたらまずい。
あるいは計算途中判定される？
入力の文字列の並びを見て、自動で逆ポーランド記法かそれ以外の記法か判定して、それに基づいて計算するプログラムとかできれば面白そうなんだが、さてさて。
じゃんけんプログラムと演算子オーバーロード
複数人でじゃんけんを続け、勝敗を記録するプログラムを作ってみた。練習用のプログラムでよくあるやつっすな。
実用性ねぇ
その際、グー、チョキ、パーとその勝敗をどう表そうか若干悩む。
C言語の列挙体みたいなのを使えればわかりやすそうだが、Pythonだと列挙体なさそう（最新版だとあるみたい？）だから、
とりあえず文字列'g' 'c' 'p'をそのまま使えばいいだろうとなった。
勝敗判定は、条件分岐をいちいち全部書いてたらだるそうだから、
辞書{'g':'c', 'c':'p', 'p':'g'}を定義することで行数削減。
その方針でコードを書き進めていたが、途中で演算子オーバーロードが使えるのでは？ と気づく。
要するに、グー＞チョキ、チョキ＞パー、パー＞グー みたいに書きたい。
A > B かつ B > C のときに A > Cが成り立っていない不等号なので、こういう定義の仕方は微妙かもしれんが。
というわけで、文字列の大小関係を定義しなおせばいいんだな。しめしめ、とテストコードを書き始める。
class String: def __gt__(self, x): # overload > return self < x print( 'a' > 'b' ) # 出力 False
期待通りに動かない。残当。
これでは既存のStringクラスのメソッドを書き換えようとしているので、
演算子オーバーロードでなく、そしてオーバーライドですらない（オーバーライドとは派生クラスのメソッドを再定義するものだから）。
ただただ危険な行為だから、そんなことはPythonでは最初からできないようにしているようだ。優しい。
一方、Rubyでは
class String def >(x) self < x end end print 'a' > 'b' # 出力 true
trueになったし！ 元のメソッド書き換えちまったし！ こわｗｗｗｗｗ
いや、それとももっと上位のクラスでメソッド>()が定義されていて、それをStringクラスで上書きしているだけなのか・・・？
それならこういう挙動になるのは理解できる。
まあ、Rubyの話はおいといて、Pythonでは既存のStringクラスのメソッドは書き換えられないので、
新たにJankenクラスを定義し、Jankenオブジェクト同士の不等号を定義することにする。
これなら問題はない。
import random class Janken: def __init__(self, gcp): # gcp in ['g','c','p'] self.gcp = gcp def __gt__(self, janken): # overload > tmp = {'g':'c', 'c':'p', 'p':'g'} return janken.gcp == tmp[self.gcp] class Human: def __init__(self, name): self.name = name self.win = 0 self.lose = 0 self.same = 0 self.mylist = [] def janken(self): tmp = [Janken('g'), Janken('c'), Janken('p')] n = random.randint(0, 2) self.mylist.append(tmp[n].gcp) return tmp[n] def show_result(self): print (self.mylist) print (self.win, self.lose, self.same) class Taikai: def __init__(self, *human): self.human_list = list(human) def janken(self, i, j): # human_i vs human_j def win(human1, human2): human1.win += 1 human2.lose += 1 def draw(human1, human2): human1.same += 1 human2.same += 1 human_i = self.human_list[i] human_j = self.human_list[j] comp_i = human_i.janken() comp_j = human_j.janken() if comp_i > comp_j: win(human_i, human_j) elif comp_j > comp_i: win(human_j, human_i) else: draw(human_i, human_j) taro = Human('Taro') jiro = Human('Jiro') taikai_1 = Taikai(taro, jiro) for i in range(24): taikai_1.janken(0, 1) taro.show_result() jiro.show_result() # 出力 # ['g', 'g', 'c', 'p', 'p', 'g', 'c', 'p', 'c', 'p', 'p', 'c', 'g', 'g', 'c', 'g', 'c', 'p', 'c', 'p', 'c', 'p', 'c', 'c'] # 8 6 10 # ['p', 'c', 'c', 'p', 'c', 'c', 'c', 'p', 'c', 'p', 'g', 'c', 'g', 'p', 'p', 'c', 'c', 'g', 'p', 'c', 'g', 'c', 'p', 'c'] # 6 8 10
変数・クラス・メソッド名があまりにもお粗末だったり、直接フィールド弄ってたりと色々よろしくない部分が多いが、
その問題はいったん見なかったことにする。
__eq__()も定義しようか迷ったが、元々Jankenクラスのオブジェクトに適用される、存在するわけでもない>記号を「新たに定義」するのと違って、
元から==演算子はJankenクラスのオブジェクトに対して適用できる。
これを上書き（？ 多重定義？ どっちだ？）しちゃうのは流石に危険だなーと思ってやめた。
こうして改めてコードを書いてみると、演算子オーバーロードとは何なのか、よくわかる。
オーバーライドとオーバーロードの違いは簡単だ。派生クラスで元のクラスのメソッドを上書きするか、同じクラスで同名のメソッドを複数定義するかの違いに過ぎない。
だが、「演算子オーバーロード」という言葉には昔から引っ掛かりしかなかった。
なぜ「オーバーライド」でないのか疑問に思っていたが、今回謎が若干解けたかもしれない。
例えば、Point(1, 3) + Point(10, 20) = Point(11, 23) みたいに「新しい」演算子+を定義するというお話だが、
ここで重要なのは「新しい」というところだ。
オーバーライドは上書きのことなので、上書きされる前の元のメソッドがある。
Pointクラスがどのクラスを継承しているのか知らないが（もしかしたらトップレベルを継承しているのかもしれないが）、
その派生元クラスに上書きされる前の元のメソッドがあるということになってしまう。
そういう話ではないだろう。
、とこう考えた後、悩むわけですよ。
例えば、実数クラスを継承して複素数クラスをつくるって話なら、実数クラスの演算・メソッドを継承して複素数の演算をつくるという話だっておかしくはない、少なくとも数学では。
Pointクラスだって、抽象ベクトル空間インターフェースを継承して加算演算を実装したという解釈だってできる。少なくとも数学では。
実際、Haskellの型クラスとかはそういう考えに立脚してるように思えるし。
あと、Jankenクラスに==演算子（__eq__()メソッド）を定義できるのは一体何なのかと。
これは多重定義というべきなのか、それとも上書きなのかと。
元から==演算子をJankenクラスのオブジェクトに適用できるので、全く新しい演算子とは言い難く、挙動だけ見ると上書き？ と言いたくなる。
それに、トップレベルでの
def 既存の+(<Type1> 引数群) {}
def 新しい+(<Type2> 引数群) {}
と、
def +(<Interface Addable>引数群) {引数1.add(引数2)}
って結局同じじゃない？ っていう疑問にも辿り着く。
ああ、わからない、わからない。演算子オーバーロードがわからない。
そもそも演算子オーバーロードというのはC++での概念で、他の言語でいうところの演算子オーバーロードなんて、
本家演算子オーバーロードに似てるからそう呼んでいるだけの俗称、と言われれば確かにそうだ。
動的型付けでオーバーロードとかそんなのあるのかって話だし（あるのかもしれない）。
結局、少なくともC++ではオーバーロードなんだから、そこは疑問の余地ないだろうという結論になる。
あとC++勉強しろという結論になる。
参照型変数の値渡しと参照渡しの違い
1.値型変数の値渡し 2.値型変数の参照渡し
3.参照型変数（ポインタ変数）の値渡し 4.参照型変数（ポインタ変数）の参照渡し
2と3が結果的に似たような挙動になるからといって、3のことを雑に参照渡しと呼んじゃうケースが多い気がする。
雑に説明するときはそれでいいのかもしれないが、後々混乱を招きそう。
using System.Collections.Generic; using System; class Test { public static void change(ref List<string> array) { array = new List<string>(); array.Add("bbb"); } public static void change2(List<string> array) { array = new List<string>(); array.Add("aaa"); } public static void change3(List<string> array) { array.Add("aaa"); } public static void Main() { List<string> array = new List<string>(); array.Add("hogehoge"); array.Add("foo"); change(ref array); // change2(array); // change3(array); foreach (string str in array) { Console.WriteLine(str); } } }
C#なんて全然触ったことないから、出鱈目な書き方してるかもしれない。とりあえず動きはしてる。
- changeの方は参照型変数の参照渡しで、array:["hogehoge", "foo"] が初期化された後、"bbb"が追加され、array:["bbb"]となる。
- change2の方は参照型変数の値渡しであり、メソッド内のarrayが色々変わるだけ。元のarray:["hogehoge", "foo"]は何も変わらない。
- change3も参照型変数の値渡しであるが、この場合はきっちりarrayが["hogehoge", "foo", "aaa"]に変更される。
C言語でポインタを苦労して学んだからこういう挙動の違いもすんなり理解できてる気がする。
やっぱりC言語の勉強は大事なのでは？
オブジェクトIDと関数への引数渡し
import java.util.List; import java.util.ArrayList; public class Main { public static void func(List<Integer> array) { array.set(0, 10); } public static void func2(List<Integer> array) { array = new ArrayList<Integer>(); array.add(10); array.add(2); } public static void main(String[] args) { List<Integer> p1 = new ArrayList<Integer>(); p1.add(1); p1.add(2); List<Integer> p2 = new ArrayList<Integer>(); p2.add(1); p2.add(2); func(p1); func2(p2); for (int n1: p1) System.out.print(n1 + ","); System.out.println(""); for (int n2: p2) System.out.print(n2 + ","); } } // 出力結果 // 10,2, // 1,2,
これは納得の挙動。
p2にはリスト[1, 2]への参照値が代入されていて、これがfunc2に渡される。
func2の仮引数arrayにp2に代入されていた[1, 2]への参照値がコピーされる。
新しいリストを作成し、その参照値をarrayに代入することで、arrayがp2を指さなくなる。
よって、arrayの指すリストをいくら弄ろうと、p2の指すリストは何一つ変わらない。
それでは言語を変えて。
def func(array): array[0] = 10 def func2(array): array = [10, 2] p1 = [1, 2] p2 = [1, 2] print( id(p1), id(p2), sep=', ') func(p1) func2(p2) print( p1, p2, sep= ', ' ) print( id(p1), id(p2), sep=', ') p2[1] = 20 print( id(p2), ',', sep= '', end='' ) p2 = [30, 40] print( '', id(p2) ) # 出力結果 # 140422113705928, 140422113251528 # [10, 2], [1, 2] # 140422113705928, 140422113251528 # 140422113251528, 140422113705160
p2に関してなんとも不思議な挙動をしている。
最後の行で示したように、p2[i] = n のようにリストの各要素の値を変更するだけでは、リストのidは変わらないが、
p2 = [n1, n2]のようにすると、リストのidは変わってしまう。
ということは、新しいリストを作成して、変数がその新しいリストを指すようになった、としか思えない。
だったら、func2でp2のidは変わらないとおかしくない？
PythonだけでなくRubyでも全く同じ結果で困惑している。
func2(p2)と書くところをfunc(p2)とタイプミスしてました。
正しく書くと完全に想定通りの結果でした。
マージソート
部分リストのうまい取り方がわからん
merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys mergesort :: [Int] -> [Int] mergesort [] = [] mergesort [n] = [n] mergesort list = merge list1 list2 where size_center = (length list) `div` 2 leftlist = [list !! index | index <- [0..size_center - 1]] rightlist = [list !! index | index <- [size_center..(length list) - 1]] list1 = mergesort leftlist list2 = mergesort rightlist
素数の列を返すプログラム、素数かどうか判定するプログラム
素数の列を返すプログラムを書いてみる。
def prime(n): # nまでの素数のリストを返す if n == 2: return [2] elif n > 2: array = [2] # 素数を集める for i in range(3, n + 1): # 3～nが素数かどうか for p in array: if i % p == 0: # 素数で割り切れたとき break else: array.append(i) return array
2以上の整数nが素数であることの定義は、nが1とn以外のいずれの整数でも割り切れないことなので、
3以上の整数については、2～n-1の範囲で割れるか調べればよい。
のだが、それでは効率が悪い、実際は2～n-1の中の素数で割れるか調べるだけで十分。
（素数以外の整数（合成数という）は素数の積に分解できるので、素数で割れないならその素数を素因数にもつ合成数でも割れない）
なので、素数を集めておくリストを作っておき、素数判定のたびにリストに追加していき、そのリストを用いて次の数の素数判定を行っている。
素数の列を返して欲しいプログラムなのでどうせこのリストは必要になり、この方法が効率がよい。
だが、単にある数nが素数かどうか判定したいだけのときに、まずn-1までの数が素数かどうか調べるこの方法がいいのかどうかは知らん。
というか、ちょっと考えただけでもめっちゃ効率悪そう。
「9999までの素数をすべて列挙せよ」ならともかく、「9999が素数かどうか判定せよ」なんていう本来一瞬で解き終わる問題が、この方法だと途方もない時間がかかりそうだ。
アルゴリズムの発想はあまり変えず、微妙に書き方を変えてみる。
def ismyprime(n): # nが素数かどうか判定する if n == 2: return True elif n > 2: # 「nが素数である」とは、「nがn未満の素数で割り切れない」 array = filter(ismyprime, range(2, n)) for p in array: if n % p == 0: return False else: return True else: return False def myprime(n): # nまでの素数のリストを返す return list( filter(ismyprime, range(2, n + 1)) )
先ほどのプログラムでは2重ループでarrayにどんどん追加していったが、
ここでは再帰を用いて宣言的に書き換えた。
このプログラムでも動くが、代償として実行速度がお察し状態になった。
myprime(70)を試すと一瞬で動作が終わるprime(70)と比べて遅く感じられる。
myprime(100)は待ち切れないので強制終了させた。
インタプリタだから遅いとか元のアルゴリズムが非効率とかいうより、
酷い再帰の書き方で実行速度がお察しになったのだろう。
isprime :: Int -> Bool isprime n | n <= 1 = False | n == 2 = True | otherwise = foldr (\p acc -> if n `mod` p == 0 then False else acc) True (filter isprime [2..n - 1]) prime :: Int -> [Int] prime n = filter isprime [2..n]
畳み込み関数を使うとコンパクトにまとまるが、慣れていないと読みにくい。しかも無駄な計算してる気がする。
原始的な再帰で書くとこうなる。
not_divisible :: Int -> [Int] -> Bool not_divisible n [] = True not_divisible n (x:xs) | n `mod` x == 0 = False | otherwise = not_divisible n xs isprime :: Int -> Bool isprime n | n <= 1 = False | n == 2 = True | otherwise = not_divisible n (filter isprime [2..n - 1])
部分適用とelem関数を上手く使うともっとわかりやすくなる。遅延評価の言語だから途中で無駄な計算は発生しないはず？
isprime2 :: Int -> Bool isprime2 n | n <= 1 = False | n == 2 = True | otherwise = not $ 0 `elem` (map (n `mod`) (filter isprime [2..n - 1])) prime2 :: Int -> [Int] prime2 n = filter isprime2 [2..n]
いずれのプログラムもprime 70くらいから遅い。これならfilter isprime [2..n - 1]とか使わずに[2..n - 1]をそのまま使っとけって感じだ。
というわけで、エラトステネスの篩ってどう実装すればいいんだっけとググる。
正しくはこうらしい。
prime :: [Int] -> [Int] prime [] = [] prime (x:xs) = x : prime [y | y <- xs, mod y x /= 0]
なるほど、頭いいな。これなら先の酷い再帰アルゴリズムと違って、一瞬で動作が終わる。
Pythonならこう。こちらもさっきの酷い再帰アルゴリズムと違って、一瞬で動作が終わる。
def myprime2(n): array = list(range(2, n + 1)) def primes(array): if not array: return [] else: return [array[0]] + primes([x for x in array if x % array[0] != 0]) return primes(array)
再帰を使わずに書くとこうか。
def myprime3(n): array = list(range(2, n + 1)) answer = [] while array: answer.append(array[0]) array = [x for x in array if x % array[0] != 0] return answer
効率のよいアルゴリズムってむずかしい
＜補足＞
2番目の再帰でなぜこんなに遅くなったか？
多分だが、isprime(n)を定義するのに、isprime(2)～isprime(n-1)を使っていて、・・・（ア）
isprime(n-1)を求めるにはisprime(2)～isprime(n-2)を使っていて、
isprime(n-2)を求めるにはisprime(2)～isprime(n-3)を使っていて・・・となっているのだが、
求めたisprime(i)を共用できていないからではないか？
アの各isprimeの下にisprimeのツリーが広がって、その下にまたツリーが広がって、と
おぞましいことになっている気がする。
計算結果を共有できてればいいのだが、できてないからとんでもない時間がかかっている、ということだろうか。
