JPH04160675A - 集合要素・ビット表現装置 - Google Patents
集合要素・ビット表現装置Info
- Publication number
- JPH04160675A JPH04160675A JP28963290A JP28963290A JPH04160675A JP H04160675 A JPH04160675 A JP H04160675A JP 28963290 A JP28963290 A JP 28963290A JP 28963290 A JP28963290 A JP 28963290A JP H04160675 A JPH04160675 A JP H04160675A
- Authority
- JP
- Japan
- Prior art keywords
- bit
- sets
- elements
- correspondence table
- executed
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000006243 chemical reaction Methods 0.000 claims description 7
- 230000001174 ascending effect Effects 0.000 abstract description 3
- 230000008707 rearrangement Effects 0.000 abstract 1
- 238000000034 method Methods 0.000 description 5
- 238000010586 diagram Methods 0.000 description 4
- 230000000694 effects Effects 0.000 description 2
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は集合要素およびビットの対応づけ表現に利用す
る。本発明はスケジューリングなどにおける資源の時区
間の関係のような数値の要素に着目したときの関係を表
現する要素・ビット対応テーブルの生成を自動的に行う
集合要素・ビット表現装置に関する。
る。本発明はスケジューリングなどにおける資源の時区
間の関係のような数値の要素に着目したときの関係を表
現する要素・ビット対応テーブルの生成を自動的に行う
集合要素・ビット表現装置に関する。
本発明は複数個の要素で構成された複数の集合間の関連
性および集合の操作を行う集合要素・ビット表現装置に
おいて、 集合の一つの要素を一つのビットに関係付は集合をビッ
ト列化し、ビット演算を集合操作に適用することにより
、 集合操作を効率的に行えるようにしたものである。
性および集合の操作を行う集合要素・ビット表現装置に
おいて、 集合の一つの要素を一つのビットに関係付は集合をビッ
ト列化し、ビット演算を集合操作に適用することにより
、 集合操作を効率的に行えるようにしたものである。
従来、集合を表現する際にはリストを用いていた。この
表現方法では集合に関する操作を行う場合、各集合を現
すリストをおのおの少なくとも１回は走査しなければな
らないため、二つの集合の大きさの和に比例する時間を
要していた。
表現方法では集合に関する操作を行う場合、各集合を現
すリストをおのおの少なくとも１回は走査しなければな
らないため、二つの集合の大きさの和に比例する時間を
要していた。
この種の従来の技術では、集合を表現するのに必要な記
憶総量は集合の要素の数に比例し、集合に関する操作に
必要な時間量はその操作の性質によって異なる。
憶総量は集合の要素の数に比例し、集合に関する操作に
必要な時間量はその操作の性質によって異なる。
たとえば、二つの集合をＡ、Ｂとすると、ＡｎＢという
操作はＡＳＢを現すリストをおのおの少なくとも１回は
走査しなければならないため、操作の時間量は二つの集
合Ａ、Ｂの大きさの和に比例する。ＡＵＢの操作につい
ても同じ要素が両方に現れている場合にはどちらか一方
を取り除かなければならないため、同様に少なくとも集
合の大きさの和に比例する時間を必要としていた。
操作はＡＳＢを現すリストをおのおの少なくとも１回は
走査しなければならないため、操作の時間量は二つの集
合Ａ、Ｂの大きさの和に比例する。ＡＵＢの操作につい
ても同じ要素が両方に現れている場合にはどちらか一方
を取り除かなければならないため、同様に少なくとも集
合の大きさの和に比例する時間を必要としていた。
本発明はこのような欠点を解決するもので、リストに代
わるものとしてビット列表現を用い、ビット演算を集合
操作に適用することによって効率的に実行できる集合要
素・ビット表現装置を提供することを目的とする。
わるものとしてビット列表現を用い、ビット演算を集合
操作に適用することによって効率的に実行できる集合要
素・ビット表現装置を提供することを目的とする。
本発明は、複数個の要素で構成された複数の集 ゛合間
の関連性および集合の操作を行う集合要素・ビット表現
装置において、集合要素の性質をビット位置に対応させ
る要素・ビット変換手段と、対応した要素およびビット
が登録される要素・ビット対応テーブルと、複数の集合
に対して和および積を操作する集合操作手段とを備えた
ことを特徴とする１゜ 前記集合操作手段は、ある要素がどの集合に属するかを
判定する手段を含み、前記要素・ピッ’−対応テーブル
には、ビット位置に対応して要素を。
の関連性および集合の操作を行う集合要素・ビット表現
装置において、集合要素の性質をビット位置に対応させ
る要素・ビット変換手段と、対応した要素およびビット
が登録される要素・ビット対応テーブルと、複数の集合
に対して和および積を操作する集合操作手段とを備えた
ことを特徴とする１゜ 前記集合操作手段は、ある要素がどの集合に属するかを
判定する手段を含み、前記要素・ピッ’−対応テーブル
には、ビット位置に対応して要素を。
記憶することが望ましい。
集合を構成する複数の要素を昇順に並び換え、この並び
換えにより得られた集合を一つ取り出しその中の要素を
それぞれ１ビツトに対応づけ、対応づけられたビット列
を要素・ビット対応テーブルに登録する。このような処
理をすべての集合に対して行いビット列化し、このビッ
ト列表現を用いてビット演算を行う。これにより、集合
操作を効率的に行うことができる。
換えにより得られた集合を一つ取り出しその中の要素を
それぞれ１ビツトに対応づけ、対応づけられたビット列
を要素・ビット対応テーブルに登録する。このような処
理をすべての集合に対して行いビット列化し、このビッ
ト列表現を用いてビット演算を行う。これにより、集合
操作を効率的に行うことができる。
次に、本発明実施例を図面に基づいて説明する。
第１図は本発明実施例の構成および処理の流れを示す流
れ図である。
れ図である。
本発明実施例は、複数個の要素で構成された複数の集合
間の関連性および集合の操作を効率的に行うための手段
として、集合要素の性質をビット位置に対応させる要素
・ビット変換手段１と、対応した要素およびビットが登
録される要素・ビット対応テーブル３と、複数の集合に
対して和および積を操作する集合操作手段２とを備え、
集合操作手段２には、ある要素がどの集合に属するかを
判定する手段を含み、要素・ビット対応テーブル３には
、ビット位置に対応して要素が記憶される。
間の関連性および集合の操作を効率的に行うための手段
として、集合要素の性質をビット位置に対応させる要素
・ビット変換手段１と、対応した要素およびビットが登
録される要素・ビット対応テーブル３と、複数の集合に
対して和および積を操作する集合操作手段２とを備え、
集合操作手段２には、ある要素がどの集合に属するかを
判定する手段を含み、要素・ビット対応テーブル３には
、ビット位置に対応して要素が記憶される。
次に、このように構成された本発明実施例の動作につい
て説明する。
て説明する。
まず、要素・ビット変換手段１が要素・ビット対応テー
ブル３の初期化などの準備作業を総括して行い（ステッ
プ１１）、それぞれの集合の要素を昇順に並び換える（
又テップ１２）。
ブル３の初期化などの準備作業を総括して行い（ステッ
プ１１）、それぞれの集合の要素を昇順に並び換える（
又テップ１２）。
次いで、集合操作手段２が要素の並び換えが行われた集
合を一つ取り出し、その中の要素をそれぞれ１ビツトに
対応付け（ステップ１３）、対応付けられたビット列を
要素・ビット対応テーブル３に登録する（ステップ１４
）。このビット化処理をすべての集合に対して繰り返し
行う（ステップ１５．１６）。
合を一つ取り出し、その中の要素をそれぞれ１ビツトに
対応付け（ステップ１３）、対応付けられたビット列を
要素・ビット対応テーブル３に登録する（ステップ１４
）。このビット化処理をすべての集合に対して繰り返し
行う（ステップ１５．１６）。
ここで一つの要素を対応するビットに割り付ける手続き
について説明する。
について説明する。
集合の一つの要素を一つのビットに関係付けることによ
り集合をビット列化し集合操作を効率的に行うために各
要素の性質をビットの位置情報を元に表現するには、第
２図に示すような二つの集合が与えられたとき、集合Ａ
の第１番目の要素から逐次ビットに対応付け、同じ要素
が既に設定されているときはその要素の対応付けは行わ
ない。
り集合をビット列化し集合操作を効率的に行うために各
要素の性質をビットの位置情報を元に表現するには、第
２図に示すような二つの集合が与えられたとき、集合Ａ
の第１番目の要素から逐次ビットに対応付け、同じ要素
が既に設定されているときはその要素の対応付けは行わ
ない。
その過程を第３図に示す。作成された要素・ビットテー
ブル３を用いて集合Ａ、Ｂをビット化すると第４図に示
すような表現となる。
ブル３を用いて集合Ａ、Ｂをビット化すると第４図に示
すような表現となる。
第２図〜第６図は二つの集合に対するビット表現と和お
よび積の集合への適用を表した図である。
よび積の集合への適用を表した図である。
集合ＡＸＢが与えられたとき第１図に示すステップ１２
の処理が行われ、ステップ１３およびステップ１４によ
り集合Ａは第３図右上に示すように要素・ビット対応テ
ーブル３に登録される。次に、ステップ１５により集合
Ｂはまだ実行されていないのでステップ１３、ステップ
１４が実行され、第３図右下に示すように集合Ｂが要素
・ビット対応テーブル３に登録される。さらに、ステッ
プ１６で登録された要素・ビット対応テーブル３を元に
集合Ａ、 Ｂがビット列に変換される。
の処理が行われ、ステップ１３およびステップ１４によ
り集合Ａは第３図右上に示すように要素・ビット対応テ
ーブル３に登録される。次に、ステップ１５により集合
Ｂはまだ実行されていないのでステップ１３、ステップ
１４が実行され、第３図右下に示すように集合Ｂが要素
・ビット対応テーブル３に登録される。さらに、ステッ
プ１６で登録された要素・ビット対応テーブル３を元に
集合Ａ、 Ｂがビット列に変換される。
次に、和集合および積集合について説明する。
集合Ａ、Ｂの和集合ＡＵＢを求める場合、集合Ａ、Ｂは
ビット列で表現されているため第５図に示すようにビッ
ト演算ＯＲを適用して求めることができる。求めたビッ
ト列は要素・ビット対応テーブル３を参照し、ビットを
要素に対応付けることにより要素に変換することができ
る。
ビット列で表現されているため第５図に示すようにビッ
ト演算ＯＲを適用して求めることができる。求めたビッ
ト列は要素・ビット対応テーブル３を参照し、ビットを
要素に対応付けることにより要素に変換することができ
る。
同様に積集合ＡｎＢを求める場合、第６図に示すように
ビット演算子ＡＮＤを適用して求め、要素・ビット対応
テーブル３により要素に変換することができる。
ビット演算子ＡＮＤを適用して求め、要素・ビット対応
テーブル３により要素に変換することができる。
以上説明したように本発明によれば、複数の集合をビッ
ト列で表現し、集合操作にビット演算を適用することに
より、高速に解を求めることができる効果がある。
ト列で表現し、集合操作にビット演算を適用することに
より、高速に解を求めることができる効果がある。
第１図は本発明実施例の構成および処理の流れを示す流
れ図。 第２図〜第４図は二つの集合に対する要素・ビット対応
テーブルの生成およびビット変換を示す図。 第５図は和集合操作を示す図。 第６図は積集合操作を示す図。 １・・・要素・ビット変換手段、２・・・集合操作手段
、３・・・要素・ビット対応テーブル。
れ図。 第２図〜第４図は二つの集合に対する要素・ビット対応
テーブルの生成およびビット変換を示す図。 第５図は和集合操作を示す図。 第６図は積集合操作を示す図。 １・・・要素・ビット変換手段、２・・・集合操作手段
、３・・・要素・ビット対応テーブル。
Claims (1)
- 【特許請求の範囲】 １、複数個の要素で構成された複数の集合間の関連性お
よび集合の操作を行う集合要素・ビット表現装置におい
て、 集合要素の性質をビット位置に対応させる要素・ビット
変換手段と、 対応した要素およびビットが登録される要素・ビット対
応テーブルと、 複数の集合に対して和および積を操作する集合操作手段
と を備えたことを特徴とする集合要素・ビット表現装置。 ２、前記集合操作手段は、ある要素がどの集合に属する
かを判定する手段を含む請求項１記載の集合要素・ビッ
ト表現装置。 ３、前記要素・ビット対応テーブルには、ビット位置に
対応して要素が記憶された請求項１記載の集合要素・ビ
ット表現装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP28963290A JPH04160675A (ja) | 1990-10-25 | 1990-10-25 | 集合要素・ビット表現装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP28963290A JPH04160675A (ja) | 1990-10-25 | 1990-10-25 | 集合要素・ビット表現装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04160675A true JPH04160675A (ja) | 1992-06-03 |
Family
ID=17745752
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP28963290A Pending JPH04160675A (ja) | 1990-10-25 | 1990-10-25 | 集合要素・ビット表現装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04160675A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007193477A (ja) * | 2006-01-18 | 2007-08-02 | Kddi Corp | コンテンツ保護装置及びプログラム |
| JP2010175427A (ja) * | 2009-01-30 | 2010-08-12 | Advantest Corp | 電圧測定装置、方法、プログラム、記録媒体およびテスタ |
-
1990
- 1990-10-25 JP JP28963290A patent/JPH04160675A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007193477A (ja) * | 2006-01-18 | 2007-08-02 | Kddi Corp | コンテンツ保護装置及びプログラム |
| JP2010175427A (ja) * | 2009-01-30 | 2010-08-12 | Advantest Corp | 電圧測定装置、方法、プログラム、記録媒体およびテスタ |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103793349A (zh) | 一种数据处理方法及装置 | |
| JPH04160675A (ja) | 集合要素・ビット表現装置 | |
| Del Lungo et al. | ECO method and the exhaustive generation of convex polyominoes | |
| Chung et al. | Efficient search algorithm on compact S-trees | |
| JP2980303B2 (ja) | 仕分け方法 | |
| JP4427307B2 (ja) | 図形処理装置 | |
| JPH0756920A (ja) | 構造化文書処理装置 | |
| JPH02195481A (ja) | 論理回路図入力方法 | |
| JPH04115325A (ja) | 文字コードのソート方式 | |
| JP2889319B2 (ja) | 図形描画装置 | |
| JPS6346537A (ja) | 検索処理装置における検索条件判定方法 | |
| JPH03216730A (ja) | 電子計算機 | |
| CN115658972A (zh) | 一种同型异码数据检索构成方法和系统 | |
| JPH04155521A (ja) | ソーティング処理方式 | |
| Fine | Solve problems with the appropriate SPC tool | |
| JPH03262050A (ja) | パラメータパターンデータ作成装置 | |
| JPH08167849A (ja) | コード変換方法及びコード変換器 | |
| JPH05274119A (ja) | 構成定義方式 | |
| JPH05143280A (ja) | 数量管理システムにおける単位換算制御装置 | |
| JPH0527976A (ja) | 状態コード割付け方法および状態コード割付け装置 | |
| JPH02266413A (ja) | コード変換方法 | |
| JPH06138913A (ja) | プログラマブルコントローラ | |
| JPH04271467A (ja) | 階層的計画生成装置 | |
| JPH02259827A (ja) | レコード編集方式 | |
| JPS59167771A (ja) | 因果関係知識獲得装置 |