各種エラー検出符号のエラー検出率 - 豪鬼メモ
データベースにエラー検出符号を組み込んだはいいが、実際にどの程度の確率でエラーを検出できるだろうか。単純なチェックサムとAdlerチェックサムとCRCを比較してみた。実際にランダムに文字列を書き換えて、それがきちんと検出できるかどうかの統計を取った。以下は、各種エラー検出符号の、エラーの長さ（バイト数）とエラー検出率のグラフである。 ファイルにデータを記録したとして、ストレージのエラーやシステムの暴走などが理由で、記録したはずのデータと異なるものが読み出される可能性がある。ネットワークでデータを転送した場合も、途中の経路のエラーにより、送信したはずのデータと異なるものが受信される可能性がある。そういったデータの破損または改変を検知するために、データのハッシュ値を添付しておいて、それと比較することで確率的に一貫性を調べる手法が多数ある。エラー検出符号とか誤り検出符号とか呼ばれるものだ。データ
Binary search with modern processors
第16回 StringBeginners での発表資料
排他制御の基礎の基礎
はじめに システムに存在するリソースには同時にアクセスしてはいけないものが多々あります。身近な例を挙げると、Ubuntuのパッケージ管理システムのデータベースがあります。aptコマンドの動作によってこのデータベースは更新されるのですが、同時に2つ以上のaptが動作できたとすると、データベースが破壊されてシステムが危機的状況に陥ります。 このような問題を避けるために、あるリソースに同時に1つの処理しかアクセスできなくする排他制御というしくみがあります。排他制御はOSが提供する重要な機能の一つです。 排他制御が必要なケース 排他制御は直感的ではなく非常に理解が難しいのですが、ここでは比較的理解が簡単なファイルロックというしくみを使って説明します。説明には、あるファイルの中身を読みだして、その中に書いてある数字に1を加えて終了するincというという単純なプログラムを使います。
How to implement Japanese full-text search in Elasticsearch
全文検索は一般的に知られていますが、検索エクスペリエンスで非常に重要な役割を果たしています。ただし、日本語など、一部の言語では、全文検索を実装するのが難しい場合があります。このブログでは、日本語で全文検索を実装する際の課題を探り、Elasticsearchでこれらの課題を解決する方法をいくつか示します。 全文検索とは？ Wikipediaより、下記が定義となります。 全文検索とは、コンピュータにおいて、複数の文書（ファイル）から特定の文字列を検索すること。「ファイル名検索」や「単一ファイル内の文字列検索」と異なり、「複数文書にまたがって、文書に含まれる全文を対象とした検索」という意味で使用される。 全文検索は、現在多くのデジタル体験を強化するものです。全文検索は、データセット内に隠れている可能性のある単語やフレーズを見つけようとしてくれます。例えば、ネットショッピングして「phone」を検
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
文字列から浮動小数点数に変換する、なるべく速く - toge's diary
TL;DR 文字列から浮動小数点数に変換するならfastfloat使いましょう。 私が試せる環境で比較する限り、とても速いです。 細かいことが気になります C++でちょっとしたプログラムを書くときにいつも気になるのが 「文字列データから指定データ型への変換処理をどうやって効率的に書くか」 です。私だけかもしれませんが。 特に悩んでしまうのが「文字列→浮動小数点」です。 std::scanf, std::stringstreamを使うものは大抵すごく遅い std::strtodstd::stodはstd::stringへの変換が入るので避けたい std::from_charsは(libstdc++が)浮動小数点型に対応していない boost::sprit::qiが何故か速いのだけれどこのためにboost::sprit使うのは重い と色々制約が多いのです。どうにかならないものか。 fast_f
ビオンテックとファイザーのSARS-CoV-2ワクチンのソースコードのリバースエンジニアリング: パート２ • Articles
エントリーや更新は bert@hubertnet.nl もしくは @PowerDNS_Bert まで。 ビオンテックデータを共有してくれたビオンテック(BioNTech)に感謝します。 また、このようなワクチンが開発できるような最先端の技術を実現するために、数十年に渡って携わってきた非常に多くの研究者・研究員の方々にも感謝します。 これは驚くべき仕事です。 あまりにも素晴らしいので、このワクチンのすべてを理解したくなり、それでワクチンのmRNAがどうなっっているかをザックリ説明する「ビオンテックとファイザーのSARS-CoV-2ワクチンのソースコードのリバースエンジニアリング」という記事を書きました。 記事の内容が面白いことは請け合いますので、以降を読み進める前に読んでおくことをオススメします。 先の記事では幾つか疑問が残っていましたが、それこそが興味深く、以下で取り上げる点です。 コドン
PHPとPythonとRubyの連想配列のデータ構造が同時期に同じ方針で性能改善されてた話 - hnwの日記
PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実
どれだけリクエストをさばけるのかを待ち行列理論で考えてみた - Qiita
テレビで素敵なサイトが紹介されていたのでアクセスしてみたら、なかなかレスポンスが返ってこなかったりステータスコード503になったりすることってありますよね。 テレビで紹介されたことで多くの人がサイトにアクセスした結果、そのサービスのキャパシティを超えてしまったわけです。 どうなるとキャパシティを超えるのでしょうか？ また、いつからレスポンスが遅くなるのでしょう。 効果的にリクエストをさばくにはどうしたらいいのでしょう。 Photo by Roman Arkhipov on Unsplash 待ち行列理論を使って理想的なモデルからこれらを考えてみたいと思います。 待ち行列理論はコンピュータサイエンスをやってきた人はみんな触れたことがあるとは思いますが、大石の場合はそれが何十年も(!)前のことなのであらためて思い出してみました。 モデル Railsでサービスを提供するとき、rackサーバとして
西暦1年は閏年か？ - プログラマーの脳みそ
閏年（うるうどし）の話題。 Twitterで見かけた話題で「西暦1年は閏年かどうかぱっとわからん人おる？」という些か煽り気味のツイートを見かけたのだけども、反射的に「閏年じゃないに決まってるじゃん」とぱっと答えてしまわないだろうか。本当にそうだろうか？ そう単純な話なのだろうか？ プログラミングを学んでカレンダーを扱うことを学ぶ際に置閏法についても簡単に触れられることがある。置閏法というのは閏年や閏月（太陰暦では1年が13ヵ月になるケースがあり追加の月を閏月と呼ぶ）をどのようなルールで挿入するかという話で、まさにアルゴリズムであるからプログラミングの話題と相性がいい。 置閏法 現代の西暦の置閏法（ちじゅんほう）は 西暦を 400 で割り切れる年は閏年 上記以外で西暦を 100 で割り切れる年は平年 上記以外で西暦を 4 で割り切れる年は閏年 上記以外は平年 といった手続きで閏年（つまり2月
浮動小数点数の二段階丸め誤差 - hydrakecat’s blog
さいきん『浮動小数点数小話』という同人誌を読んでFMA (Fused Multiply-Add)の二段階丸め誤差（double rounding error）について色々と知る機会があったのでまとめておく。ついでにFMAに関するOpenJDKのバグっぽい挙動を見つけたのでそれも併せて記しておく。 FMA (Fused Multiply-Add)とは FMAは以下のような演算のことを呼ぶ。 この演算自体は行列の乗算やベクトルの内積の計算でよく現れるものであるが、通常の浮動小数点数の乗算と加算を別々に行うと誤差が出るので一度の演算で正確な値を算出したいときに用いる。たとえばC言語（C99）では fma、fmaf、fmalという3つの関数が導入されているらしい。 FMAの実装における二段階丸め誤差 FMAはターゲットとなるCPUのアーキテクチャがFMA命令をサポートしていればその命令を直接呼び出
【Rust】文字列型のUTF-8検証の中身 - Qiita
コード値：00000000_00000000_0xxxxxxx（1-7ビット） ⇒ UTF-8：0xxxxxxx（1バイト） コード値：00000000_00000yyy_yyxxxxxx（8-11ビット） ⇒ UTF-8：110yyyyy 10xxxxxx（2バイト） コード値：00000000_zzzzyyyy_yyxxxxxx（12-16ビット） ⇒ UTF-8：1110zzzz 10yyyyyy 10xxxxxx（3バイト） コード値：000wwwzz_zzzzyyyy_yyxxxxxx（17-21ビット） ⇒ UTF-8：11110www 10zzzzzz 10yyyyyy 10xxxxxx（4バイト） 特に重要な点は以下の2つである。 1バイト目（開始バイト）の先頭のビットパターンによって全体のバイト数を判定できる。 （0...：1バイト、110...：2バイト、1110...
つながりをデータから解き明かしたい ~ 複雑ネットワークの世界とそれを活用した不正検知の紹介 | メルカリエンジニアリング
この記事は、Merpay Tech Openness Month 2020 の17日目の記事です。こんにちは。メルペイのMachine Learningチームのhmjです。 検知精度とオペレーション負荷のトレードオフ解消 取引の連続性に着目した検知 と不正決済の検知への機械学習の適用の内容にて投稿してきました．今回は「集団的な不正の検知」がテーマとなります． 昨今，Web不正検知やセキュリティに関わるでもECサイトでの集団による不正の手口は多様化や複雑化してきていることが報告されています[1]． メルペイでも，今後起こり得る集団的な不正決済への対策を講じる必要があると考えています． 集団的な不正は検知できたとしてもその全体像がみえにくいこともあり，ソリューションとしては「検知できること」と「すばやく全体像を把握できる」を満たすものが求められています． 両者を満たす解決方法として，グラフ理論
UTF-8 の文字列をできる限り Shift_JIS に変換したい - きりきりやま
Shift_JIS の CSV で連携する外部サービスがあり、DB では UTF-8 でテキストを持っていたため文字コードを変換する必要が生じた。 ところが UTF-8 に存在する多くの文字は Shift_JIS に対応がないため変換することができない1。 そこで、事前に NFKC 形式で Unicode 正規化することで変換可能な文字を増やすことを試みた。 まずは Unicode 正規化の前提として、Unicode の正準等価と互換等価について説明する。 以降の U+16進数 という表記は Unicode のコードポイント (文字に ID のようなものが割り当てられている) を示す。 また、コードポイントに対応する文字の詳細は https://codepoints.net/ といったサイトで確認することができる。 正準等価 例として、ひらがなの「が」について考える。Unicode では「
ポケモンを題材に因果推論を実践してみる - kanayamaのブログ
問題設定 有意差検定 交絡因子の存在 線形重回帰によるモデル化 回帰係数の推定 回帰係数の仮説検定 補足など 残差の分布について 他の交絡因子について データの生成方法について 参考文献 @tkanayama_です。最近「計量経済学*1」と「効果検証入門 *2」を読んだので、せっかくなので実際に手を動かすことによって理解の整理をしたいと思いました。 www.yuhikaku.co.jp gihyo.jp そこで今回は、人工データを用いて「ボールの性能と捕獲確率」の関係性を効果検証してみました（人工データの生成方法は記事の末尾に記述しました）。 問題設定 今は昔、モンスターボールしか存在せず、スーパーボールが世の中で出回り始めたばかりの頃、オーキド博士が「スーパーボールは本当にモンスターボールより捕まえやすいのか？」という仮説を検証しようとしています。 そこでオーキド博士は世界中のトレーナー
JVNVU#99619336: 勾配降下法を使用する機械学習モデルに、誤った識別をさせるような入力を作成することが可能な問題
勾配降下法を用いて学習させたモデルを用いた分類を行う場合に、任意の分類結果が得られるような入力を意図的に作成することが可能です。これは、Kumar et al. による攻撃分類では、perturbation attacks や adversarial examples in the physical domain に該当します。 攻撃対象のシステムに対して、攻撃者がデータの入力や出力の確認などを行うことができる余地が大きいほど、攻撃が成功する可能性は大きくなります。 また、学習プロセスに関する情報（教師データ、学習結果、学習モデル、テストデータなど）があれば、攻撃はより容易に行えるようになります。 現状では、数秒で攻撃できるものから何週間も必要になるものまで様々な事例が知られています。 本件はアルゴリズムの脆弱性であり、攻撃対象となるシステムにおいて機械学習の仕組みがどのように使われている
smartcache ~ プリフェッチするインメモリキャッシュ | おそらくはそれさえも平凡な日々
https://github.com/Songmu/smartcache smartcacheというGoのインメモリキャッシュライブラリを書いた。 一般的に、キャッシュを実装する場合以下のような問題が起こりがちです。 キャッシュ更新時にリクエストが殺到してしまう(いわゆるThundering Herd問題) キャッシュ生成に時間がかかる場合、キャッシュ更新時に処理がブロックしてしまう smartcacheは上記の問題を以下のアプローチで解決しています。 キャッシュ更新処理を一本化する Goの場合 golang.org/x/sync/singleflight を使えば簡単! キャッシュ期限切れ前に内部的に更新処理をおこなう いわゆるプリフェッチ的な処理 使い方 コンストラクタにキャッシュの実際の有効期限、softな有効期限、そしてキャッシュ生成関数を渡します。 // コンストラクタ ca :
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
浮動小数点数オタクが AtCoder Beginner Contest 169 のC問題をガチで解説してみる - Qiita
高評価アクションゲーム『Celeste』開発者が、“手触り“に関する極意を明かす。プレイヤーにストレスを与えないように取り組んだこと - AUTOMATON
The HashSet<T>.removeAll method is surprisingly slow