查找字符串匹配使用Python

我读了一些分析文本文件列表计数，每个字被添加到列表，并给出一个ID查找字符串匹配使用Python

#!/usr/bin/python3 
with fi as myfile: 
    for line in myfile: 
    for item in line.split(' '): 
     db[0].append(id_+1) 
     db[2].append(item) 
     ...more stuff

然后，我在列表中搜索每个字的找其匹配并存储计数为sim1。如果找到匹配项，我测试下一个单词是否与连续匹配，并将其计数存储为sim2。同样适用于sim3。我的代码如下所示：

for i in range(id_-3): 
    sim1=0 
    sim2=0 
    sim3=0 
    for j in range(id_-3): 
    if i==j: continue; 
    if db[2][i] == db[2][j]: 
     sim1 += 1 
     if db[2][i+1] == db[2][j+1]: 
     sim2 += 1 
     if db[2][i+2] == db[2][j+2]: 
      sim3 += 1 
    db[3].append(sim1) 
    db[4].append(sim2) 
    db[5].append(sim3)

这有用，但速度太慢！我相信Python提供更快的搜索方法，但我仍然是一个Py新手！

来源

2013-06-03 Tarek Eldeeb

示例输入/输出？ –

看起来您可以从更改数据存储方式中受益。例如，将其转化为词汇映射（字典）到索引列表。然后你可以检查这些列表中的连续值。根本没有搜索。换一种说法;你不是在寻找更快的Python，你正在寻找更好的算法。 –

只需使用字典！它会让你的生活变得更容易，并且需要更少的代码，并且很可能会加速它的速度。 –

算法的慢度主要来自于你有一个内部循环迭代len（db [2]）次的外部循环中包含的len（db [2]）次。这意味着内部代码执行len（db [2]）^ 2次。例如，如果您的文件很大，并且您解析5000个单词，那么代码将运行5000^2 = 25,000,000次！

因此，解决问题的攻角是找到一种方法来消除或显着降低内部循环的成本。下面是一个示例解决方案，它只需要一次遍历len（db [2]），然后执行第二个单独的循环，通过更小的一组项目进行迭代。第二次迭代中有几个内部循环，但它们的运行次数更少，几乎没有任何成本。

我使用一个约48kb的文本文件定时算法和算法。你的算法在我的电脑上平均约为14秒，我的算法平均为0.6秒。因此，通过消除内部循环，该算法现在速度提高了23倍以上。我还做了其他一些小的优化，比如将比较改为数字而不是文本，并从头开始全尺寸创建存储阵列以避免使用append（）。 Append（）会导致解释器根据需要动态增加数组的大小，这比较慢。

from collections import defaultdict 

# Create zero-filled sim1, sim2, sim3 arrays to avoid append() overhead 
len_ = len(db[2]) - 2 
for _ in range(3): 
    db.append([0] * len_) 

# Create dictionary, containing d['word'] = [count, [indexes]] 
# Do just one full iteration, and make good use of it by calculating 
# sim1 (as 'count') and storing an array of number indexes for each word, 
# allowing for a very efficient loop coming up... 
d = defaultdict(lambda: [0, []]) 
for index, word in enumerate(db[2]): 
    if index < len_: 
     # Accumulate sim1 
     d[word][0] += 1 
    # Store all db[2] indexes where this word exists 
    d[word][1].append(index) 

# Now loop only through words which occur more than once (smaller loop) 
for word, (count, indexes) in d.iteritems(): 
    if count > 1: 
     # Place the sim1 values into the db[3] array 
     for i in indexes: 
      if i < len_: 
       db[3][i] = count - 1 
       # Look for sim2 matches by using index numbers 
       next_word = db[2][i+1] 
       for next_word_index in d[next_word][1]: 
        if next_word_index - 1 != i and next_word_index - 1 in indexes: 
         # Accumulate sim2 value in db[4] 
         db[4][i] += 1 
         # Look for sim3 matches 
         third_word = db[2][i+2] 
         if third_word == db[2][next_word_index + 1]: 
          # Accumulate sim3 value in db[5] 
          db[5][i] += 1

来源

2013-10-06 22:42:30

-2

是的，你正在执行一个字符串比较。这真的很慢。你想要的是将你的字符串编译为一个常规模式。 :)

查看来自python的库文库re。 Python: re

来源

2013-06-03 22:59:00

-1：字符串比较不是“非常慢” - 它比使用re进行简单比较要快......“re”不是有用的建议在这种情况下 –

真的吗？我已经使用编译好的正则表达式搜索了一个文件，其中包含了3M使用字符串比较的更好时间。 –

你使用的模式是什么？ –

查找字符串匹配使用Python

回答

相关问题