자바스크립트 데이터 구조 및 알고리즘 모음(세트)

설정

집합 얘기가 나와서 말인데, 제가 처음 고등학교에 입학했을 때 첫 번째 수학 수업이 집합에 관한 내용이었던 것으로 기억합니다. 그래서 컬렉션의 데이터 구조를 학습할 때 더욱 친근하게 느껴집니다.
집합의 기본 속성 중 하나는 집합의 요소가 반복되지 않는다는 것입니다. 이 속성 때문에 우리는 배열 대신 개체를 컬렉션 컨테이너로 선택했습니다.
배열은 모든 비반복을 달성할 수도 있지만 궁극적으로 너무 번거롭고 컬렉션만큼 좋지 않습니다.

수거작업

집합의 기본 연산에는 교집합, 합집합, 차이 등이 있습니다. 여기에서는 JavaScipt 컬렉션의 교집합, 합집합 및 차이 구현을 소개합니다.

JavaScipt에서 컬렉션 구현

먼저 생성자를 만듭니다.

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

로그인 후 복사

컬렉션에는 다음 메서드가 있어야 합니다.

has(value): 컬렉션에 요소가 있는지 확인
add(value): 컬렉션에 요소를 추가합니다
remove(value): 컬렉션에서 요소를 제거합니다
clear(value): 컬렉션을 지웁니다
size(): 컬렉션의 길이를 반환합니다
values(): 집합에서 변환된 배열을 반환합니다
union(otherSet): 두 세트의 합집합을 반환합니다
intersection(otherSet): 두 세트의 교집합을 반환합니다
difference(otherSet): 두 집합의 차이를 반환합니다
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 = {};
};

로그인 후 복사

사이즈 방법

설명: 컬렉션의 길이를 반환합니다. 여기에는 두 가지 방법이 있습니다. 첫 번째 방법은 Object.keys API를 사용하지만 IE9 이상만 지원합니다. 두 번째는 모든 브라우저에서 작동합니다.
구현:

/**
 * 返回集合长度，只可用于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;
}

로그인 후 복사

가치방식

설명: 집합 변환의 배열을 반환합니다. 여기에는 두 가지 방법이 있습니다. 이유는 위와 동일합니다. 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;
};

로그인 후 복사

결합방식

설명: 두 세트의 합집합을 반환합니다
구현:

/**
 * 返回两个集合的并集
 * @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;
};

로그인 후 복사

교차방식

설명: 두 집합의 교집합을 반환합니다
구현:

/**
 * 返回两个集合的交集
 * @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;
};

로그인 후 복사

차이방법

설명: 두 세트의 차이를 반환합니다
구현:

/**
 * 返回两个集合的差集
 * @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;
};

로그인 후 복사

부분 집합 방법

설명: 세트가 수신 세트의 하위 세트인지 확인합니다. 이 코드를 다 작성한 후 책에 나온 코드와 비교해보니 굉장히 낮다는 느낌이 들었습니다. 내가 작성한 것은 배열을 세 번 순회해야 하는 반면 책에 있는 것은 한 번만 필요하며 알고리즘 복잡성은 내 것보다 훨씬 낮습니다.
구현:

/**
 * 判断该集合是否为传入集合的子集
 * @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대 킹콩으로 간주되므로 데이터 구조 및 알고리즘에 관한 최근 기사 시리즈는 매우 느리게 업데이트될 수 있습니다. 나에게도 그것은 장애물이다. 이번 겨울방학에는 이 난관을 극복할 수 있었으면 좋겠습니다.