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)
なんか良さそうな記事を見つけた。でもちょっと古いかも
14. Longest Common Prefix
- https://github.com/inohiro/LeetCode/blob/master/14_longest_common_prefix/self.rb
- https://leetcode.com/problems/longest-common-prefix/
文字列の配列から、共通接頭辞を探し出す。長さが最小のものを一文字ずつ見ながら、幅優先探索するように他の文字列をチェックして、揃わなくなったらそこで止めるという感じにやった。Easy だったこともあり、一発で通った。
LeetCode は、個人的な感覚ではあるが AtCoder やこれまでやったことあるオンラインジャッジのシステムよりも意地悪な入力が多く、その辺に注意が回るようになってきたような気がする。まあ、これは簡単な問題だったからかも...
LeetCode Weekly Contest 58 に参加
メールでお知らせが来て、見たところ PDT に優しい時間帯(18:30-20:00)だったので初参加。AtCoder と同じように4問、だんだん難易度が上がっているように見える(正解すると得られるポイントが大きくなるように設定されていた)。
724. Find Pivot Index
難易度は Easy。数字の配列が与えられて、ある位置ではその右側のすべての要素と、左側のすべての要素の和が等しくなる位置(Pivota Index)を探す。完全に難しく考えすぎて、時間を消費してしまった。0番目の要素から見ていくような単純なやり方では解けないようになっているだろうと邪推してしまい、最初に配列の真ん中に行って、右側と左側の和を比較しながらインデックスをずらして、Pivot Index を見つける方法を考えた。
↑のやり方を実装していると、無駄に実装が複雑になり(もっと良い書き方はあったはずだが)、単純に 0 番目の要素から、左右の和を比較するアルゴリズムを書いたら解けた... 難易度 Easy だったので、段順な実装をまず試してみるべきだったな...
- 正解したやつ: https://github.com/inohiro/LeetCode/blob/master/contests/58_2017_11_11/a2.rb
- 未完: https://github.com/inohiro/LeetCode/blob/master/contests/58_2017_11_11/a.rb
725. Split Linked List in Parts
難易度は Medium。Linked List が渡されて、それを展開し、指定された要素数の配列(配列の配列になる)を作る。配列の要素の個数はなるべく等しくなるようにし、要素数が異なる場合は差が1になるようにする。 問題を間違えて理解していた...
Linked List を配列に展開するのは簡単にできたが、結局解けなかった。配列に展開したあと、指定された要素数の配列になるようにやってみたが、うまくいかず。公式の解説はなかったが、Python 版の正解をアップロードしている人がいたので、それを参考に書いた。
とりあえず問題をまちがえて理解していることがわかった。木を作ってバランスさせるのかな、とか思ってたけどわりと愚直なやり方で良かった。ポインタの繋ぎ変えとかは数をこなさないと、このままでは解ける気がしないな。
あと2問は着手できず...