一道算法题，请大佬解答一下

Question

let a = [
  {id:1,all:20}
  {id:2,all:120}
  {id:3,all:220}
  {id:4,all:320}
]

let b = [
  {id:1,bkk:230}
  {id:2,bkk:12320}
  {id:3,bkk:223420}
  {id:4,bkk:323420}
]

let c = [
    {id:1,v:??}
    {id:2,v:??}
    {id:3,v:??}
    {id:4,v:??}
]
v=all/bkk

a,b数组内部有10w条 ,现在怎么生成c数组？用最少的遍历次数

Answer 1

最简单的情况

如果 a 和 b 等长，而且按顺序一一对应，那就是一个循环的事情，非常简单

const c = a.map((it, i) => ({
    id: it.id,
    v: it.all / b[i].bkk
}));

为了做这个测试，我随机生成了各 10 万条数据

function randomGenerate(key, length = 100000) {
    return Array.from(
        Array(length),
        (_, i) => ({
            id: i + 1,
            [key]: Math.floor(Math.random() * 100000)
        }));
}

console.time("generate");
const a = randomGenerate("all");
const b = randomGenerate("bkk");
console.timeEnd("generate");

console.time("calculate");
const c = a.map((it, i) => ({
    id: it.id,
    v: it.all / b[i].bkk
}));
console.timeEnd("calculate");

console.log(c.filter((_, i) => i < 10));

这是其中一次的输出（执行环境 Node.js 15）

generate: 43.985ms
calculate: 19.011ms
[
  { id: 1, v: 0.6844209161624892 },
  { id: 2, v: 0.6300826791163506 },
  { id: 3, v: 1.4403092519180325 },
  { id: 4, v: 0.012814119709264549 },
  { id: 5, v: 0.5078792426691295 },
  { id: 6, v: 1.9799324831207803 },
  { id: 7, v: 12.956561922365989 },
  { id: 8, v: 5.375453499690293 },
  { id: 9, v: 0.3358354918856055 },
  { id: 10, v: 1.195731361061481 }
]

复杂的情况

如果情况复杂一点，就是 a 和 b 虽然有按 ID 一对一的数据，但是顺序可能不同……这种情况，先排个序也可以处理；

这个处理过程简单，代码就不写了

更复杂的情况

或者 a 和 b 压根就没有一对一的数据，中间可能缺那么两个 ID 什么的，但顺序是按 ID 从小到大来的，那可以用一个循环解决

// 这个函数最后加了个 filter，随机去掉一些项（大概 10%）
function randomGenerate(key, length = 100000) {
    return Array
        .from(
            Array(length),
            (_, i) => ({
                id: i + 1,
                [key]: Math.floor(Math.random() * 100000)
            }))
        .filter(() => Math.random() > 0.1);
}

console.time("generate");
const a = randomGenerate("all", 110000);
const b = randomGenerate("bkk", 110000);
console.log(`a.length = ${a.length}, b.length = ${b.length}`);
console.timeEnd("generate");

(() => {
    console.time("calculate");

    // bCurrent 用来记录遍历 b 的当前位置
    const bCurrent = {
        index: 0,
        id: 0,
    }
    const c = [];
    const skips = [];
    
    // 遍历 a
    for (let i = 0; i < a.length; i++) {
        const aIt = a[i];
        
        // 对于下面那层循环中保存的 b 状态，进行查找，
        // 直到 aIt.id 与之相等或大于
        // 相等时会在下层循环中马上匹配到，存入 c
        if (aIt.id < bCurrent.id) {
            skips.push(`a: ${aIt.id}`)  // DEBUG 记录跳过的 ID
            continue;
        }

        // 对于 aIt.id，遍历 b 去寻找
        for (let j = bCurrent.index; j < b.length; j++) {
            const bIt = b[j];
            // bIt.id < aIt.id 说明要找的数据还在后面
            if (bIt.id < aIt.id) {
                skips.push(`b: ${bIt.id}`); // DEBUG 记录跳过的 ID
                continue;
            }
            // bIt.id > aIt.id 说明找不到（b 中缺失）
            // 这时候把当前状态（index 和 id）记录下来，需要在 a 中去匹配
            if (bIt.id > aIt.id) {
                bCurrent.index = j;
                bCurrent.id = bIt.id;
                break;
            }

            // 剩下是相等的情况
            c.push({
                id: aIt.id,
                v: aIt.all / bIt.bkk,
            });
        }
    }

    console.timeEnd("calculate");

    console.log(c.filter((_, i) => i < 20));
    console.log(skips.filter((_, i) => i < 10));
})();

因为是有序的，所以这个思路是按顺序在两个列表中找，谁大谁等。某次执行的输出（根据 skips 的输出可以看到 id 是补齐了的）

a.length = 98974, b.length = 98971
generate: 70.063ms
calculate: 31.054ms
[
  { id: 1, v: 0.5490888935079332 },
  { id: 4, v: 4.810793199455008 },
  { id: 5, v: 2.3331157076297595 },
  { id: 6, v: 0.6420172750069657 },
  { id: 7, v: 0.8823165378581811 },
  { id: 8, v: 1.0010915217236551 },
  { id: 9, v: 0.076162900484673 },
  { id: 10, v: 1.1235221165770979 },
  { id: 11, v: 3.844020145831767 },
  { id: 12, v: 0.1030885938769981 },
  { id: 13, v: 2.370326643053916 },
  { id: 14, v: 0.5597336817425232 },
  { id: 15, v: 0.826716104475653 },
  { id: 16, v: 0.8489707285509043 },
  { id: 17, v: 2.7180432645034416 },
  { id: 20, v: 0.344454164278604 },
  { id: 21, v: 3.2986106163163518 },
  { id: 22, v: 0.9003790812375169 },
  { id: 24, v: 0.9454501762255687 },
  { id: 25, v: 0.29758954337124427 }
]
[
  'b: 2',  'b: 3',
  'a: 18', 'b: 19',
  'a: 23', 'a: 32',
  'a: 33', 'a: 38',
  'a: 40', 'a: 41'
]

再复杂一点的情况

还没完，上面都有假设条件。现在再复杂一点，两个列表中的数据无序，不保证一一对应，该怎么办？

我为以 a 的数据作为参照，从 b 中去查，查到了就算结果出来放到 c 中去，没查到就放弃。那么要查 b，可以遍历，也可以先从 b 生成一个查找表 bMap，下面这段代码是用的查找表的办法

// 为了数据的随机顺序，使用了 lodash.shuffle 来“洗牌”
// 所以数据干脆都用 lodash 来处理
import _ from "lodash";

function randomGenerate(key, length = 100000) {
    return _(_.range(1, length))
        .filter(() => Math.random() > 0.3)
        .shuffle()
        .map(id => ({ id, [key]: _.random(100000) }))
        .value();
}

console.time("generate");
const a = randomGenerate("all", 150000);
const b = randomGenerate("bkk", 150000);
console.log(`a.length = ${a.length}, b.length = ${b.length}`);
console.timeEnd("generate");

(() => {
    console.time("calculate");

    const bMap = _.keyBy(b, "id");
    const c = a
        .map(({ id, all }) => ({
            id,
            v: all / bMap[id]?.bkk
        }))
        .filter(({ v }) => !isNaN(v));

    console.timeEnd("calculate");

    console.log(c.filter((_, i) => i < 20));
})();

执行结果，还好，速度很快

a.length = 105153, b.length = 105458
generate: 88.969ms
calculate: 28.017ms
[
  { id: 56540, v: 1.1590646524619412 },
  { id: 90784, v: 0.14467661691542288 },
  { id: 117310, v: 1.5486083984375 },
  { id: 133827, v: 0.6328737395468916 },
  { id: 90030, v: 0.9684467443470506 },
  { id: 14958, v: 0.0717709318888346 },
  { id: 94929, v: 2.6633107067480464 },
  { id: 99086, v: 0.7730212503849707 },
  { id: 46776, v: 1.7670233463035019 },
  { id: 112654, v: 0.792237767765394 },
  { id: 83424, v: 0.38164696942970733 },
  { id: 48665, v: 0.3065920993258857 },
  { id: 111322, v: 105.21703617269544 },
  { id: 130179, v: 1.560958509652703 },
  { id: 69975, v: 1.490247295647483 },
  { id: 118965, v: 0.6617197235753937 },
  { id: 123057, v: 0.6079991161197658 },
  { id: 19588, v: 0.484405798722268 },
  { id: 146579, v: 1.1163368072601798 },
  { id: 61852, v: 0.14220542231491137 }
]

前面提到可以用遍历的方式来查找，那么改一下 map() 中查找 bkk 的那一段

// v: all / bMap[id]?.bkk
v: all / (b.find(it => it.id === id)?.bkk)

这次的执行结果……就给个时间

calculate: 16.966s

30 毫秒和 17 秒（=17000毫秒），560 倍的差距……

结论

数据结构和算法真的要好好学！
数据结构和算法真的要好好学！
数据结构和算法真的要好好学！

---

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。

Answer 2

如果a,b中的数据是一一对应的，那么遍历a或者b都行，一边就可以产生c。否则就要先遍历a或b进行数据收集，在遍历另一个进行运算。

let obj = a.reduce((o, item) => {
  o[item.id] = item.all
  return o
}, {})
let c = b.map(item => ({id: item.id, v: obj[item.id] ==null ? item.bkk : (obj[item.id] / item.bkk)}))

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。