元素成本模型Python中的排序算法

Question

1.任务

使用标准输入，我读取了四行数据：

• 元素数(元素编号从1到n)
• 与移动每个元素的成本相对应的n个数
• 每个元素当前位置对应的n个数字(从1到n)
• N个数字，对应于每个元素在所需状态下的位置(从1到n)

我可以交换我想要的每两个元素。每项操作的成本是这两个要素的质量之和。程序必须返回将元素移动到所需状态所需的最低成本。使用标准输入(my_script.py

2.我的问题

我知道解决这个问题的理想理论解决方案，我创建了工作的python脚本，但它是混乱和缓慢的。我确信将数据转换为int值的方式是愚蠢的，但我必须知道如何改进它。我不确定用我所做的方式将列表划分为循环是否还可以，或者它也可以改进(graf是定向的，但我认为这并不重要)

method_1和method_2在数学上是正确的，我不会浪费你的时间来解释原因，尽管我不确定我是否正确地实现了它。

我对这个任务的几乎所有方面都很陌生(数据结构、标准输入等等)。密码乱七八糟。

3.代码

输入文件：

10
3015 4728 4802 4361 135 4444 4313 1413 4581 546
3 10 1 8 9 4 2 7 6 5
4 9 5 3 1 6 10 7 8 2

我写的剧本：

#! /usr/bin/python3
import sys

lines = []

for line in sys.stdin:
    stripped = line.strip()
    if not stripped:
        break
    lines.append(stripped)

a, b, c, d = lines

a = a.split(" ")
b = b.split(" ")
c = c.split(" ")
d = d.split(" ")

masses = [int(i) for i in b]
unsorted = [int(i) for i in c]
sorted = [int(i) for i in d]


def dfs_test(masses, unsorted, sorted):
    segregated = []
    cycles = []
    cost = 0
    for index, element in enumerate(unsorted):
        cycle = []
        if element in segregated:
            continue
        if not sorted[index] == element:
            while element not in cycle:
                cycle.append(element)
                segregated.append(element)
                index = sorted.index(element)
                element = unsorted[index]
        else:
            cycle.append(element)
        cycles.append(cycle)
    for cycle in cycles:
        if len(cycle) == 2:
            for element in cycle:
                cost += masses[element-1]
        if len(cycle) >= 3:
            sum_mass_cycle = []
            for element in cycle:
                sum_mass_cycle.append(masses[element-1])
            method_1 = sum(sum_mass_cycle) + (len(cycle) - 2) * min(sum_mass_cycle)
            method_2 = sum(sum_mass_cycle) + min(sum_mass_cycle) + (len(cycle) + 1) * min(masses)
            cost += min(method_1, method_2)
    return cost


if __name__ == "__main__":
    print(dfs_test(masses, unsorted, sorted))

Answer 1

样式:解析文件

在这里，严格地期望事物的格式是正确的，这是可以的。不应该有空行(或者可能的话，在末尾总是有一个空行)，所以if检查看起来是不相关的。你的原作也不错，但我个人会把它缩短为：

lines = [line.rstrip() for line in sys.stdin]

放下a，b，c和d。它们是不清楚的名字，这段代码是重复的。重复是敌人：

line_numbers = [[int(i) for i in line.split()] for line in line_parts]
(expected_length,), masses, unsorted, sorted = line_numbers
assert expected_length == len(masses) == len(unsorted) == len(sorted)

如果嵌套太多，您可以将line_numbers的定义拆分为parse_line函数。

您的输入是1索引的，但是python是0索引的。停止使用element-1 everywhere，并在早些时候修复它。这使得代码稍微长了一些，但更易读，而且不太容易出错。

sorted = [i-1 for i in sorted]
unsorted = [i-1 for i in unsorted]

sorted是内置函数的名称，您可以从这里的语法突出显示中看出这一点。它不会导致您使用名称的任何问题，但它可能会混淆读者。由你决定是否留着它。常见的更改可能是调用变量sorted_。

以上各点均应在主护栏内。

最后的主要警卫是：

import sys

if __name__ == '__main__':
    # Parse stdin
    lines = [line.strip() for line in sys.stdin]
    line_numbers = [[int(i) for i in line.split()] for line in line_parts]
    (expected_length,), masses, unsorted, sorted = line_numbers
    assert expected_length == len(masses) == len(unsorted) == len(sorted)

    # Switch to 0-indexing
    sorted = [i-1 for i in sorted]
    unsorted = [i-1 for i in unsorted]

    print(dfs_test(masses, unsorted, sorted))

风格: dfs_test

总的来说，除了数学解释之外，这看起来相当清楚。

总的来说，我要说的是，添加更多关于代码意图的注释(特别是代码的部分，例如“添加包含此元素的循环”)。这不是简单的代码。

自行车建造：

• 该循环生成算法是优秀的。它写得很清楚，而且可以很容易地调整，使之快速。
• 我会将循环构建分解成它自己的函数，它接受unsorted和sorted并返回循环。这使它更加清晰(为该部分提供了一个标签)，并向读者展示了这两个变量是唯一的依赖项，并且不在其他地方使用。
• segregated不是一个明确的名称。在定义点添加注释(这是已经放入cycles或当前活动构建周期的元素)。

在成本计算器中：

• 将if-if改为if-elif，这是更好的样式
• 明确1长度周期的情况(作为空的if分支或注释)
• 将定义cost = 0移到成本部分
• 考虑将成本计算器分解成它自己的功能。

算法加速

这比它可能的速度要慢。你应该知道--不要依赖别人来告诉你。测量算法的速度。

1. 你可以盯着它看，这实际上是解决或理解问题的最好方法。
2. 或者用实验来测量，这是检测问题的最好方法。通过查看输入大小加倍会改变运行时。如果它加倍，它是O(N)，如果它增加了4X，它是O(N^2)，如果它做了一些更糟糕的事情，想想你是否刚刚用完了RAM等等。如果你想要找出为什么某些东西在实验上是慢的，就开始分析。

现在，您可能只打算在20个元素列表上运行它，在这种情况下，您不应该关心，并且可以忽略下面的所有内容。但是，如果您想要一个快速运行时(如果这是一个算法问题(看起来是这样，或者您实际上需要在大型输入上运行这个问题)，那么您应该加快速度。

• 我相信这是目前的O(N^2)算法，循环查找是唯一的O(N^2)步骤。
• sorted.index是一个缓慢的操作。列表查找可以进行O(N)扫描，在最坏的情况下，每个元素都要执行一次。您可以通过添加一个预处理步骤来加快循环构建，在该步骤中，您可以反向排列以加快查找速度。inverse_sorted = {p: i for i,p in enumerate(sorted)}。
• 将segregated更改为一组。if element in segregated也是O(N)时间。
• 这两个变化应该使循环建设O(N).
• 我相信成本计算应该已经是O(N)了。通过计算sum(sum_mass_cycle)和min(sum_mass_cycle)来加快速度，而不是为每个方法计算一次。

最后注

上面所有的代码都是直接输入到codereview.stackexchange中的，没有经过测试，你就可以放心了！