代码之家 › 专栏 › 技术社区 › Daniel Santos

在javascript中搜索数组中字符串的性能和“正确”方法

javascript

Daniel Santos · 技术社区 · 6 年前

我真正需要的是:检查一个黑名单作为csv字符串的电子邮件数组。

使用 blacklist.indexOf(email) >= 0 -非常慢。我试过了

"email1@gmail.com;email2@gmail.com ..."
array.IndexOf(email) >= 0

["email1@gmail.com","email2@gmail.com" ...]
创建一个对象,其中每个属性都是来自黑名单的电子邮件,并指定为“true”和do myObject[email] ; 这似乎是更快的方式,但它看起来非常像一个“乱七八糟”。

{"email1@gmail.com":true,"email2@gmail.com":true ...}

我怎样才能使这个搜索快速而不是一个“混球”?

2 回复 | 直到 6 年前

Philip 5 年前

我想说的是,最好是用预填充的 Map 您可以拆分csv字符串并对其进行迭代。我已经编写了两个性能测试并在Chrome中运行了它们。在…的帮助下 https://developer.mozilla.org/en-US/docs/Web/API/Performance/measure .

我画了两张地图。一个有400k条目的电子邮件地图和一个有1k条目的黑名单地图。

// noprotect
console.clear();

const EMAIL_COUNT = 400000;
const BLACKLIST_EMAIL_COUNT = 1000;
let mailMatches = 0;

// arrays
const emails = new Map();
const blacklist = new Map();

// 1k blacklisted mails
for (let bl = 0; bl < BLACKLIST_EMAIL_COUNT; bl++) {
    if (bl % 2 === 0) {
        blacklist.set('email' + bl, 'email' + bl);
    } else {
        blacklist.set('email@' + bl, 'email@' + bl);
    }
}

// 400k mails
for (let j = 0; j < EMAIL_COUNT; j++) {
    emails.set('email' + j, 'email' + j);
}

performance.mark('perfMailList-start');

// 1ms (includes, emails, reverse)
blacklist.forEach(blacklistItem => {
    if (emails.has(blacklistItem)) {
        mailMatches++;
    }
});

// 32ms
/*emails.forEach(email => {
    if(blacklist.has(email)) {
        mailMatches++;
    }
})*/

performance.mark('perfMailList-end');

performance.measure('perfMailList', 'perfMailList-start', 'perfMailList-end');

const measures = performance.getEntriesByName('perfMailList');
const measure = measures[0];

console.log(`${measure.duration}ms and ${mailMatches} found blacklisted mails`);

// Clean up the stored markers.
performance.clearMarks();
performance.clearMeasures();

和一些循环(for,for reverse,forEach)交替 includes 或 indexOf .

// noprotect
console.clear();

const EMAIL_COUNT = 400000;
const BLACKLIST_EMAIL_COUNT = 1000;
let mailMatches = 0;

// arrays
const emails = [];
const blacklist = [];

// 1k blacklisted mails
for (let bl = 0; bl < BLACKLIST_EMAIL_COUNT; bl++) {
    // console.log(i)
    if (bl % 2 === 0) {
        blacklist.push('email' + bl);
    } else {
        blacklist.push('email@' + bl);
    }
}

// 400k mails
for (let j = 0; j < EMAIL_COUNT; j++) {
    emails.push('email' + j);
}

performance.mark('perfMailList-start');

// 524ms (indexOf, emails)
/*emails.forEach(mail => {
if(blacklist.indexOf(mail) >= 0){
        mailMatches++;
}
})*/

// 583ms (includes, blacklist)
/*blacklist.forEach(blacklistItem => {
if(emails.indexOf(blacklistItem) >= 0){
        mailMatches++;
}
})*/

// --------------------------

// 521ms (includes, emails)
/*emails.forEach(mail => {
if(blacklist.includes(mail)){
        mailMatches++;
}
})*/

// 600ms (includes, blacklist)
/*blacklist.forEach(blacklistItem => {
if(emails.includes(blacklistItem)){
        mailMatches++;
}
})*/

// --------------------------

// 638ms (includes, emails, reverse)
/*for(var i = BLACKLIST_EMAIL_COUNT; i--;) {
    if(emails.includes(blacklist[i])){
        mailMatches++;
    }
}*/

// 632ms (indexOf, emails, reverse)
/*for(var i = BLACKLIST_EMAIL_COUNT; i--;) {
    if(emails.indexOf(blacklist[i]) >= 0){
        mailMatches++;
    }
}*/

// --------------------------

// 530ms (includes, emails)
/*for(var i = EMAIL_COUNT; i--;) {
    if(blacklist.includes(emails[i])){
        mailMatches++;
    }
    }*/

// 530ms (indexOf, emails)
/*for(var i = EMAIL_COUNT; i--;) {
    if(blacklist.indexOf(emails[i]) >= 0){
        mailMatches++;
    }
}*/

// --------------------------

// 525ms (includes, emails)
/*for(let i = 0; i < EMAIL_COUNT; i++) {
    if(blacklist.includes(emails[i])) {
        mailMatches++;
    }
}*/

// 540ms (indexOf, emails)
/*for(let i = 0; i < EMAIL_COUNT; i++) {
    if(blacklist.indexOf(emails[i]) >= 0) {
        mailMatches++;
    }
    }*/

// --------------------------

// 668ms (includes, blacklist)
/*for(let i = 0; i < BLACKLIST_EMAIL_COUNT; i++) {
    if(emails.includes(blacklist[i])) {
        mailMatches++;
    }
}*/

// 687ms (indexOf, blacklist)
/*for(let k = 0; k < BLACKLIST_EMAIL_COUNT; k++) {
    if(emails.indexOf(blacklist[k]) >= 0) {
        mailMatches++;
    }
}*/

// --------------------------

// 1367ms (equals)
/*for(let i = 0; i < EMAIL_COUNT; i++) {
    for(let k = 0; k < BLACKLIST_EMAIL_COUNT; k++) {
        if(emails[i] === blacklist[k]) {
        mailMatches++;
        }
    }
}*/

performance.mark('perfMailList-end');

performance.measure('perfMailList', 'perfMailList-start', 'perfMailList-end');

const measures = performance.getEntriesByName('perfMailList');
const measure = measures[0];

console.log(`${measure.duration}ms and ${mailMatches} found blacklisted mails`);

// Clean up the stored markers.
performance.clearMarks();
performance.clearMeasures();

MacBook电脑: Pro(15英寸,2016)

内存: 16 GB 2133兆赫LPDDR3

-1

Benny Powers 6 年前

使用 Array#includes 让引擎实现者担心优化问题

blacklist.includes(email)

或者,使用集合或贴图

https://jsperf.com/array-includes-and-find-methods-vs-set-has