如何在Python中优化对大型（75000个项目）布尔集的操作？

Question

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

当前的问题似乎与脚本中名为RevisionSet的类有关。本质上，它所做的就是创建一个大型哈希表（？）整数键控布尔值。在最坏的情况下，我们的SVN存储库中的每个版本都有一个版本，现在已经接近75000个了。在

之后，它在如此巨大的数组上执行集合运算——加法、减法、交集等等。这个实现是最简单的O（n）实现，在如此大的集合上自然会变得相当慢。整个数据结构可以优化，因为连续值的跨度很长。例如，从1到74000的所有键都可能包含true。另外，这个脚本是为python2.2编写的，这是一个非常旧的版本，我们使用的是2.6，因此也可以从中获得一些东西。在

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

Answer 1

For example, all keys from 1 to 74,000 contain true

为什么不在子集上工作呢？最后只有74001个。在

修剪74/75的数据比编写一个比O（n）更聪明的算法要容易得多。在

Answer 2

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

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)

添加： 顺便说一下，我比较了对原始修订集和上面我的修订集的并集、交集和减法，上面的代码在两个包含75000个元素的修订集上操作时，这些操作的速度从3倍提高到7倍。我知道其他人会说numpy是最好的选择，但是如果你对Python不是很有经验，就像你的评论所说的那样，那么你可能不想走那条路，因为这将涉及到更多的变化。我建议您尝试一下我的代码，看看它是否有效，如果有效，然后看看它是否足够快。如果不是，那么我会尝试分析，看看有什么需要改进的。只有这样，我才会考虑使用numpy（这是我经常使用的一个很棒的包）。在

Answer 3

你可以试着用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行也不成问题：）