단일 감소를 사용한 트리 생성

지난 몇 달 동안 우리는 , 및 와 함께 살펴보았습니다. 오늘은 지금까지 다룬 내용 중 일부를 포함하는 뉴욕 시러큐스 JavaScript 모임의 문제를 살펴보겠습니다.

다음과 같은 속성을 가진 Guess Who 캐릭터 목록이 있다고 가정해 보겠습니다.

[
  {
    "name": "Alex",
    "hairColor": "Black",
    "wearingHat": false,
    "wearingGlasses": false
  },
  ...
]

그리고 우리는 그것들을 다음과 같은 의사 결정 트리로 구성하려고 합니다.

{
  "hairColor: Black": {
    "wearingGlasses: true": {
      "wearingHat: true": [],
      "wearingHat: false": []
    },
    "wearingGlasses: false": {
      "wearingHat: true": [],
      "wearingHat: false": []
    }
  },
  ...
}

이 문제를 어떻게 해결하시겠습니까? 서로 중첩된 각 속성을 반복하고 진행하면서 해당 속성 조합과 일치하는 모든 문자를 찾을 수 있습니다. 이것은 작동할 수 있지만 다른 속성을 추가하거나 중첩 순서를 변경하려면 어떻게 해야 합니까?

트리의 중첩 순서를 정의하는 속성 배열이 있다고 가정해 보겠습니다. 속성을 반복하는 대신 문자를 반복하고 각 문자를 트리에서 속한 위치에 배치할 수 있습니다. 트리를 미리 만들고 캐릭터가 속한 분기에 캐릭터를 배치할 수 있지만 대신 진행하면서 분기를 만들 것입니다.

지도를 이용한 경로 생성

먼저 트리에서 해당 위치를 참조할 수 있도록 경로를 생성해야 합니다. 예를 들어 캐릭터 Alex는 머리가 검은색이고 안경이나 모자를 쓰고 있지 않으므로 tree["hairColor: Black"]["wearingGlasses: false"]["wearingHat: false"] 위치의 나무에 배치됩니다. 따라서 문자와 속성 목록이 주어지면 map 메서드를 사용하여 이 경로를 생성할 수 있습니다.

const key = (attribute) => 
  `${attribute}: ${character[attribute]}`;
const path = attributes.map(key);

경로에서 분기 만들기

이제 경로가 있으므로 분기를 만들고 새로 만든 해당 분기에 캐릭터를 배치할 수 있습니다. 이를 달성하기 위해 경로를 통해reduce 진행하면서 내부 개체에 대한 참조를 반환할 수 있습니다. 개체와 배열은 항상 JavaScript에서 참조로 전달됩니다. 경로 끝에 있는 경우 중첩된 개체를 만드는 대신 목록에 항목을 추가합니다. 분기에 전체 경로를 추가한 후 전체 경로를 다시 반환해야 합니다.

const createBranch = (path, item) => {
  const branch = {};
  path.reduce((branch, key, i) => {
    const endOfPath = i == path.length - 1;
    branch[key] = endOfPath ? [item] : {};
    return branch[key];
  }, branch);
  return branch;
};

트리를 깊게 병합

마지막으로, 진행하면서 생성한 모든 가지를 깊이 병합하여 진행하면서 트리를 구축할 수 있습니다. 나는 그것을 정확히 하기 위해 우수한 deepmerge 라이브러리를 사용하고 있습니다. 완전 병합은 두 개체를 가져와 속성이 결합된 새 개체를 반환하는 함수입니다(충돌이 있는 경우 두 번째 개체가 첫 번째 개체를 재정의함). 개체를 빈 개체와 병합하면 시작했던 개체로 끝납니다. 이것은 깊은 병합 객체가 모노이드이며 reduce 와 잘 어울린다는 것을 의미합니다. 모든 것이 실제로 작동하는 것을 봅시다:

const deepmerge = require("deepmerge");

const createBranch = (path, item) => {
  const branch = {};
  path.reduce((branch, key, i) => {
    const endOfPath = i == path.length - 1;
    branch[key] = endOfPath ? [item] : {};
    return branch[key];
  }, branch);
  return branch;
};

const attributes = ["hairColor", "wearingGlasses", "wearingHat"];
const decisionTree = guessWhoCharacters
  .reduce((tree, character) => {
    const key = (attribute) => 
      `${attribute}: ${character[attribute]}`;
    const path = attributes.map(key);
    const branch = createBranch(path, character.name);
    return deepmerge(tree, branch);
  }, {});

그리고 그게 다야! 각 문자를 한 번만 반복합니다. 또한 속성을 추가하거나 트리 중첩 순서를 변경하려는 경우 속성 배열을 업데이트하기만 하면 됩니다. 이 문제에 대한 이전 솔루션은 이미 존재하는 경우 새 분기를 생성하는 것을 피했지만 약간의 복잡성이 추가되었습니다. 이 솔루션의 단순성과 가독성이 마음에 듭니다.

공유하고 싶은 다른 솔루션이 있다면 댓글에 적어주세요! 다음 시간에는 펑터에 대해 더 깊이 파고들겠습니다.