Javascript 和集合

Question

假设您在 javascript/NodeJs 中有 3 个列表/数组

1. 数组包含 1.000.000 个数据项
2. 数组包含 100.000 个数据项
3. 数组包含 50.000 个数据项

每个数据项都是一个具有 2 个属性的对象 - 比如日期和价格。 数组 2 和 3 中的所有项目都是数组 1 中项目的子集/子列表。

我的问题:我如何以最快的方式匹配数组 1 中每个项目的所有日期 - 与数组 2 和 3 中的所有日期 - 对于数组 1 中的每个单个项目？

我习惯了 .NET/C# - 像“包含(项目)”这样的东西很好......现在在 NodeJS 中我使用 3 个 for 循环 - 这是减慢速度的方式......我需要某种索引或类似的加速过程...

数据示例如下:

输入:

array 1: 1,2,3,4,5,6,7,8,10
array 2: 2,3,5,7,9
array 3: 1,4,5,10

输出(写入文件):

1,'',1
2,2,''
3,3,''
4,'',4
..ect...

Answer 1

var t = {}
// loop through once and create a constant time lookup
arr1.forEach(function(item){t[item.date] = {1: item.price, 2: null, 3:null})
arr2.forEach(function(item){if (t[item.date]) t[item.date].2 = item.price})
arr3.forEach(function(item){if (t[item.date]) t[item.date].3 = item.price})

这将是一个线性操作，首先对数据进行排序的权衡可能值得也可能不值得花时间进行排序。

无论哪种方式，它都与三重连接大致相同，我提供的解决方案是 O(N)，其中嵌套循环可能是 O(N^3)，排序的解决方案仍然可能是 O(Nlog(N )) 只是一个猜测。

如果日期已经排序，您可以将日期分桶或进行某种基数搜索，这可能会加快速度。

参见:https://en.m.wikipedia.org/wiki/Radix_tree

您也可以使用 promises 来做到这一点，因此它会异步运行:

var t = {}
// loop through once and create a constant time lookup
arr1.forEach(function(item){t[item.date] = {1: item.price, 2: null, 3:null})

var promiseArray = arr2.map(function(item){
    return Promise.resolve(item)
        .then(function(item){
              if (t[item.date]) t[item.date].2 = item.price})
         })
// concat the two promise arrays together 
promiseArray.concat(arr3.map(function(item){
    return Promise.resolve(item)
        .then(function(item){
              if (t[item.date]) t[item.date].3 = item.price})
         }))
// resolve all the promises
Promise.all(promiseArray)
    .then(function(){
        // t has results
        debugger
    })