アナグラムを素数の積で求めると簡単(ではないけど)判定できるよって話 - Line 1: Error: Invalid Blog('by Esehara' )
今日の風景 つくりおきはじめました。 はじめに 元々は 永和システムマネジメントの技術面接で出された問題らしい。こく難しく言えば「ある文字列」(この文字の集合をAとすると)と「ある文字列」(この文字の集合をBとする)とした場合、このAとBの文字の集合が一緒であるかどうかをどのように判定するか、という問題らしい。もうすこし簡単に言えば、Bの文字列はAの文字列かどうかをどのように判定するかということである。 この問題の解き方は簡単で、先に言ってしまえば次のようになる: def anagram(s1, s2) s1.chars.sort == s2.chars.sort end これは、順序を考慮しない集合の場合、同じ要素が一対一になっていればいいということなわけだから、とてもシンプルでわかりやすい解答である。ただ、元のエントリが「Scheme」で書かれているので、Redditの日本語Lispコ
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
お金の総体が変わらない市場でやりとりしたら、貧富の差が生まれるか? - Line 1: Error: Invalid Blog('by Esehara' )
今日の風景 貧乏人に再分配された(半額になった)寿司の風景です はじめに 『ベットルームで群論を』という、みすず書房から出ている本の中に、「富が一定である閉鎖的なマーケットの中で、平等に富を持ったプレイヤーに対し、ランダムに得する人と損する人を決めていき、ある一定のステップを踏んだ結果、少数の金持ちと、多数の貧民の格差に分かれることになる」という話を載せていた。 この話に興味を持ったので、実際に、そういうモデルを作って、実際に閉鎖的なマーケットで各種のプレイヤーが損と得を繰り返していった結果、貧富の差が生まれるかどうかを実際に簡単なコードでシミュレーションしたいと思う。当然、このモデルは、実際の経済市場とは乖離したものであることは認めざるを得ないが、極端なモデルにも、何らかの示唆は、多分あると思う。 ルール とはいえ、ざっくりとこのようなことを書いたとして、そもそものルールが如何なるものか
Quine Tweet: 自分自身へのリンクを持つ再帰的ツイート - まめめも
This tweet is recursive. https://t.co/bZISaPd3Ts— Quine Tweet (@quine_tweet) 2016年9月19日 「このツイートはありません」となっていますが、URL をクリックすれば自分自身に飛べます。 以下、このツイートが生まれるまでの経緯を長々と書きます。 問題設定 そのツイート自身の URL を埋め込んだツイートを作ります。ツイートの URL はツイートをした後でないと決まらないし、ツイート文面を後から更新する手段はない（と思う）ので、単純ですが意外に難しい問題です。 調査 ご存知のように、現在のツイートの URL は次のような形式です。 https://twitter.com/<username>/status/<id>username はそのままなので、id を事前に予測できれば解決です。*1 調べてみるとこの id
30のプログラミング言語でFast inverse square rootを実装してみました！ - プログラムモグモグ
あなたの好きな言語は何ですか。そして、あなたの好きなアルゴリズムは何ですか。 好きな言語があると、その言語でどんな問題でも解決しようとなりがちになります。その言語を極めるのは素晴らしいことですが、その言語や似たような言語でしかコードが書けなくなったり、他の言語に対して見向きもしなくなってしまう可能性があります。 勇気を出して新しい言語にチャレンジしてみませんか？色々な言語に挑戦してみませんか？ 何から始めればいいか分からない。次にどの言語を学べばいいか分からない。いま特に何も困っていない。何でも得意な言語で書けてしまう。そういう人が多いのではないでしょうか。 新しい言語にチャレンジするきっかけを作る一つの方法は、ある特定のアルゴリズムを一つ決めて、あらゆる言語で実装してみることです。解く問題が大きすぎると力尽きてしまうので、せいぜい20〜30行程度で書ける簡単なものが良いでしょう。大事なこ
動的配列について – JavaのLinkedListとArrayListを分析・比較する | POSTD
私はSkienaの『Algorithm Design Manual』 (訳注：『アルゴリズム設計マニュアル』 上巻 ・ 下巻 ) を読んでいました。ところでこの本は素晴らしい本で、連結リストと配列についてこんな比較をしていました(chapter 3.1.3)。 連結リストが静的配列に勝る相対的な長所には以下のものがあります。： • メモリが本当にいっぱいにならない限り、連結構造にオーバーフローが生じない。 • 連続的な(配列)リストに比べて、挿入と削除が単純である。 • 大きなレコードを扱う場合、要素自体を動かすよりもポインタを動かすほうが容易かつ高速である。 一方で、配列の相対的な長所には以下のものがあります。 • 連結構造には、ポインタのフィールドを格納するための余計な領域が必要となる。 • 連結リストでは、要素に対する効率的なランダムアクセスができない。 • 配列は、ランダムなポイン
XOR連結リストによるメモリ圧縮 – YOSBITS
XOR連結リストの概要 XOR連結リストはポインタ一つで双方向の走査を実現する連結リストの為のアルゴリズムです。通常、双方向リストを実装する場合は前方向と後ろ方向へのポインタを２つ使用しますが、XOR連結リストでは隣接するノードのアドレスの XOR(排他的論理和) した値を格納することで１つのマジックポインタに保存します。これよって単方向リストと同じメモリ消費にすることが出来ます。このアルゴリズムはメモリアドレスを整数として直接計算して代入できる安全ではないプログラミング言語でのみ実装できます。 次の図のような構造でリストを構築します。 head -> a tail -> d a b c d +---------+ +---------+ +---------+ +---------+ | 0 xor b | <---> | a xor c | <---> | b xor d | <---
Sublime Textの「あいまい一致」をリバースエンジニアリング | POSTD
Sublime Text は、私のお気に入りのプログラミング用テキストエディタです。 Sublime Textで気に入っている特徴の1つは、あいまい検索アルゴリズムです。ファイルや関数の検索が超高速なのです。これまで多くの人が、インターネット上で、この仕組みについて質問していましたが、満足の行く回答はありませんでした。そこで、私が自らこれを解明することにしました。 全部読むのが面倒な方へ 本文を読まずに最終結果だけ知りたいですか？ 了解！ 私は、あなたを責めたりしませんよ。 インタラクティブなデモ： こちらをクリック ソースコード： C++ 、 JavaScript Sublime Textの仕組み Sublime Textのあいまい一致とは何でしょうか。そして、なぜそれはそんなに賢いのでしょうか。聞いてくれてうれしいです。 Sublime Textには、2つの非常に便利なナビゲーション関
整数の公式でフィボナッチ数列を求める | POSTD
(注：2020/10/01、2017/6/10、いただいたフィードバックを元に翻訳を修正いたしました。) 次のコードを用いると、なんとフィボナッチ数列が生成できます。 def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) この記事では、その導き方と振る舞いを説明しましょう。 具体的な説明に入る前に、背景としてフィボナッチ数列の概要と計算方法を駆け足で紹介します。すでに数学の専門知識がある方は、導入部分はほとんど飛ばして、「母関数」のセクションをざっと読んでから、「整数の公式」に進んでいただいて構いません。 概要 フィボナッチ数列とは、言わずと知れた以下の数列です。 \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\] この数列の \(n\) 番目
ハミング符号 : データの誤り検知/訂正をインタラクティブに学ぶ | POSTD
今週お話しするのは、誤りの検知についてと、さらに誤りの訂正についてです。 我々が住んでいる世界は完璧ではなく、デジタルの信号(on/off)を扱う時でさえ誤りが生じます。電力の異常によりビットが反転することがあるのです。ハードウェアも失敗を起こすことがあり、信号が歪められることもあります。 デジタル信号に生じた誤りを検知する方法については既に過去に書いたことがあります。もっとも一般的なやり方は、ある種のパリティビット(ご存知なくともご心配なく。以下でパリティの意味を説明します)です。ある長さの単語に対し、シンプルなパリティビットをたった1つ加えることで、単語中のビットが1つ反転した場合にそれを検知することができます。「エラーが起こったことがわかる」ということは有益ですが、1個のパリティビットだけではその誤った信号を修復することができません。また、信号中に2個以上の誤りがあった場合、その誤り
Island Life - 2進小数の10進桁での丸め
About 南の島のプログラマ。 たまに役者。 Practical Schemeの主。 WiLiKi:Shiro 最近のエントリ 米国の大学進学無限cxr高校受験Defense振り返ってみると2019年は色々学んで楽...覚えるより忘れる方が難しい(こともある)眼鏡のつると3DプリンタIris Klein Acting ClassSAG-AFTRA conservatory: Voice Acting創作活動って自分を晒け出さねばならないと...More... 最近のコメント shiro on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/14)1357 on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/01)ベアトリーチェ on ハイポハイポハイポのシューリンガン (2022/04/02)ベアトリーチェ on ハイポハ
PHPのround関数とは一体なんだったのか - hnwの日記
（7/3 14:05追記）Javaに関する記述について誤認があったので盛大に書き換えました。Java 6、Java 7、Java 8それぞれで実装が変わっていたようです。 （7/13 23:55追記）本記事中ではroundを四捨五入と言い切ってしまっています。これは筆者がC99のroundを基準に考えているためですが、言語によっては偶数丸めになっているround関数も珍しくありません。ご注意ください。 PHPのround関数について、ネット上で次のような記述を見つけました。 PHP 四捨五入の計算を間違える唯一の言語として畏れられていましたが、そのバグは治っているかもしれません（治ってないかもしれません） 主要なプログラミング言語8種をぐったり解説 - 鍋あり谷あり 各言語を面白おかしく紹介する内容とはいえ、ずいぶん雑な理解だなーという印象です。ゆるふわな話だけでPHPがdisられ続けるの
なぜBTreeがIndexに使われているのか - maru source
※この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル CREATE TABLE user ( id INT UNSIGNED NOT NULL, name VARCHAR(255) NOT NULL, UNIQUE INDEX (id) ); idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています
Island Life - 誤差が生じるとき
About 南の島のプログラマ。 たまに役者。 Practical Schemeの主。 WiLiKi:Shiro 最近のエントリ 米国の大学進学無限cxr高校受験Defense振り返ってみると2019年は色々学んで楽...覚えるより忘れる方が難しい(こともある)眼鏡のつると3DプリンタIris Klein Acting ClassSAG-AFTRA conservatory: Voice Acting創作活動って自分を晒け出さねばならないと...More... 最近のコメント Aliza Smathers on Unbounded spigot algorithm (2025/03/21)shiro on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/14)1357 on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/01
とある偽シャッフルアルゴリズムとその分布 - 簡潔なQ
次のようなシャッフルアルゴリズムを考える(簡単のためrand()%Nと表記したが、この部分で0以上N-1未満の一様な整数乱数が生成されると仮定して議論する)。出力されるものは 0, ..., 255 を並び換えたもの(置換)である。 std::vector<int> a(N); for(int i = 0; i < N; ++i) { a[i] = i; } for(int i = 0; i < N; ++i) { std::swap(a[i], a[rand()%N]); } このアルゴリズムは均一ではない。a[i]==jとなる確率は、 i < jのときに高くなり、j <= iのときに低くなる。グラフにすると以下のようになる。 定理 上のシャッフルアルゴリズムで得られる aについて、 a[i]==jとなる確率は、 となる。 証明 2個目のループの本体が 回 実行された時点で a[i]==
フロイドの循環検出法とポラード・ロー法による素数判定 - Line 1: Error: Invalid Blog('by Esehara' )
今日の料理 自宅超会議の様子です。クローズドソース。あと汚ない。 概要 ある数の因数を見つけ出すためには、ポラード・ロー法という方法がある。このポラード・ロー法は、フロイドの循環検出法と呼ばれる、循環を見つける方法が関連してくる。今回は、簡単なリストを使い、この循環法を確認したのちに、ポラード・ロー法について説明をする。 はじめに 最近の日課は素数について調べることになっているのだけれど、yuguiさんのサイトにて『UBASICによるコンピュータ整数論』という本が紹介されていて、「へー」なんで思っていたりした。その中に、ロー法と呼ばれる奴が紹介されていたので実装してみるといいのかなと思って実装することにしてみた。以下はそのメモである。 循環する合同式 という式における任意の数pについて観察してみよう。例えば、53の変化の一覧を出したい場合、次のようにコードが書ける。 def modulo_
素数候補を効率よく絞りこむ「Wheel factorization」について調べたこと - Line 1: Error: Invalid Blog('by Esehara' )
今日の料理 サーモン漬け丼 概要 素数リストの求め方に関しては、前回アトキンのふるいを紹介した。この他にもWheel factorizationという方法がある。調べてみたところ、直接的な日本語の紹介が乏しいので、実装したついでに、調べた範囲のことについてメモをしておく。 はじめに 素数リストを求める方法にも様々あって、前回はアトキンのふるいを紹介したのだが、論文を読めばわかるように、確かに高速なのかもしれないが、あまり直感的とは言いがたい側面がある。 そんな中、アトキンのふるいに関して調べていた最中にJulia の素数周りの実装 - Qiitaという記事を見つけた。これによれば、「Wheel factorizationを使った Eratosthenesのふるい」にアルゴリズムを変更したことが書いてある。しかし、このWheel factorizationの日本語情報を探してみたのだが、自分
素数列挙について - MugiCha
Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。 N以下の素数をすべて求めよ。 N以下の素数の個数を求めよ。 A以上B以下の素数の個数を求めよ。 こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？ このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness ICPC 国内予選 2011 A
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Facebook、Zlibを上回る新しい圧縮アルゴリズムをオープンソース化
GitHub - benoitvallon/computer-science-in-javascript: Computer science reimplemented in JavaScript
