如何基于自定义排序函数高效排序多类型实体列表？

给定数据 #

未排序实体数组 #

const entities = [
  { id: "person-1", type: "person", fields: { age: 34 }}, 
  { id: "car-2", type: "car", fields: { manufacturer: "bar" }}, 
  { id: "house-2", type: "house", fields: { constructionYear: 2010 }}, 
  { id: "person-4", type: "person", fields: { age: 71 }},
  { id: "person-2", type: "person", fields: { age: 57 }}, 
  { id: "house-1", type: "house", fields: { constructionYear: 1968 }}, 
  { id: "car-1", type: "car", fields: { manufacturer: "foo" }},
  { id: "person-3", type: "person", fields: { age: 42 }},
];

类型排序配置 #

const sources = [
  { type: "person", sort: { index: 1, isLessThanFunctionAsString: "(left, right) => left.fields.age < right.fields.age" }},
  { type: "car" },
  { type: "house", sort: { index: 0, isLessThanFunctionAsString: "(left, right) => left.fields.constructionYear < right.fields.constructionYear" }},
];

问题背景 #

每个source对应一种实体类型的处理规则，带sort配置的source定义了该类型实体的内部排序逻辑，其中isLessThanFunctionAsString是字符串形式的比较函数，签名为(leftEntity: Entity, rightEntity: Entity) => boolean，逻辑不可控。当前实现的sortEntities函数在处理超过100个实体、20个source时性能极差，需要优化思路。

优化思路 #

1. 预编译并缓存排序函数 #

不要在每次比较时重复解析字符串函数，提前把所有isLessThanFunctionAsString编译成实际函数并缓存到类型映射中，避免重复解析的开销：

// 预构建类型排序配置映射
const typeSortConfigMap = new Map();
sources.forEach(source => {
  if (source.sort) {
    // 用new Function替代eval，作用域更可控、性能略优
    const compareFn = new Function('left', 'right', `return ${source.sort.isLessThanFunctionAsString}`);
    typeSortConfigMap.set(source.type, {
      index: source.sort.index,
      compareFn
    });
  } else {
    // 无排序配置的类型优先级设为最低
    typeSortConfigMap.set(source.type, { index: Infinity });
  }
});

2. 分组排序后合并，减少跨类型比较 #

直接全局排序会产生大量无效的跨类型比较，可拆分步骤优化：

// 1. 按类型分组
const groups = new Map();
entities.forEach(entity => {
  const type = entity.type;
  if (!groups.has(type)) groups.set(type, []);
  groups.get(type).push(entity);
});

// 2. 每组内按类型规则排序
groups.forEach((entities, type) => {
  const config = typeSortConfigMap.get(type);
  if (config.compareFn) {
    entities.sort(config.compareFn);
  }
});

// 3. 按sort.index对分组排序
const sortedGroups = Array.from(groups.entries())
  .sort(([typeA], [typeB]) => {
    const indexA = typeSortConfigMap.get(typeA).index;
    const indexB = typeSortConfigMap.get(typeB).index;
    return indexA - indexB;
  })
  .map(([_, entities]) => entities);

// 4. 合并分组得到最终结果
const sortedEntities = sortedGroups.flat();

这种方式将全局排序拆分为多个小分组的排序，总时间复杂度仍为O(n log n)，但常数项更小，同时避免了大量跨类型的无效比较。

3. 预计算类型优先级，避免重复查找 #

排序前预计算每个类型的优先级（sort.index），构建映射表，避免每次比较都遍历source数组查找配置：

// 预构建类型优先级映射
const typePriorityMap = new Map();
sources.forEach(source => {
  typePriorityMap.set(source.type, source.sort?.index ?? Infinity);
});

// 全局排序时直接使用预计算的映射
entities.sort((a, b) => {
  const priorityA = typePriorityMap.get(a.type);
  const priorityB = typePriorityMap.get(b.type);
  
  // 不同类型先按优先级排序
  if (priorityA !== priorityB) {
    return priorityA - priorityB;
  }
  
  // 同类型用预编译的比较函数
  const compareFn = typeSortConfigMap.get(a.type)?.compareFn;
  return compareFn ? (compareFn(a, b) ? -1 : 1) : 0;
});

4. 预计算排序键，减少比较时的重复计算 #

如果isLessThanFunctionAsString的逻辑基于实体的某个字段，提前提取该字段作为排序键，用键值比较替代实体比较：

// 预计算每个实体的排序键
const entitiesWithSortKey = entities.map(entity => {
  const config = typeSortConfigMap.get(entity.type);
  let sortKey = null;
  if (config.compareFn) {
    // 根据实际比较逻辑提取对应字段，示例中适配person和house的规则
    sortKey = entity.fields.age ?? entity.fields.constructionYear;
  }
  return { ...entity, sortKey };
});

// 用预计算的键排序
entitiesWithSortKey.sort((a, b) => {
  const priorityA = typePriorityMap.get(a.type);
  const priorityB = typePriorityMap.get(b.type);
  if (priorityA !== priorityB) return priorityA - priorityB;
  return a.sortKey - b.sortKey;
});

这种方式把比较时的计算提前到排序前，避免每次比较重复执行相同逻辑。

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