使用堆可以提高字符串重排的性能

Question

使用堆可以提高字符串重排的性能

pythonalgorithmperformancepython-2.7heap

3

我正在解决以下问题，并发布了我的代码。我的问题是，我目前的实现在Python中使用了排序 - sorted(sorted_freq, reverse=True)。我参考了一些其他的实现，它们使用了最大堆(http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/)。我认为它们具有相同的时间复杂度，即O(n*log n)(如果我计算错误，请随时更正)。所以我想知道除了排序之外，使用堆是否有任何性能上的好处？

我的代码是用Python 2.7编写的。

问题：

给定一个字符串和一个正整数d。给定字符串中可能会重复出现某些字符。重新排列给定字符串的字符，使得相同的字符离彼此至少有d个距离。请注意，可能会有许多可能的重新排列，输出应该是可能的重新排列之一。如果没有这样的安排，则应报告。

期望的时间复杂度是O(n)，其中n是输入字符串的长度。

例子：

Input:  "abb", d = 2
Output: "bab"

Input:  "aacbbc", d = 3
Output: "abcabc"

Input: "geeksforgeeks", d = 3
Output: egkegkesfesor

Input:  "aaa",  d = 2
Output: Cannot be rearranged

源代码：

from collections import defaultdict
def rearrange(source, distance):
    freq = defaultdict(int)
    for c in source:
        freq[c] += 1
    sorted_freq = []
    for k,v in freq.items():
        sorted_freq.append((v,k))
    sorted_freq = sorted(sorted_freq, reverse=True)
    result = [0] * len(source)
    for i, (v,k) in enumerate(sorted_freq):
        index = i
        while index < len(result) and result[index] != 0:
            index += 1
        if index == len(result):
            return None
        count = v
        while count > 0:
            result[index] = k
            index += distance
            count -= 1
            if index >= len(source) and count > 0:
                return None
    return result

if __name__ == "__main__":
    print rearrange('abb', 2)
    print rearrange('aacbbc', 3)
    print rearrange('geeksforgeeks', 3)
    print rearrange('aaa', 2)

- Lin Ma

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- niemmi · Accepted Answer

链接中提供的最佳算法的时间复杂度为O(n + m log m)，其中m是输入字符串中唯一字符的数量。正如所提到的，由于m始终小于字母表中的总字母数（这是一个固定常数），因此如果m相对于n较小，则可以将时间复杂度视为O(n)。当使用O(m log m)排序算法来排序频率而不是堆时，时间复杂度没有区别。

请注意，您的实现具有时间复杂度O(nm)，因为您在每个循环中都用i初始化了index。这里提供了一个替代实现，使用Counter而不是defaultdict，已经解决了这个问题，并对退化情况下的性能进行了简短的比较：

from collections import Counter

def rearrange2(s, dist):
    start = 0
    result = [None] * len(s)
    for char, count in Counter(s).most_common():
        while result[start]:
            start += 1
        end = start + dist * (count - 1) + 1
        if end > len(s):
            return None
        for i in xrange(start, end, dist):
            result[i] = char

    return ''.join(result)


def rearrange3(s, dist):
    start = 0
    result = [None] * len(s)
    for char, count in sorted(Counter(s).items(), key=lambda x: x[1], reverse=True):
        while result[start]:
            start += 1
        end = start + dist * (count - 1) + 1
        if end > len(s):
            return None
        for i in xrange(start, end, dist):
            result[i] = char

    return ''.join(result)

if __name__ == '__main__':
    import timeit
    print timeit.timeit("rearrange(src,2)", setup="from __main__ import rearrange; src='a'*10000 + 'b'*10000 + 'cdefghijk'", number=100)
    print timeit.timeit("rearrange2(src,2)", setup="from __main__ import rearrange2; src='a'*10000 + 'b'*10000 + 'cdefghijk'", number=100)
    print timeit.timeit("rearrange3(src,2)", setup="from __main__ import rearrange3; src='a'*10000 + 'b'*10000 + 'cdefghijk'", number=100)

输出：

3.23630073078
0.756645293244
0.753287190129

更新：most_common使用heapq.nlargest 在底层中，当n为给定可迭代对象的长度时，等同于堆排序。从上面的结果可以看出，没有实质性的区别。结果当然取决于数据的大小和唯一字符的数量。