Q&A
実行速度を優先したい、ということで間違いないですか？
前提・実現したいこと
rubyで競技プログラミングをしていますが、うまくいかない部分があるので質問します。
配列の順番をいじることなく配列の中身が一致しているかどうかを知る方法はないのでしょうか
今現在は二つの配列同士で引き算をして空かどうかで判定していますが、もう少し早さが欲しいのです
（例としては[0,3,0,3]と[3,3,0,0]を等しいとみなす）
そうです
配列の要素は「整数だけ」のような特定の条件はありますか？それとも、汎用に作る必要がありますか？
要素は整数のみです ただし配列のサイズは汎用的にお願いします
「汎用的に」とありますが、最大個数はどれぐらい必要ですか？
（条件が詳しければ詳しいほど、ピンポイントなものが書けるようになります）
100個くらいまでで済みそうですが…
> 二つの配列同士で引き算をして空かどうかで判定
[0,3,0,3]-[3,0,0,0] #=> []
ですが、これも「一致」という判断ですか？これも「一致」なら、
[0,3,0,3]-[0,3] #=> []
もですか？
違います、片方からもう片方の引き算を&&でつなげてます
（全貌が見えないのであくまで自分の感覚でしかないですが）もっと手前、つまり配列を生成する時点で対応できるなら、そのほうが効率的になるかな、という気がしています。
> 違います、片方からもう片方の引き算を&&でつなげてます
a=[0,3,0,3]
b=[3,0]
a-b==[] && b-a==[] #=> true
ということですか？
そういう風にしていますが… やっぱりsort!して==でつなげた方がいいかもしれませんね
どういう基準で同一と見なすのかが明確じゃ無いと、進まないですが、
a-b==[] && b-a==[] #=> true
をもって同一の判断にすると言うことなんでしょうか？sortして==するのとは結果が違いますが。
中身の組み合わせ、要素の個数は同じで、順番はバラバラであるということです
ソートして比較する以上に速くするのは無理なんじゃないでしょうか。元の配列の順番をいじりたくないならコピーすればいいと思います。
もし比較回数の頻度が高いなら、そのたびにいちいちソートするよりも辞書を構築した方が速いかもしれませんし、問題によってはそもそも配列を使わないという手もあるかもしれません。
ここで言う辞書を構築するというのは、[0,3,0,3] から {"0" => 2, "3" => 2} のように、要素とその数を紐づけたハッシュを作ることです。ハッシュならば「==」で比較できます。これは比較のたびにいちいち構築しなおすのではなく、最初に一度作り、配列の要素が一部変化した時にハッシュ内のその要素の数をインクリメント・デクリメントすることでメンテできます。
ハッシュを使うんですか…発想が及びませんでした
回答2件
0
ベストアンサー
arr1.size == arr2.size && arr1.sum == arr2.sum && (arr1-arr2).empty?
適当にしか試してませんので負値が混ざったりすると誤判定するかもしれません。
偶然だったようで、やはりsortが必要ですね
ruby
1arr1.size == arr2.size && arr1.sum == arr2.sum && arr1.sort == arr2.sort
追記
ついでにメモ化
ruby
1module ArrayMemSort 2 refine Array do 3 def sort(*) 4 @sort ||= super 5 end 6 end 7end 8 9using ArrayMemSort
投稿2020/03/19 16:20
編集2020/03/19 23:10
総合スコア15147
0
違います、片方からもう片方の引き算を&&でつなげてます
等しくなるパターンが多いなら、ふつうにソートして比較（arr.sort == arr2.sort）したほうが速いかもしれません。特に、片方の配列が固定できるなら、そちらはソート済みのものを事前に用意することでさらに高速化できます。
投稿2020/03/19 01:06
総合スコア145183
maisumakunさんならなにか技が出てくるのでは、とちょっと期待してclipしてたのですが、やはりないですね。
引き算 が 「同じものを全部引いてしまう」 のではなく 「ひとつづつ引いてくれる」 というversionがあると嬉しい時があります。
修正欄にも書きましたが、自分が考えるのでしたら「もっと手前」で何かできないか、というほうがいい結果になりそうな印象です。
あなたの回答
tips
プレビュー
