如何对字符串列表进行排序,并在java中查找1000个最常用的值

Question

在java(使用外部库或不使用外部库)中,我需要获取大约500,000个值的列表,并找到最常出现的(模式)1000.尽我所能将复杂性降至最低.

我到目前为止尝试过,做一个哈希,但我不能,因为它必须向后键= count value = string,否则当获得前1000名时,我的复杂性将是垃圾.并且向后的方式并没有真正起作用,因为我会有一个非常复杂的插入,因为我搜索我的字符串能够删除它并将其插入更高的位置...

我已经尝试过使用二进制搜索树,但是在计数或字符串上存在与数据排序相同的问题.如果它在字符串上,那么获得前1000的计数是不好的,反之亦然插入是坏的.

我可以先对列表进行排序(按字符串),然后遍历列表并保持计数直到它更改字符串.但是我应该使用什么数据结构来跟踪前1000名呢？

谢谢

Answer 1

我会先创建一个Map<String, Long>存储每个单词的频率.然后,我按降序按值排序这个地图,最后我会保留第一个1000条目.

在代码中:

List<String> top1000Words = listOfWords.stream()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
    .entrySet().stream()
        .sorted(Map.Entry.comparingByValue().reversed())
        .limit(1000)
        .map(Map.Entry::getKey)
        .collect(Collectors.toList());

您可能会发现将上述内容分为两个步骤更加清晰:首先收集到频率图,然后按值对其条目进行排序并保留前1000个条目.

Answer 2

我将其分为三个阶段：

• 计算单词出现次数（例如使用 a HashMap<String, Integer>）
• 对结果进行排序（例如，通过将映射转换为条目列表并按值降序排序）
• 输出排序结果的前1000条

如果计数很小（例如，如果您实际上有 500,000 个单独的单词），则排序会很慢，但如果您期望有大量重复单词，则应该没问题。