アナグラムを素数の積で求めると簡単(ではないけど)判定できるよって話 - 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コ
お金の総体が変わらない市場でやりとりしたら、貧富の差が生まれるか? - Line 1: Error: Invalid Blog('by Esehara' )
今日の風景 貧乏人に再分配された(半額になった)寿司の風景です はじめに 『ベットルームで群論を』という、みすず書房から出ている本の中に、「富が一定である閉鎖的なマーケットの中で、平等に富を持ったプレイヤーに対し、ランダムに得する人と損する人を決めていき、ある一定のステップを踏んだ結果、少数の金持ちと、多数の貧民の格差に分かれることになる」という話を載せていた。 この話に興味を持ったので、実際に、そういうモデルを作って、実際に閉鎖的なマーケットで各種のプレイヤーが損と得を繰り返していった結果、貧富の差が生まれるかどうかを実際に簡単なコードでシミュレーションしたいと思う。当然、このモデルは、実際の経済市場とは乖離したものであることは認めざるを得ないが、極端なモデルにも、何らかの示唆は、多分あると思う。 ルール とはいえ、ざっくりとこのようなことを書いたとして、そもそものルールが如何なるものか
FizzBuzzによるTyped Racket入門 ーー静的に型を付けるLispに向けて - Line 1: Error: Invalid Blog('by Esehara' )
今日の看板 概要 Lispにも静的型付けをおこなおうとする試みはされてきた。現在、その静的型付けLispを触るのにうってつけの環境は、恐らくTyped Racketだろう。そこで、FizzBuzzを通じて、Typed Racketがどういう型付け戦略を取っているのかを一通り試してみることにする。 はじめに 最近では、動的型付けを採用しているプログラミング言語でも、その言語を使った開発規模が大きくなるにつれて、なんらかの型チェックを行ないたいという需要が出てきている。 いくつかの言語、例えばPHPやPython、既にType Hintingと呼ばれる、何らかの関数やメソッドに対して、引数の型と返り値の型を指定できるようになっている。これらが喜ばしいのは、その関数を利用するためのインターフェイスに関するドキュメントを、実行不可能なコメントによって注意を喚起するのではなく、型を利用して、実行可能
2進法への信奉 (Courseraの "From Nand to Tetris" Week2前半のおさらい) - Line 1: Error: Invalid Blog('by Esehara' )
今日の料理 砂肝のアヒージョ。 概要 Courseraでは、2進法で如何に計算するかということを説明していた。今回は、10進法を混じえながら、負の整数おび正の整数を如何に足すのか、について説明する。 n進法とは何か まず最初に、身近な10進法について考えてみよう。9999以下の任意の正の整数をmとし、10進法を式で表わした場合、下のように表わすことができる。以下に現れる各nは10未満の正の整数だ。 この式を見るとわかるように、10進法を表現したい場合、下のような数式に直すことが可能であることがわかる。 この式自体はなんでもないというか、「当たり前のことじゃないか」と思われるかもしれない。しかし、この当たり前のことというのは、2進法の表現にも同様に使える。上と同様に、各nを2未満、0か1で表現する場合、15未満の任意の正の整数を表現したい場合には、次のように書くことができる。 2進法の表記は
フロイドの循環検出法とポラード・ロー法による素数判定 - 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の日本語情報を探してみたのだが、自分
Word2Vec + MeCabで「ボケる」ための単語候補をピックアップするやつをやってみる - Line 1: Error: Invalid Blog('by Esehara' )
近況 はじめに 最近、ちょっと大喜利を始めていて、如何に面白いことを言えるのか、ということを考えたりしているんだけど、考えてみれば、自分は少しプログラミングができるし、むしろ形態素解析や自然言語処理という観点から「質問」と「ボケ」を考えてみると面白いかもしれない、と思って、力技でそういうことをやってみた次第。 今回の方針 とはいえ、何となく「質問に対して上手いボケを返してほしいな」ということであるならば、それこそ単語のランダム検出でもいいという話になってしまうので、ある程度仮説を立てて実装する。今回の仮説としては、「ある文が連想する知識の、派生する知識がその文と結びつけられた場合、人は上手いと思うのではないか」ということだ。 どういうことか。 例えば、謎かけの場合、「Aとときまして、Bととく。その心はCです」と言った際に、一見無関係の文(あるいは単語)が、Cという意味づけによって接続するこ
バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
