ソート済の整数列を圧縮する件
圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。 一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。 で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。 検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号（の特殊系であるライス符号
社内勉強会：iOSのBluetooth通信でRSA暗号化体験 - Tech Blog
はじめまして、iOSエンジニアの千吉良です。 今回は社内で行われている勉強会の内容の一つを紹介したいと思います。 弊社では社内勉強会として、幾つかのチームごとに題材を決め、定期的に発表を行う会を開いております。僕は「SICP(計算機プログラムの構造と解釈)」を題材としています。SICPはMITで計算機科学の入門的な教科書として使われているものらしく、表紙に魔術師のような絵が描かれている事から、巷では「魔術師本」とか呼ばれているみたいですね。 今回紹介する内容 SICPの序盤に、素数に関する箇所があります。素数を使って何か発表向けのものができないかと考えたところ、RSA暗号が思い浮かびました。秘密鍵・公開鍵って良く聞くし使いますよね。iOS担当でもある事ですし、2台のiPhone端末間でRSA暗号を使ってやりとりをするようなものができないかと思い、Bluetooth通信を利用して鍵の受け渡し
双方向ダイクストラ - tshitaの備忘録Ⅱ
・（追記）2015年11月3日：Mi_Sawaさんとtmaeharaさんのソースコードへのリンクとtmaeharaさんのプログラムとの比較 [概要] 双方向ダイクストラを初めて実装したので備忘録としてまとめておきます． 時間がないのでざっくりとしか書いてません． 双方向ダイクストラ法を知らなかったのでMi_Sawaさんに教えていただきました．有り難うございます． 無向グラフ上で始点sと終点tが与えられたときのsからtへの最短路を求める問題を考えます．この問題は2頂点対最短経路問題と呼ばれています．グラフの上で最短経路を求める問題は一般的に最短経路問題と呼ばれておりいろいろな種類があります． 最短経路問題 - Wikipedia 特にsから各頂点への最短経路を求める問題は単一始点最短経路問題と呼ばれており，その問題を解く有名なアルゴリズムにダイクストラ法（ダイクストラ法 - Wikipedi
暗号技術の要点を学ぶ - 「暗号技術入門」を読んだ - $shibayu36->blog;
最近SSLやユーザアカウント管理の安全性とかに興味があって、その要素技術である暗号技術に興味が湧いてきたので、最近新板が出た「暗号技術入門」を読んだ。 暗号技術入門 第3版 秘密の国のアリス 作者:結城 浩SBクリエイティブAmazon この本は、暗号学者がよく使う仕組群(この本では暗号学者の道具箱と呼称)である、対称暗号、公開鍵暗号、一方向ハッシュ関数、メッセージ認証コード、デジタル署名、擬似乱数生成器について、仕組みを順に解説してくれる。また、ただ解説してくれるだけではなくて、その仕組みによって解決できる問題と解決できない問題を明示し、では解決できない問題を解決するにはどうするかというふうに章が進んでいくので、暗号技術を分かりやすく学んでいくことが出来る。 暗号技術というと数学的で非常に難しい印象があるけど、著者である結城さんが単純化して説明してくれているおかげで数学的知識がなくとも分
乱数の性質とセッショントークンの作成 - $shibayu36->blog;
ユーザアカウントのログイン機能とか作ってると、何らかの形でセッション用のトークンを作成する機会がある。今まではこれは適当にランダムな値を利用していればいいんでしょと思っていたのだけど、ちょっと違ったのでメモ。 乱数の性質 http://akademeia.info/index.php?%CD%F0%BF%F4によると、乱数には三つの性質がある。 無作為性：統計的な偏りがなく、でたらめな数列になっているという性質。 予測不可能性：過去の数列から次の数を予測できないという性質。 再現不可能性：同じ数列を再現できないという性質。再現するためには、数列そのものを保存しておくしかない。 この時、少なくとも無作為性のみ満たされていると弱い擬似乱数、無作為性と予測不可能性が満たされていると強い擬似乱数、全てが満たされていれば真の乱数と呼ばれる。ソフトウェアだけでは、真の乱数を作ることができず、真の乱数に
RFC6238 Time-based One-time Password Algorithm (TOTP)の仕組みのメモ - Qiita
RFCはこれ。Javaでの実装例もアリ: RFC 6238 - TOTP: Time-Based One-Time Password Algorithm RFCも十分短いけど、Wikipediaのほうはさらに簡潔: Time-based One-time Password Algorithm - Wikipedia, the free encyclopedia 日本語での参照情報: Googleの2段階認証で使われているOTPの仕様が気になった - r-weblife RFCに書いてある実装使うとかでサクッとワンタイムパスワードを生成できるので、もっと普及するといいですね。その場合はシークレットの扱いは適切にお願いします。 認証の概要 サーバーと共有しているシークレットキーと現在時刻からハッシュを生成してそれが合ってるかをみる、というのが大筋の流れ。 ワンタイムパスワードの生成 Wikip
TinySegmenterをJulia移植したらMITの先生に指導してもらえた話 - once upon a time,
先日、工藤さんがJavaScript向けに作った日本語のコンパクトな分かち書きツール、TinySegmenterをJuliaに移植したTinySegmenter.jlを作りました。 もともとは、PyconJPでjanomeの話を聞いたら居ても立っても居られなくなって、簡単なTinySegmenterを移植したんですが、そしたら思いもよらぬ展開が待っていました。 [2015/10/22 23:38 追記] 計測の問題を @repeatedly さんから指摘いただいたので再計測しました。 パッケージ登録時にMITの先生からツッコミが入る JuliaのパッケージはMETADATA.jlというセントラルなレポジトリで管理されています。 ここに登録されたパッケージはPkg.add("TinySegmenter")とREPLで実行するだけでパッケージが導入できます。*1 ここに登録をしようとした時に、
定番アルゴリズム本リスト - カレーなる辛口Javaな加齢日記
どうせ何度も使い回ししそうなので，独立した項目に切り離した． アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/08/02メディア: 単行本購入: 1人 クリック: 16回この商品を含むブログ (21件) を見るアルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/12/26メディア: 単行本購入: 1人 クリック: 4回
ITエンジニアなら知っておきたい、今更聞けないアルゴリズムの種類一覧 -
Photo by Oferico 皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？ 仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。 今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。 ■アルゴリズムを学ぶ意味 例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しか
浮動小数点、その中身とは « demoscene.jp
Tweetこんにちは、Falken/brainstormです。 デモの中では、映像を表示するには色んな数学計算が行われてますね。整数計算は簡単だと思いますが、FPUの小数点はどう計算しているのかと考えたことありませんか？そもそも、floatの中の32ビットはどんな意味を持つのでしょう？ 今日の記事はIEEE 754を判りやすく説明いたします。 floatの構造体 では、floatの32ビットの中の割り当てるビットを見ましょう。 floatのビットは3つの部分に別けられてますね。 sign bitは1ビットであり、符号という意味。このビットが0の場合は正の数、1の場合は負の数です。 exponentは8ビットであり、指数部という意味。簡単で言うと、この8ビット分は、基数2で小数点の位置が決められます。 mantissaは残りの23ビットで仮数部という意味。指数部で決められた幅の中で、この23
ゲームAI - 基礎編(2) - 『はじめてのエージェントベースアーキテクチャ』
みなさん、こんにちは! Cygamesエンジニアの佐藤です。 季節も秋を迎えて、すっかり涼しくなってきましたね。 秋の夜長はのんびり箱庭ゲームなどいかがでしょうか？ SkyrimやGTAなどのオープンワールド系の箱庭ゲームでは、 街を歩くNPC達の動きも作り込まれています。 モブキャラクターたちが街や村の中で生活感豊かに動いていると、 ゲーム世界の日常の中に実際に入り込んでいるような気持ちになれますよね! 今回の記事では、NPCの生活行動のためのAIを一例にあげつつ、 自律エージェントの考え方に基づいたキャラクター駆動の仕組みについて 御紹介したいと思います。 Ⅰ.自律エージェントとは？ 周囲の環境を認識して状況を解釈し、自身の内的な方針に基づいて意思決定を行って、 環境に働きかける行動を取る能力を持つ存在を自律エージェントと呼びます。 わかりやすく、ゲームの敵キャラクターに置き換えて考え
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
SharedArrayBufferとAtomics APIについて - JS.next
概要 JSで大きな処理を効率良く捌きたい時、今までもWorker等でスレッド立てて処理を分割する事はできたが、 スレッド間のやり取りの方法は制限されたものしかなく、バッファを共有することもできなかった。 そこで新しく導入されたSharedArrayBufferを用いると、スレッド間で共同利用できるバッファを作る事ができる。 記事更新履歴 ※この記事はV8が仕様の新しいバージョンを実装するのに合わせて断続的に更新していきます。 [2016/07/19] V8の半年ぶりの新仕様追従に対応 [2015/09/30] 公開 通常のArrayBufferとの比較 前準備： // メッセージを受け取ると渡された型付配列のインデックス0を123にするWorker w = new Worker(URL.createObjectURL(new Blob([` self.onmessage = e => {
高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開
Yahoo! JAPAN研究所の岩崎です。 私は主に特定物体認識の研究開発を行っていますが、その一方で特定物体認識において必須技術である高次元ベクトルデータの近傍検索の研究開発も行っています。近傍検索の一種であるk最近傍検索とは、クエリとしてベクトルデータが与えられた時に、クエリと空間内に点在するベクトルデータとの距離に基づき近い順にk個のデータを検索する、ことです。kが5の場合の最近傍検索の例を図1に示します。図中の数字は距離の順位で、青い点が検索結果となるデータです。 空間内のすべてのデータとの距離を計算すると時間がかかるので、高速化のためにインデックスを利用します。インデックスを用いることにより数次元といった低次元のベクトルデータ空間では高速な検索が比較的容易に実現できます。しかし、インデックスを用いても100次元を超えるような高次元ベクトルデータの場合には高速に検索することが困難と
トピックモデルを利用したアプリケーションの作成 | Tech-Sketch
最近、「機械学習」や「自然言語処理」、といったキーワードを聞くことが多くなってきていると思います。 反面、すごそうだけどなんだか難しいもの、というイメージもあるのではないかと思います。そこで、今回は「自然言語処理」の一種であるトピックモデルを取り上げ、その仕組みを紹介するとともに、その実装方法について解説していきたいと思います。 (「機械学習」の方については、以前開催した勉強会の資料がありますので、興味があればそちらもご参照ください。) トピックモデルとは トピックモデルは、確率モデルの一種になります。つまり、何かが「出現する確率」を推定しているわけです。 トピックモデルが推定しているのは、文章中の「単語が出現する確率」になります。これをうまく推定することができれば、似たような単語が出てくる文章(=似たようなモデルの文書)が把握でき、ニュース記事などのカテゴリ分類を行ったりすることができま
飛行機搭乗方法のシミュレーション - Qiita
はじめに 私はほぼ毎週飛行機に乗るため、飛行機搭乗時に、「混雑を避けるため、後方座席のお客様からご案内いたします」という案内、非常に良く聞くのですが、いつもこのアルゴリズムにあまり納得がいっていませんでした。 搭乗時の混雑の原因は主に二つあります。 手荷物の上部収納 既に乗客が座っているよりも奥の座席に入る場合（例えば、通路側に既に座っている人がいる時に、窓側の席に座ろうとすると、一度通路側の席の乗客が立つ必要がある） 私は、この2点については、後方座席・前方座席を分けることによって、むしろ上記渋滞発生箇所が近くで発生してしまい、より混雑を生むように思っていました。 全ての乗客を早く搭乗させることを目的とするならば、例えば窓側の乗客を先に搭乗させれば上記の混雑はある程度解消されます。しかし、飛行機では上部収納がいっぱいになってしまって席の近くの収納棚が使えないことがしばしばありますので、そ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「この中で最初に見つけた3つの単語」は、どうやって作っているのか - Qiita
「スプラトゥーン」リアルタイム画像解析ツール 「IkaLog」の裏側
強くなるためのプログラミング -プログラミングに関する様々なコンテストとそのはじめ方-#pyconjp
ページ移転のお知らせ