Dies ist eine Interviewfrage, und sollte sich auf Effizienz beziehen. Wie berechnet man das Vorkommen eines bestimmten Wortes in einer großen Textdatei? Ich kann nur an die Methode indexOf() in den meisten Programmiersprachen denken, aber ich denke nicht, dass die richtige Antwort.Berechnen Sie das Vorkommen des angegebenen Wortes in einer großen Textdatei
Was Sie wollen, ist die Boyer-Moore algorithm. Es ist die effizienteste bekannte allgemeine Methode für dieses Problem.
Der beste Weg, ein Wort Vorkommen zu identifizieren, da nur als Teil einer Zeile der Datei auftreten, zu dieser Folge von Zeichen gegenüber, mit einem regulären Ausdruck ist wahrscheinlich Pattern von \bword\b zusammengestellt - die \b sind „Wort Grenzen".
Sobald Sie diese Pattern haben gibt es keine direkte Methode, um die Anzahl der Vorkommen in einer Zeile zu zählen, so dass Sie einen Benchmark benötigen, um herauszufinden, was schneller ist - a split (die Länge des resultierenden Arrays von Strings minus ein), nicht wahrscheinlich, aber möglich, oder eine Matcher mit der matcher Methode des Musters dann Schleifen auf seine find Methode während des Zählens (ich wette auf diese), oder etwas anderes wieder. Aber das Erkennen von Wortgrenzen alleine reicht für eine PITA, die dazu tendiert, immer reguläre Ausdrücke zu verwenden ;-).
Es ist möglich, etwas Geschwindigkeit durch das Lesen (und Zählen von Wortvorkommen) mehr als eine Zeile pro Zeiteinheit - sagen wir mal MB - zu erreichen. Aber wenn Sie das tun, dann müssen Sie auf die letzte "teilweise" Linie im Megabyte-Schluck achten, da ein Vorkommen des Wortes möglicherweise zwischen dem Ende dieser Teillinie und dem Beginn des nächsten Schluckes aufgeteilt werden kann - machbar , aber die Art der Optimierung tut man einfach unter Zwang, da es so einfach ist, einen Bug einzuführen ;-).
+1 für Ihre Antwort gute Idee, aber einige Code wäre auch schön: D – ant
Wenn die Textdatei wirklich groß ist, ist indexOf() möglicherweise keine gute Idee, weil Sie die ganze Datei in eine Zeichenfolge laden und daher Speicher aufzehren müssten. Bei genügend Daten würde das Programm abstürzen. Ich denke, Sie müssten in die Stream-Lese-APIs schauen, um die Datei in Chunks zu lesen, die mit indexOf() praktischer zu scannen sind.
Die Datei unter Verwendung von buffered stream char-by-char in Array lesen, bis Leerzeichen Zeichen oder Gruppe von ihnen (Leerzeichen, Tabs, neue Zeilen, ...), Inhalt des Arrays mit Zielwort vergleichen, Zähler erhöhen, wenn übereinstimmen , löschen Sie das Array, kehren Sie zum Lesen zurück.
Array mit ausreichender Größe vorbelegen und zum Lesen wiederverwenden, bei Bedarf vergrößern, nicht bei jeder Iteration zuweisen. Löschen Sie das Array nicht jedes Mal, sondern setzen Sie seinen Lesezähler auf Null.
Sie können auch das Lesen von Char kombinieren und es mit dem Ziel in einzelne Schleife vergleichen, wodurch die Notwendigkeit eines Zwischenarrays beseitigt wird. Die erste Variante ist leicht in diese umwandelbar, wirf einfach das Array weg und vergleiche im Fluge, du musst nur das aktuelle Char und seine Position im Wort wissen.
Ja, ich erinnere mich nicht an diesen Algorithmus, bis du es erwähnt hast. – Sawyer