如何在对数时间内检查容器中是否存在相等值的对象

Question

我想要在对数时间内查看容器中是否有一个具有相等值的对象。

我想要以下功能：

const a = [];

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};
const b = {name: 'name1', directive: 'directive1'};

a.push(el1);
a.push(el2);
a.push(el3);


if(a.some(el => (el.name === b.name && el.directive === b.directive ))) {
  console.log("YES!");
} else {
  console.log("NO!");
}

这让我得到了想要的结果。但是，这是O（N）时间复杂度。

const s = new Set();

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};
const b = {name: 'name1', directive: 'directive1'};

s.add(el1);
s.add(el2);
s.add(el3);

if(s.has(b)) {
  console.log("YES!");
} else {
  console.log("NO!");
}

这是O(logN)的时间复杂度，但结果并不符合我的要求。

那么，我可以使用哪种JavaScript数据结构来打印出在上述代码中打印“YES”，并具有O(logN)的复杂度？（我不想自己实现一个数据结构）

- bsky

---

如果您的数据已经排序并且进行了二分查找，那么怎么样呢？ - JasonB

您的需求是可以实现的，但是要提供最佳方法需要更多关于您允许的对象类型的信息。它们是否总是只包含具有字符串值的普通对象的浅层数组？ - Patrick Roberts

返回 false，因为它们（el1 和 b）是不同的对象引用。你可以通过 el1 填充 b。 - Ramin Bateni

@octavian 它能正常工作是因为 b.name === undefined，但如果你那样写它可能会记录 NO!。 - Patrick Roberts

你是想解决这个特定的 [{name, directive}] 情况还是更一般的情况？ - Scott Sauyet

Answer 1

您可以使用以名称为键的Map，相应的值是指令的Set集合：

const elements = [
    {name: 'name1', directive: 'directive1'},
    {name: 'name2', directive: 'directive2'},
    {name: 'name3', directive: 'directive3'}
];

const map = new Map(elements.map(({name}) => [name, new Set]));
elements.forEach(({name, directive}) => map.get(name).add(directive));

const b = {name: 'name1', directive: 'directive1'};

if (map.has(b.name) && map.get(b.name).has(b.directive)) {
    console.log("YES!");
} else {
    console.log("NO!");
}

- trincot

Answer 2

假设数组a按字典序排序，即当a[i].name<a[j].name || (a[i].name==a[j].name && a[i].description<a[j].description)时a[i]<a[j]。

这是一个具有对数复杂度的二分查找算法：

const a = [];
for (i = 0; i < 100000; i++) {
  si = String(i);
  el = {
    name: 'name' + si,
    directive: 'directive' + si
  };
  a.push(el);
}

const b = {
  name: 'name70000',
  directive: 'directive70000'
};


var c = 0; // counter 

// binary search
function binary_search(a, b) {
  c++;
  var l = 0;
  var r = a.length - 1;
  if (l > r) {
    return false;
  }
  m = Math.floor((l + r) / 2);
  if ((a[m].name < b.name) || (a[m].name == b.name && a[m].directive < b.directive)) {
    return binary_search(a.slice(m + 1), b);
  } else if ((a[m].name > b.name) || (a[m].name == b.name && a[m].directive > b.directive)) {
    return binary_search(a.slice(0, m), b);
  } else {
    return true;
  }
}



found = binary_search(a, b);
console.log(found, "in " + String(c) + " steps");

- user2314737

---

最优的性能并不一定是对数时间呀，是吧？ - JasonB

一般来说不行，但如果数组已经排序，你可以使用二分查找以达到对数复杂度。 - user2314737

Answer 3

我们可以使用Array作为数据结构。考虑到我们可以利用递归对数时间函数来排序（或查找插入/删除位置）多个维度，通过确定父字段部分的端点并进行递归。

假设我们的维度是搭建的：名称 -> 指令 -> 第三属性

首先按照名称对数组进行排序。现在在log n时间内找到每个名称部分，并根据指令快速排序该部分，类似地处理第三属性。然后要查找一个元素，使用类似的二分搜索，首先找到名称属性的范围，然后在该范围内使用二分搜索查找指令等。

或者简单地通过为每个元素创建一个可以排序和二分搜索的键来绕过所有这些： element.key = element.name + element.directive :)

- גלעד ברקן

Answer 4

不要看这个答案的负分，使用它并享受它。它简单易用，在O(logN)时间复杂度下运行良好。

---

它返回false，因为它们（el1和b）是不同的对象引用。你可以通过el1填充b，但如果你想要一个简单的方法来使用O(logN)搜索，你可以使用我以下的代码：

var orderObj = function(unordered){
   const ordered = {};
   Object.keys(unordered).sort().forEach(function(key) {
       ordered[key] = unordered[key];
    });
    return ordered;
}
Set.prototype.addIt = function(item){s.add(JSON.stringify(orderObj(item)));}
Set.prototype.hasIt = function(item){return s.has(JSON.stringify(orderObj(item)));}
    
//-------------------------------------

const s = new Set();

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};

const b = {name: 'name1', directive: 'directive1'};
const c = {directive: 'directive3', name: 'name3'};

s.addIt(el1);
s.addIt(el2);
s.addIt(el3);

s.hasIt(b)
 ?console.log("YES!")
 :console.log("NO!");

s.hasIt(c)
 ?console.log("YES!")
 :console.log("NO!");

---

更新:

我更新了我的回答，现在它支持不同顺序的对象。正如您可以在上面的示例中看到的那样，c 与 el3 的顺序不同，但脚本返回了 Yes 的结果 ;)

- Ramin Bateni

---

我认为OP已经意识到了这一点，但需要在b是具有相同属性值的不同对象时使其工作。 - trincot

关于您基于JSON的更新解决方案：请注意，对象属性可能以不同的字符串顺序出现，但从语义上讲，属性顺序对JavaScript对象并不重要，因此即使在这种情况下，它们也应被视为匹配。 - trincot

@trincot 我不认为这是一个好的解决方案，但我们能否在插入和查询之前对JSON字符串进行排序？ - גלעד ברקן