Je l'ai essayé car il y avait un problème d'algorithme pour accélérer la recherche de chaînes de caractères au camp de développement de l'entreprise. Au fait, je suis un programmeur soi-disant copier / coller qui sait fabriquer des produits similaires et les refactoriser par rapport à ceux existants.
Des échantillons et des données de test implémentés à l'avance avec certaines des tâches suivantes cachées et cachées ensemble, et leurs fichiers de résultats de traitement seront fournis.
■ Contenu du programme
・ Recherchez plusieurs chaînes de caractères pour plusieurs fichiers texte et affichez les éléments suivants -Combien de chaînes de caractères applicables sont incluses (nombre total dans plusieurs textes) -Nombre de fichiers texte contenant la chaîne de caractères correspondante
・ Exécuter sur l'invite de commande ou Windows PowerShell ・ Spécifiez les arguments suivants pour "programme" Fichier de sortie du fichier d'entrée du dossier programme Dossier: stocke les fichiers cibles de recherche (pluriel) Fichier d'entrée: liste la chaîne de caractères de recherche Fichier de sortie: résultats de la recherche
・ Lors de la recherche, faites la distinction entre les majuscules et les minuscules, pleine largeur et demi-largeur ・ Le texte à rechercher et la chaîne de caractères de recherche sont utf-8.
・ Recherche chaîne de caractères -150 cas dans un fichier, séparés par des sauts de ligne Rechercher le nombre d'occurrences dans le fichier pour toutes -Toute longueur de 1 ou plusieurs caractères -Ne comprend pas les blancs, les tabulations, les sauts de ligne, les symboles spéciaux -Toute chaîne de caractères pouvant faire partie d'un mot
・ Résultats de la recherche -Sortir le nombre d'occurrences dans l'ordre d'apparition de la chaîne de caractères de recherche, séparés par des tabulations Le nombre d'apparitions est la somme des résultats de plusieurs fichiers
échantillon,
-Nombre de fichiers texte contenant la chaîne de caractères correspondante
Une partie n'a pas été mise en œuvre.
"""
Compter le nombre d'occurrences de la chaîne de caractères spécifiée à partir de tous les fichiers du dossier spécifié
Le résultat est sorti dans TSV
python sample1.py text_folder strings_file result_file
"""
import sys
from pathlib import Path
class TextManager:
"""
Classe qui gère les informations dans les fichiers texte
"""
def __init__(self, foldername):
'''
Lisez et stockez les fichiers dans le dossier
Parameters
----------
foldername : str
Nom de dossier
'''
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):
'''
Chercher
Rechercher du texte enregistré dans la liste des chaînes de recherche
Parameters
----------
string_list : List[str]
Liste des chaînes de recherche
Returns
-------
Dict[str, int]
Résultats de recherche
'''
result = {}
for s in string_list:
count = self.__search_one(s)
result[s] = count
return result
def __search_one(self, string):
'''
Rechercher une chaîne
Parameters
----------
string : str
Chaîne de recherche
Returns
-------
int
Nombre de chaînes de recherche existantes
'''
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]
#Lire le groupe de fichiers cible (fichiers dans le dossier)
text_manager = TextManager(text_folder)
#Lire la chaîne de recherche
search_strings = []
with open(strings_file, 'r', encoding='utf-8') as fi:
search_strings = [s.strip() for s in fi.readlines() if s.strip() != '']
#Exécution de la recherche: List[str] -> Dict[str, int]
result = text_manager.search(search_strings)
with open(result_file, 'w', encoding='utf-8') as fo:
#Sortie dans l'ordre décrit dans le fichier de chaîne de recherche
for s in search_strings:
c = result.get(s, 0)
fo.write("{}\t{}\n".format(s, c))
Il faut beaucoup d'efforts pour revoir toute la logique, donc en tant que programmeur copier / coller, utilisez la logique actuelle telle qu'elle est. Commencez par diviser la partie qui a été lue à partir de plusieurs fichiers dans chaque fichier et enregistrez-la. Une certaine considération est accordée aux puces à grande vitesse.
class TextManager:
"""
Classe qui gère les informations dans les fichiers texte
"""
def __init__(self, foldername):
'''
Lisez et stockez les fichiers dans le dossier
Parameters
----------
foldername : str
Nom de dossier
'''
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)
Ajoutez une boucle pour chaque fichier à la boucle for de la partie qui recherche une chaîne de recherche dans l'ensemble, augmentez le nombre du fichier de 1 lorsque la chaîne de recherche y est trouvée, et enfin la chaîne de recherche existait Renvoie le nombre et le nombre de fichiers dans lesquels la chaîne de recherche existait.
Le commentaire print () est un rappel que je l'ai modifié tout en vérifiant s'il fonctionnait correctement.
def __search_one(self, string):
'''
Rechercher une chaîne
Parameters
----------
string : str
Chaîne de recherche
Returns
-------
int
Nombre de chaînes de recherche existantes
int
Nombre de fichiers dans lesquels la chaîne de recherche existait
'''
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
Le résumé de la recherche correspond à l'obtention de deux valeurs de retour à partir d'une recherche individuelle.
def search(self, string_list):
'''
Chercher
Rechercher du texte enregistré dans la liste des chaînes de recherche
Parameters
----------
string_list : List[str]
Liste des chaînes de recherche
Returns
-------
Dict[str, int]
Résultats de recherche
Dict[str, int]
Nombre de fichiers de résultats de recherche
'''
result = {}
fresult = {}
for s in string_list:
rtn = self.__search_one(s)
result[s] = rtn[0]
fresult[s] = rtn[1]
return result, fresult
La section de sortie a le même support, elle est donc omise. Maintenant, vous pouvez facilement obtenir la bonne réponse, qui est l'exigence minimale pour la tâche.
Actuellement, le même jugement est fait en décalant chaque caractère du début à la fin de la ligne lue par __search_one ().
Le problème est de savoir comment accélérer cela, mais si vous supprimez des blocs qui ne contiennent pas de caractères non cibles dans la chaîne de caractères cible de la recherche, l'efficacité de la correspondance devrait augmenter.
C'est pourquoi il est séparé par la partie lecture. C'est la partie de .split ('[,." "<< >> | [#]]').
D'autres parenthèses doivent être ciblées, mais comme la cible de l'affectation était le fichier importé d'Aozora Bunko, cela est suffisant pour le moment.
def __init__(self, foldername):
'''
Lisez et stockez les fichiers dans le dossier
Parameters
----------
foldername : str
Nom de dossier
'''
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 () augmente également la boucle correspondant au découpage.
Il devrait y avoir un moyen de l'écrire qui n'a pas besoin d'être augmenté, mais pour le moment, une boucle était nécessaire s'il s'agissait d'une méthode de défaite.
Print () est utile pour vérifier.
En fait, les données de test qui ont été distribuées avec l'échantillon à l'avance étaient en anglais, donc je les ai codées avec split () sans argument, mais cela ne fonctionne pas en japonais. Puisque le résultat est étrange, quand j'imprime, il a été haché caractère par caractère en japonais.
Donc, une fois que je l'ai enlevé, j'ai correspondu au nombre de fichiers, puis j'ai à nouveau «divisé».
def __search_one(self, string):
'''
Rechercher une chaîne
Parameters
----------
string : str
Chaîne de recherche
Returns
-------
int
Nombre de chaînes de recherche existantes
int
Nombre de fichiers dans lesquels la chaîne de recherche existait
'''
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
Il est très inefficace de comparer l'apparence des chaînes de caractères en les décalant caractère par caractère.
Peu importe combien vous concevez le langage de script, la vitesse n'augmentera pas si vous le comparez vous-même.
Si vous pouvez gérer avec les fonctions de la bibliothèque standard, c'est absolument plus rapide.
Je connaissais la méthode de String in String, mais je l'ai rejetée car elle ne fonctionnerait pas si elle apparaissait plusieurs fois dans une cible.
Je n'ai pas confiance en ma mémoire, alors je vais la chercher.
[Recherche par google "correspondance de chaîne python"](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 & sourceid = chrome & ie
Oh, il y avait une fonction que je voulais.
Rechercher une chaîne de caractères avec Python (déterminer si elle contient, obtenir la position, le nombre)
Alors, réécrivez le processus au milieu de __search_one.
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
~~~
Cela accélère le temps de traitement d'un ordre de grandeur.
# 6.Examen du traitement
Lorsque vous pouvez trouver le nombre d'apparitions de la cible en un seul coup, 4.Ajouté dans`split`Est plutôt une cause de ralentissement car il ne fait qu'augmenter les boucles.
Je n'ai plus besoin de le sculpter, alors je vais le remettre.
ici`__search_one`Je n'écrirai qu'à l'intérieur.
```python
for line in filelines:
# print(line)
c = line.count(string)
if c > 0:
count += c
find = True
countPuisque vous pouvez connaître le nombre d'apparitions en une seule prise de vue, il est inutile de lire ligne par ligne.
Dans ce problème, il n'y a pas de limite sur la quantité de mémoire utilisée, seule la mémoire installée de l'environnement de vérification est écrite.
Si vous lisez le fichier entier, cela ne fait aucune différence que vous le lisez ligne par ligne ou par fichier.
C'est pourquoi j'ai opté pour la lecture par lots de fichiers.
J'aurais dû changer le nom de la variable en quelque chose de plus approprié, mais je n'y ai pas vraiment pensé.
def __init__(self, foldername):
'''
Lisez et stockez les fichiers dans le dossier
Parameters
----------
foldername : str
Nom de dossier
'''
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)
La partie de recherche réelle est simple
def __search_one(self, string):
'''
Rechercher une chaîne
Parameters
----------
string : str
Chaîne de recherche
Returns
-------
int
Nombre de chaînes de recherche existantes
int
Nombre de fichiers dans lesquels la chaîne de recherche existait
'''
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
C'est 116 fois plus rapide que la première bonne réponse.
Puisqu'il s'agit d'un problème d'algorithme, nous aurions dû concevoir une méthode d'appariement.
En réalité,countCertaines personnes ont écrit du code qui prendrait la moitié du temps du premier code sans utiliser.
Cependant, même si vous concevez divers algorithmes dans le langage de script, vous ne pouvez pas battre les fonctions de la bibliothèque dont la substance est écrite en C.
Si vous savez si la bonne bibliothèque existe, vous atteindrez rapidement la bonne réponse.
En fait, il y avait une personne qui a obtenu un score d'ordre de grandeur en un clin d'œil en participant au milieu, et à partir de là j'ai pensé à diverses choses et j'ai cherché et j'ai atteint le point final.
Je voudrais savoir quel type de méthode est un algorithme qui traite en deux fois moins de temps sans se déplacer avec la fonction de bibliothèque.
Recommended Posts