JavaScript：如何有效地将数组对象项检索到某个属性？

Question

给定这个数组对象：[{eventTitle=Event title 1, eventId=[e-mail], startDate=Sun Mar 18 00:00:00 GMT+01:00 2018, endDate=Mon Mar 19 00:00:00 GMT+01:00 2018}, {eventTitle=Event title 2, eventId=[e-mail], startDate=Tue Mar 19 00:00:00 GMT+01:00 2019, endDate=Wed Mar 20 00:00:00 GMT+01:00 2019}, {eventTitle=Event title 3, eventId=[e-mail], startDate=Fri Mar 20 00:00:00 GMT+01:00 2020, endDate=Sat Mar 21 00:00:00 GMT+01:00 2020}, . . .]如何在不循环/搜索数组的情况下有效地检索与startDate某个特定的对应？eventTitle例如，我有Event title 2并且想要得到Tue Mar 19 00:00:00 GMT+01:00 2019.编辑：数组对象按 排序startDate。

Answer 1

您可以对数组应用二进制搜索。前提是您的数组已排序。->O(log(n))

[obj1,obj2,obj3....obj100]

测试中间的对象(obj50)，然后决定是否必须在一半[obj1...obj49]或一半中进行搜索，[obj51...obj100]

否则您可以将对象（事件）传递到其他数据结构中，例如树。->O(log(n)) 只是循环遍历整个数组不会有效率，但如果你不重复它太多也可以。但是从一开始就对数组进行排序将是最好的解决方案。

编辑：以下代码显示了二进制搜索实现的基本示例。

const events = [{

    eventTitle: "Event title 1",

    eventId: "[e-mail]",

    startDate: "Sun Mar 18 00:00:00 GMT+01:00 2018",

    endDate: "Mon Mar 19 00:00:00 GMT+01:00 2018"

  },

  {

    eventTitle: "Event title 2",

    eventId: "[e-mail]",

    startDate: "Tue Mar 19 00:00:00 GMT+01:00 2019",

    endDate: "Wed Mar 20 00:00:00 GMT+01:00 2019"

  },

  {

    eventTitle: "Event title 3",

    eventId: "[e-mail]",

    startDate: "Fri Mar 20 00:00:00 GMT+01:00 2020",

    endDate: "Sat Mar 21 00:00:00 GMT+01:00 2020"

  },

  {

    eventTitle: "Event title 4",

    eventId: "[e-mail]",

    startDate: "Fri Mar 21 00:00:00 GMT+01:00 2021",

    endDate: "Sat Mar 22 00:00:00 GMT+01:00 2021"

  },

  {

    eventTitle: "Event title 5",

    eventId: "[e-mail]",

    startDate: "Fri Mar 22 00:00:00 GMT+01:00 2022",

    endDate: "Sat Mar 23 00:00:00 GMT+01:00 2022"

  }

];

function binarySearch(array, value, borderLeft, borderRight) {

  if (borderLeft <= borderRight) {

    var index = Math.floor((borderLeft + borderRight) / 2);

    var number = getNumberFromTitle(array[index].eventTitle);

    if (number == value) {

      return array[index].startDate;

    } else if (number > value) {

      return binarySearch(array, value, borderLeft, index - 1);

    } else {

      return binarySearch(array, value, index + 1, borderRight);

    }

  } else {

    return null;

  }

}

function getNumberFromTitle(title) {

  var tmp = title.split(" ");

  return tmp[tmp.length - 1];

}

console.log(binarySearch(events, 4, 0, events.length - 1));

Answer 2

您可以创建映射器实用程序。首先，它会循环一次，O(n). 以后所有的电话都会O(1)

我有工作代码：

https://gist.github.com/deepakshrma/4b6a0a31b4582d6418ec4f76b7439781

function Mapper(array , key){

    this.map = array.reduce(function(map, item){

        var val = item[key];

        if(!map[val]){

            map[val] = [];

        }

        map[val].push(item);

        return map;

    },{});

}

Mapper.FIRST_INDEX = 0;

Mapper.prototype.find = function find(key){

    return this.map[key] && this.map[key][Mapper.FIRST_INDEX]//return blank array

};

Mapper.prototype.findAll = function find(key, returnUndefined){

    return this.map[key] && this.map[key] || (returnUndefined? undefined: []);//return blank array

};

var users = [{eventTitle:"Event title 1", eventId:"[e-mail]", startDate:"Sun Mar 18 00:00:00 GMT+01:00 2018", endDate:"Mon Mar 19 00:00:00 GMT+01:00 2018"},

 {eventTitle:"Event title 2", eventId:"[e-mail]", startDate:"Tue Mar 19 00:00:00 GMT+01:00 2019", endDate:"Wed Mar 20 00:00:00 GMT+01:00 2019"},

 {eventTitle:"Event title 3", eventId:"[e-mail]", startDate:"Fri Mar 20 00:00:00 GMT+01:00 2020", endDate:"Sat Mar 21 00:00:00 GMT+01:00 2020"}];

//How to use

var userMapper = new Mapper(users , 'eventTitle');

console.log(userMapper.find("Event title 2")); 

var userToFind = ["Event title 3", "Event title 2"];

var reqUsers =  userToFind.map(function(name){

    return userMapper.find(name);

});

console.log(reqUsers);

Answer 3

如果你只有数组，你别无选择，只能搜索它。

但是，如果您将不得不多次搜索它，您可以通过它进行一次遍历以生成 Map，以便后续搜索是次线性的（比使用循环搜索数组更快）。你会这样做：

const map = new Map(theArray.map(entry => [entry.eventTitle, entry.startDate]));

然后按标题获取是：

const startDate = map.get("some title");

现场示例：

显示代码片段

（你可以用一个对象而不是一个 Map 来做同样的事情（只要确保创建它，Object.create(null)这样它就没有原型），但 Map 是专门为此设计的。）

---

请注意，此示例假定每个标题只有一个事件。如果可能有多个，您需要以不同的方式构建地图，以便将您指向该标题的唯一条目数组。