无需排序实现事件序列分析：Top10高频事务变体优化问询

问题背景 #

系统会为每个Transaction生成若干事件，事务没有固定起止事件（事件随机执行）。核心任务是找出关联事务数最多的Top10事件变体。

示例说明 #

假设有6个事件：

1. 早上起床
2. 吃早餐
3. 去上学
4. 回家
5. 吃晚餐
6. 睡觉

示例数据：

Transaction Id   Event name       TimeStamp
 T1            回家                6 PM
 T1            睡觉                11 PM
 T2            睡觉                8 PM
 T2            吃晚餐              6 PM
 T3            回家                7 PM
 T3            睡觉                11 PM
 T4            吃晚餐              6 PM
 T4            睡觉                8 PM  

变体统计结果：

• 变体1：(回家, 睡觉)，关联事务T1、T3，总计数2
• 变体2：(吃晚餐, 睡觉)，关联事务T2、T4，总计数2

现有实现步骤 #

1. 按Transaction Id分组事件
2. 对每个Transaction的事件按时间戳排序
3. 拼接该Transaction的事件名称（如T1对应回家,睡觉）
4. 将所有拼接结果存入哈希表
5. 统计相同序列的事务数量，更新哈希表
6. 排序哈希表结果，取出Top10高频变体

性能现状与需求 #

现有方案处理65K条记录耗时约65-80ms，要求优化至50ms以内。需要解决两个核心问题：

• 是否存在更优算法？
• 能否无需排序实现？

现有Java实现代码 #

// Case Id 对应 Transaction Id
public String findTopVariants(List<EventlogRow> eventlogRows, int limit) throws JsonProcessingException {

    Map<String, List<EventlogRow>> caseIdsEventLogRowsMap = eventlogRows
            .stream()
            .peek(this::validateInput)
            .collect(Collectors.groupingBy(EventlogRow::getCaseId));

    Map<String, Integer> commaSeparatedEventsNameToCaseIdsCountMap = getCommaSeparatedEventNamesWithCaseIdCount(caseIdsEventLogRowsMap);

    Map<String, Integer> topEventVariants = getTopEventVariants(limit, commaSeparatedEventsNameToCaseIdsCountMap);

    EventVariantResponse eventVariantResponse = new EventVariantResponse();

    topEventVariants.forEach((eventNames, caseCount) -> {
                EventVariant eventVariant = new EventVariant(eventNames, caseCount);
                eventVariantResponse.getVariants().add(eventVariant);
            }
    );

    return objectMapper.writeValueAsString(eventVariantResponse);
}

private void validateInput(EventlogRow eventlogRow) {
    if (Objects.isNull(eventlogRow.getCaseId()) || Objects.isNull(eventlogRow.getEventName()) || Objects.isNull(eventlogRow.getTimestamp())) {
        throw new RequiredFieldValuesMissingException();
    }
}

private Map<String, Integer> getCommaSeparatedEventNamesWithCaseIdCount(Map<String, List<EventlogRow>> caseIdsEventLogRowsMap) {
    Map<String, Integer> commaSeparatedEventsNameToCaseIdsCountMap = new HashMap<>();

    caseIdsEventLogRowsMap.forEach((caseId, caseIdEventLogs) -> {
        caseIdEventLogs.sort(Comparator.comparing(EventlogRow::getTimestamp));
        String commaSeparatedEventNames = caseIdEventLogs.stream().distinct().map(EventlogRow::getEventName).collect(Collectors.joining(","));
        int count = commaSeparatedEventsNameToCaseIdsCountMap.getOrDefault(commaSeparatedEventNames, 0);

        commaSeparatedEventsNameToCaseIdsCountMap.put(commaSeparatedEventNames, ++count);
    });

    return commaSeparatedEventsNameToCaseIdsCountMap;
}

private Map<String, Integer> getTopEventVariants(int limit, Map<String, Integer> commaSeparatedEventsNameToCaseIdsCountMap) {
    return commaSeparatedEventsNameToCaseIdsCountMap.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
            .limit(limit).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
}

优化方案建议 #

1. 避免排序的核心思路 #

你需要的是同一事务事件按时间顺序的序列作为唯一统计键，排序的本质是为了生成这个键。如果原始数据中同一事务的事件是按时间顺序流入系统的（即同一Transaction的事件在列表中已经按Timestamp递增排列），可以直接跳过排序步骤，直接拼接事件名称。

如果数据是乱序的，排序是生成正确变体标识的必要步骤，但可以优化排序时机：

• 提前对所有事件按CaseId+Timestamp全局排序，再分组，这样每个分组后的事件列表天然有序，避免对每个小分组单独排序（批量排序的效率远高于多次小批量排序）。

2. 性能优化细节 #

• 预分配集合容量：根据预估的事务数量初始化HashMap容量，避免动态扩容的开销；
• 替换低效Stream操作：生成事件序列字符串时，用普通循环+StringBuilder拼接替代Stream链式调用，减少对象创建和Stream的额外开销；
• 优化TopN提取：用最小堆（PriorityQueue）维护Top10元素，而非对所有条目排序——当变体数量远大于10时，这种方式能大幅减少排序耗时；
• 提前去重：在拼接事件名称时直接跳过重复事件，避免后续的distinct()操作。

3. 优化后的核心代码示例 #

// 优化后的序列生成逻辑
private Map<String, Integer> getCommaSeparatedEventNamesWithCaseIdCount(Map<String, List<EventlogRow>> caseIdsEventLogRowsMap) {
    // 预分配容量，按负载因子0.75计算
    int estimatedSize = (int) (caseIdsEventLogRowsMap.size() / 0.75f) + 1;
    Map<String, Integer> countMap = new HashMap<>(estimatedSize);

    for (Map.Entry<String, List<EventlogRow>> entry : caseIdsEventLogRowsMap.entrySet()) {
        List<EventlogRow> logs = entry.getValue();
        // 若已全局排序，此处可跳过
        logs.sort(Comparator.comparing(EventlogRow::getTimestamp));
        
        StringBuilder sb = new StringBuilder();
        String prevEvent = null;
        // 循环拼接+去重
        for (EventlogRow log : logs) {
            String eventName = log.getEventName();
            if (!eventName.equals(prevEvent)) {
                if (sb.length() > 0) sb.append(',');
                sb.append(eventName);
                prevEvent = eventName;
            }
        }
        String key = sb.toString();
        countMap.put(key, countMap.getOrDefault(key, 0) + 1);
    }
    return countMap;
}

// 用最小堆优化TopN提取
private Map<String, Integer> getTopEventVariants(int limit, Map<String, Integer> countMap) {
    PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(limit, Map.Entry.comparingByValue());
    
    for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
        if (minHeap.size() < limit) {
            minHeap.offer(entry);
        } else if (entry.getValue() > minHeap.peek().getValue()) {
            minHeap.poll();
            minHeap.offer(entry);
        }
    }
    
    // 转换为从高到低排序的LinkedHashMap
    Map<String, Integer> result = new LinkedHashMap<>(limit);
    minHeap.stream()
            .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
            .forEach(entry -> result.put(entry.getKey(), entry.getValue()));
    return result;
}

关键结论 #

• 若原始数据中同一事务的事件天然时间有序，可完全跳过排序；若数据乱序，排序不可避免，但全局预排序比分组后逐个排序更高效；
• 结合预分配容量、替换低效操作、最小堆提取TopN等手段，可将处理时间压缩至50ms以内。

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