et - 06

この文章は『JavaScriptデータ構造とアルゴリズムを学ぶ』という本の内容をまとめた.
間違いや修正が必要な内容があれば、お知らせください.
5章まで,順序(順序)資料構造:配列,スタック,キュー,接続リストを学習した.第6章のテーマは集合資料構造です.集合よりSet

Setはソートされていない集合であり,重複する要素はない.

これは数学の本の中の有限集合(finite set)の概念をコンピュータ科学に応用することである.

セットの実装

では、SetクラスはECMAScript 6リストに基づいています.

function Set() {
   var items = {}; 
}  

重要なのは「配列ではなくオブジェクトで集合(要素)を表す」ことです.

JS内のオブジェクトは同じキーで複数のプロセスを持つことができないため,集合内の要素は繰り返されない.

次に、Setクラスで実装する方法を示します.(ECMASIPt 6Setクラスの真似.)

add(item):要素の追加

remove(item):要素の削除

has(item):要素が含まれているかどうかを確認

clear():すべての要素を削除

size():戻り要素数

showValues():Setのすべての要素が配列で表示されます.

has(value)

this.has = function (value) {
    return value in items;
    // return items.hasOwnProperty(value)
    // 이 방법이 상속받은 객체의 프로퍼티는 확인하지 않고
    // 대상 객체 고유의 프로퍼티만 확인하므로 더 권장된다.
  };

add(value)

this.add = function (value) {
    // value가 이미 Set에 포함되어 있는 확인 필요
    if (!this.has(value)) {
      items[value] = value; // 키와 값을 동일하게 저장하는 이유는 나중에 편하라고. 딱히 이유는 없다.
      return true;
    }
    return false;
  };

remove(value), clear()

remove

 this.remove = function (value) {
    if (this.has(value)) {
      delete items[value];
      return true;
    }
    return false;
  };

clear

this.clear = function () {
    items = {};
  };

空のオブジェクトを割り当てて初期化します.loopを回して消すよりはましだ.

size()

  // 첫 번째 방법
   this.size = function () {
    return Object.keys(items).length;
  };

  // 두 번째 방법
   this.size = function () {
    let count = 0;
    for (let prop in items) {
      if (items.hasOwnProperty(prop)) ++count;
    }
    return count;
  };

values(), showValues()

values

this.values = function () {
    return Object.values(items);
  };

showValues

// 화면에 현재 Set의 상태를 보여주기 위한 용도
this.showValues = function () {
    return console.log(Object.values(items));
  };

Setクラスの使用

const set = new Set();
set.add(1);
set.showValues(); // ["1"]
console.log(set.has(1)); // true
console.log(set.size()); // 1

set.add(2);
set.showValues(); // ["1", "2"]
console.log(set.has(2)); // true
console.log(set.size()); // 2

set.remove(1);
set.showValues(); // ["2"]

set.remove(2);
set.showValues(); // []

しゅうごうえんざん

コレクションで使用できる演算は4種類あります.

パラレル/交差/セカンダリ/ローカルセット

しゅうごう

Setクラス内の構成unionメソッド(並列):

  this.union = function (otherSet) {
    const unionSet = new Set();
    var values = this.values();

    for (let i = 0; i < values.length; i++) unionSet.add(values[i]);

    var values = otherSet.values();
    for (let i = 0; i < values.length; i++) unionSet.add(values[i]);

    return unionSet;
  };


const set = new Set();
set.add(1);
set.add(2);
set.add(3);

const set2 = new Set();
set.add(3);
set.add(4);
set.add(5);
set.add(6);

let unionAB = set.union(set2);
console.log(unionAB.values()); // 1,2,3,4,5,6

交差

交差の説明は省略する.

  this.intersection = function (otherSet) {
    let intersectionSet = new Set();
    var values = this.values();

    for (let i = 0; i < values.length; i++) {
      // 두 집합에 서로 겹치는 원소가 있는지 찾아준다.
      if (otherSet.has(values[i])) intersectionSet.add(values[i]);
    }

    return intersectionSet;
  };

ダイバーシティ

ex)A,Bの2つの集合は、Aに属するがBに属さない要素xの集合を表す.

  // difference
  this.difference = function (otherSet) {
    const differenceSet = new Set();

    let values = this.values();
    for (let i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) differenceSet.add(values[i]);
    }
    return differenceSet;
  };

ぶぶんしゅうごう

ex)は、要素Aのすべての要素がBに存在しなければならないことを示す.

this.subset = function (otherSet) {
    if (this.size() > otherSet.size()) return false;
    else {
      let values = this.values();
      for (let i = 0; i < values.length; i++) {
        if (!otherSet.has(values[i])) return false;
      }
      return true;
    }
  };