11. Container With Most Water

• https://leetcode.com/problems/container-with-most-water/

O(n²) なアルゴリズムを書いてTLEを食らって、枝刈りするようにしてみたが結局解けず。

• https://github.com/inohiro/LeetCode/blob/master/11_container_with_most_water/self_2.rb

解説を読んだところ、配列の始まりと終わりから範囲を狭めながら、得られる面積の最大値を求める。確かに最大の面積を求めたいのだから、狭い範囲から探すよりも、広い範囲から探すほうが理にかなっているか。2つの添字を動かしながらなんとかする、という問題が続いた。解き方のアイデアさえも思い浮かばないことが多いけど、数をこなせばふわっとわかるようになるんだろうか...

• https://github.com/inohiro/LeetCode/blob/master/11_container_with_most_water/solution.rb

---

• あまり考えずに手を動かしてしまうことが多いので、よく考えてから動くようにしている。結局やろうとしていることを説明できないといけないわけで。
• 久しぶりに HackerRank を見たら、問題の種類から選べる画面があることに気がついて、これはこれで良さそうだ
  • 例えば動的計画法を使う問題の一覧がある https://www.hackerrank.com/domains/algorithms/dynamic-programming

26, 27 配列から{重複, 指定された要素}を取り除いたあとの要素数

両方とも Easy だけど、よくわからなかったので解説を読んだ。両方とも2つの変数を使って、先を行く変数と、後ろからついていく変数が指す配列中の値をつかって、条件に合う要素数を 数える。

• https://github.com/inohiro/LeetCode/blob/master/26_remove_duplicates_from_sorted_array/self.rb
• https://github.com/inohiro/LeetCode/blob/master/27_remove_element/solution.rb

26 は配列から、重複している数を取り覗いたあとの要素数を返すプログラムなので、Ruby で書くと nums.uniq.length でできてしまう。また、27 は配列から、指定された数字を取り除いたあとの要素数を数えるプログラムなので、nums.remove(val); nums.length でできてしまう。

プロコン（競プロ）だと上記のように解けばよいけど、コーディング面接だと配列の扱いとか、解法を思いつけるかというところが評価されるのでめんどくさいなと思う... 「そもそも実務ではこんなコード書かないだろう」とか本当に毎回思うけど、仕方ないのでこういう感情は抑えて解くしかない。

Ruby でマルチスレッドプログラミング

ある問題で、Redis からデータを読んで、中身に書いてあることをやって（sleepするとか）というものがあった。その発展系では、並列でやるようにしろと言うものだった。だいたい処理を並列にさせたい時は、parallel gem を使っている。とっても簡単で、仕事でもよく使っている。

任意のスレッド数、またはプロセス数はを指定して、#map #each などのメソッドを使ってブロックで囲むと、内側が並列で動作するようになる。本当に簡単なのでおすすめ。

require 'parallel'

Parallel.each((1..12), in_threads: 3) do |i|
# Parallel.each((1..12), in_processes: 3) do |i|
  puts "[Worker: #{Parallel.worker_number}] #{i}"
end

$ ruby paralle.rb
[Worker: 1] 1
[Worker: 0] 3
[Worker: 2] 2
[Worker: 1] 4
[Worker: 1] 7
[Worker: 0] 5
[Worker: 1] 8
[Worker: 2] 6
[Worker: 0] 9
[Worker: 1] 10
[Worker: 2] 11
[Worker: 0] 12

ここまで良いんだけど、parallel gem を使える時は予め処理する対象が配列になってる必要があるようだ。今回の用途だと、複数のスレッドを起動して、それぞれが Redis に読みに行くというのをやりたかったので、並列に実行する箇所の前では、処理対象のオブジェクトが用意できなかった。

[追記] うーん、適当に配列を作って渡したら動いたな... コード書いてる時はなぜかうまく動いてくれなかったんだが...

Parallel.each((0..10), in_threads: 10) do |i|
  Worker.new(i).exec_job
end

そこで、concurrent-rugy gem はどうだろうと見てみたが、良い感じに当てはまるものを見つけられなかった。今思うと Future か Promise を使うのが良かったかもしれないが、そんなに複雑なことがしたいわけでもなかった。

最終的に、今回は Thread をそのまま使うことになった。Thread をそのまま使うのはなんとなく避けてきたが、簡単に動いて便利（そのうち罠にハマりそう）。

threads = (1..num_parallel).map do |num|
  Thread.new do
    Worker.new.exec_job
  end
end
threads.map(&:join)

---

なんか良さそうな記事を見つけた。でもちょっと古いかも

www.toptal.com