3

我想实现与第三版 CLRS 的问题 2-4 相关的 python 代码。问题是第 41 页中的“查找列表中的Inversion的数量”，我编写了以下代码：

mainCounter = 0
def merg(array,counter):
    if len(array)==1:
            return array
    left = array[:len(array)/2]
    right = array[len(array)/2:]
    return combine(merg(left, counter), merg(right, counter), counter)

def combine(array1, array2, counter):
    global mainCounter
    result = []
    pointer1 = 0
    pointer2 = 0
    while(pointer1 != len(array1) and pointer2 != len(array2)):
            if array1[pointer1] < array2[pointer2]:
                    result.append(array1[pointer1])
                    pointer1 += 1
            elif array1[pointer1] == array2[pointer2]:
                    result.append(array1[pointer1])
                    pointer1 += 1
            else:
                    result.append(array2[pointer2])
                    counter += (len(array1)-pointer1)
                    pointer2 += 1
    if pointer1 == len(array1):
            for i in array2[pointer2:]:
                    result.append(i)
    else:
            for i in array1[pointer1:]:
                    result.append(i)
    mainCounter+=counter
    return result

问题是当我在 python 控制台中导入这个模块时 mainCounter 没有改变，但这必须改变！！：

Python 2.7.3 (default, Aug  1 2012, 05:16:07) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from mergSort import *
>>> merg([1,4,2,3],0)
0
0
2
[1, 2, 3, 4]
>>> merg([1,4,2,3],0)
2
2
4
[1, 2, 3, 4]
>>> mainCounter
0
>>> merg([1,4,2,3],0)
4
4
6
[1, 2, 3, 4]
>>> merg([1,4,2,3],0)
6
6
8
[1, 2, 3, 4]
>>> merg([1,4,2,3],0)
8
8
10
[1, 2, 3, 4]
>>> mainCounter
0

每次我调用该merg函数时，我都会得到不同的结果，但 mainCounter 并没有改变！我错在哪里？

4

2 回答 2

4

tldr：不要使用from module import *

import *没有你想象的那么特别——当你用 导入东西时from mergSort import *，把它想象成

import mergSort
mainCounter = mergSort.mainCounter
merg = mergSort.merg
del mergSort

因此，您实际上只是引用mergSort.mainCounter了导入时引用的 int 对象。mergSort使用mergSort.mainCounter一个；以同样的方式

>>> a = 1
>>> b = a
>>> a += 1 # or a = a + 1 or a = a.__add__(1)
>>> a
2
>>> b
1

我们有两个对整数对象的单独引用，并且递增一个（将引用更改为指向由对旧对象的方法调用产生的新对象）不会影响另一个。要确认这一点，请尝试

merg.__globals__['mainCounter']

或者

import sys; sys.modules[merg.__module__].mainCounter

这些应该具有 merg 正在使用的 mainCounter 值。

（sys.modules['mergSort'] is merg.__globals__是真的，它们是同一个字典）

当一个名称在函数中声明为全局名称时，它会在函数模块的命名空间中查找。

import *经常受到诽谤，因为它很难追踪名称的来源，但在这里它也很糟糕，因为它打破了我们对模块的概念——仅仅因为你从一个模块导入 * 并不意味着你实际上在它的命名空间中，你刚刚完成了from module import a, b, c, d, e, ...。这更糟，因为许多名称在 Python 中并没有太多重新绑定，但有些名称一直存在，例如通过引用整数充当计数器的名称。

于 2013-09-13T07:14:02.887 回答
1

完全不使用是一个好习惯import *。您导入的对象对彼此一无所知，使用global mainCounter也无济于事。

尝试这个：

import mergSort

mergSort.merg([1, 4, 2, 3], 0)
print mergSort.mainCounter
于 2013-09-13T07:45:31.557 回答