ReDoS 検出の最先端 recheck の紹介 / State of the Art of ReDoS DetectionYAPC::Japan::Online 2022 での発表資料です。 recheck:
MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと | Raccoon Tech Blog [株式会社ラクーンホールディングス 技術戦略部ブログ]
株式会社ラクーンホールディングスのエンジニア/デザイナーから技術情報をはじめ、世の中のためになることや社内のことなどを発信してます。 bashパフォーマンスMySQLInnoDBDB設計インデックス こんにちは、羽山です。 今回は MySQL のプライマリキーに UUID を採用する場合に起きるパフォーマンスの問題を仕組みから解説します。 MySQL(InnoDB) & UUID のパフォーマンスについては各所でさんざん議論・検証されていますが、論理的に解説した記事が少なかったり一部には誤解を招くようなものもあるため、しっかりと理由から理解するための情報として役立つことができればと思っています。 UUID と比較される古き良き昇順/降順のプライマリキーはというと、 MySQL の InnoDB において良いパフォーマンスを出すために縁の下の力持ちのような働きをしてくれているケースが実は少な
![MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと | Raccoon Tech Blog [株式会社ラクーンホールディングス 技術戦略部ブログ]](https://cdn-ak-scissors.b.st-hatena.com/image/square/5e9d48c3c6f38c2d5f71897d98efcb251289d1f9/height=288;version=1;width=512/https%3A%2F%2Ftechblog.raccoon.ne.jp%2Fwp-content%2Fuploads%2F2021%2F07%2Fboard-755792_800.jpg)
CPUとGPUのマルチスレッディングの違いについて - arutema47's blog
"Locality is efficiency, Efficiency is power, Power is performance, Performance is King", Bill Dally マルチスレッディングとは？ CPUとGPUのマルチスレッディングの違いをブログにまとめていたけど例によって誰も興味なさそう— arutema47 (@arutema47) 2021年8月16日 つぶやいたら読みたい方が多そうだったので完成させました。 マルチスレッディングとはメモリ遅延を隠蔽しスループットを上げるハードウェアのテクニックです。 ただCPUとGPUで使われ方がかなり異なるため、その違いについて考えてみる記事です。 （SIMDについて並列プログラミングの観点から触れるべきでしたが、時間無いマルチスレッディングに注目するため初版では省きました。） 本記事について 本記事はCPUとG
「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！ エンジニアリンググループ マルチデバイスチーム 新卒1年目の小林です。 エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリスト このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。 文字列照合アルゴリズムとは テキストとパターンという文字列が与えられたときに、中に出現す
圧縮ファイルの展開速度を最大1万倍超高速化するデータ構造を広島大が考案
広島大学は8月31日、富士通研究所と共同で、多くのデータ圧縮方式で採用されている「ハフマン符号」の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案したことを発表した。NVIDAのGPU「Tesla V100」を用いて実験した結果、従来の最速展開プログラムと比較して、2.5倍から1万1000倍の高速化を達成できたとしている。 同成果は、同大学大学院先進理工系科学研究科の中野浩嗣教授らの共同研究チームによるもの。詳細は、2020年8月に開催された国際会議「International Conference on Parallel Processing (ICPP)」において発表され、269件の投稿論文の中から最優秀論文賞に選ばれた。 インターネットを介して多数の画像ファイルや動画ファイルなどを転送したり、また記録メディアに保存したりする際、データの圧縮は誰でも日常的に行っている。そ
高速な詰将棋アルゴリズムを完全に理解したい（完成版） - コンピュータ将棋 Qhapaq
Qhapaq アドベント将棋記事10日目 今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索(depth first - proof number)による詰将棋アルゴリズムの完全理解を目指していきます。 参考文献： memo.sugyan.com 【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み(proof number)/不詰(disproof number)を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面についてはpn、dnは0になります。局面のpn、dn（厳密には非0のpn、dn
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
計算量について、償却/期待/平均など - noshi91のメモ
本記事は皆様からのご指摘を募集しております 誤った記述があるかもしれません 概要 競技プログラミングをやっていると などの表記を見掛けることも多いでしょう *1。 それぞれについて、大雑把な意味をまとめました。 アルゴリズムの挙動の正確な把握は競技においても重要です。 以降、全て時間計算量に付いて議論します。 注: 本稿内で用いられる はほとんどが に置き換えられますが、 Big O notation と同時に説明すると混乱を招くと判断し、競技プログラミングにおいて常用されている を使用しています。 最良計算量 多くのアルゴリズムは、入力によって計算量が変化します *2。 例えば、ソートアルゴリズムには大まかに 通りの入力が存在します。 あり得る全ての入力のうちの計算量の最小値を最良計算量と呼び、 を付けて表記します。 線形探索は (最初に求める値が存在した場合) マージソートは 挿入ソー
SymSpell対BK木：100倍速い文字列のあいまい検索とスペルチェック | POSTD
注釈：500,000単語収録の辞書内における1,000単語の検索時間 X:最大編集距離 Y:検索時間/ms 従来、スペル修正や文字列のあいまい検索には、 BK木 が適していると言われてきました。しかし、これは本当でしょうか。 また、 スペル修正に関する私のブログ に寄せられたコメントには、BK木が、あいまい検索のためのデータ構造として優れていると言及されていました。 そのような経緯から、今回、BK木と他の選択肢のベンチマークを取って比較してみようと思い立ったわけです。 近似文字列検索アルゴリズム 近似文字列検索では、文字列リスト内の文字列を検索し、特定の 文字列メトリック に従って、それに近い文字列を返します。 文字列メトリックは多数あり、例えば レーベンシュタイン距離 、 Damerau-Levenshtein距離 、 ハミング距離 、 ジャロ・ウィンクラー距離 、 Strike a m
動くようにする、正しくする、速くする。 - Qiita
今までに扱ったことの無い分野で新規開発をする場合、いろんな問題が出てくるだろう。そのようなときに、何をどうすればよいのか迷うことがあるだろう。そのようなときに、複数の課題があるときに、何をどの順序で解決していけばよいのか迷うこともあるだろう。 私が心がけているのは、「動くようにする、正しくする、速くする。」の順序で物事の優先順位をもって考えてようにしていることです。この内容は何かの本で読んだことからきている。何かしら動かないうちは、正しくすることもできないし、正しくなっていないうちは、速くすることに意味がない。 物事を解決する際に、全てのことが同時に解決することは少ない。 前に経験を積んだことのある分野の近くでは、動いて正解率もそれなりに高くて、メモリ消費や処理時間が少ないもの１回目の挑戦で作れることがあったりもするが、それは極めてまれなことだ。 1. 何かしら既存の技術をまねて、「動くよ
Segment Tree を少し速くする - Fixstars Tech Blog /proc/cpuinfo
このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。 Segment Treeと呼ばれるデータ構造があります。 プログラミングコンテストでも解法の一部として使われることが多いため、よくコンテストに参加するような人だとコピペで使えるように準備しているということも多いのではないかと思います。 このデータ構造を使うと、1次元の数列に対する以下の操作が $O(\log n)$ の時間計算量で可能となります。 query(l, r): $a_{l}\ \textrm{op}\ a_{l+1}\ \textrm{op}\ \cdots\ \textrm{op}\ a_{r-2}\ \textrm{op}\ a_{r-1}$ を求める update(i, x): $a_{i}$ に $x$ を代入する たとえば、最初に数列 $a = [ 0, 1, 2
CUDAによるバンディング低減フィルタの高速化（2） - Fixstars Tech Blog /proc/cpuinfo
このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。 前回の続きです。メモリアクセス周りをもう少し見てみましょう。 カーネル内でメモリアクセスしてるデータは、乱数表と入出力画像です。このうち、読み書きデータ量の多い入出力画像を見てみます。画像のデータ型はPIXEL_YCです。これはAviUtlのフィルタ処理におけるデータ型で、以下のように定義されています。 typedef struct { short y; short cb; short cr; } PIXEL_YC; 画像データはこれの配列なので、構造体の配列（Array of Structures, AoS）です。AoSはCUDAが苦手なデータ構造です。なぜならコアレスアクセスができないからです。本来、教科書通りのやり方なら、ここでAoSをSoA（Structure of Array
私が書いた最速のハッシュテーブル – PART 3 | POSTD
テーブルを、異なるmax_load_factor()と比較する 先に示した最後のグラフは、私のテーブルとgoogle::dense_hash_mapがmax_load_factorに0.5を使う一方で、std::unordered_mapとboost::multi_indexが1.0を使って動作検証を行っていました。もしかすると他のテーブルも、低いmax_load_factorの値を使えば、より速くなるのではないでしょうか？ それを確かめるため、最初のグラフ（成功したルックアップ）に使ったのと同じベンチマークを実行しました。ただし、どのテーブルもmax_load_factorは0.5に設定しました。そして、テーブルの再割り当ての直前に測定を行いました。もう少し詳しく説明しますが、まずは次のグラフをご覧ください。 注釈： 成功したルックアップの占有率（load factor） 0.5 （縦軸
私が書いた最速のハッシュテーブル – PART 2 | POSTD
素数か2のべき乗か ハッシュテーブルのアイテムをルックアップする際に高負荷なステップが3つあります。 キーをハッシングする キーをスロットにマッピングする 該当スロットのメモリをフェッチする ステップ1は、キーが整数であれば、低負荷になります。単にintをsize_tにキャストするだけです。しかし、文字列のようなタイプのキーの場合は高負荷となります。 ステップ2はよくある整数モジュロ演算です。 ステップ3はポインタの間接参照です。std::unordered_mapの場合は複数のポインタ間接参照となります。 処理の遅いハッシュ関数でなければ、直観的にステップ3が最も高負荷になると考えると思います。しかし、全てのルックアップでキャッシュミスが生じなければ、整数モジュロが最も高負荷な処理となります。現代のハードウェアにおいても整数モジュロは非常に遅いのです。 Intelマニュアル では、整数モ
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
Java で最速の乱数生成器を目指す: (3) ガンマ分布に従う乱数
TL;DR: ガンマ分布に従う乱数生成器を Java で実装し、Commons Math の実装と比較して 最大で約 16 倍 (任意の形状パラメータの乱数を生成する場合) の速度効率を達成しましたよ、というお話です。 (Header image: Mundhenk at en.wikipedia) ガンマ分布に従う乱数生成の実装方法Permalink これまで 正規分布に従う乱数生成、指数分布に従う乱数生成 をそれぞれ Java で実装してきましたが、今回はガンマ分布に従う乱数生成を Java で実装してみます。 ガンマ分布 は、形状パラメータ k>0 と スケールパラメータ θ>0 (もしくは形状パラメータ α=k と比率パラメータ β=1/θ) の 2 つのパラメータを持ち、その確率密度関数は次の式で表されます。 f(x)=xk−1e−x/θΓ(k)θk ガンマ分布の形状パラメータ
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムの計算量見積もりの基礎 - Qiita
物理サーバを選定する際のポイント – Eureka Engineering – Medium
