20210731のJavaに関する記事は3件です。

Redisを使って排他制御を行う(タイムアウト考慮版)

この記事は以下の記事の続きです。先に前の記事を読むことをお勧めします。 今回は前に投稿した上記記事の最後で指摘したロックがタイムアウトした場合に起こる問題を解消します。 1.仕組み 簡易版での問題はロックのタイムアウト時間より処理が長くなってしまった場合、その長くなってしまった処理が最後に自分のロックしたものでないキーを削除してしまうことで意図せずロックが解除されてしまうということでした。 なのでロックを解除する際に自分のかどうかを調べて、自分の獲得したロック出なかった場合は削除しないようにすれば解決します。 1.1.NG例 実は既に前回のプログラムでも自分の獲得したロックかどうかの値はUUIDとしてロックキーに対応する値として入れてあります。 なので、ロックをリリースしている箇所net.penguinsan.redis.MutexRedisServiceのreleaseMutexメソッドで以下のようにしてやればよいでしょうか? public void releaseMutex(Mutex m) { final String objectKey = m.getObjectKey(); try (Jedis r = this.jedisPool.getResource()) { String lockId = r.get(objectKey); if (lockId.equals(m.getLockId())) { r.del(objectKey); System.out.printf("delete key : lock_id=%s\n", m.getLockId()); } else { System.out.printf("not delete key : lock_id expect=%s actual=%s\n", m.getLockId(), lockId); } } } これだと最初のgetから次のdelまでの間にRedis側で値が書き換わってしまう可能性がある(間にRedisのコマンドが割り込む可能性がある)ので確実ではありません(大抵はうまくいってしまうかもしれませんが・・・) 1.2.正解例 getとdelの間にコマンドを割り込ませず判定するにはどうするか? Luaスクリプトで上記と同じ判定を記述してRedis側で実行すれば間にコマンドを挟まれることなく実行できます。 public void releaseMutex(Mutex m) { try (Jedis r = this.jedisPool.getResource()) { r.eval( "local id = redis.call('GET',KEYS[1])\n" + "if id == ARGV[1] then\n" + " redis.call('DEL',KEYS[1])\n" + "end\n", List.of(m.getObjectKey()), List.of(m.getLockId())); } } Luaスクリプトに関しては詳しく説明しませんが、RedisにevalコマンドでLuaスクリプトと必要なパラメータを渡してやることでスクリプトに書かれた一連の処理をアトミックに実行することができます。 2.まとめ 上記のコードをもう少しまとめて書き直したものをgithubに公開してありますので参考にしてみてください。 Luaスクリプトを駆使すると分散処理系で各サーバーにユニークなIDを発行したり、いろいろなことができるので面白いです。
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

CodeSignal - firstDuplicateを解いていきます

コーディングしなさすぎてコーディングを忘れたエンジニアがコーディングを思い出すためにコーティングします。 今回は、アメリカのコーデイング練習サイトCodeSignalの問題「firstDuplicate」を解いていきます。 サイトによるとGoogleの面接で出された問題ようです。 問題 [2, 1, 3, 5, 3, 2]のような数値配列が渡されるので、左から見ていって最初に重複した数値を探します。 最初というのは、上の例なら、左から見ていくと3の重複が最初に検知できるので、答えは3です。 たしかに2も重複していて、1個目の2は配列の冒頭で登場しますが、2個目の2が出てくる前に3の重複が見つかるので、答えは2ではありません。 もし配列の中に重複した数値がなければ-1を返します。 その他、配列をaとするとこんな制約があります。 1 ≤ a.length ≤ 10^5 ⇨配列の要素数は1以上10,000以下 1 ≤ a[i] ≤ a.length ⇨配列内の数値は1以上、配列の要素数以下 たとえば[2, 2]なら、配列の要素数は2なので、中の数値も2以下(1か2)になります。 [2, 9]や[160, 3]はなしです。 考え方 まず最初に思いつくのは、ブルートフォースです。 ブルートフォースとは、力技で問題を解くことを意味し、単純な考えでいいけど計算量が多くなるのがデメリットです。 a = [2, 1, 3, 5, 3, 2]であれば、まず最初の数値2を基準にし、その後の値1, 3, 5, 3, 2と比較し、重複が見つかればその位置のindexを変数に格納します。 2個目の2はindex5で見つかるので、5を変数に格納します。 次に1を基準にし確認し、重複なし。 3を基準にし、index4の位置で重複が見つかります。そしたら変数の5よりももっと早いindexで重複が見つかったので、変数を4に書き換えます。 同じ要領ですべての値を確認し終えたあと、変数の格納されているindexを使って、a[変数]のようにして、配列から値を取り出せばOKです。 この方法は、普通に答えを目で探すときの方法と同じ要領だと思うので、簡単に思いつくのですが、ベストではありません。 なぜなら、ネステッドループ(ループの中にループがある状態)になるので、計算量が多くなるからです。 そこでなんとかループを一個できないかと考えると、すでに見た数値を別の集合体に突っ込んで、ループで見ていく数値がその集合体の中にあるか確認する方法が思い浮かびます。 もし既に見た(集合体の中にある)のであれば、その値が答えです。 なぜなら既に集合体にある=今回が2回目の登場なので、その値は重複しており、かつ一番最初に検知した重複になるからです。 Javaで書くとこんな感じです。 集合体は別に順番を持っていなくていいし、重複を許可しない方が無駄が少ないので、HashSetを使用しています。 solution.java int firstDuplicate(int[] a) { HashSet<Integer> seen = new HashSet<>(); for (int i=0; i<a.length; i++){ if (seen.contains(a[i])){ return a[i]; } else { seen.add(a[i]); } } return -1; } 学んだこと 要は、ブルートフォースはベストではないので、どうやって別の解き方を考えるかがキーだと思います。 その場合、ネステッドループをなくし、ループを一つにする方法があります。 ループを一つ減らしたいと言うことは、ループで確認する値と突き合わせるのは、過去にループで見た値しかありません。(ループが一個しかないので、ネステッドループのように先の配列の値を検索することはできない) そのため、過去にループで見た値をどこかに格納しておかなければいけません。そこで集合体を利用します。 とはいえ、過去に見た値をすべて集合体に突っ込んだらそれは結局ネステッドループしてるようなものなので、集合体をもっとスマートにしたいです。 そのため、JavaのHashSetのような重複を許さない集合が利用できます。 集合の要素が少なければ、その分検索も早くなります。
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

CodeSignal - firstDuplicateにチャレンジ

コーディングしなさすぎてコーディングを忘れたエンジニアがコーディングを思い出すためにコーティングします。 今回は、アメリカのコーデイング練習サイトCodeSignalの問題「firstDuplicate」を解いていきます。 サイトによると、この問題はGoogleの面接で出されたようです。 問題 [2, 1, 3, 5, 3, 2]のような数値配列が渡されるので、左から見ていって最初に重複した数値を探します。 最初というのは、上の例なら、左から見ていくと3の重複が最初に検知できるので、答えは3です。 たしかに2も重複していて、1個目の2は配列の冒頭で登場しますが、2個目の2が出てくる前に3の重複が見つかるので、答えは2ではありません。 もし配列の中に重複した数値がなければ-1を返します。 その他、配列をaとするとこんな制約があります。 1 ≤ a.length ≤ 10^5 ⇨配列の要素数は1以上10,000以下 1 ≤ a[i] ≤ a.length ⇨配列内の数値は1以上、配列の要素数以下 たとえば[2, 2]なら、配列の要素数は2なので、中の数値も2以下(1か2)になります。 [2, 9]や[160, 3]はなしです。 考え方・解説 まず最初に思いつくのは、ブルートフォースです。 ブルートフォースとは、力技で問題を解くことを意味し、単純な考えでいいけど計算量が多くなるのがデメリットです。 a = [2, 1, 3, 5, 3, 2]であれば、まず最初の数値2を基準にし、その後の値1, 3, 5, 3, 2と比較し、重複が見つかればその位置のindexを変数に格納します。 2個目の2はindex5で見つかるので、5を変数に格納します。 次に1を基準にし確認し、重複なし。 3を基準にし、index4の位置で重複が見つかります。そしたら変数の5よりももっと早いindexで重複が見つかったので、変数を4に書き換えます。 同じ要領ですべての値を確認し終えたあと、変数の格納されているindexを使って、a[変数]のようにして、配列から値を取り出せばOKです。 この方法は、普通に答えを目で探すときの方法と同じ要領だと思うので、簡単に思いつくのですが、ベストではありません。 なぜなら、ネステッドループ(ループの中にループがある状態)になるので、計算量が多くなるからです。 そこでなんとかループを一個できないかと考えると、すでに見た数値を別の集合体に突っ込んで、ループで見ていく数値がその集合体の中にあるか確認する方法が思い浮かびます。 もし既に見た(集合体の中にある)のであれば、その値が答えです。 なぜなら既に集合体にある=今回が2回目の登場なので、その値は重複しており、かつ一番最初に検知した重複になるからです。 Javaで書くとこんな感じです。 集合体は別に順番を持っていなくていいし、重複を許可しない方が無駄が少ないので、HashSetを使用しています。 solution.java int firstDuplicate(int[] a) { HashSet<Integer> seen = new HashSet<>(); for (int i=0; i<a.length; i++){ if (seen.contains(a[i])){ return a[i]; } else { seen.add(a[i]); } } return -1; } コードの説明 forで配列の要素を一つづつチェックしています。 もしその要素の文字をHashSetの中で検索し、もし初見であれば、HashSetに突っ込みます。 逆に、すでにHashSetの中に存在している場合はそれが2回目の登場なので答えとして返却します。 学んだこと 要は、ブルートフォースはベストではないので、どうやって別の解き方を考えるかがキーだと思います。 その場合、ネステッドループをなくし、ループを一つにする方法があります。 ループを一つ減らしたいと言うことは、ループで確認する値と突き合わせるのは、過去にループで見た値しかありません。(ループが一個しかないので、ネステッドループのように先の配列の値を検索することはできない) そのため、過去にループで見た値をどこかに格納しておかなければいけません。そこで集合体を利用します。 とはいえ、過去に見た値をすべて集合体に突っ込んだらそれは結局ネステッドループしてるようなものなので、集合体をもっとスマートにしたいです。 そのため、JavaのHashSetのような重複を許さない集合が利用できます。 集合の要素が少なければ、その分検索も早くなります。
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む