第5回 転置索引の実装 | gihyo.jp
はじめに 前回、前々回と転置索引の論理的構造について見てきました。今回は、転置索引の具体的なデータ構造や実装について説明していきます。 辞書の実装 辞書は通常、単語に対応した情報を高速に取得するために、ハッシュや木構造などのデータ構造を取ります。現在は, 安定した性能や単語の順序関係を利用したいなどの理由で、木構造のデータ構造が使われることが多いと思います。最も単純な場合、2分探索木（Binary Search Tree）や2分探索（Binary Search）の実装が考えられます。 2分探索（木）による辞書の実装 では、辞書の具体的なデータ構造について、図を交えて解説していきましょう。 前回も触れましたが、辞書には単語とその単語に対応するポスティングリストの位置情報のペア（のリスト）が格納されています。単語で検索をするので、ペア自体は単語をキーとして並び換えられます。 たとえば, 前回の
第4回 転置索引の詳細 | gihyo.jp
前回は転置索引の概要を説明しました。今回は転置索引をもう少し詳しく見ていきます。 転置索引＝辞書＋転置リスト 転置索引は大きく分けて2つの部分から構成されています。文書に出現する単語のリストである「辞書」と、その辞書にある各単語がどの文書に出現するかを表したポスティングリストの集合の「転置リスト」からなります（図1）。ポスティングリストやポスティングに関しては前回簡単に説明しましたが、図を見て再度確認してください[1]。 図1 転置索引の構成 辞書は単語だけでなく、その単語に対応するポスティングリストの位置情報を含んでいます。よって、辞書を探索することで、該当する単語のポスティングリストを取り出すことが可能となります。 一方、ポスティングリストは、どの文書に出現するかを表すのに最低でも文書のID（数値）が必要となります。書籍の場合は、文書はページなのでページ番号が文書IDとなります。
線形計画法 - Wikipedia
出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（2023年5月） 線形計画法（せんけいけいかくほう、線型計画法、英語: linear programming、略称: LP）は、数理計画法において、いくつかの1次不等式および1次等式を満たす変数の値の中で、ある1次式を最大化または最小化する値を求める方法である。線形計画法の対象となる最適化問題を線形計画問題という。 線形計画法はいくつかの理由で最適化の重要な分野である。オペレーションズリサーチの多くの実際的な問題は線型計画問題として記述できる。ある特殊なケースのネットワークフロー問題や多品種流問題（英語版）といった線型計画問題はこれらを解くために特別なアルゴリズムを考案するに値するほど重要だと考えられている。他のタイプの最適化問題に使われる多くのアルゴリズム
線型計画問題 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "線型計画問題" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2011年11月) 線型計画問題 (せんけいけいかくもんだい、英: linear programming problem) とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。この問題を解く手法を線型計画法という。 行列やベクトルを用いて表現すると、行列Aとベクトルb,cが与えられたとき、制約条件Ax≤b, x≥0をみたしつつcTxを最大化するベクトルxを求める問題のことである。 線型計画問題は次のように記述できる
11．動的計画法と擬多項式時間アルゴリズム
内容 スライド 1 11．動的計画法と擬多項式時間アルゴリズム スライド 2 これまでは、主に、「問題がいかに難しいか」を理論的に証明する方法について学んで... スライド 3 １１−１．部分和問題（SUBSET SUM Problem) スライド 4 インスタンス例 スライド 5 入力サイズ スライド 6 部分和問題の指数時間アルゴリズム スライド 7 したがって、次のようなアルゴリズムが得られる。 スライド 8 このアルゴリズムの計算量は、1-3を 回繰り返しており、 ２．において... スライド 9 部分和問題の擬多項式時間アルゴリズム スライド 10 方針 スライド 11 表の概形 （アルゴリズムの基礎にあたる。） スライド 12 要素 に注目した表の更新。 スライド 13 要素 に注目した表の更新。 スライド 14 要素
部分和問題 - Wikipedia
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。NP完全であることが知られている。 部分和問題は、分割問題 (Number Partitioning) の一般形でもある。分割問題とは、与えられた n 個の整数 a1,...,an を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。分割問題も、NP完全であることが示されている。 たとえば、「{1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？」であれば存在する（{1,7,13}である）、が答えである。また「{2,4,6,8,10} の部分和で、和が 19 になる
DPとは何か フィボナッチで - 簡潔なQ
主に漸化式で与えられる問題を解くのに使われる動的計画法(DP)。 DPとメモ化再帰の定義を、フィボナッチ数列を計算するプログラムを例にして考える。 /* 「フィボナッチ 再帰バージョン」 * フィボナッチ数列を漸化式の通りに実装したもの * この計算ではO(1.618^N)つまり指数オーダーの時間がかかる */ #include <stdio.h> int fib(int n) { if(n==0)return 0; if(n==1)return 1; return fib(n-1)+fib(n-2); } int main(int argc, char **argv) { printf("%d\n", fib(10)); return 0; } /* 「フィボナッチ メモ化再帰バージョン」 * 計算結果を配列に保存するようにした再帰 * この計算では線形時間でできる */ #includ
動的計画法 - Wikipedia
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。 「動的計画法 (dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いはじめ、1953年に
足し算引き算で10を作るゲームと部分和問題、DP - 素人がプログラミングを勉強していたブログ
切符の問題 切符の裏に印刷してある4桁の数字を4つの数字と考えて、足し算と引き算だけで10を作るゲームの解き方。 例えば、1,2,3,4の場合は1+2+3+4=10。 プログラム的には、 prob([1,2,3,4]); // [{plus: [1,2,3,4], minus: []}] こんな感じに返ってくるようにしたい。 まず、2,4,5,7から10を作る場合。2+4+5+7=18であるので、上記の式のいくつかの符号を-にすればいいことが分かる。一つの数字を引くと、18を出す時に最初に足した分と、今引こうとしている分の2つ引かなければならないから、逆算して、(18-10)/2=4を引けばいいと分かる。 この場合、合計が4になる組合せは、4そのものしかないから、2-4+5+7=10、が答えと分かる。 (合計-10)/2が引く数の合計で、それ以外が足す数である。2で割っているので、全部の数
第7回 性能改善の鍵、インデックスの特性を知る～B-treeとハッシュ （1）B-tree | gihyo.jp
SQLアタマアカデミー 第7回性能改善の鍵、インデックスの特性を知る～B-treeとハッシュ （1）B-tree はじめに データベースを扱う仕事をしていると、パフォーマンスの問題に悩まされることは日常茶飯事です。とくに最近は、データベースに格納されるデータ量が飛躍的に増え、サーバのCPUやメモリといったハード面の増強だけでは追いつかないことも多くあります。 そのようなケースに対応するため、DBMSは性能改善のための手段を多く用意しています。その中で最もコストパフォーマンスの良い方法が、インデックス（索引）です。アプリケーションにもハード構成にも影響を与えずに実行でき、うまくいかなければすぐに削除できるという手軽さが大きな魅力で、効果はしばしば絶大です。 インデックスにはいろいろな種類があり、またDBMSによってもサポートする種類に差がありますが、本稿では最も重要な2つを取り上げます。それ
heap sortを使った上位ランキング取得プログラム - 遥かへのスピードランナー
Managing Gigabytes 4.6章で解説されているソートのプログラムを実装してみた。 検索エンジンなどでN個のデータの中から上位r個を取得したい場合、まずN個のデータからなるmax-heapを構成して、ルート（最大値）から順にr個をヒープから取り除くというアプローチが考えられる。しかしN>>rの場合、r個のデータからなるmin-heapを構成して、残りのN-r個のデータをheapのルート（最小値）と順次比較して、ルートよりも大きい場合はルートと入れ替えて、heapを再構成する、という手順を取った方がより計算量が少なくて済む、という話。 10万件のランダムな数値をスペース区切りで出力するプログラム #include <iostream> #include <stdlib.h> using namespace std; int main (int argc, char *argv[
とある愚直のリニアサーチ - 神様なんて信じない僕らのために
前のエントリで線形探索のメモリアロケータは駄目だ駄目だ、と言いました。 で、まず線形探索の何が駄目って、メモリは以下のようになっています。 最初は「未使用領域（青）」しかありません。ここからどう領域をとっても良いです。 ただ、使っていくうちに「使用領域（赤）」と「未使用領域（青）」の数珠つなぎになりがちです。 new/deleteの順番を意識すればこういったメモリの配置問題が解決できることもありますが、 実際には「クラスがメモリの状態に束縛される」とすると非常に面倒です。 なので、効率的なアロケータは必須なのです。 あなたが下のような断片化した領域をつなぐ双方向リストを持っていると仮定してください。 ここから効率よくメモリを探すことは絶対にできません。 ソートしておくといったことも考えられますが、ソートすると解放された領域のマージが困難です。 （freeされた隣接した領域はより大きなメモリ
第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
2D衝突編その5 円と線分から多角形と円へ
ホーム < ゲームつくろー！< 衝突判定編 2D衝突編 その５ 円と線分から多角形と円へ 多角形は線で構成された閉じた図形です。多角形と円が衝突しているかどうかを判定できれば、複雑な形状をしたものと球とを正しく衝突判定させる事ができるようになります。効率はあまり良くありませんが、知って損はありません。 ひとつ注意。ここでの多角形は「凸多角形（多角形のどの内側の角度も180度以下である多角形）」です。凹多角形だとうまくいきません。 ① 多角形の定義 まず多角形を定義します。記号化がちょっと面倒なのですが、配列のような書き方にしておきます： 多角形 ： 頂点P[n](x[n], y[n]) 円は言わずもがなですが、中心点の座標と半径で定義できます： 円 ： 中心点C(xc, yc)、半径r では下の図を御覧ください： この図は多角形の一部と幾つかの衝突を起こしている円の状態を示しています。C1
第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
線分と楕円が交差する条件
No.1です。 > d=abs((ay2-ay1) *x1+(ax1-ax2)*y1+(ay1*ax2-ax1*ay2 ))/sqrt((ay2-ay1) ^2+(ax1-ax2)^2)・・・(1) > (ax2-ax1)(x1-ax1)+(ay2-ay1)(y1-ay1)>0・・・(2) > (ax1-ax2)(x1-ax2)+(ay1-ay2)(y1-ay2)>0・・・(3) > この 3式の > x1をx1 / |px2-px1| > y1をy1 / |py2-py1| > に置き換えたので宜しいのでしょうか？ それでいいと思います。 他のやり方としては、線分の方程式はtを媒介変数として x=(ax2-ax1)t+ax1, y(ay2-ay1)t+ay1 (0≦t≦1) と表せますから、これを楕円の方程式に代入して、 tの解が0から1の範囲にあるかどうかを調べる手もあります。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://next1.msi.sk.shibaura-it.ac.jp/MULTIMEDIA/numeanal2/numeanal2.html
シリーズ一覧 - 共立出版
線分と円が交差する条件