如何优化对象数组中地址与行政区的前缀搜索性能？

问题描述 #

我有一组地址数据，需要实现基于去除"St. "前缀后的地址和区域title的前缀搜索，但当前实现运行速度较慢，希望找到更高效的方案，同时确保结果无重复：

地址数据如下：

const addresses = [
  { id: 1, address: "St. East Baltimore, 820", district: [{ id: 1, title: "Mfume" }] },
  { id: 2, address: "St. Darnestown Rd, 12187", district: [{ id: 7, title: "Trone" }] },
  { id: 3, address: "St. Elm Street", district: [{ id: 4, title: "Raskin Sarbanes" }] },
  { id: 4, address: "St. Bethesda Ave", district: [{ id: 12, title: "Rayburn House" }] },
  { id: 5, address: "St. Bethesda Lane, 7111", district: [{ id: 2, title: "Connolly" }] },
  { id: 6, address: "St. Trolls Toys, 643", district: [{ id: 8, title: "Beyer" }] },
  { id: 7, address: "St. Houlton, 12", district: [{ id: 45, title: "Lee Zeldin House" }] },
];

当前的实现代码：

const searchQuery = "Be"
const regex = new RegExp('^' + searchQuery, 'i');
const searchByAddress = addresses.filter((addr) => {
  return addr.address.replace("St. ", '').trim().search(regex) == 0;
});
const searchByDistrict = addresses.filter((addr) => {
  return addr.district[0].title.search(regex) == 0;
});
var result = []
result.push(searchByAddress)
searchByDistrict.map(item => {
  const found = result.some(el => el.id === item.id);
  if (!found) {
    result.push(item);
  }
})
console.log(result);

为什么原代码速度慢？ #

咱们拆解一下原代码的性能瓶颈：

1. 两次完整遍历数组：用了两个filter，相当于把整个地址列表扫了两遍，数据量大的时候开销翻倍
2. 低效的去重逻辑：用some检查元素是否存在，每次都要遍历已有的结果数组，时间复杂度是O(k)（k是已匹配元素的数量）
3. 重复的字符串处理：每次过滤地址时都重复执行replace("St. ", '')，没有复用计算结果
4. 正则表达式的开销：用RegExp.search做前缀匹配，不如原生字符串方法高效

优化方案与代码实现 #

针对上面的问题，我们可以从「减少遍历次数、高效去重、优化匹配逻辑」三个方向入手：

1. 单次遍历完成双重条件检查

只遍历一次数组，同时判断地址和区域是否符合搜索条件，直接把时间复杂度从O(2n)降到O(n)。

2. 用Set做高效去重

Set的has方法是O(1)时间复杂度，比数组的some快得多，能快速判断当前元素是否已经被加入结果。

3. 用startsWith替代正则

原生的startsWith方法是专门为前缀匹配设计的，配合大小写转换，比正则表达式的search性能更好。

完整优化代码

const addresses = [
  { id: 1, address: "St. East Baltimore, 820", district: [{ id: 1, title: "Mfume" }] },
  { id: 2, address: "St. Darnestown Rd, 12187", district: [{ id: 7, title: "Trone" }] },
  { id: 3, address: "St. Elm Street", district: [{ id: 4, title: "Raskin Sarbanes" }] },
  { id: 4, address: "St. Bethesda Ave", district: [{ id: 12, title: "Rayburn House" }] },
  { id: 5, address: "St. Bethesda Lane, 7111", district: [{ id: 2, title: "Connolly" }] },
  { id: 6, address: "St. Trolls Toys, 643", district: [{ id: 8, title: "Beyer" }] },
  { id: 7, address: "St. Houlton, 12", district: [{ id: 45, title: "Lee Zeldin House" }] },
];

const searchQuery = "Be";
const lowercasedQuery = searchQuery.toLowerCase();
const result = [];
const matchedIds = new Set();

// 单次遍历数组，同时检查两个条件
for (const addr of addresses) {
  // 处理地址：去除前缀并转小写，判断是否以查询字符串开头
  const cleanedAddress = addr.address.replace("St. ", "").trim().toLowerCase();
  const matchesAddress = cleanedAddress.startsWith(lowercasedQuery);
  
  // 处理区域title：转小写后判断前缀
  const districtTitle = addr.district[0].title.toLowerCase();
  const matchesDistrict = districtTitle.startsWith(lowercasedQuery);
  
  // 任一条件满足且未被加入过，就添加到结果
  if ((matchesAddress || matchesDistrict) && !matchedIds.has(addr.id)) {
    matchedIds.add(addr.id);
    result.push(addr);
  }
}

console.log(result);

针对频繁搜索的进一步优化

如果需要多次执行搜索操作，可以提前预处理地址数据，把去除"St. "前缀后的地址缓存起来，避免每次搜索都重复做字符串替换：

// 预处理：一次性处理所有地址的前缀
const preprocessedAddresses = addresses.map(addr => ({
  ...addr,
  cleanedAddress: addr.address.replace("St. ", "").trim().toLowerCase()
}));

// 封装成可复用的搜索函数
const performSearch = (query) => {
  const lowercasedQuery = query.toLowerCase();
  const result = [];
  const matchedIds = new Set();
  
  for (const addr of preprocessedAddresses) {
    const matchesAddress = addr.cleanedAddress.startsWith(lowercasedQuery);
    const matchesDistrict = addr.district[0].title.toLowerCase().startsWith(lowercasedQuery);
    
    if ((matchesAddress || matchesDistrict) && !matchedIds.has(addr.id)) {
      matchedIds.add(addr.id);
      result.push(addr);
    }
  }
  
  return result;
};

// 使用示例
console.log(performSearch("Be"));

性能提升效果 #

• 遍历次数从2次降到1次，直接减少一半的遍历开销
• 去重操作的时间复杂度从O(k)降到O(1)，数据量越大提升越明显
• 用原生startsWith替代正则，前缀匹配的效率更高
• 预处理方案避免了重复的字符串替换，适合频繁搜索的场景

内容的提问来源于stack exchange，提问作者Andreas Hunter