我被要求查找给定字符串中出现的子字符串(不区分大小写,带/不带标点符号(的总数。一些例子:
count_occurrences("Text with", "This is an example text with more than +100 lines") # Should return 1
count_occurrences("'example text'", "This is an 'example text' with more than +100 lines") # Should return 1
count_occurrences("more than", "This is an example 'text' with (more than) +100 lines") # Should return 1
count_occurrences("clock", "its 3o'clock in the morning") # Should return 0
我选择了regex而不是.count()
,因为我需要一个精确的匹配,结果是:
def count_occurrences(word, text):
pattern = f"(?<![a-z])((?<!')|(?<='')){word}(?![a-z])((?!')|(?=''))"
return len(re.findall(pattern, text, re.IGNORECASE))
我得到了所有匹配的计数,但我的代码占用了0.10secs
,而预期时间是0.025secs
。我是不是错过了什么?有什么更好的(性能优化的(方法可以做到这一点吗?
好吧,我很难在没有正则表达式的情况下让它工作,因为我们都知道正则表达式很慢。以下是我的想法:
def count_occurrences(word, text):
spaces = [' ', 'n', '(', '«', 'u201d', 'u201c', ':', "''", "__"]
endings = spaces + ['?', '.', '!', ',', ')', '"', '»']
s = text.lower().split(word.lower())
l = len(s)
return sum((
(i == 0 and (s[0] == '' or any(s[i].endswith(t) for t in spaces)) and (s[1] == '' or any(s[i+1].startswith(t) for t in endings)))
or (i == l - 2 and any(s[i].endswith(t) for t in spaces) and (s[i+1] == '' or any(s[i+1].startswith(t) for t in endings)))
or (i != 0 and i != l - 2 and any(s[i].endswith(t) for t in spaces) and any(s[i+1].startswith(t) for t in endings))
) for i in range(l - 1))
整个文件以videone运行:
Ran 1 test in 0.025s
OK
这就是问题所要求的。
逻辑很简单。让我们将text
除以word
,两者都是小写。现在让我们看看每对邻居。例如,如果索引0以一个有效的分隔符结束,而索引1以一个合法的分隔符开始,那么让我们将其算作一次出现。让我们一直做到最后几次分手。
由于性能在这里很重要,我们必须注意spaces
和endings
的顺序。我们基本上是在寻找名单中第一个符合条件的人。因此,首先找到更常见的变量是很重要的。例如,如果我声明:
spaces = ['(', '«', 'u201d', 'u201c', ':', "''", "__", 'n', ' ']
我得到的不是解决方案中的内容,而是0.036
秒。
例如,如果我声明一个数组:
spaces = [' ', 'n', '(', '«', 'u201d', 'u201c', ':', "''", "__", '?', '.', '!', ',', ')', '"', '»']
它有所有的分隔符,只使用它,我得到0.053秒。这比我的解决方案多60%。
以另一种顺序声明分隔符可能有更好的解决方案
如果你搜索的单词是定义的和有限的,那么通过re.compile
预编译regex可以帮助加快速度。类似于:
search_words = [
'foo',
'bar',
'baz',
]
words_to_re = {w: re.compile(f"(?<![a-z])((?<!')|(?<='')){w}(?![a-z])((?!')|(?=''))") for w in search_words}
def count_occurrences(word, text):
regex = words_to_re[word]
return len(regex.findall(text))
您可以使用string.lower((函数手动将所有单词变为小写。检查一下,也许这会对你有所帮助:
def count_occurrences2(word, text):
text = text.lower()
word = word.lower()
pattern = f"(?<![a-z])((?<!')|(?<='')){word}(?![a-z])((?!')|(?=''))"
return len(re.findall(pattern, text))
我使用timeit库检查了执行时间:
import timeit
def checkTime(word, text, function):
now = timeit.default_timer()
function("more than", lines)
return timeit.default_timer()-now
text = "This is an example 'text' with (more than) +100 lines "*1000
word = "more than"
time_0 = checkTime("more than",text, count_occurrences)
time_1 = checkTime("more than",text, count_occurrences2)
print(time_0)
print(time_1)
print(time_1 < time_0) //true
编辑:
这是另一种方式:
def count_occurences_in_text(word, text):
pattern = r"(?<![a-z])((?<!')|(?<=''))"+str(word.lower())+"(?![a-z])((?!')|(?=''))"
line_now = text.lower()
count = 0
search = re.search(pattern, line_now)
while search:
count +=1
line_now = line_now[search.span()[1]:]
search = re.search(pattern,line_now)
return count
编辑2:
此函数将传递代码中的所有断言(考虑执行时间(:
def count_occurences_in_text(word, text):
text = text.lower()
word = word.lower()
word_len = len(word)
text_len = len(text)
if not (word[0] >= 'a' and word[0] <= 'z') :
word = word[1:word_len]
if not (word[len(word) - 1] >= 'a' and word[len(word) - 1] <= 'z') :
word = word[1:len(word)-1]
count = 0
index = 0
have = [' ', ",","!","?",".","n",":"]
haveP = [' ',':']
if word_len > text_len:
return 0;
while index < text_len-word_len+1:
if text[index:index+word_len] == word:
if index != 0:
prev_word = text[index-1]
# if (prev_word >= 'a' and prev_word <= 'z') or prev_word == "'":
if prev_word not in haveP:
if index > 1 and text[index-1] =="'" and text[index-2]=="'":
count+=1
index += word_len+1
continue
if index > 1 and text[index-1] =="_" and text[index-2]=="_":
count+=1
index += word_len+1
continue
else:
index += 1
continue
if index + word_len <= text_len-1:
last_word = text[index+word_len]
# if (last_word >= 'a' and last_word <= 'z') or last_word == "'":
if last_word not in have:
if index+word_len <= text_len-2 and last_word =="'" and text[index+word_len+1]=="'":
count +=1
index += word_len+1
continue
if index+word_len <= text_len-2 and last_word =="_" and text[index+word_len+1]=="_":
count +=1
index += word_len+1
continue
else:
index += 1
continue
count += 1
index += word_len+1
index += 1
return count
使用正则表达式拆分
def count_occurrences(search_word,text):
alist=re.split(r's+',text)
matches=[word for word in alist if word==search_word]
return len(matches)
count_occurrences("clock", "its 3o'clock in the morning")
输出
0
第一个错误是使用单词"Python";以及";性能;在同一句话中。Python在很大程度上是朝着";廉价——快速开发代码;用";良好——按预期运行";可行。快速是正确的。这里的任何建议都严格取决于执行情况。
-
您可以清理正则表达式。我建议使用组快捷方式
b
(单词边界(。在所有情况下,我强烈建议您在regex101或等效版本中以交互方式使用regex。 -
您可以用Python编写自己的搜索函数。在Python中运行会更慢,跳过匹配存储和其他通用性会更快。
-
您可以将您的速度与简单字符串
.count()
进行比较。您将需要使用CCD_ 12并决定单词";这个";匹配";sthisany";是否。 -
您可以将测试函数修改为实际有一百行,例如
text = (text + 'n')*100
。 -
您可以使用PyPi,它通常会通过牺牲一些启动正常运行时间和一些元编程灵活性来加快执行速度。
-
您可以编写一小段C代码,并学习从Python中调用它。本身就很有趣。
我建议你做好笔记和比较,并将它们与你的家庭作业一起交出来,而不仅仅是最终产品。