6

for、while、および do-while ループを使用して低レベルの Java 最適化を行う方法、およびそれが必要かどうかについては、多くの質問と回答、および意見があります。

私の質問は、設計におけるハイレベルベースの最適化です。私が次のことをしなければならないと仮定しましょう：

特定の文字列入力について、文字列内の各文字の出現回数をカウントします。

文字列が数文の場合、これは大きな問題ではありませんが、代わりに、900,000 語のファイル内の各単語の出現回数をカウントしたい場合はどうなるでしょうか。ループの構築は時間を無駄にするだけです。

では、この種の問題に適用できる高レベルの設計パターンは何でしょうか。

私の主なポイントは、多くの問題を解決するためにループを使用する傾向があることであり、ループを使用する習慣をやめたいと考えています。

前もって感謝します

サム

ps 可能であれば、900,000 ワードのファイルの問題を解決するための疑似コードを作成していただけますか? 私は英語よりもコードをよく理解する傾向があります。これは、このサイトのほとんどの訪問者にとって同じであると思います。

4

6 に答える 6

10

文字数の問題は、ビッグデータの世界で最も広く取り上げられている問題の 1 つです。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
}

データセットが大きすぎてメモリ内ハッシュマップを作成できない場合は、次のようにカウントできます。

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

これらの 3 つのステップは、Unix パイプラインで行われます。ここでは、OS に作業を任せてください。

さらに多くのデータを取得したら、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 を使用している場合、1 秒あたり 240 億クロック サイクルになります。;)

ただし、を使用して文字をカウントする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 倍でさえ、数分の 1 秒しかかかりません。

はるかに長い並列バージョンは少し高速です。

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

しかし、100 万語未満の文字列の場合、その価値はほとんどありません。

于 2011-08-13T07:00:55.177 に答える
0

原則として、単純な方法で物事を書き、それをできるだけ速くするためにパフォーマンス調整を行う必要があります。それがより高速なアルゴリズムを導入することを意味する場合は、そうしますが、最初は単純にしてください。このような小さなプログラムの場合、それほど難しくはありません。

パフォーマンスチューニングの基本的なスキルは推測ではありません。代わりに、プログラム自体に修正する内容を教えてもらいます。 これが私の方法です。

このようなより複雑なプログラムの場合、経験から、回避しようとしているパフォーマンスの低下の多くを引き起こすような考えすぎを回避する方法がわかります。

于 2011-08-13T22:24:05.613 に答える
0

分割統治法を使用し、リソースの競合を回避する必要があります。そのためのさまざまなアプローチや実装があります。考え方は同じです。作業を分割し、処理を並列化します。

単一のマシンでは、データのチャンクを別々のスレッドで処理できますが、同じディスクにチャンクがあると、処理速度が大幅に低下します。Hスレッドが多いということは、コンテキストスイッチングが多いことを意味します。スループットは、スレッドの数を減らしてビジー状態に保つ方がIMHOの方が優れているからです。

処理をステージに分割し、SEDAなどを使用して、 map-reduceに使用する非常に大きなデータを使用できます。クラスター全体にデータを分散する費用を考慮してください。

誰かが別の広く使用されているAPIを指摘してくれることをうれしく思います。

于 2011-08-13T23:22:22.227 に答える