1

因此，我试图在 Java 中搜索 Arraylist 并创建一个直方图，该直方图由字符串长度与大型文本文件中存在的频率的频率组成。我想出了一个蛮力算法，但它太慢了，无法用于大型数据文件。有没有更有效的方式通过 Arraylist 进行处理？我已经包含了我想出的蛮力方法。

for (int i = 0; i < (maxLen + 1); i++)
{
    int hit = 0;
    for (int j = 0; j < list.size(); j++)
    {
        if (i == list.get(j).length())
            ++hit;

        histogram[i] = hit;
    }

}
4

2 回答 2

2

这是非常低效的。

与其遍历每个可能的长度值，然后遍历每个可用的单词，不如简单地遍历文档中的可用单词并计算它们的长度，怎么样？

例如：

Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();

for(int i=0; i<list.size(); i++) {
    String thisWord = list.get(i);
    Integer theLength = (Integer)(thisWord.length());
    if(frequencies.containsKey(theLength) {
        frequencies.put(theLength, new Integer(frequencies.get(theLength).intValue()+1));
    }
    else {
        frequencies.put(theLength, new Integer(1));
    }
}

然后，如果 中不存在该键，则HashMap您知道文档中不存在该长度的单词。如果密钥确实存在，您可以准确查找发生了多少次。

注意：此代码示例的某些方面是为了防止对装箱和拆箱产生任何额外的混淆。可以写得稍微干净一些，我当然会在生产环境中这样做。此外，它假设您不知道任何最小或最大单词长度（因此稍微灵活、可扩展和包罗万象）。否则，用于简单声明原始数组的其他技术也可以正常工作（请参阅 Jon Skeet 的回答）。

对于利用自动装箱的更清洁的版本：

Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();

for(int i=0; i<list.size(); i++) {
    String thisWord = list.get(i);
    if(frequencies.containsKey(thisWord.length()) {
        frequencies.put(thisWord.length(), frequencies.get(thisWord.length())+1);
    }
    else {
        frequencies.put(thisWord.length(), 1);
    }
}
于 2012-10-23T17:28:32.450 回答
1

你为什么不只循环一次列表呢？

int[] histogram = new int[maxLen + 1]; // All entries will be 0 to start with
for (String text : list) {
    if (text.length() <= maxLen) {
        histogram[text.length()]++;
    }
}

这现在只是 O(N)。

于 2012-10-23T17:29:19.127 回答