Python中的性能任务

Question

我们在我的国家举办奥运会。通常，它们是用爪哇、C或C++编写的。我用了一年左右的时间，他们还包括python等其他语言。 我试图用Python解决前几年的一项任务，名为字母，但我总是失败。任务是编写一个代码，计算相邻字母之间的最小移位数，以将一个字符串转换为另一个字符串

作为输入，您可以得到一个字符串中的字母数，两个字符串中的字母数相同，但顺序不同。一个字符串的长度为2到1000个字母。只有大写字母，它们可以但不必排序，可以重复

下面是一个例子： 7. AABCDDD DDDBCAA

正确的输出应该是16

作为输出，您必须返回单个值，即最小移位数。它必须在5秒内计算输出。 我让它计算正确的输出，但在更长的字符串（比如800000个字母）中，它开始变慢。最长的输入在大约30秒内返回值。还有一个输入，每个单词90万个字母，计算30分钟

在“链接”下，您可以找到测试的所有输入文件： https://oi.edu.pl/l/19oi_ksiazeczka/

单击此链接下载“信件”任务的文件： 十九、我是罗兹维扎尼亚-扎德。照明（I etap）（3.5 MB）

下面是我的密码。我怎样才能加快速度

# import time
import sys

# start = time.time()
def file_reader():
    standard_input=""
    try:
        data = sys.stdin.readlines()
        for line in data:
            standard_input+=line
    except:
        print("An exception occurred")
    return standard_input
def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0
    else:
        a = arr[:len(arr)//2]
        b = arr[len(arr)//2:]
        a, ai = mergeSortInversions(a)
        b, bi = mergeSortInversions(b)
        c = []
        i = 0
        j = 0
        inversions = 0 + ai + bi
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
            inversions += (len(a)-i)
    c += a[i:]
    c += b[j:]
    return c, inversions
def literki():
    words=(file_reader()).replace("\n", "")
    number = int("".join((map(str, ([int(i) for i in list(words) if i.isdigit()])))))
    all_letters = [x for x in list(words) if x not in str(number)]
    name = all_letters[:number]
    anagram = all_letters[number:]
    p=[]
    index=list(range(len(anagram)))
    anagram_dict = {index[i]: anagram[i] for i in range(len(index))} 

    new_dict = {} 
    anagram_counts={}
    for key, value in anagram_dict.items(): 
        if value in new_dict: 
            new_dict[value].append(key) 
        else: 
            new_dict[value]=[key] 
    for i in new_dict: 
        anagram_counts.update({i:new_dict[i]})
    for letter in name:
        a=anagram_counts[letter]
        p.append(a.pop(0))
    print(mergeSortInversions(p)[1])
#>>
literki()   

# end = time.time()
# print(start-end)

因此，为了解释它的部分功能：File_reader：简单地从标准输入读取输入文件。mergeSortInversions（arr）：通常它会对字符串进行排序，但在这里，我希望它返回反转的总和。我自己也没那么聪明，我是在网上找到的，但它确实有用。不幸的是，对于1mln字符串，它大约在10秒钟内完成。在“literki”函数中：首先，我将输入划分为符号数和两个，即使在长单词中也是列表

然后，我制作了一些类似于stacks阵列的功能（如果用英语这样称呼，则不是舒尔）。基本上，我制作了一个字典，每个字母作为键，这些字母的索引作为值列表（如果一个字母出现多次，值将包含该字母的所有索引列表）。在“慢的事情”之前我做的最后一件事是，对于“name”变量中的每个字母，我都提取了相应的索引。到那时为止，每个输入的所有操作都需要大约2秒的时间。现在有两行代码生成了计算结果的剩余时间：-我将索引附加到p=[]列表中，同时从字典的列表中弹出它，这样它就不会再读取另一个相同的字母了。-我根据p=[…]列表计算mergeSortInversions（arr）的移动次数（反转），并将其打印为输出

我知道从底部弹出很慢，但另一方面，我必须从底部创建索引列表（这样我可以从顶部弹出索引），但这需要更长的时间。我也尝试过用deque转换a=[…]，但速度也很慢

Answer 1

我想我应该用遗传算法来解决这个问题。遗传算法并不总是能给出最优解，但它们非常适合在合理的时间内得到可接受的解。对于较小的输入，它们可能是最优的

要点是提出： 1） 一种适应度函数，指定一个数字，指示特定候选解决方案的优劣 2） 一种有性生殖函数，它以一种简单的方式结合了两个候选解的一部分 3） 一个变异函数，它对候选解引入一个小的变化

因此，您只需让这些函数运行，创建一个又一个解决方案，并保留最好的函数—而不是最好的，最好的函数

过了一段时间，找到的最佳解决方案就是你的答案

这里有一个使用遗传算法解决另一个难题的例子，称为房屋抢劫问题。它是用Python编写的： http://stromberg.dnsalias.org/~strombrg/house-robber-problem/