9

有一个名为svnmerge.py的脚本，我正在尝试对其进行调整和优化。不过，我对 Python 完全陌生，所以这并不容易。

当前的问题似乎与RevisionSet脚本中调用的类有关。本质上，它所做的是创建一个包含整数键布尔值的大型哈希表（？）。在最坏的情况下 - 我们的 SVN 存储库中的每个修订版本都有一个，现在接近 75,000 个。

之后，它对如此庞大的数组执行集合操作——加法、减法、交集等等。该实现是最简单的 O(n) 实现，自然会在如此大的集合上变得相当慢。可以优化整个数据结构，因为有很长的连续值跨度。例如，从 1 到 74,000 的所有键都可能包含true. 此外，该脚本是为 Python 2.2 编写的，这是一个相当旧的版本，而且我们无论如何都在使用 2.6，所以那里也可能会有所收获。

我可以尝试自己拼凑它，但这会很困难并且需要很多时间——更不用说它可能已经在某个地方实现了。虽然我喜欢学习经验，但现在结果更重要。你会建议我做什么？

4

5 回答 5

7

你可以尝试用 numpy 而不是普通的 python 来做。我发现这样的操作非常快。

例如：

# Create 1000000 numbers between 0 and 1000, takes 21ms
x = numpy.random.randint(0, 1000, 1000000)

# Get all items that are larger than 500, takes 2.58ms
y = x > 500

# Add 10 to those items, takes 26.1ms
x[y] += 10

因为那有更多的行，我认为 75000 也不应该是一个问题:)

于 2010-10-19T10:59:26.647 回答
1

这是 RevisionSet 的快速替换，可以将其变成一个集合。它应该快得多。我没有完全测试它，但它适用于我所做的所有测试。毫无疑问，还有其他方法可以加快速度，但我认为这确实会有所帮助，因为它实际上利用了集合的快速实现，而不是在 Python 中执行原始代码在函数中执行的循环，如__sub__和__and__。唯一的问题是迭代器没有排序。您可能需要更改一些代码来解决此问题。我相信还有其他方法可以改进这一点，但希望它会给你一个好的开始。

class RevisionSet(set):
    """
    A set of revisions, held in dictionary form for easy manipulation. If we
    were to rewrite this script for Python 2.3+, we would subclass this from
    set (or UserSet).  As this class does not include branch
    information, it's assumed that one instance will be used per
    branch.
    """
    def __init__(self, parm):
        """Constructs a RevisionSet from a string in property form, or from
        a dictionary whose keys are the revisions. Raises ValueError if the
        input string is invalid."""


        revision_range_split_re = re.compile('[-:]')

        if isinstance(parm, set):
            print "1"
            self.update(parm.copy())
        elif isinstance(parm, list):
            self.update(set(parm))
        else:
            parm = parm.strip()
            if parm:
                for R in parm.split(","):
                    rev_or_revs = re.split(revision_range_split_re, R)
                    if len(rev_or_revs) == 1:
                        self.add(int(rev_or_revs[0]))
                    elif len(rev_or_revs) == 2:
                        self.update(set(range(int(rev_or_revs[0]),
                                         int(rev_or_revs[1])+1)))
                    else:
                        raise ValueError, 'Ill formatted revision range: ' + R

    def sorted(self):
        return sorted(self)

    def normalized(self):
        """Returns a normalized version of the revision set, which is an
        ordered list of couples (start,end), with the minimum number of
        intervals."""
        revnums = sorted(self)
        revnums.reverse()
        ret = []
        while revnums:
            s = e = revnums.pop()
            while revnums and revnums[-1] in (e, e+1):
                e = revnums.pop()
            ret.append((s, e))
        return ret

    def __str__(self):
        """Convert the revision set to a string, using its normalized form."""
        L = []
        for s,e in self.normalized():
            if s == e:
                L.append(str(s))
            else:
                L.append(str(s) + "-" + str(e))
        return ",".join(L)

补充： 顺便说一下，我比较了原始 RevisionSet 和上面我的 RevisionSet 的并集、交集和减法，当对两个具有 75000 个元素的 RevisionSet 进行操作时，上面的代码对于这些操作的速度要快 3 倍到 7 倍。我知道其他人说 numpy 是要走的路，但是如果您对 Python 不是很有经验，正如您的评论所示，那么您可能不想走那条路，因为它将涉及更多的更改。我建议尝试我的代码，看看它是否有效，如果有效，然后看看它对你来说是否足够快。如果不是，那么我会尝试分析以查看需要改进的地方。只有这样我才会考虑使用 numpy（这是一个我经常使用的很棒的包）。

于 2010-10-19T19:12:40.950 回答
0

只是一个想法。我曾经在二进制图像处理中使用运行编码来做这种事情。也就是说，将每个集合存储为一系列数字：关闭的位数、打开的位数、关闭的位数等。

然后，您可以对它们进行各种布尔运算，作为简单合并算法的装饰。

于 2010-10-19T16:00:28.867 回答
0

您应该重写 RevisionSet 以获得一组修订。我认为修订的内部表示应该是一个整数，并且应该根据需要创建修订范围。

没有令人信服的理由使用支持 python 2.3 及更早版本的代码。

于 2010-10-19T15:07:36.177 回答
0

例如，从 1 到 74,000 的所有键都包含 true

为什么不对子集工作？就74001到最后。

修剪 74/75 的数据比尝试编写比O (n) 更聪明的算法要容易得多。

于 2010-10-19T11:35:38.823 回答