JavaScriptのデータ構造とアルゴリズム集（セット）

JavaScriptのデータ構造とアルゴリズム集（セット）_基礎知識

WBOY

リリース： 2016-05-16 15:16:51

オリジナル

1396 人が閲覧しました

設定

集合と言えば、私が高校に入学したとき、数学の最初の授業が集合についてだったことを思い出します。したがって、コレクションのデータ構造を学ぶときは、より親密に感じられます。
セットには基本的なプロパティが 1 つあります。それは、セット内の要素が繰り返されないということです。この特性のため、コレクションコンテナーとして配列ではなくオブジェクトを選択しました。
配列でもすべての非反復を実現できますが、最終的には非常に煩雑で、コレクションほど優れたものではありません。

収集操作

集合の基本演算には、交差、和集合、差分などが含まれます。ここでは、JavaScipt コレクションにおける交差、共用、および差分の実装を紹介します。

JavaScipt でのコレクションの実装

まず、コンストラクターを作成します。

/**
 * 集合的构造函数
 */
function Set方法 {
 /**
  * 集合元素的容器，以对象来表示
  * @type {Object}
  */
 var items = {};
}

ログイン後にコピー

コレクションには次のメソッドが必要です:

has(value): セット内に要素があるかどうかを確認します
add(value): コレクションに要素を追加します
remove(value): コレクションから要素を削除します
clear(value): コレクションをクリアします
size(): コレクションの長さを返します
values(): set
union(otherSet): 2 つのセットの和集合を返します
intersection(otherSet): 2 つのセットの共通部分を返します
difference(otherSet): 2 つのセットの差を返します
subset(otherSet): セットが受信セットのサブセットであるかどうかを判断します

にはメソッドがあります:

注: セット内の要素は繰り返されません。したがって、他の操作の前に、 has メソッドを使用して、コレクションに特定の要素があるかどうかを確認する必要があります。ここでは hasOwnProperty メソッドを使用して検出します。
実装:

/**
 * 检测集合内是否有某个元素
 * @param {Any} value  要检测的元素
 * @return {Boolean}    如果有，返回true
 */
this.has = function(value) {
 // hasOwnProperty的问题在于
 // 它是一个方法，所以可能会被覆写
 return items.hasOwnProperty(value)
};

ログイン後にコピー

メソッドの追加:

説明: 要素をコレクションに追加します。
実装:

/**
 * 给集合内添加某个元素
 * @param {Any} value 要被添加的元素
 * @return {Boolean}    添加成功返回True。
 */
this.add = function(value) {
 //先检测元素是否存在。
 if (!this.has(value)) {
  items[value] = value;
  return true;
 }
 //如果元素已存在则返回false
 return false;
};

ログイン後にコピー

メソッドの削除:

説明: コレクションから要素を削除します
実装:

/**
 * 移除集合中某个元素
 * @param {Any} value 要移除的元素
 * @return {Boolean}    移除成功返回True。
 */
this.remove = function(value) {
 //先检测元素是否存在。
 if (this.has(value)) {
  delete items[value];
  return true;
 }
 //如果元素不存在，则删除失败返回false
 return false;
};

ログイン後にコピー

クリアメソッド:
説明: コレクションをクリアします
実装:

/**
 * 清空集合
 */
this.clear = function() {
 this.items = {};
};

ログイン後にコピー

サイズメソッド

説明: コレクションの長さを返します。ここには 2 つのメソッドがあります。最初の方法では Object.keys API を使用しますが、IE9 以降のみをサポートします。 2 番目の方法はすべてのブラウザで動作します。
実装:

/**
 * 返回集合长度，只可用于IE9及以上
 * @return {Number} 集合长度
 */
this.size = function() {
 // Object.keys方法能将对象转化为数组
 // 只可用于IE9及以上，但很方便
 return Object.keys(items).length;
}

/**
 * 返回集合长度，可用于所有浏览器
 * @return {Number} 集合长度
 */
this.sizeLegacy = function() {
 var count = 0;
 for (var prop in items) {
  if (items.hasOwnProperty(prop)) {
   ++count;
  }
 }
 return count;
}

ログイン後にコピー

値メソッド

説明: 集合変換の配列を返します。ここには 2 つのメソッドがあります。理由は上記と同じです。 Object.keys が使用され、IE9 以降のみをサポートできます。
実装:

/**
 * 返回集合转换的数组，只可用于IE9及以上
 * @return {Array} 转换后的数组
 */
this.values = function() {
 return Object.keys(items);
};

/**
 * 返回集合转换的数组，可用于所有浏览器
 * @return {Array} 转换后的数组
 */
this.valuesLegacy = function() {
 var keys = [];
 for (var key in items) {
  keys.push(key)
 };
 return keys;
};

ログイン後にコピー

ユニオンメソッド

説明: 2 つのセットの和集合を返します
実装:

/**
 * 返回两个集合的并集
 * @param {Set} otherSet 要进行并集操作的集合
 * @return {Set}     两个集合的并集
 */
this.union = function(otherSet) {
 //初始化一个新集合，用于表示并集。
 var unionSet = new Set();
 //将当前集合转换为数组，并依次添加进unionSet
 var values = this.values();
 for (var i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }

 //将其它集合转换为数组，依次添加进unionSet。
 //循环中的add方法保证了不会有重复元素的出现
 values = otherSet.values();
 for (var i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }

 return unionSet;
};

ログイン後にコピー

交差メソッド

説明: 2 つのセットの共通部分を返します
実装:

/**
 * 返回两个集合的交集
 * @param {Set} otherSet 要进行交集操作的集合
 * @return {Set}     两个集合的交集
 */
this.intersection = function(otherSet) {
 //初始化一个新集合，用于表示交集。
 var interSectionSet = new Set();
 //将当前集合转换为数组
 var values = this.values();
 //遍历数组，如果另外一个集合也有该元素，则interSectionSet加入该元素。
 for (var i = 0; i < values.length; i++) {

  if (otherSet.has(values[i])) {
   interSectionSet.add(values[i])
  }
 }

 return interSectionSet;
};

ログイン後にコピー

差分法

説明: 2 つのセットの差を返します
実装:

/**
 * 返回两个集合的差集
 * @param {Set} otherSet 要进行差集操作的集合
 * @return {Set}     两个集合的差集
 */
this.difference = function(otherSet) {
 //初始化一个新集合，用于表示差集。
 var differenceSet = new Set();
 //将当前集合转换为数组
 var values = this.values();
 //遍历数组，如果另外一个集合没有该元素，则differenceSet加入该元素。
 for (var i = 0; i < values.length; i++) {

  if (!otherSet.has(values[i])) {
   differenceSet.add(values[i])
  }
 }

 return differenceSet;
};

ログイン後にコピー

サブセットメソッド

説明: セットが受信セットのサブセットであるかどうかを判断します。このコードを書き終えた後、本のコードと比較してみたところ、非常に低いと感じました。私が書いたものでは配列を 3 回走査する必要がありますが、この本の場合は 1 回だけ必要で、アルゴリズムの複雑さは私のものよりもはるかに低いです。
実装:

/**
 * 判断该集合是否为传入集合的子集
 * @param {Set} otherSet 传入的集合
 * @return {Boolean}   是则返回True
 */
this.subset = function(otherSet) {
 // 第一个判定,如果该集合长度大于otherSet的长度
 // 则直接返回false
 if (this.size() > otherSet.size()) {
  return false;
 } else {
  // 将当前集合转换为数组
  var values = this.values();

  for (var i = 0; i < values.length; i++) {

   if (!otherSet.has(values[i])) {
    // 第二个判定。只要有一个元素不在otherSet中
    // 那么则可以直接判定不是子集，返回false
    return false;
   }
  }

  return true;
 }
};

ログイン後にコピー

ES6 のコレクション

ES6 もコレクションを提供しますが、以前は ES6 のコレクション操作にいつも混乱していました。実際に実装して改めて見てみると、コンセプトがより明確になったように感じました。
詳細についてはまだ学習中なので、書き留めることはしません。Ruan Yifeng 先生の「ECMAScript 6 の概要」にある ES6 セットの概要を読むことをお勧めします。
「ECMAScript 6 の概要」 – データ構造の設定とマップ

感想

この時点で、いくつかの基本的なデータ構造をマスターしました。残りは（私にとって）割るのが難しいナットです。

辞書のハッシュテーブル、グラフ、ツリー、並べ替えアルゴリズム。これは 4 人のキングコングと考えられているため、データ構造とアルゴリズムに関する最近の一連の記事の更新が非常に遅くなる可能性があります。私にとって、それはハードルでもあります。この冬休みにはこのハードルを乗り越えられるといいですね。