l'utilisation du tas permet d'améliorer les performances pour le réarrangement des chaînes de caractères

Question

Je travaille sur le problème ci-dessous et j'ai posté mon code. Ma question est la suivante : mon implémentation actuelle utilise un tri en Python - sorted(sorted_freq, reverse=True) . Je me suis référé à une autre mise en œuvre qui utilise un tas maximum ( http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/ ). Je pense qu'ils ont la même complexité temporelle qui est O(n*log n) (si je calcule mal, n'hésitez pas à corriger). Je me demande donc s'il y a un avantage en termes de performance à utiliser le tas autre que le tri ?

Mon code est écrit en Python 2.7.

Problème :

Étant donné une chaîne de caractères et un nombre entier positif d . Certains caractères peuvent être répétés dans la chaîne donnée. Réorganisez les caractères de la chaîne donnée de sorte que les mêmes caractères deviennent d distance les uns des autres. Notez qu'il peut y avoir plusieurs réarrangements possibles, la sortie devrait être l'un des réarrangements possibles. Si aucun arrangement n'est possible, cela doit également être signalé. La complexité temporelle attendue est O(n) où n est la longueur de la chaîne d'entrée.

Exemples :

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

Code source :

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)

Answer 1

La complexité temporelle du meilleur algorithme présenté au lien est de O(n + m log m) donde m est le nombre de caractères uniques dans la chaîne d'entrée. Comme il a été mentionné, puisque m toujours inférieur au nombre total de lettres de l'alphabet (qui est une constante fixe), si m est faible par rapport à n la complexité temporelle peut être considérée O(n) . Il n'y a pas de différence dans la complexité du temps lorsque O(m log m) L'algorithme de tri est utilisé pour trier les fréquences au lieu d'un tas.

Notez que votre implémentation a une complexité temporelle O(nm) puisque vous initialisez index avec i dans chaque boucle. Voici une implémentation alternative utilisant Counter au lieu de defaultdict qui a le problème résolu et une brève comparaison de la performance dans le cas dégénéré :

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)

Sortie :

3.23630073078
0.756645293244
0.753287190129

Mise à jour : most_common utilise heapq.nlargest sous le capot qui est égal à heapsort dans le cas où n est la longueur de l'itérable donné. Comme on peut le voir dans les résultats ci-dessus, il n'y a pas de réelle différence. Les résultats dépendent bien sûr de la taille des données et du nombre de caractères uniques.