JavaScript 中的元组集合？

Question

在 JavaScript 中实现坐标

Set

的最佳方法是什么？我希望能够做这样的事情：

let s=new Set();
s.add([1,1]);
if (s.has([1,1])) // false, since these are different arrays

上面的方法不起作用，因为

Set

存储的是对数组的引用而不是内容。

Answer 1

您可以子类化

Set

以获得更大的灵活性。

class ObjectSet extends Set{
  add(elem){
    return super.add(typeof elem === 'object' ? JSON.stringify(elem) : elem);
  }
  has(elem){
    return super.has(typeof elem === 'object' ? JSON.stringify(elem) : elem);
  }
}
let s=new ObjectSet();
s.add([1,1]);
console.log(s.has([1,1]))
console.log(s.has([1,2,3]));
console.log([...s]);
console.log([...s].map(JSON.parse));//get objects back

Answer 2

如果您只打算存储坐标对，另一种可能性是使用 Map（对于第一个坐标）和 Set（对于第二个坐标）的组合。

function TupleSet() {
    this.data = new Map();

    this.add = function([first, second]) {
        if (!this.data.has(first)) {
            this.data.set(first, new Set());
        }

        this.data.get(first).add(second);
        return this;
    };

    this.has = function([first, second]) {
        return (
            this.data.has(first) &&
            this.data.get(first).has(second)
        );
    };

    this.delete = function([first, second]) {
        if (!this.data.has(first) ||
            !this.data.get(first).has(second)
        ) return false;

        this.data.get(first).delete(second);
        if (this.data.get(first).size === 0) {
            this.data.delete(first);
        }

        return true;
    };
}

let mySet = new TupleSet();
mySet.add([0,2]);
mySet.add([1,2]);
mySet.add([0,3]);
console.log(mySet.has([1,3]));
console.log(mySet.has([0,2]));
mySet.delete([0,2]);
console.log(mySet.has([0,2]));

不幸的是，与普通套装不同：

您可以按插入顺序迭代集合的元素。 — MDN 集

对于上面的示例，此方法将按以下顺序迭代：

[0,2]
[0,3]
[1,2]

Answer 3

当我遇到这个问题时，我正在构建一个游戏。

这里有一个打字稿课程可能会对您有所帮助。它利用一棵树来发挥它的魔力。

您应该能够轻松修改它以使用数组而不是

x

和

y

参数

// uses an internal tree structure to simulate set-like behaviour
export default class CoordinateSet {
  tree: Record<number, Record<number, boolean>> = {}

  add(x: number, y: number) {
    this.tree[x] ||= {}
    this.tree[x][y] = true;
  }

  remove(x: number, y: number) {
    // if the coordinate doesn't exist, don't do anything
    if (!this.tree[x] || !this.tree[y]) {
      return;
    }

    // otherwise, delete it
    delete this.tree[x][y];

    // if the branch has no leaves, delete the branch, too
    if (!Object.keys(this.tree[x]).length) {
      delete this.tree[x]
    }
  }

  has(x: number, y: number) {
    return !!this.tree[x]?.[y];
  }
}

还有测试，这也会向您展示它是如何工作的：

import CoordinateSet from "./CoordinateSet";

describe("CoordinateSet", () => {
  it("Can add a coordinate", () => {
    const cs = new CoordinateSet();
    expect(cs.has(1,1)).toBeFalsy();
    cs.add(1, 1);
    expect(cs.has(1,1)).toBeTruthy();
  });

  it("Can remove a coordinate", () => {
    const cs = new CoordinateSet();
    cs.add(1, 1);
    expect(cs.has(1,1)).toBeTruthy();
    cs.remove(1,1);
    expect(cs.has(1,1)).toBeFalsy();
  })
})

Answer 4

这可以用字符串来完成：

let s=new Set();
s.add("1,1");
s.add("2,2");
console.log(s.has("1,1"), s.has("1,2")); // true false

但是，我更愿意使用某种类型的数字元组来执行此操作，以避免重复的字符串转换逻辑。

Answer 5

如果我们可以假设我们的元组是有限整数，那么它们可以被编码为浮点数。

class TupleSet extends Set{
    add(elem){
      return super.add((typeof elem === 'object' 
                        && Number.isSafeInteger(elem[0]) 
                        && Number.isSafeInteger(elem[1])) 
                        ? elem[0]+elem[1]/10000000 : elem);
    }
    has(elem){
      return super.has((typeof elem === 'object'
                        && Number.isSafeInteger(elem[0]) 
                        && Number.isSafeInteger(elem[1])) 
                        ? elem[0]+elem[1]/10000000 : elem);
    }
  }
  function TupleSetParse(elem){
     return (Number.isFinite(elem)?
        [Math.round(elem),Math.round((elem-Math.round(elem))*10000000)]:elem);
  }
  
  let s=new TupleSet();
  s.add([1,5]);
  s.add([1000000,1000000]);
  s.add([-1000000,-1000000]);
  console.log(s.has([1,5]));  // true
  console.log(s.has([1,2]));  // false
  console.log([...s].map(TupleSetParse));  
    // [ [ 1, 5 ], [ 1000000, 1000000 ], [ -1000000, -1000000 ] ]

当然，这是有限范围的。而且它对于某些格式错误的输入很脆弱，因此应该添加额外的错误检查。然而，经过一些测试，这种方法在速度和内存使用方面只比 JSON.stringify 方法好 25%。因此，JSON 是首选方法。

Answer 6

您可以使用

keyalesce

（它为相同的值序列返回相同的键）来解决此问题。

const set = new Set()
set.add(keyalesce([1, 1]))

console.log(set.has(keyalesce([1, 1])))
//=> true

请参阅这篇文章了解

keyalesce

内部如何工作。