タグ

関連タグで絞り込む (1)

タグの絞り込みを解除

Algorithmとgolangに関するcrafのブックマーク (2)

  • Goの正規表現が遅いって言う人がいたから、(速い)正規表現エンジンを作ったよ

    はじめに 「Goの正規表現は遅い」 そんなふうによく言われていました。(最近はあまり聞かなくなりましたが) たとえば、↓の記事ではPythonの正規表現と比較して1.5倍くらい遅いという結果になっています: この話には「Goの正規表現は最悪時間が短くなるように安定したアルゴリズムを採用しているから」という回答があります: ↑の記事の比較では、GoPerlに対して約10倍以上高速という結果が出ているので、「Goの正規表現は遅くない!はい、論破ー!」というわけですね。 なんでこうなるのかも↑の記事で説明されているとおりですが、Perl(などのバックトラック型エンジン)が入力長に対して指数関数的に実行時間が伸びていくのに対し、Goの正規表現エンジンは入力長に対して線形時間で実行時間が伸びていくアルゴリズムを採用しているため、入力が長くなると急激にGoのほうが有利になるからです: 一方で、入力が

    Goの正規表現が遅いって言う人がいたから、(速い)正規表現エンジンを作ったよ
  • smartcache ~ プリフェッチするインメモリキャッシュ | おそらくはそれさえも平凡な日々

    https://github.com/Songmu/smartcache smartcacheというGoのインメモリキャッシュライブラリを書いた。 一般的に、キャッシュを実装する場合以下のような問題が起こりがちです。 キャッシュ更新時にリクエストが殺到してしまう(いわゆるThundering Herd問題) キャッシュ生成に時間がかかる場合、キャッシュ更新時に処理がブロックしてしまう smartcacheは上記の問題を以下のアプローチで解決しています。 キャッシュ更新処理を一化する Goの場合 golang.org/x/sync/singleflight を使えば簡単! キャッシュ期限切れ前に内部的に更新処理をおこなう いわゆるプリフェッチ的な処理 使い方 コンストラクタにキャッシュの実際の有効期限、softな有効期限、そしてキャッシュ生成関数を渡します。 // コンストラクタ ca :

    smartcache ~ プリフェッチするインメモリキャッシュ | おそらくはそれさえも平凡な日々
  • 1