research!rsc: Floating-Point Printing and Parsing Can Be Simple And Fast (Floating Point Formatting, Part 3)
Introduction A floating point number f has the form f=m·2e where m is called the mantissa and e is a signed integer exponent. We like to read numbers scaled by powers of ten, not two, so computers need algorithms to convert binary floating-point to and from decimal text. My 2011 post “Floating Point to Decimal Conversion is Easy” argued that these conversions can be simple as long as you don’t car
試してわかるGo ModulesとMinimal Version Selection
このブラウザ バージョンのサポートは終了しました。サポートされているブラウザにアップグレードしてください。
Googleの検索アルゴリズムの内部資料が漏洩か？「SEO業界で長年疑われていたものが明らかに」
Mic King @iPullRank Ok, let's get this party started! A couple weeks ago I said I was publishing the most important thing I ever wrote. I was wrong. Documentation related to the Google Search algorithm leaked and I spent the weekend tearing it apart. ipullrank.com/google-algo-le… ✌🏾 2024-05-28 11:10:19 数週間前、私はこれまで書いた中で最も重要なものを発表すると言いました。それは間違いだった。 Google検索のアルゴリズムに関するドキュメントが漏洩したため、私は週末をかけてそれを徹底的に調
Twitter's Recommendation Algorithm
Twitter aims to deliver you the best of what’s happening in the world right now. This requires a recommendation algorithm to distill the roughly 500 million Tweets posted daily down to a handful of top Tweets that ultimately show up on your device’s For You timeline. This blog is an introduction to how the algorithm selects Tweets for your timeline. Our recommendation system is composed of many in
Haskell で、優先度付きキューを使ったダイクストラ法
Haskellのカレンダー | Advent Calendar 2022 - Qiita に参加させていただきます! 突然ですが Haskell でダイクストラ法を実装します。 ダイクストラ法は重み付きグラフで最短経路問題を解くアルゴリズムのひとつです。ダイクストラ法 - Wikipedia に詳しい解説があります。 ダイクストラ法は、重み付きグラフにおいて、その重みに負の値がない･･･つまり重みが正であることを前提にしています。この構造上の仮定によって、貪欲的手法を取ることができるのがその特徴で、結果ベルマン・フォード法などの汎用的なアルゴリズムよりも計算量的に有利になります。 ダイクストラ法では、始点から各頂点への到達コストを最初に \infty と置いて、そこから緩和操作によって徐々にそれらを最適コストまで収束させていくわけですが、このとき グラフの頂点集合からその時点で最小のコスト
PoSで本当にいいのか？
Ethereumのマージが迫っています。 PoSへの移行を見る前に、最後にPoSは今までの懸念を払拭できているか？このままPoSを主流にして良いのか冷静に考えてみましょう。 PoSには元々多くの懸念がありました。多くの理論的なアップグレードがされ、残された論点はビザンチン将軍問題や二重支払いに関するシステマティックな話よりも、公平性や一般的に言う非中央集権性の議論に移っているように思われます。 まず、第一に「PoSとPoWの比較」について考える時、重要なのはパラメータ(=実際の数字)です。実際の値について考えなければPoWとPoSの比較議論は、「女性に生まれる方が男に生まれるより幸せだと思う」くらいの解像度の議論になってしまい、最高級のお世辞を言っても「完全に世界最悪の時間の無駄ではない議論」程度の内容でしょう。例えば、極端な例で「年間100%以上インフレでスパコンを持ってないと参加不可能
【重要】予測公開停止予定のお知らせ - 競馬AIゆま牧場
8月末をもって当サイト及びTwitterでの予測公開を停止します。 停止理由は「ゆまの利用者増加を支えきれなくなったため」です。 幸いなことにこの4年半の間で多くの人にゆまを利用いただけるようになりましたが、それに伴いオッズの低下も当然発生しました。(※1) 御存知の通り、競馬は同じ予想をしている人が増えるとオッズが下がり勝つのが難しくなります。 これまでオッズの低下をカバーするように予測性能の改善を行っていましたが、そろそろカバーできないレベルになりつつあります。(※2) このまま公開を続けていくと更にオッズが下がり、近々勝てない（勝つのが難しい）予測になりえます。 勝てない予想を提供することはポリシー上やりたくないので、その前に公開を終了することにしました。 今後は個人的に非公開のまま運用を続ける予定です。 オッズ低下がない状態、すなわち斤量ゼロの状態でどれだけのパフォーマンスが出るの
リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み – RORO
Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。 (追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future) なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。 リアルタイム共同編集の流れ 共同編集システムの登場人物は次の通りです： サーバ x 1（各クライアントから届く編集操作をもとに、最新の文書を保持します） クライアント x N（文書を編集する側です） そ
Python 3.11 からデフォルトの文字列ハッシュアルゴリズムが SipHash13 になります - methaneのブログ
Pythonの文字列やバイト列に対するハッシュアルゴリズムは、HashDoS対策としてPython 3.4から SipHash24が使われていました。 その後、ラウンド数を減らしたSipHash13でも十分に安全だとして2015年にRustが、2016年にRubyが、SipHash24からSipHash13への切り替えを行いました。 https://github.com/rust-lang/rust/issues/29754 https://bugs.ruby-lang.org/issues/13017 Python でもSipHash13に切り替えようという提案を2017年に行っていたのですが、実装した人がなかなかプルリクエストを作ってくれず、またPythonは文字列がimmutableでハッシュ値をキャッシュしているためにそこまで大きなインパクトがなかったこともあり、ずっと放置されてい
浮動小数点数の表現と誤差 - Floating Point Number
はじめに デジタル計算機におけるデータは、全て有限の bit によって表現されています。 ですから、 ある値を表現するために仮に N bit 使っているとするならば、 その値とは高々 2 N の状態しか取りえないわけです。 しかし、 数学における実数とは無限の値を取りうるものであり、 どんなに狭い区間だけを対象とすることにしても、 その区間内に無限個の値が存在するような代物です。 では、 そんな実数を、 高々数十とか百数十のビット数でどのように表現するのでしょうか。 そのことで、 どんな事態が起るのでしょうか。 浮動小数点形式 デジタル計算機を使って数値を表現する場合、 まず、 私たちは数値を『整数』と『実数』とに区別します。 デジタル計算機で用いる整数とは、 零を中心にプラス側とマイナス側にほぼ同じ拡がりを持つ変域を持ち、 その絶対値の最大値は整数表現に用いるビット数で決まります。 一方
赤黒木の本質 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い
２つのことを同時に学ばない
こんにちは、ある人のところてんです。プロシンという情報処理学会の<s>新年会</s>学会にかれこれ15年くらい参加しているわけですが、本稿はそこで水島さんと話をした「2つのことを同時に学ばない」という考え方についてのまとめになります。 初手レイトレーシング「２つのことを同時に学ばない」というのは私が発した言葉ですが、この言葉には私の友人の影響があります。 私の友人に「新しいプログラミング言語を覚える際には、とりあえずレイトレーシングを書いてみる」と言うやつがいます。 彼にとってはレイトレーシングのコードは、資料を何も調べずとも書けるそこそこに複雑なコードという位置づけのようです。 そのため、彼にとってはレイトレーシングを新しい言語で書くことで、言語仕様にのみ問題を絞って勉強することができるわけです。仮に実行結果がマズかったとしても、それは言語仕様の理解の問題であり、アルゴリズム自体に問題な
Regular Expression Matching with a Trigram Index or How Google Code Search Worked
Regular Expression Matching with a Trigram Index or How Google Code Search Worked Russ Cox rsc@swtch.com January 2012 Introduction In the summer of 2006, I was lucky enough to be an intern at Google. At the time, Google had an internal tool called gsearch that acted as if it ran grep over all the files in the Google source tree and printed the results. Of course, that implementation would be fairl
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「Xのアルゴリズム」は数日であなたの政治的意見を変えられる――米スタンフォード大が1000人以上で検証
Sorting a Dependency Graph in Go | Andrew Meredith
bcrypt vs pbkdf2 for encrypting private keys
Human sorting
GitHub - philipstanislaus/performant-array-to-tree: Converts an array of items with ids and parent ids to a nested tree in a performant O(n) way. Runs in browsers and Node.js.
GitHub - slaypni/randomized-hopcroft-karp: An algorithm to find maximum cardinality matching of bipartite graph
google/codesearch: Fast, indexed regexp search over large file trees
