Ich habe es versucht, weil es ein Algorithmusproblem gab, um die Suche nach Zeichenfolgen im Entwicklungslager des Unternehmens zu beschleunigen. Übrigens bin ich ein sogenannter Copy / Paste-Programmierer, der gut darin ist, ähnliche Produkte herzustellen und sie unter Bezugnahme auf bestehende umzugestalten.
Es werden Beispiele, Testdaten und Verarbeitungsergebnisdateien bereitgestellt, die im Voraus mit einigen der folgenden Aufgaben implementiert wurden, die zusammen verborgen sind.
■ Programminhalt
・ Suchen Sie nach mehreren Zeichenfolgen für mehrere Textdateien und geben Sie Folgendes aus -Wie viele zutreffende Zeichenfolgen enthalten sind (Gesamtzahl in mehreren Texten) -Anzahl der Textdateien, die die entsprechende Zeichenfolge enthalten
・ An Eingabeaufforderung oder Windows PowerShell ausführen ・ Geben Sie die folgenden Argumente für "Programm" an Programmordner-Eingabedatei Ausgabedatei Ordner: Speichert Suchzieldateien (Plural) Eingabedatei: Listet die Suchzeichenfolge auf Ausgabedatei: Suchergebnisse
・ Unterscheiden Sie bei der Suche zwischen Groß- und Kleinschreibung, voller Breite und halber Breite ・ Der zu durchsuchende Text und die Suchzeichenfolge sind utf-8.
・ Zeichenkette suchen -150 Fälle in einer Datei, getrennt durch Zeilenumbrüche Suchen Sie nach der Anzahl der Vorkommen in der Datei für alle -Jede Länge von 1 oder mehr Zeichen
- Enthält keine Leerzeichen, Tabulatoren, Zeilenumbrüche und speziellen Symbole -Jede Zeichenkette, die Teil eines Wortes sein kann
・ Suchergebnisse -Ausgabe der Anzahl der Vorkommen in der Reihenfolge des Auftretens der Suchzeichenfolge, getrennt durch Tabulatoren Die Anzahl der Auftritte ist die Summe der Ergebnisse mehrerer Dateien
Stichprobe,
-Anzahl der Textdateien, die die entsprechende Zeichenfolge enthalten
Teil wurde nicht implementiert.
"""
Zählen Sie die Anzahl der Vorkommen der angegebenen Zeichenfolge aus allen Dateien im angegebenen Ordner
Das Ergebnis wird in TSV ausgegeben
python sample1.py text_folder strings_file result_file
"""
import sys
from pathlib import Path
class TextManager:
"""
Klasse, die Informationen in Textdateien verwaltet
"""
def __init__(self, foldername):
'''
Lesen und speichern Sie die Dateien im Ordner
Parameters
----------
foldername : str
Ordnernamen
'''
self.__alllines = []
p = Path(foldername)
for filename in p.iterdir():
with open(filename, 'r', encoding='utf-8') as f:
lines = [s.strip() for s in f.readlines() if s.strip() != '']
self.__alllines.extend(lines)
def search(self, string_list):
'''
Suche
Suchen Sie in der Suchzeichenfolgenliste nach registriertem Text
Parameters
----------
string_list : List[str]
Liste der Suchzeichenfolgen
Returns
-------
Dict[str, int]
Suchergebnisse
'''
result = {}
for s in string_list:
count = self.__search_one(s)
result[s] = count
return result
def __search_one(self, string):
'''
Suchen Sie nach einer Zeichenfolge
Parameters
----------
string : str
Suchbegriff
Returns
-------
int
Anzahl der vorhandenen Suchzeichenfolgen
'''
l = len(string)
count = 0
for line in self.__alllines:
for i in range(0, len(line)-l+1):
if string == line[i:i+l]:
count += 1
return count
if __name__ == "__main__":
args = len(sys.argv)
if args != 4:
print("USAGE: python sample1.py text_folder strings_file result_file")
sys.exit()
text_folder = sys.argv[1]
strings_file = sys.argv[2]
result_file = sys.argv[3]
#Lesen Sie die Zieldateigruppe (Dateien im Ordner).
text_manager = TextManager(text_folder)
#Lesen Sie die Suchzeichenfolge
search_strings = []
with open(strings_file, 'r', encoding='utf-8') as fi:
search_strings = [s.strip() for s in fi.readlines() if s.strip() != '']
#Suchausführung: List[str] -> Dict[str, int]
result = text_manager.search(search_strings)
with open(result_file, 'w', encoding='utf-8') as fo:
#Ausgabe in der in der Suchzeichenfolgendatei beschriebenen Reihenfolge
for s in search_strings:
c = result.get(s, 0)
fo.write("{}\t{}\n".format(s, c))
Es ist sehr aufwändig, die gesamte Logik zu überprüfen. Verwenden Sie als Programmierer zum Kopieren / Einfügen die aktuelle Logik unverändert. Teilen Sie zunächst den Teil, der aus mehreren Dateien gelesen wurde, in jede Datei auf und speichern Sie ihn. Hochgeschwindigkeits-Chips werden in Betracht gezogen.
class TextManager:
"""
Klasse, die Informationen in Textdateien verwaltet
"""
def __init__(self, foldername):
'''
Lesen und speichern Sie die Dateien im Ordner
Parameters
----------
foldername : str
Ordnernamen
'''
self.__alllines = []
__alllines_extend = self.__alllines.extend
p = Path(foldername)
for filename in p.iterdir():
__filelines = []
__filelines_extends = __filelines.extend
with open(filename, 'r', encoding='utf-8') as f:
f_readlines = f.readlines
lines = [s.strip() for s in f_readlines() if s.strip() != '']
__filelines_extends(lines)
self.__alllines.append(__filelines)
Fügen Sie der for-Schleife des Teils, der eine Suchzeichenfolge aus dem Ganzen durchsucht, eine Schleife für jede Datei hinzu, erhöhen Sie die Anzahl der Dateien um 1, wenn die Suchzeichenfolge darin gefunden wird, und schließlich ist die Suchzeichenfolge vorhanden Gibt die Anzahl und die Anzahl der Dateien zurück, in denen die Suchzeichenfolge vorhanden war.
Das auskommentierte print () erinnert daran, dass ich es geändert habe, während ich überprüft habe, ob es richtig funktioniert hat.
def __search_one(self, string):
'''
Suchen Sie nach einer Zeichenfolge
Parameters
----------
string : str
Suchbegriff
Returns
-------
int
Anzahl der vorhandenen Suchzeichenfolgen
int
Anzahl der Dateien, in denen die Suchzeichenfolge vorhanden war
'''
l = len(string)
count = 0
fcount = 0
# print(string, count, fcount)
for filelines in self.__alllines:
# print(filelines)
find = False
for line in filelines:
# print(line)
for i in range(0, len(line)-l+1):
if string == line[i:i+l]:
count += 1
find = True
if find:
fcount +=1
# print(string, count, fcount)
# print(string, count, fcount)
return count, fcount
Die Suchzusammenfassung entspricht dem Abrufen von zwei Rückgabewerten aus der einzelnen Suche.
def search(self, string_list):
'''
Suche
Suchen Sie in der Suchzeichenfolgenliste nach registriertem Text
Parameters
----------
string_list : List[str]
Liste der Suchzeichenfolgen
Returns
-------
Dict[str, int]
Suchergebnisse
Dict[str, int]
Anzahl der Suchergebnisdateien
'''
result = {}
fresult = {}
for s in string_list:
rtn = self.__search_one(s)
result[s] = rtn[0]
fresult[s] = rtn[1]
return result, fresult
Der Ausgabeabschnitt hat dieselbe Unterstützung, daher wird er weggelassen. Jetzt können Sie leicht die richtige Antwort erhalten, was die Mindestanforderung für die Aufgabe ist.
Derzeit wird das gleiche Urteil getroffen, indem jedes Zeichen vom Anfang bis zum Ende der von "__search_one ()" gelesenen Zeile verschoben wird.
Der Punkt ist, wie Sie dies beschleunigen können. Wenn Sie jedoch Blöcke, die keine Nichtzielzeichen enthalten, aus der Zeichenfolge des Suchziels ausschneiden, sollte sich die Übereinstimmungseffizienz erhöhen.
Deshalb wird es durch den Leseteil getrennt. Dies ist der Teil von .split ('[,." "<< >> | [#]]').
Andere Klammern sollten als Ziel ausgewählt werden. Da das Ziel der Zuweisung jedoch die von Aozora Bunko mitgebrachte Datei war, ist dies vorerst ausreichend.
def __init__(self, foldername):
'''
Lesen und speichern Sie die Dateien im Ordner
Parameters
----------
foldername : str
Ordnernamen
'''
self.__alllines = []
__alllines_append = self.__alllines.append
p = Path(foldername)
for filename in p.iterdir():
__filelines = []
__filelines_extends = __filelines.extend
with open(filename, 'r', encoding='utf-8') as f:
f_readlines = f.readlines
lines = [s.strip().split('[、。「」《》｜［＃］]')
for s in f_readlines() if s.strip() != '']
__filelines_extends(lines)
__alllines_append(__filelines)
__Search_one () erhöht auch die Schleife, die dem Schnitzen entspricht.
Es sollte eine Schreibweise geben, die nicht erhöht werden muss, aber vorerst wurde eine Schleife benötigt, wenn es sich um eine Niederlage handelte.
Print () ist nützlich, um sich umzusehen.
Eigentlich waren die Testdaten, die mit der Stichprobe im Voraus verteilt wurden, auf Englisch, also habe ich sie ohne Argument mit "split ()" codiert, aber das funktioniert nicht auf Japanisch. Da das Ergebnis seltsam ist, wurde es beim Drucken Zeichen für Zeichen auf Japanisch gehackt.
Nachdem ich es entfernt hatte, entsprach ich der Anzahl der Dateien und "teilte" mich erneut.
def __search_one(self, string):
'''
Suchen Sie nach einer Zeichenfolge
Parameters
----------
string : str
Suchbegriff
Returns
-------
int
Anzahl der vorhandenen Suchzeichenfolgen
int
Anzahl der Dateien, in denen die Suchzeichenfolge vorhanden war
'''
l = len(string)
count = 0
fcount = 0
# print(string, count, fcount)
for filelines in self.__alllines:
# print(filelines)
find = False
for line in filelines:
# print(line)
for sentence in line:
for i in range(0, len(sentence)-l+1):
if string == sentence[i:i+l]:
count += 1
find = True
# print(sentence, string, sep='\t')
if find:
fcount +=1
# print(string, count, fcount)
# print(string, count, fcount)
return count, fcount
Es ist sehr ineffizient, das Erscheinungsbild von Zeichenketten zu vergleichen, indem sie zeichenweise verschoben werden. Egal wie sehr Sie die Skriptsprache entwickeln, die Geschwindigkeit erhöht sich nicht, wenn Sie sie selbst vergleichen. Wenn Sie mit den Funktionen der Standardbibliothek auskommen, ist das absolut schneller. Ich kannte die Methode von "String in String", lehnte sie jedoch ab, da sie nicht funktionieren würde, wenn sie in einem Ziel mehrmals vorkommen würde. Ich bin nicht sicher in meinem Gedächtnis, also werde ich danach suchen. [Suche nach Google "Python String Match"](https://www.google.com/search?q=python+%E6%96%87%E5%AD%97%E5%88%97+%E3%83 % 9E% E3% 83% 83% E3% 83% 81 & oq = Python +% E3% 83% 9E% E3% 83% 83% E3% 83% 81 & aqs = chrome.2.69i57j0i7i30l2j0j0i7i30j0j0i7i30l2.11559j0j7 & id Oh, es gab eine Funktion, die ich wollte. Suchen Sie mit Python nach einer Zeichenfolge (bestimmen Sie, ob sie ~ enthält, holen Sie die Position ab, zählen Sie) Schreiben Sie den Prozess also in der Mitte von "__search_one" neu.
for line in filelines:
# print(line)
for sentence in line:
# for i in range(0, len(sentence)-l+1):
# if string == sentence[i:i+l]:
c = sentence.count(string)
if c > 0:
count += c
find = True
~~~
Dies beschleunigt die Verarbeitungszeit um eine Größenordnung.
# 6.Überprüfung der Verarbeitung
Wenn Sie die Anzahl der Auftritte des Ziels in einem Schuss finden können, 4.Hinzugefügt in`split`Ist eher eine Ursache für Verlangsamung, da es nur Schleifen erhöht.
Ich muss es nicht mehr schnitzen, also lege ich es zurück.
Hier`__search_one`Ich werde nur drinnen schreiben.
```python
for line in filelines:
# print(line)
c = line.count(string)
if c > 0:
count += c
find = True
countDa Sie die Anzahl der Auftritte in einer Aufnahme mit kennen können, macht es keinen Sinn, Zeile für Zeile zu lesen.
In dieser Ausgabe gibt es keine Begrenzung für die verwendete Speichermenge. Es wird nur der installierte Speicher der Überprüfungsumgebung geschrieben.
Wenn Sie die gesamte Datei lesen, spielt es keine Rolle, ob Sie sie zeilenweise oder dateiweise lesen.
Aus diesem Grund habe ich zum Batch-Lesen von Dateien gewechselt.
Ich hätte den Variablennamen in einen passenderen Namen ändern sollen, aber ich habe nicht wirklich darüber nachgedacht.
def __init__(self, foldername):
'''
Lesen und speichern Sie die Dateien im Ordner
Parameters
----------
foldername : str
Ordnernamen
'''
self.__alllines = []
__alllines_extend = self.__alllines.extend
p = Path(foldername)
for filename in p.iterdir():
with open(filename, 'r', encoding='utf-8') as f:
lines = f.read()
self.__alllines.append(lines)
Der eigentliche Suchteil ist einfach
def __search_one(self, string):
'''
Suchen Sie nach einer Zeichenfolge
Parameters
----------
string : str
Suchbegriff
Returns
-------
int
Anzahl der vorhandenen Suchzeichenfolgen
int
Anzahl der Dateien, in denen die Suchzeichenfolge vorhanden war
'''
count = 0
fcount = 0
# print(string, count, fcount)
for lines in self.__alllines:
c = lines.count(string)
if c > 0:
count += c
fcount += 1
# print(string, count, fcount)
# print(string, count, fcount)
return count, fcount
Dies ist 116-mal schneller als die erste richtige Antwort.
Da es sich um ein Algorithmusproblem handelt, hätten wir eine Matching-Methode entwickeln sollen.
Eigentlich,countEinige Leute haben Code geschrieben, der die Hälfte der Zeit des ersten Codes benötigt, ohne ihn zu verwenden.
Selbst wenn Sie verschiedene Algorithmen in der Skriptsprache entwickeln, können Sie die Funktionen der Bibliothek, deren Inhalt in C geschrieben ist, nicht übertreffen.
Wenn Sie wissen, ob die richtige Bibliothek vorhanden ist, werden Sie schnell die richtige Antwort finden.
Tatsächlich gab es eine Person, die durch die Teilnahme an der Mitte im Handumdrehen eine Größenordnung erhielt, und von dort aus dachte ich über verschiedene Dinge nach und suchte und erreichte den Endpunkt.
Ich würde gerne wissen, welche Art von Methode ein Algorithmus ist, der in der Hälfte der Zeit verarbeitet, ohne mit der Bibliotheksfunktion zu wechseln.
Recommended Posts