プロセッサ親和性 - Wikipedia
プロセッサ親和性（プロセッサしんわせい）、プロセッサアフィニティ (英 : Processor affinity) とは、中央制御のキューを用いたタスクスケジューリングのアルゴリズムの派生形で、タスクが特定のプロセッサと関連付けられるよう制御を行う。キュー内の各タスク（プロセスないしスレッド）が、推奨の（あるいは指定の）プロセッサを示すタグを持ち、各タスクはタグで指定されたプロセッサを割り当てられる。 プロセスは、実行されるとプロセッサ内に状態として残る（特に、キャッシュメモリ) 。プロセスがあるプロセッサで実行された後、同じプロセスが次回動作する際、プロセッサ親和性を用いて前回と同じプロセッサで動作させるようにすると、他のプロセッサで実行するより効率的に動作できるようになる。 プロセッサ親和性を用いたスケジューリングアルゴリズムの実装は、プロセッサとの親和性をどの程度強く持つかによって異
制御理論 - Wikipedia
制御理論（せいぎょりろん、英：control theory）とは、制御工学の一分野で、数理モデルを対象とした、主に数学を用いた制御に関係する理論である[1]。いずれの理論も「モデル表現方法」「解析手法」「制御系設計手法」を与える。 古典制御論は、伝達関数と呼ばれる線型の単入出力システムとして表された制御対象を中心に、周波数応答などを評価して望みの挙動を達成する理論である。1950年代に体系化された。代表的な成果物と言えるPID制御は、現在でも産業では主力である（化学プラント等、伝達関数が複雑な生産設備の制御に用いられる）[2][3]。
リーキーバケット - Wikipedia
リーキーバケット（英: leaky bucket）とは、トラフィックシェーピングなどで使われるアルゴリズムである。一般にこのアルゴリズムはネットワークに注入されるデータの転送レートを制御するのに使われ、データ転送レートの「バースト性」を平準化する。 なお、バケット (bucket) とは、バケツのことであり、転送すべきネットワークトラフィックを集積する抽象化されたコンテナである（実装は例えばバッファやキュー）。 トラフィックシェーピングではリーキーバケットのほかにトークンバケットというアルゴリズムもよく利用する。この2つは誤って混同されやすい。これらは性質も異なり、目的も異なる[1]。大きな違いは、リーキーバケットがデータ転送レートの上限を設定するのに対して、トークンバケットはデータ転送レートの平均に制限を課して、ある程度のバースト性を許容する。 リーキーバケットはネットワークに送信するト
トークンバケット - Wikipedia
トークンバケット（英: token bucket）とは、ネットワークへのデータ流入量を制御するアルゴリズムの一種であり、バースト性のあるデータ送信を許容する。いくつかの用途があるがトラフィックシェーピングの手法として使うことが多い。 なお、バケット (bucket) とは、バケツのことであり、転送すべきネットワークトラフィックを集積する抽象化されたコンテナである（実装は例えばバッファやキュー）。 トラフィックシェーピングのアルゴリズム[編集] トラフィックシェーピングでは、トークンバケットのほかにリーキーバケットも使われる。この2つは誤って混同されやすい。これらは性質も異なり、目的も異なる[1]。大きな違いは、リーキーバケットがデータ転送レートの上限を設定するのに対して、トークンバケットはデータ転送レートの平均に制限を課して、ある程度のバースト性を許容する。 概要[編集] トークンバケット
クラスカル法 - Wikipedia
クラスカル法（英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 概要[編集] このアルゴリズムは、1956年にジョゼフ・クラスカル（英語版）が Proceedings of the American Mathematical Society で発表した (pp. 48–50)。 クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、逆削除法（英語版）、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」（それぞれの連結部分の最小全域木の集合）を求められる。 アルゴリズムの解説[編集] クラスカル法の手順は次の通り。 グラフの各頂点がそれぞれの木に属するように、森（木の集合） F
プリム法 - Wikipedia
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。 アルゴリズムの解説[編集] このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。 入力: 重み付きグラフ（頂点集合 V、辺集合 E） 出力
等比数列 - Wikipedia
等比数列（とうひすうれつ）または幾何数列（きかすうれつ、英: geometric progression, geometric sequence）は、隣り合う2つの項の比が項番号によらず等しい数列をいう。各項に共通するその一定の比のことを公比（こうひ、英: common ratio）という。 例えば初項が 4, 公比が 3 の等比数列の最初の数項を列挙すると 4, 12, 36, 108, … となる。ある数列について、隣り合う項の比（この場合、12/4, 36/12, 108/36, …）が常に等しいならその数列は等比数列である。 等比数列 {an} について、（定義より公比は 0 でないため）公比 r は任意の n 番目の項とその次の項の比 r = an+1/an から得られる（特に r = 1 の場合は公差が 0 の等差数列でもある）。等比数列の各項は初項 a と公比 r を用いて具
Unix File System - Wikipedia
Unix File System (UFS) とは、Unix系オペレーティングシステム (OS) において使用されるファイルシステムである。 また固有のファイルシステムを指す言葉ではなく、Version 7 Unixのファイルシステムおよびそこから派生した一連のファイルシステムの総称である。 一般にUFSと呼ぶ場合は4.2BSDで実装された Fast File System (FFS) のことを指す場合が多く[要出典]、他にはFFFS、UFS2、UFS Logging等が存在する。 UFSボリュームは以下の部分から構成される。 パーティションの先頭数ブロックはブートブロックとして予約されている（ファイルシステムとは別に初期化する必要がある）。 UFSであることを示すマジックナンバーやファイルシステムの構成を示す基本的な値や統計情報やチューニングパラメータを含むスーパーブロック。 シリンダグ
非線形計画法 - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2023年10月） 非線形計画法（ひせんけいけいかくほう、英: nonlinear programming, NLP）は、制約条件群と未知の実変数群から成る一連の等式と不等式で、制約条件または目的関数の一部が非線形なものについて、目的関数を最小化または最大化するような解を求めるプロセスである。また、非線形計画法の対象となる問題を非線形計画問題と呼ぶ。 目的関数 f が線形で、制約空間がポリトープの場合、その問題は線形計画問題であり、線形計画法で解くことができる。 目的関数が凹関数（最大化問題）または凸関数（最小化）で制約集合が凸集合の場合、その問題は凸計画問題と呼ばれ、凸最適化の手法を用いることができる。 非凸
Logical Block Addressing - Wikipedia
Logical Block Addressing (ロジカルブロックアドレッシング) は、コンピュータの 補助記憶装置内のデータ位置を示す方法の1つ。LBAと略される。 LBAは単純に装置の最初のセクタから何番目かを示す数値である。補助記憶装置内の全セクタに 一意の通し番号が割り当てられており、それを使ってアドレッシングするわけである。 従って、ハードディスクのような同心円上に複数のトラックをもつ装置でも、CD-ROMやテープドライブのように1本のトラックで構成される装置でも同じように扱える利点がある。 ハードディスクの場合、ATAで28bit、SCSIで32bit、BigDrive対応のATAで48bitが使用されている。
Scoreboarding - Wikipedia
Scoreboarding とは、CDC 6600で用いられた、命令の衝突がなくハードウェアが利用できる状態のときにアウト・オブ・オーダー実行を行うためにパイプラインを中央管制的にスケジュールするための方法である。Scoreboarding では、すべての命令のデータ依存性が記録され、各命令は過去に発行したまだ完了していない命令との衝突がないとスコアボードが判断した場合のみ解放される。ある命令の実行が安全ではないと判断され、実行を停止した場合には、その命令が発行されたときに存在していたすべての依存関係が解決するまでスコアボードが実行のフローを監視しつづける。 ステージ[編集] 命令はインオーダーでデコードされ、以下の４つのステージを経て実行される。 発行: システムは命令によりどのレジスタを読み出すか、どのレジスタに書き込むかをチェックする。この情報は以降のステージで必要になるため記憶され
Tomasuloのアルゴリズム - Wikipedia
Tomasulo のアルゴリズムとは、1967 年にIBMのRobert Tomasuloによって考案されたコンピュータハードウェアのためのアルゴリズムで、連続した複数の命令が互いの依存関係が解けるまで実行できないような状況で、順序を入れ替えることにより実行できるようにする (アウト・オブ・オーダー実行)ためのものである。このアルゴリズムは、IBM System/360 Model 91 の浮動小数点演算ユニットで最初に実装された。 このアルゴリズムは レジスタ・リネーミングを用いるという点で、CDC 6600のScoreboardingとは異なる。Scoreboardingは、書き込み後の書き込み (WAW) と 読み込み後の書き込み (WAR) によるハザードを、命令の実行を一時停止させることで解決するが、レジスタリネーミングでは命令を連続して発行し続けることが可能である。また、Tom
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
ゴロム符号 - Wikipedia
ゴロム符号（ゴロムふごう、Golomb coding)とは、南カリフォルニア大学のソロモン・ゴロムによって開発された、幾何分布に従って出現する整数を最適に符号化することのできる整数の符号化手法である。 ゴロム符号と類似の手法にライス符号があるが、ゴロム符号の特別な場合がライス符号になるため、ライス符号のことをゴロム・ライス符号(Golomb-Rice coding)と呼称することが多い。特にライス符号は符号化・復号の計算量が少ないことが特徴。圧縮率は幾何分布の時はハフマン符号と同一で、それ以外ではそれよりも悪い。 符号化の原理[編集] 符号化のパラメータとして、1 以上の整数値 m を用いる。 m > 1 のとき、符号化対象とする整数値 x(≧0) に対して、x を m で割った商を q 余りを r とする。 商 q をunary符号を用いて符号化する。 余り r は に従って、次のように
データ圧縮（アルゴリズム一覧） - Wikipedia
「圧縮ファイル」はこの項目へ転送されています。複数のファイルを一つのファイルにまとめることについては「アーカイブ (コンピュータ)」をご覧ください。 データ圧縮（データあっしゅく、英: data compression）とは、あるデータを、そのデータの実質的な内容（情報、あるいはその情報量）を可能な限り保ったまま、データ量を減らした別のデータに変換すること。高効率符号化ともいう。 データ圧縮は、データ転送におけるトラフィックやデータ蓄積に必要な記憶容量の削減といった面で有効である。しかし圧縮されたデータは、利用する前に伸長（解凍）するという追加の処理を必要とする。つまりデータ圧縮は、空間計算量を時間計算量に変換することに他ならない。例えば映像の圧縮においては、それをスムーズに再生するために高速に伸長（解凍）する高価なハードウェアが必要となるかもしれないが、圧縮しなければ大容量の記憶装置を必
Prediction by Partial Matching - Wikipedia
Prediction by Partial Matching(PPM)は1984年にJ.G.ClearyとI.H.Wittenによって考案されたデータ圧縮アルゴリズムの1つ。 この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。 この亜種としてPPMC、PPMd、PPMZ等がある。 符号化の原理[編集] aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを統計的に予測する。 この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現確率に偏りがあるとハフマン符号や算術符号で圧縮することが出来る。 しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号(dとする
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
ループ展開 - Wikipedia
ループ展開（ループてんかい、英語: Loop Unwinding）は、プログラムのサイズを犠牲に実行速度を最適化する（時間と空間のトレードオフ）、ループ変換（英語版）と呼ばれる手法の1つである。ループアンローリング（英語: Loop Unrolling）とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。 ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる（もしくはなくす）事によって、実行速度を向上させることである[1][2]。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる[3]。 ループのオーバーヘッドは、ポインタまたはインデックスをインクリメントして配列の次の要素を指すための命令群（ポインタ演算）と「ループ終了条件」のテストに由来する。最適化コンパイラなど
ラビン-カープ文字列検索アルゴリズム - Wikipedia
ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種[1][2]。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
)
窓関数 (SQL) - Wikipedia