6

关于如何使用 for、while 和 do-while 循环以及是否有必要进行低级 Java 优化，有很多问题、答案和意见。

我的问题更多是基于高级别的设计优化。假设我必须执行以下操作：

对于给定的字符串输入，计算字符串中每个字母的出现次数。

当字符串是几个句子时，这不是一个主要问题，但是如果我们想要计算每个单词在 900,000 个单词文件中的出现次数怎么办。建立循环只是浪费时间。

那么可以应用于此类问题的高级设计模式是什么。

我想我的主要观点是我倾向于使用循环来解决很多问题，并且我想摆脱使用循环的习惯。

提前致谢

山姆

ps 如果可能的话，您能否提供一些伪代码来解决 900,000 字的文件问题，我倾向于理解代码而不是理解英语，我认为对于本网站的大多数访问者来说都是一样的

4

6 回答 6

10

字数统计问题是大数据世界中覆盖最广泛的问题之一；它有点像 Hadoop 等框架的 Hello World。您可以在整个网络上找到有关此问题的大量信息。

无论如何，我会给你一些想法。

首先，900000 个单词可能仍然小到可以为其构建哈希图，所以不要忽视明显的内存方法。你说伪代码很好，所以：

h = new HashMap<String, Integer>();
for each word w picked up while tokenizing the file {
  h[w] = w in h ? h[w]++ : 1
}

现在，一旦您的数据集太大而无法构建内存中的 hashmap，您可以像这样进行计数：

Tokenize into words writing each word to a single line in a file
Use the Unix sort command to produce the next file
Count as you traverse the sorted file

这三个步骤进入 Unix 管道。让操作系统在这里为您完成工作。

现在，随着您获得更多数据，您希望引入像 hadoop 这样的 map-reduce 框架来对机器集群进行字数统计。

现在，我听说当你进入非常大的数据集时，在分布式环境中做事不再有帮助，因为传输时间超过了计数时间，而且在你的字数统计的情况下，一切都必须“重新组合在一起”无论如何”，所以你必须使用一些我怀疑你可以在研究论文中找到的非常复杂的技术。

附录

OP 要求提供一个在 Java 中对输入进行标记的示例。这是最简单的方法：

import java.util.Scanner;
public class WordGenerator {
    /**
     * Tokenizes standard input into words, writing each word to standard output,
     * on per line.  Because it reads from standard input and writes to standard
     * output, it can easily be used in a pipeline combined with sort, uniq, and
     * any other such application.
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            System.out.println(input.next().toLowerCase());
        }
    } 
}

现在这里是一个使用它的例子：

echo -e "Hey Moe! Woo\nwoo woo nyuk-nyuk why soitenly. Hey." | java WordGenerator

这输出

hey
moe!
woo
woo
woo
nyuk-nyuk
why
soitenly.
hey.

您可以将此标记器与 sort 和 uniq 结合起来，如下所示：

echo -e "Hey Moe! Woo\nwoo woo nyuk-nyuk why soitenly. Hey." | java WordGenerator | sort | uniq

屈服

hey
hey.
moe!
nyuk-nyuk
soitenly.
why
woo

现在，如果您只想保留字母并丢弃所有标点符号、数字和其他字符，请将扫描仪定义行更改为：

Scanner input = new Scanner(System.in).useDelimiter(Pattern.compile("\\P{L}"));

现在

echo -e "Hey Moe! Woo\nwoo woo^nyuk-nyuk why#2soitenly. Hey." | java WordGenerator | sort | uniq

产量

hey
moe
nyuk
soitenly
why
woo

输出中有一个空行；我会让你弄清楚如何敲打它。:)

于 2011-08-13T04:43:27.143 回答
3

最快的解决方案是 O(n) AFAIK 使用循环来迭代字符串，获取字符并相应地更新 HashMap 中的计数。最后，HashMap 包含所有出现的字符和所有出现的计数。

一些伪代码（可能无法编译）

HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++)
{
    char c = str.charAt(i);
    if (map.containsKey(c)) map.put(c, map.get(c) + 1);
    else map.put(c, 1);
}
于 2011-08-13T04:41:57.890 回答
1

你很难比使用循环来解决这个问题更好。IMO，加速此类操作的最佳方法是将工作负载拆分为不同的工作单元，并使用不同的处理器处理工作单元（例如，如果您有一台多处理器计算机，则使用线程）。

于 2011-08-13T04:45:18.740 回答
1

你不应该假设 900,000 是很多字。如果您有一个具有 8 个线程和 3 GHZ 的 CPU，那就是每秒 240 亿个时钟周期。;)

然而，使用 an 来计算字符int[]会快得多。只有 65,536 个可能的字符。

StringBuilder words = new StringBuilder();
Random rand = new Random();
for (int i = 0; i < 10 * 1000 * 1000; i++)
    words.append(Long.toString(rand.nextLong(), 36)).append(' ');
String text = words.toString();

long start = System.nanoTime();
int[] charCount = new int[Character.MAX_VALUE];
for (int i = 0; i < text.length(); i++)
    charCount[text.charAt(i)]++;
long time = System.nanoTime() - start;
System.out.printf("Took %,d ms to count %,d characters%n", time / 1000/1000, text.length());

印刷

Took 111 ms to count 139,715,647 characters

即使是单词数量的 11 倍，也只需要几分之一秒。

更长的并行版本更快一些。

public static void main(String... args) throws InterruptedException, ExecutionException {
    StringBuilder words = new StringBuilder();
    Random rand = new Random();
    for (int i = 0; i < 10 * 1000 * 1000; i++)
        words.append(Long.toString(rand.nextLong(), 36)).append(' ');
    final String text = words.toString();

    long start = System.nanoTime();
    // start a thread pool to generate 4 tasks to count sections of the text.
    final int nThreads = 4;
    ExecutorService es = Executors.newFixedThreadPool(nThreads);
    List<Future<int[]>> results = new ArrayList<Future<int[]>>();
    int blockSize = (text.length() + nThreads - 1) / nThreads;
    for (int i = 0; i < nThreads; i++) {
        final int min = i * blockSize;
        final int max = Math.min(min + blockSize, text.length());
        results.add(es.submit(new Callable<int[]>() {
            @Override
            public int[] call() throws Exception {
                int[] charCount = new int[Character.MAX_VALUE];
                for (int j = min; j < max; j++)
                    charCount[text.charAt(j)]++;
                return charCount;
            }
        }));
    }
    es.shutdown();
    // combine the results.
    int[] charCount = new int[Character.MAX_VALUE];
    for (Future<int[]> resultFuture : results) {
        int[] result = resultFuture.get();
        for (int i = 0, resultLength = result.length; i < resultLength; i++) {
            charCount[i] += result[i];
        }
    }
    long time = System.nanoTime() - start;
    System.out.printf("Took %,d ms to count %,d characters%n", time / 1000 / 1000, text.length());
}

印刷

Took 45 ms to count 139,715,537 characters

但是对于少于一百万字的字符串来说，它可能不值得。

于 2011-08-13T07:00:55.177 回答
0

作为一般规则，您应该以直接的方式编写内容，然后进行性能调整以使其尽可能快。如果这意味着要使用更快的算法，那就这样做，但首先要保持简单。对于这样的小程序，它不会太难。

性能调优的基本技能不是猜测。相反，让程序本身告诉您要修复什么。 这是我的方法。

对于更多涉及的程序，比如这个，经验将告诉你如何避免过度思考，最终导致它试图避免的许多糟糕的性能。

于 2011-08-13T22:24:05.613 回答
0

您必须使用分而治之的方法并避免争夺资源。为此有不同的方法和/或实现。想法是一样的——拆分工作并并行处理。

在单台机器上，您可以在单独的线程中处理数据块，尽管将块放在同一个磁盘上会大大减慢速度。H 拥有更多线程意味着拥有更多的上下文切换，因为吞吐量是恕我直言，最好拥有更少的线程并使它们保持忙碌。

您可以将处理拆分为多个阶段并使用SEDA或类似的东西，并使用您为map-reduce执行的真正大数据- 只需计算跨集群分布数据的费用即可。

我会很高兴有人指出另一个广泛使用的 API。

于 2011-08-13T23:22:22.227 回答