Python加速语料库文档相似度计算

Question

我的输入是这种(spintax)格式的字符串，

"The {PC|Personal Computer|Desktop} is in {good|great|fine|excellent} condition"

然后使用 itertools，我生成所有可能的组合。 例如

"The PC is in good condition"
"The PC is in great condition"
.
.
.
"The Desktop is in excellent condition"

在这些字符串中，我只想根据相似度阈值保留最独特的字符串，例如只保留相似度小于 60% 的字符串。我用了SequenceMatcher库，但由于循环，它不适用于大型数据集(250K+ 项)。这是当前的实现，

def filter_descriptions(descriptions):
    MAX_SIMILAR_ALLOWED = 0.6  #40% unique and 60% similar
    i = 0
    while i < len(descriptions):
        print("Processing {}/{}...".format(i + 1, len(descriptions)))
        desc_to_evaluate = descriptions[i]
        j = i + 1
        while j < len(descriptions):
            similarity_ratio = SequenceMatcher(None, desc_to_evaluate, descriptions[j]).ratio()
            if similarity_ratio > MAX_SIMILAR_ALLOWED:
                del descriptions[j]
            else:
                j += 1
        i += 1
    return descriptions

我(几乎)每次迭代都会缩短列表，以加快流程。但我绝对需要一个更快的算法来解决这个问题。我也尝试了 Cosine Similarity，但遇到了缩放问题。它适用于大约 10K 个项目，但超过它就卡在了我的机器上。 这是实现，

from sklearn.metrics.pairwise import cosine_similarity
tfidf_vectorizer = TfidfVectorizer()
tfidf_matrix = tfidf_vectorizer.fit_transform(descriptions)
val = cosine_similarity(tfidf_matrix[:10000], tfidf_matrix[:10000])

对此有什么优化的解决方案吗？我只想从列表中选择 n 个最独特的字符串。

Answer 1

可以优化的一件事是您对 del 的使用。现在你执行了很多次 del，虽然我不知道 Python 如何处理这个问题，但我认为使用一个 del 语句的解决方案更好，因为我相信 Python 必须为每个执行的 del 创建一个新列表。

所以我决定测试这个方法:

import time
import argparse

def test1(long_list, max_num):
    """
    Removing values from a list with delete every step in the loop
    """
    i = 0
    while i < len(long_list):
        if long_list[i] > max_num:
            del long_list[i]
        else:
            i += 1
    return long_list


def test2(long_list, max_num):
    """
    Removing values from a list with delete, lastly after swapping values into the back of the array - marked as garbage
    """
    garbage_index = len(long_list) - 1
    i = 0
    while i <= garbage_index:
        if long_list[i] > max_num:
            long_list[i],long_list[garbage_index] =  long_list[garbage_index], long_list[i]
            garbage_index -= 1
        else:
            i += 1

    del long_list[garbage_index + 1 :]
    return long_list


def get_args():
    """
    Fetches needed arguments for test1() and test2()
    """
    parser = argparse.ArgumentParser()
    parser.add_argument("list_size", help="Set the size of the list.", type=int)
    parser.add_argument("max_element", help="Set max-element value.", type=int)

    return parser.parse_args()


if __name__ == '__main__':
    """
    Simply times the two test functions and prints the time difference
    """
    args = get_args()
    long_list = [x for x in range(args.list_size) ]
    print("Using list size {}".format(args.list_size))

    start = time.time()
    test1(long_list, args.max_element)
    end1 = time.time()
    test2(long_list, args.max_element)
    end2 = time.time()

    print("test1:",end1-start)
    print("test2:",end2-end1)

并为您提供了一些有趣的结果:

$ python3 Code/Playground/stackoverflow/pyspeedup.py 10 5
Using list size 10
test1: 4.5299530029296875e-06
test2: 2.384185791015625e-06
$ python3 Code/Playground/stackoverflow/pyspeedup.py 100 50
Using list size 100
test1: 1.71661376953125e-05
test2: 5.9604644775390625e-06
$ python3 Code/Playground/stackoverflow/pyspeedup.py 1000 500
Using list size 1000
test1: 0.00022935867309570312
test2: 4.506111145019531e-05
$ python3 Code/Playground/stackoverflow/pyspeedup.py 10000 5000
Using list size 10000
test1: 0.006038665771484375
test2: 0.00046563148498535156
$ python3 Code/Playground/stackoverflow/pyspeedup.py 100000 5000
Using list size 100000
test1: 2.022616386413574
test2: 0.0004937648773193359
$ python3 Code/Playground/stackoverflow/pyspeedup.py 1000000 5000
Using list size 1000000
test1: 224.23923707008362
test2: 0.0005621910095214844
$ python3 Code/Playground/stackoverflow/pyspeedup.py 10000000 5000
Using list size 10000000
test1: 43293.87373256683
test2: 0.0005309581756591797

test2() 解决方案也不创建新的垃圾列表，而是在同一个列表中使用内存交换 - 从而节省空间和时间。

希望这有助于实现更优化的算法。