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

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(？(我不想自己实现数据结构(

Answer 1

您可以使用按名称键控的 Map，其中相应的值是一组指令：

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!");
}

Answer 2

假设：数组a按字典顺序排序，即 a[i]<a[j]无论何时a[i].name<a[j].name || (a[i].name==a[j].name && a[i].description<a[j].description))

这是一个具有对数复杂性的二叉搜索：

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");

Answer 3

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

假设我们的尺寸是脚手架式的：name -> directive -> third_property

首先根据数组name对数组进行排序。现在log n找到每个name部分，并根据directive仅对该部分进行快速排序，同样适用于third_property。然后要查找元素，请使用类似的二叉搜索，首先查找 name 属性的范围，然后在该范围内对directive使用二叉搜索，依此类推。

或者简单地绕过所有这些，为每个元素创建一个键，我们可以对其进行排序并对其进行二分搜索：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;)