Java-Optimierung auf hoher Ebene

Question

Es gibt viele Fragen, Antworten und Meinungen darüber, wie man Java auf niedriger Ebene mit for-, while- und do-while-Schleifen optimieren kann und ob dies überhaupt notwendig ist.

Meine Frage bezieht sich eher auf eine Optimierung auf hoher Ebene im Design. Nehmen wir an, ich muss das Folgende tun:

für eine gegebene Zeichenketteneingabe das Vorkommen jedes Buchstabens in der Zeichenkette zählen.

dies ist kein großes Problem, wenn die Zeichenfolge ein paar Sätze ist, aber was, wenn wir stattdessen das Auftreten jedes Wort in einer 900.000-Wort-Datei zählen wollen. bauen Schleifen verschwendet nur Zeit.

Welches ist also das übergeordnete Entwurfsmuster, das auf diese Art von Problem angewendet werden kann?

Ich denke, mein Hauptargument ist, dass ich dazu neige, Schleifen zu verwenden, um viele Probleme zu lösen, und dass ich mir die Verwendung von Schleifen abgewöhnen möchte.

vielen Dank im Voraus

Sam

p.s. Wenn möglich, können Sie einen Pseudocode für die Lösung des 900.000-Wörter-Problems erstellen. Ich verstehe Code besser als Englisch, und ich nehme an, dass dies für die meisten Besucher dieser Website gilt.

Answer 1

En Problem der Wortanzahl ist eines der am häufigsten behandelten Probleme in der Big-Data-Welt; es ist sozusagen die "Hello World" von Frameworks wie Hadoop. Sie können im Internet zahlreiche Informationen zu diesem Problem finden.

Ich werde Ihnen trotzdem ein paar Gedanken dazu geben.

Erstens könnten 900000 Wörter immer noch klein genug sein, um eine Hashmap zu erstellen, also schließen Sie den offensichtlichen In-Memory-Ansatz nicht aus. Sie sagten, Pseudocode sei in Ordnung, also:

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

Sobald Ihr Datensatz zu groß ist, um eine speicherinterne Hashmap zu erstellen, können Sie die Zählung wie folgt vornehmen:

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

Diese drei Schritte laufen in einer Unix-Pipeline ab. Lassen Sie das Betriebssystem hier die Arbeit für Sie erledigen.

Jetzt, da Sie noch mehr Daten erhalten, möchten Sie Map-Reduce-Frameworks wie Hadoop einsetzen, um die Wortzählung auf Maschinenclustern durchzuführen.

Ich habe gehört, dass bei obszön großen Datenmengen eine verteilte Umgebung nicht mehr hilfreich ist, weil die Übertragungszeit die Zählzeit übersteigt, und in Ihrem Fall der Wortzählung muss alles "sowieso wieder zusammengesetzt werden", so dass man einige sehr ausgeklügelte Techniken anwenden muss, die Sie vermutlich in Forschungsunterlagen finden.

ADDENDUM

Der OP fragte nach einem Beispiel für die Tokenisierung der Eingabe in Java. Hier ist der einfachste Weg:

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());
        }
    } 
}

Hier ist ein Beispiel für die Verwendung dieses Instruments:

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

Diese Ausgaben

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

Sie können diesen Tokenizer mit sort und uniq wie folgt kombinieren:

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

Ausbeute

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

Wenn Sie nur Buchstaben behalten und alle Interpunktionszeichen, Ziffern und andere Zeichen wegwerfen wollen, ändern Sie Ihre Scanner-Definitionszeile in:

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

Und jetzt

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

Ausbeute

hey
moe
nyuk
soitenly
why
woo

In der Ausgabe gibt es eine Leerzeile; ich überlasse es Ihnen, herauszufinden, wie Sie sie beseitigen können :)

Answer 2

Die schnellste Lösung hierfür ist O(n) AFAIK verwenden eine Schleife, um die Zeichenfolge zu iterieren, erhalten das Zeichen und aktualisieren die Anzahl in einer HashMap entsprechend. Am Ende enthält die HashMap alle aufgetretenen Zeichen und eine Zählung aller Vorkommen.

Einige pseduo-Codes (möglicherweise nicht kompilierbar)

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);
}

Answer 3

Es ist schwer, dieses Problem besser zu lösen als mit einer Schleife. IMO ist der beste Weg, diese Art von Vorgang zu beschleunigen, die Arbeitslast in verschiedene Arbeitseinheiten aufzuteilen und die Arbeitseinheiten mit verschiedenen Prozessoren zu verarbeiten (z.B. mit Threads, wenn Sie einen Multiprozessor-Computer haben).

Answer 4

Sie sollten nicht davon ausgehen, dass 900.000 Wörter eine Menge sind. Wenn Sie eine CPU mit 8 Threads und 3 GHZ haben, sind das 24 Milliarden Taktzyklen pro Sekunde ;)

Für das Zählen von Zeichen mit einer int[] wird viel schneller sein. Es gibt nur 65.536 mögliche Zeichen.

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());

druckt

Took 111 ms to count 139,715,647 characters

Selbst die 11-fache Anzahl von Wörtern dauert nur einen Bruchteil einer Sekunde.

Eine viel längere parallele Version ist ein wenig schneller.

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());
}

druckt

Took 45 ms to count 139,715,537 characters

Aber für einen String mit weniger als einer Million Wörtern lohnt es sich wahrscheinlich nicht.

Answer 5

In der Regel sollten Sie die Dinge einfach schreiben und dann die Leistung optimieren, um sie so schnell wie möglich zu machen. Wenn das bedeutet, dass man einen schnelleren Algorithmus einbauen muss, sollte man das tun, aber am Anfang sollte man es einfach halten. Bei einem kleinen Programm wie diesem wird das nicht allzu schwer sein.

Die wichtigste Fähigkeit bei der Leistungsoptimierung ist nicht ahnend . Lassen Sie sich stattdessen vom Programm selbst sagen, was zu tun ist. Das ist meine Methode.

Für umfangreichere Programme, wie dieses Die Erfahrung wird Ihnen zeigen, wie Sie das übermäßige Nachdenken vermeiden können, das am Ende einen Großteil der schlechten Leistung verursacht, die es zu vermeiden versucht.