如何基于用户分日期购买记录高效计算各品牌关联购买概率最高的品牌

你原本想到的用Map存储共现次数的思路已经是渐近复杂度最优的方案，不存在时间效率更高的算法——因为你必须遍历所有购买记录才能统计共现关系，这一步是无法省略的。
如果你觉得后续遍历全量共现Map的开销太高，可以在统计共现次数的同时同步维护每个品牌的最高共现结果，省去后续全量遍历的步骤，优化后的实现思路如下：

• 定义两个存储结构：
  1. 共现计数表：Map<String, Map<String, Integer>> coCount，外层key是目标品牌，内层key是共现品牌，value是两者的共现次数
  2. 最高共现结果表：Map<String, Map.Entry<Integer, List<String>>> topRes，key是目标品牌，value的key是最高共现次数，value的value是所有达到该次数的共现品牌列表
• 逐天处理购买记录：
  对单日的品牌列表生成所有不重复的两两组合（比如当天有[A,B,C]，就生成(A,B)、(A,C)、(B,C)三组），每组两个品牌分别更新对方的共现计数：
  1. 对组合(X,Y)，先给coCount.get(X).put(Y, coCount.get(X).getOrDefault(Y, 0) + 1)
  2. 拿到X和Y的最新共现次数，和topRes中X存储的最高次数对比：
     • 若新次数 > 最高次数：更新最高次数为新次数，清空品牌列表后加入Y
     • 若新次数 == 最高次数：直接把Y加入品牌列表
     • 若新次数 < 最高次数：不做处理
  3. 用同样逻辑更新Y对应的共现计数和最高共现结果
• 所有日期处理完成后，直接遍历topRes即可输出结果，不需要再遍历全量共现计数表

示例实现代码（Java） #

import java.util.*;
import java.util.AbstractMap.SimpleEntry;

public class BrandCoOccur {
    public static void main(String[] args) {
        List<String[]> records = Arrays.asList(
                new String[]{"Nike", "Adidas", "Croc"},
                new String[]{"Adidas", "Croc", "Reebok"},
                new String[]{"Croc", "Reebok", "Sketchers"}
        );

        Map<String, Map<String, Integer>> coCount = new HashMap<>();
        Map<String, SimpleEntry<Integer, List<String>>> topRes = new HashMap<>();

        for (String[] dayRecord : records) {
            int len = dayRecord.length;
            // 生成两两不重复组合
            for (int i = 0; i < len; i++) {
                String x = dayRecord[i];
                coCount.putIfAbsent(x, new HashMap<>());
                topRes.putIfAbsent(x, new SimpleEntry<>(0, new ArrayList<>()));
                for (int j = i + 1; j < len; j++) {
                    String y = dayRecord[j];
                    coCount.putIfAbsent(y, new HashMap<>());
                    topRes.putIfAbsent(y, new SimpleEntry<>(0, new ArrayList<>()));

                    // 更新x对y的计数和最高结果
                    int newCountX = coCount.get(x).getOrDefault(y, 0) + 1;
                    coCount.get(x).put(y, newCountX);
                    SimpleEntry<Integer, List<String>> xTop = topRes.get(x);
                    if (newCountX > xTop.getKey()) {
                        xTop.setValue(new ArrayList<>(Collections.singletonList(y)));
                        xTop.setKey(newCountX);
                    } else if (newCountX == xTop.getKey()) {
                        xTop.getValue().add(y);
                    }

                    // 更新y对x的计数和最高结果
                    int newCountY = coCount.get(y).getOrDefault(x, 0) + 1;
                    coCount.get(y).put(x, newCountY);
                    SimpleEntry<Integer, List<String>> yTop = topRes.get(y);
                    if (newCountY > yTop.getKey()) {
                        yTop.setValue(new ArrayList<>(Collections.singletonList(x)));
                        yTop.setKey(newCountY);
                    } else if (newCountY == yTop.getKey()) {
                        yTop.getValue().add(x);
                    }
                }
            }
        }

        // 输出结果
        for (Map.Entry<String, SimpleEntry<Integer, List<String>>> entry : topRes.entrySet()) {
            System.out.println(entry.getKey() + " -> " + String.join(", ", entry.getValue().getValue()));
        }
    }
}

该方案的时间复杂度为O(M*K²)，其中M是天数，K是单日平均购买的品牌数量，只要单日购买的品牌数量不是极大（通常业务场景下K都远小于总品牌数），该方案的运行效率远高于先统计全量共现再逐个遍历找最大值的实现，已经是理论上能达到的最优效率。

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