一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
芸能人の相関関係を探ってみるスクリプト - download_takeshi’s diary
ちょっとした実験をしてみました。芸能人の相関関係を機械的に探索してみます。 具体的には「○○というタレントと関係が深い芸能人は？」といった、芸能人にフォーカスした類似検索みたいな実験です。 技術的には「潜在的意味インデキシング」（Latent Semantic Indexing）といった手法を使います。 これは普通は自然言語処理の世界で使われるテクニックですが、なにも言語だけでなく他のデータ素材でも面白い結果が得られるかもしれないので、やってみようという試みです。 以下に大まかな手順をまとめます。 wikipedia から有名人のリストを抽出 それらの有名人リストについて、一人ずつ「誰と関連が深いか」を集計。具体的には有名人個々のwikipediaのページ中に、先ほど抽出しておいた人名リストとマッチする人名がどれだけ掲載されているかをピックアップしていきます。 上記の方法で有名人の間の相関
【人工知能】物理エンジンで人工生命つくって学習させた
運動学習させました。この仮想生物が試行錯誤をして動き方を学習しました。この動画はマルチエージェント進化シミュレータのanlifeを開発していたときに作りました。2020/10/4 追記この後作ったゾンビを宮崎駿監督にみていただいたところが2016年にNHKで放送され一部話題になりました。2016年超会議での超人工生命の生放送企画を経て、ドワンゴにて新たな人工生命を開発することに→ リリース後半年でサービスクローズ人工生命を作る会社を立ち上げました→ https://attructure.com/
Sedue Flex - あいまい検索が可能な全文検索エンジン
Sedue Flex - あいまい検索が可能な全文検索エンジン 概要 Sedue Flexは最先端の文字列検索アルゴリズムを利用し、高速なあいまい検索処理を実現した検索エンジンです。ゲノム解析やノイズの含まれた入力データに対する解析で重要となる、ミスマッチを許したあいまい検索が重要となりますが、従来であればスーパーコンピュータ級の処理能力を必要としていたゲノム解析などを１台～数台の PC上で高速に処理することが可能です。 特徴 Sedueに利用されている検索技術そのままでは完全マッチングを効率的に行うことのみが可能となっておりますが、Sedueの検索技術と各種配列アライメント技術を統合することにより、効率的なあいまい検索を実現することができます。これにより文字列の欠落や追加、ミスマッチありの場合でも高速検索が可能となります。Sedue Flexでは、10%～20%の誤りを許した全文検索を、
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 × GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
DO : Bep: 最小完全ハッシュ関数を用いた連想配列
Bepという連想配列のライブラリを公開しました。BSDライセンスです． キーは文字列限定で，前もって大量のキーと値のペアが前もって分かっている場合（１千万個とか）、使ってもらえるよう最適化しています。（一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています） 特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです．今のところ１千万キーぐらいで動作するのは確認しています．１キーあたり必要な作業領域量は大体3bit + キー自体の長さになります． 最小完全ハッシュ関数の構築自体も面白い問題です．最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました．3-ハイパーグラフの頂点割り当
P2P上のSNSでマイミクをどう表現するか？ - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 ◇はじめに MixiでSNS on P2Pコミュニティというものがある。これはP2PでSNSを実装するために各種の検討をするためのコミュニティである。（個人的にはSNS over P2Pと言ったほうがしっくりくるけども。） かなり以前となるが、MixiのP2PコミュニティでP2PでSNSは構築できるのか？という話題があった。私がその際に考えたのはFOAFを使ってマイミク情報を記述することである。 今回SNS on P2Pコミュニティに加入することによって改めてFOAFを使うことの利点と課題を考えてみたので、SNSでP2Pを実現したいと考えている方は参考にして欲しい。 ◇Ｆ
Parsing expression grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
Ruby/Bsearch: a binary search library for Ruby
Ruby/Bsearch is a binary search library for Ruby. It can search the FIRST or LAST occurrence in an array with a condition given by a block. The latest version of Ruby/Bsearch is available at <URL:/ruby-bsearch/> . Example % irb -r ./bsearch.rb >> %w(a b c c c d e f).bsearch_first {|x| x <=> "c"} => 2 >> %w(a b c c c d e f).bsearch_last {|x| x <=> "c"} => 4 >> %w(a b c c c d e f).bsearch_upper_boun
すべらない名無し | 独身者が増えた理由
71 名無しさん＠八周年 2007/07/10(火) 19:05:42 ID:WWAUdqld0 10人の男と10人の女がいたとする。 まず、いちばんもてる男に、女が３人くらい寄っていく。 ２番目にもてる男も、負けじと２人くらい持っていく。 したがって３番目の男は、６番目の女と一緒になる。 以下、４番目の男は７番目の女と、 ５番は８番と、６番は９番とカップルになる。 しかし、残る７番目以降の男にもプライドだけはあるので、 最後に余った10番目の女など誰も相手にしようとしない。 さて、上位の女を独占したNo.1＆2のモテ男も、最終的には 一人を選ばねばならないから、ここで３人の女があぶれる。 でも、すでにモテ男と付き合った経験のあるこの３人の女は、 いまさら下位の男と一緒になろうなどとは考えない。 こうして、互いに性質の異なる独身男と独身女が残る。 男 女 １ ○ ○ ２ ○ ×
h指数 - Wikipedia
h指数（エイチしすう、h-Index）とは、物理学者ジョージ・E・ハーシュ（英語版）が引用索引データベースWeb of ScienceのTimes Cited（被引用数）を元に考案した指標で、論文数と被引用数とに基づいて、科学者の研究に対する相対的な貢献度を示すものである。ただし引用に関する慣習は研究分野により異なるため、h指数は同じ研究分野における研究者同士の比較にのみ使用されるべき量である[1]。 科学者の研究評価は、研究の内容や重要性など様々な要素が絡んでいるため難しい。そのため、分かりやすい客観的な基準として研究の成果である論文数が使用されている。単純な論文の数だけでは、論文の質が保証されないので、論文が他の論文に引用された数（被引用数）を規準にすることが一般的である。 しかし、被引用数を基準とした評価では、科学者個人の仕事の質は分かりにくい。分かりやすい例として、100の引用を受
[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 □はじめに ＤＨＴやＳｋｉｐｇｒａｐｈなどの技術が注目されるとともに、位置情報をP2Pで扱いたいという要望がでてきている。だがＤＨＴやＳｋｉｐｇｒａｐｈは1次元の数値で各ノードが扱う情報範囲を扱うため、位置情報など多次元の情報を扱うのには、当初は向いてないと見られていた。しかしあるテクニックを使うとそれは一発で解消する。それがZ-orderingである。なお、このZ-orderingは位置情報を扱えるP2PミドルウェアPIAXでも採用されている。 □簡単な例 多次元を1次元で表すにはどうすればよいのだろうか？まずここで一例を挙げてみる。 例えば、2次元空間においてｘ＝｛１
Tx: Succinct Trie Data Structure
English 概要 TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます．内部データ構造にはSuccinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています． ダウンロード Txはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます. tx-0.12.tar.gz: HTTP Archives tx-0.11.tar.gz: HTTP tx
Judy Arrays Web Page
What is Judy? Judy is a C library that provides a state-of-the-art core technology that implements a sparse dynamic array. Judy arrays are declared simply with a null pointer. A Judy array consumes memory only when it is populated, yet can grow to take advantage of all available memory if desired. Judy's key benefits are scalability, high performance, and memory efficiency. A Judy array is extensi
Skip list - Wikipedia
In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. Fast search
Microsoft Corporation
Microsoft Learn. Spark possibility. Build skills that open doors. See all you can do with documentation, hands-on training, and certifications to help you get the most from Microsoft products. Learn by doing Gain the skills you can apply to everyday situations through hands-on training personalized to your needs, at your own pace or with our global network of learning partners. Take training Find
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Robert Sedgewick - Robert Sedgewick
Knowledge-Domain Interoperability and an OHS - 1990 (AUGMENT,132082,) - Doug Engelbart Institute
凸最適化 - DO++