二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な
Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium
基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
JavaScript・再帰・トランポリン - Qiita
現状整理 JavaScript では末尾再帰最適化(PTE: Proper Tail Call) は、完全には期待できない https://kangax.github.io/compat-table/es6/ 末尾再帰による最適化 - Qiita なので再帰は注意して使わねばならない スタックオーバーフローしないことをチェック 再帰を辞めて for 文とかに何とか変換する とはいえ再帰を使いたい こともある じゃあどうするか？が本稿の目的 再帰におけるスタックオーバーフローは、末尾再帰の最適化ができる他の言語でも起こりえる(例: 末尾再帰できない場合)。じゃあ、他の言語の場合どうしているかというと、トランポリンするらしい。もちろん JavaScript でもトランポリンできる。トランポリンすると、再帰が深くなってもスタックオーバーフローしない。 処方箋 ざっくりいうと以下の処方でスタックオ
高速な文字列探索：Daachorseの技術解説 - LegalOn Technologies Engineering Blog
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse（ダークホース）を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術（トライ木・Aho–Corasick法・ダブル配列） Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
Haversine formula - Wikipedia
The haversine formula determines the great-circle distance between two points on a sphere given their longitudes and latitudes. Important in navigation, it is a special case of a more general formula in spherical trigonometry, the law of haversines, that relates the sides and angles of spherical triangles. The first table of haversines in English was published by James Andrew in 1805,[1] but Flori
Maps JavaScript API を使って地図上の 2 地点間の距離を計算する
.app 1 .dev 1 #11WeeksOfAndroid 13 #11WeeksOfAndroid Android TV 1 #Android11 3 #DevFest16 1 #DevFest17 1 #DevFest18 1 #DevFest19 1 #DevFest20 1 #DevFest21 1 #DevFest22 1 #DevFest23 1 #hack4jp 3 11 weeks of Android 2 A MESSAGE FROM OUR CEO 1 A/B Testing 1 A4A 4 Accelerator 6 Accessibility 1 accuracy 1 Actions on Google 16 Activation Atlas 1 address validation API 1 Addy Osmani 1 ADK 2 AdMob 32 Ads
緯度経度から2地点間の距離を計算する！Google方式とヒュベニ式・表計算ソフトで計算できる・GPSデータも使える
緯度経度から2地点間の距離を計算する！Google方式とヒュベニ式・表計算ソフトで計算できる・GPSデータも使える 地上の2地点の距離を緯度と経度から計算する。地球は真球ではなく回転楕円体に近いので、より高い精度を求めるならば回転楕円体による計算をする必要がある。しかし地球を真球をとして計算しても実用的には十分な数値が得られる。ヒュベニの近似式による計算方法も追加した。 緯度経度から2地点の距離を計算 真球として計算するので、長半径と短半径のどれを使うのかというと、平均半径を使用する。平均半径にも色々な考え方があり、いろいろな数値がある。最初はGoogle Mapで使用されている方法で計算する。真球として計算され、地球の半径を6371kmとしている。 球面上の最短距離(D)を求める公式を下に示す。地中を貫通する最短距離ではなく、表面に沿った距離だ。単位はkmである。2地点の座標は地点1が（
緯度経度から2点間の距離を求める – ぷちのいず
久しぶりに開発途中のネタです。 POI の最寄検索や、検索結果表示で現在値からの距離を表示させたくて、任意2点の緯度経度から距離を計算する方法を調べてみました。 地球が球体なら何となく頭をひねれば分かるかもしれませんが、楕円体の緯度経度から距離を求めるのは私には見当もつきません。 ということでググってみると、楕円体を考慮していて、世界中の緯度経度で通用しそうな計算式が2つ見つかりました。 ヒュベニの公式 (参考HP: 日本は山だらけ～ 技術研究本部) Lambert-Andoyerの公式 (参考HP: 測地線航海算法(Geodesic Sailing)) 何となく航海で使用する下の公式のほうが正確な気はしますが、上のヒュベニの公式の方が演算が簡単そうな気がします。 また、qgmapでは多少の誤差も許容できるので数％程度(?)の精度で十分です。そこで近似式も候補に入れてみます。 簡易近似式
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
How We Made Bracket Pair Colorization 10,000x Faster In Visual Studio Code
Register now for a full day of community, learning, and all things Visual Studio Code Bracket pair colorization 10,000x faster September 29, 2021 by Henning Dieterichs, @hediet_dev When dealing with deeply nested brackets in Visual Studio Code, it can be hard to figure out which brackets match and which do not. To make this easier, in 2016, a user named CoenraadS developed the awesome Bracket Pair
頭が痛くならない「ダメージ計算式」の基本の話｜だらねこ
戦闘のあるゲームを作るなら、考えないといけないのがダメージの計算式。でも、計算式のコツとか基本とか調べると、小難しそうな話が出てきて め、めんどくせぇ～ってなったりしませんか？私はなります。色んな計算式とその特徴を羅列されても、よくわかんなくなっちゃう。 とはいえ私もゲームデザイナーの端くれなので、ダメージ計算式を考える機会がそれなりにあります。そして他人の作った変な計算式に苦しめられることも、いっぱいあります。泣きたい。 大元の計算式が悪いと、それを利用してバランス調整しても苦労する事が多いんですよ。なので、そんな悲劇を少しでも食い止めるためにもですね。 この記事では 数字が苦手な文系の人でも、なんかいい感じに計算式を考る…とっかかりになることを目指して書いていこうかと思います。 ※こういう計算式がある！選んで使え！！という記事ではありません。 ※計算式を考える時、こういうのを把握して、
線形計画法の問題の解き方を詳しく解説！例題つき｜高校生向け受験応援メディア「受験のミカタ」
線形計画法は線形計画問題を解く方法のうちの一つです。 線形計画問題は大学入試問題でも度々出題されます。 この記事では、線形計画法についてまとめます。 【PR】勉強を効率的に継続して、志望校に合格したい方必見！ ↓無料ダウンロードはこちら↓ １．線形計画法とは 線形計画法という言葉は、高校の数学の教科書に載っている単語ではありません。 高校の教科書でよく使われる単語としては「領域における最大・最小」などと言うのが一般的でしょう。 どちらにせよ、問題の解き方が変わるわけではありませんが、実際に問題を解く前に、線形計画法についてもう少し詳しく説明しておきましょう。 線形計画法は、線形計画問題を解くための手法です。 さらに、線形計画問題は最適化問題のうちの一つで、多くの分野に応用されています。 最適化問題をしっかり理解するためには大学の知識が必要ですから、詳しくは大学の「線形代数学」や「解析学」を
魔方陣 - Wikipedia
魔方陣（まほうじん、英語: magic square）とは、n × n 個の正方形の方陣に数字を配置し、縦・横・対角線のいずれの列についても、その列の数字の合計が同じになるもののことである。特に1から方陣のマスの総数 n2 までの数字を1つずつ過不足なく使ったものを言う。 このときの一列の和は、 と計算できる。 魔方陣の歴史は古く、中国では紀元前190年前には存在していた。魔法や神話的な意味を獲得し、芸術作品の象徴として様々な場所で用いられてきた。 現代では縦・横・対角線以外の形状の和や、数字の積などの単なる和以外の演算などにも一般化されている。 魔方陣の例[編集] 1×1の魔方陣は明らかである。 2×2の魔方陣は同じ数字を使用しない限り存在しない。 ＜証明＞ ゆえに したがって3×3のものが意味のあると思われる最小の魔方陣になる。 3×3の魔方陣[編集] 3×3の魔方陣（三方陣）は、対称
本当は遅い「似非エラトステネスの篩」の罠
この記事は？ インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の3つのアルゴリズムを比較して、その違いを解説します。 3つのアルゴリズムの比較 1. 試し割り 実装 まず他のアルゴリズムに対する評価基準として、試し割りのアルゴリズムを示します。 試し割りは、nが素数であるかを判定するために\sqrt{n}以下の全ての素数で割って確認するアルゴリズムです。 import sys # limit 以下の全ての素数を返す def list_primes(limit): primes = [] for i in range(2, limit + 1): is_prime = True for p in
検索エンジンの数値インデックスを支える Bkd-Tree - 好奇心に殺される。
Computer Science / Algorithm 検索エンジンの数値インデックスを支える Bkd-Tree Elasticsearchの数値データインデックスに使われるBkd-Treeというアルゴリズムを論文を読みながらまとめました。 Overview こんにちは pon です。Elasticsearch & Lucene 輪読会を弊社で毎週開催しているのですが、そこでBkd-Treeというアルゴリズムに行き着きました。そこでBkd-Treeの論文を読んでみたので、まとめたものを共有しようと思います。 論文はこちら Bkd-Tree: A Dynamic Scalable kd-Tree LuceneでのBkd-Tree Bkd-TreeはLucene6から導入されたようで下記のようにスペース効率、パフォーマンスが大幅に改善されたようです。 以下こちらのElasticsearch公
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言語の連想配列の従来実
レーティングについてと，グリコ2レーティング(Glicko-2 System)におけるレーティング算出方法 - 機械学習、たまにゲーム
概要 オンラインゲームやチェスなどのボードゲームで使われているレーティングに関する記事です． レーティングの算出方法は何種類かありますが，その中でSplatoon2やシャドウバースなど，様々な対戦ゲームで使われているグリコ2レーティング(Glicko-2 System)というレーティングアルゴリズムについて説明します． 「アルゴリズムの中身をはやく知りたい！」という方は，下の『本題：グリコ2レーティングのしくみ』からご覧ください． アルゴリズムの説明には数式が登場します．「数式なんて見たくない！」という方は，この記事の前半でレーティング全般およびその歴史について書いたので，そちらでレーティングに対するイメージ・理解を深めていただければ嬉しいです． はじめに：レーティングとは みなさんは「レーティング」という言葉を聞いて，どんなものが思い浮かびますか． 国語辞書でレーティングを調べてみると，
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
UNIXTIME
The Algorithms
