Je suis en train de concevoir un algorithme pour faire ce qui suit : Étant donné un tableau A[1... n] pour chaque i < j trouver toutes les paires d'inversion telles que A[i] > A[j] . J'utilise le tri par fusion et copie le tableau A dans le tableau B, puis compare les deux tableaux, mais j'ai du mal à voir comment je peux utiliser cette méthode pour trouver le nombre d'inversions. Toute indication ou aide serait grandement appréciée.
Réponses
Trop de publicités?
PM 2Ring
Points
11424
Le but premier de cette réponse est de comparer les vitesses des différentes versions de Python que l'on trouve ici, mais j'ai aussi quelques contributions personnelles. (Pour info, je viens de découvrir cette question en effectuant une recherche de doublons).
Les vitesses d'exécution relatives des algorithmes implémentés en CPython peuvent être différentes de ce que l'on pourrait attendre d'une simple analyse des algorithmes et de l'expérience acquise avec d'autres langages. C'est parce que Python fournit de nombreuses fonctions et méthodes puissantes implémentées en C qui peuvent opérer sur des listes et d'autres collections à une vitesse proche de celle que l'on obtiendrait dans un langage entièrement compilé, de sorte que ces opérations s'exécutent beaucoup plus rapidement que les algorithmes équivalents implémentés "manuellement" avec du code Python.
Le code qui tire parti de ces outils peut souvent surpasser les algorithmes théoriquement supérieurs qui tentent de tout faire avec des opérations Python sur des éléments individuels de la collection. Bien entendu, la quantité réelle de données traitées a également un impact sur ce point. Mais pour des quantités modérées de données, le code qui utilise un algorithme O(n²) fonctionnant à la vitesse du C peut facilement battre un algorithme O(n log n) qui effectue la majeure partie de son travail avec des opérations Python individuelles.
La plupart des réponses postées à cette question sur le comptage des inversions utilisent un algorithme basé sur le mergesort. En théorie, il s'agit d'une bonne approche, sauf si la taille du tableau est très petite. Mais la fonction intégrée de Python TimSort (un algorithme de tri stable hybride, dérivé du tri par fusion et du tri par insertion) fonctionne à la vitesse du C, et un tri par fusion codé à la main en Python ne peut espérer rivaliser avec lui en termes de vitesse.
L'une des solutions les plus intrigantes ici, en la réponse donnée par Niklas B utilise le tri intégré pour déterminer le classement des éléments d'un tableau, et une fonction Arbre indexé binaire (alias arbre de Fenwick) pour stocker les sommes cumulées nécessaires au calcul du nombre d'inversion. En essayant de comprendre cette structure de données et l'algorithme de Niklas, j'ai écrit quelques variations de mon propre algorithme (voir ci-dessous). Mais j'ai également découvert que pour des listes de taille modérée, il est en réalité plus rapide pour utiliser la fonction intégrée de Python sum fonction que le charmant arbre Fenwick.
def count_inversions(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return totalFinalement, quand la taille de la liste atteint environ 500, l'aspect O(n²) de l'appel à sum à l'intérieur de ce for la boucle se manifeste, et les performances commencent à chuter.
Mergesort n'est pas le seul tri O(nlogn), et plusieurs autres peuvent être utilisés pour effectuer le comptage des inversions. La réponse de prasadvk utilise un tri par arbre binaire, mais son code semble être en C++ ou l'un de ses dérivés. J'ai donc ajouté une version Python. A l'origine, j'utilisais une classe pour implémenter les nœuds de l'arbre, mais j'ai découvert qu'un dict est nettement plus rapide. J'ai finalement utilisé une liste, ce qui est encore plus rapide, bien que cela rende le code un peu moins lisible.
L'un des avantages de treesort est qu'il est beaucoup plus facile à mettre en œuvre de manière itérative que mergesort. Python n'optimise pas la récursion et possède une limite de profondeur de récursion (bien qu'elle puisse être augmentée si vous vraiment en ont besoin). Et bien sûr, les appels de fonction Python sont relativement lents, donc lorsque vous essayez d'optimiser la vitesse, il est préférable d'éviter les appels de fonction, lorsque cela est possible.
Un autre tri O(nlogn) est le vénérable tri radix. Son grand avantage est qu'il ne compare pas les clés entre elles. Son inconvénient est qu'il fonctionne mieux sur des séquences contiguës d'entiers, idéalement une permutation d'entiers en range(b**m) où b est généralement 2. J'ai ajouté quelques versions basées sur le tri radix après avoir tenté de lire Comptage des inversions, comptage hors ligne des plages orthogonales et problèmes connexes qui est lié à calculer le nombre d'"inversions" dans une permutation .
Pour utiliser efficacement le tri radix pour compter les inversions dans une séquence générale seq de longueur n, nous pouvons créer une permutation de range(n) qui a le même nombre d'inversions que seq . Nous pouvons le faire en (au pire) temps O(nlogn) via TimSort. L'astuce consiste à permuter les indices de seq en triant seq . Il est plus facile d'expliquer cela à l'aide d'un petit exemple.
seq = [15, 14, 11, 12, 10, 13]
b = [t[::-1] for t in enumerate(seq)]
print(b)
b.sort()
print(b)sortie
[(15, 0), (14, 1), (11, 2), (12, 3), (10, 4), (13, 5)]
[(10, 4), (11, 2), (12, 3), (13, 5), (14, 1), (15, 0)]En triant les paires (valeur, index) de l'application seq nous avons permuté les indices de seq avec le même nombre de swaps qui sont nécessaires pour mettre seq dans son ordre original à partir de son ordre trié. Nous pouvons créer cette permutation en triant range(n) avec une fonction clé appropriée :
print(sorted(range(len(seq)), key=lambda k: seq[k]))sortie
[4, 2, 3, 5, 1, 0]Nous pouvons éviter cela lambda en utilisant seq 's .__getitem__ méthode :
sorted(range(len(seq)), key=seq.__getitem__)Ce n'est que légèrement plus rapide, mais nous recherchons toutes les améliorations de vitesse que nous pouvons obtenir ;)
Le code ci-dessous exécute timeit teste tous les algorithmes Python existants sur cette page, plus quelques uns de mes propres algorithmes : quelques versions O(n²) de force brute, quelques variations sur l'algorithme de Niklas B, et bien sûr un algorithme basé sur mergesort (que j'ai écrit sans me référer aux réponses existantes). Il y a aussi mon code treesort basé sur une liste, dérivé grossièrement du code de prasadvk, et diverses fonctions basées sur le tri radix, certaines utilisant une stratégie similaire aux approches mergesort, et d'autres utilisant sum ou un arbre Fenwick.
Ce programme mesure le temps d'exécution de chaque fonction sur une série de listes aléatoires d'entiers ; il permet également de vérifier que chaque fonction donne les mêmes résultats que les autres, et qu'elle ne modifie pas la liste d'entrée.
Chaque timeit call donne un vecteur contenant 3 résultats, que je trie. La valeur principale à regarder ici est la valeur minimale, les autres valeurs donnent simplement une indication de la fiabilité de cette valeur minimale, comme discuté dans la Note dans le site timeit documentation sur les modules .
Malheureusement, les résultats de ce programme sont trop volumineux pour être inclus dans cette réponse. sa propre réponse (wiki communautaire) .
Les résultats sont issus de trois exécutions sur mon ancienne machine 32 bits à cœur unique de 2 GHz, qui utilise Python 3.6.0 sur une ancienne distribution dérivée de Debian. YMMV. Pendant les tests, j'ai fermé mon navigateur Web et je me suis déconnecté de mon routeur pour minimiser l'impact des autres tâches sur le CPU.
La première exécution teste toutes les fonctions avec des tailles de liste allant de 5 à 320, avec des tailles de boucle allant de 4096 à 64 (lorsque la taille de la liste double, la taille de la boucle est divisée par deux). Le pool aléatoire utilisé pour construire chaque liste est la moitié de la taille de la liste elle-même, donc nous sommes susceptibles d'obtenir lots de doublons. Certains des algorithmes de comptage d'inversion sont plus sensibles aux doublons que d'autres.
La deuxième exécution utilise des listes plus grandes : 640 à 10240, et une taille de boucle fixe de 8. Pour gagner du temps, elle élimine plusieurs des fonctions les plus lentes des tests. Mes fonctions O(n²) de force brute sont juste chemin trop lente à ces tailles, et comme mentionné précédemment, mon code qui utilise sum qui réussit si bien sur les petites et moyennes listes, n'arrive pas à suivre sur les grandes listes.
L'exécution finale couvre des tailles de liste de 20480 à 655360, et une taille de boucle fixe de 4, avec les 8 fonctions les plus rapides. Pour les tailles de liste inférieures à 40 000 environ, le code de Tim Babych est le grand gagnant. Bravo Tim ! Le code de Niklas B est également très performant, bien qu'il soit battu sur les petites listes. Le code de "python" basé sur la bissection s'en sort également plutôt bien, bien qu'il semble être un peu plus lent avec les grandes listes comportant beaucoup de doublons, probablement à cause de cette méthode linéaire. while boucle qu'il utilise pour passer sur les doublons.
Cependant, pour les listes de très grande taille, les algorithmes basés sur la bissection ne peuvent pas rivaliser avec les vrais algorithmes O(nlogn).
#!/usr/bin/env python3
''' Test speeds of various ways of counting inversions in a list
The inversion count is a measure of how sorted an array is.
A pair of items in a are inverted if i < j but a[j] > a[i]
See https://stackoverflow.com/questions/337664/counting-inversions-in-an-array
This program contains code by the following authors:
mkso
Niklas B
B. M.
Tim Babych
python
Zhe Hu
prasadvk
noman pouigt
PM 2Ring
Timing and verification code by PM 2Ring
Collated 2017.12.16
Updated 2017.12.21
'''
from timeit import Timer
from random import seed, randrange
from bisect import bisect, insort_left
seed('A random seed string')
# Merge sort version by mkso
def count_inversion_mkso(lst):
return merge_count_inversion(lst)[1]
def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = len(lst) // 2
left, a = merge_count_inversion(lst[:middle])
right, b = merge_count_inversion(lst[middle:])
result, c = merge_count_split_inversion(left, right)
return result, (a + b + c)
def merge_count_split_inversion(left, right):
result = []
count = 0
i, j = 0, 0
left_len = len(left)
while i < left_len and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += left_len - i
j += 1
result += left[i:]
result += right[j:]
return result, count
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Using a Binary Indexed Tree, aka a Fenwick tree, by Niklas B.
def count_inversions_NiklasB(a):
res = 0
counts = [0] * (len(a) + 1)
rank = {v: i for i, v in enumerate(sorted(a), 1)}
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i <= len(a):
counts[i] += 1
i += i & -i
return res
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by B.M
# Modified by PM 2Ring to deal with the global counter
bm_count = 0
def merge_count_BM(seq):
global bm_count
bm_count = 0
sort_bm(seq)
return bm_count
def merge_bm(l1,l2):
global bm_count
l = []
while l1 and l2:
if l1[-1] <= l2[-1]:
l.append(l2.pop())
else:
l.append(l1.pop())
bm_count += len(l2)
l.reverse()
return l1 + l2 + l
def sort_bm(l):
t = len(l) // 2
return merge_bm(sort_bm(l[:t]), sort_bm(l[t:])) if t > 0 else l
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by Tim Babych
def solution_TimBabych(A):
sorted_left = []
res = 0
for i in range(1, len(A)):
insort_left(sorted_left, A[i-1])
# i is also the length of sorted_left
res += (i - bisect(sorted_left, A[i]))
return res
# Slightly faster, except for very small lists
def solutionE_TimBabych(A):
res = 0
sorted_left = []
for i, u in enumerate(A):
# i is also the length of sorted_left
res += (i - bisect(sorted_left, u))
insort_left(sorted_left, u)
return res
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by "python"
def solution_python(A):
B = list(A)
B.sort()
inversion_count = 0
for i in range(len(A)):
j = binarySearch_python(B, A[i])
while B[j] == B[j - 1]:
if j < 1:
break
j -= 1
inversion_count += j
B.pop(j)
return inversion_count
def binarySearch_python(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
return midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by Zhe Hu
def inv_cnt_ZheHu(a):
_, count = inv_cnt(a.copy())
return count
def inv_cnt(a):
n = len(a)
if n==1:
return a, 0
left = a[0:n//2] # should be smaller
left, cnt1 = inv_cnt(left)
right = a[n//2:] # should be larger
right, cnt2 = inv_cnt(right)
cnt = 0
i_left = i_right = i_a = 0
while i_a < n:
if (i_right>=len(right)) or (i_left < len(left)
and left[i_left] <= right[i_right]):
a[i_a] = left[i_left]
i_left += 1
else:
a[i_a] = right[i_right]
i_right += 1
if i_left < len(left):
cnt += len(left) - i_left
i_a += 1
return (a, cnt1 + cnt2 + cnt)
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by noman pouigt
# From https://stackoverflow.com/q/47830098
def reversePairs_nomanpouigt(nums):
def merge(left, right):
if not left or not right:
return (0, left + right)
#if everything in left is less than right
if left[len(left)-1] < right[0]:
return (0, left + right)
else:
left_idx, right_idx, count = 0, 0, 0
merged_output = []
# check for condition before we merge it
while left_idx < len(left) and right_idx < len(right):
#if left[left_idx] > 2 * right[right_idx]:
if left[left_idx] > right[right_idx]:
count += len(left) - left_idx
right_idx += 1
else:
left_idx += 1
#merging the sorted list
left_idx, right_idx = 0, 0
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] > right[right_idx]:
merged_output += [right[right_idx]]
right_idx += 1
else:
merged_output += [left[left_idx]]
left_idx += 1
if left_idx == len(left):
merged_output += right[right_idx:]
else:
merged_output += left[left_idx:]
return (count, merged_output)
def partition(nums):
count = 0
if len(nums) == 1 or not nums:
return (0, nums)
pivot = len(nums)//2
left_count, l = partition(nums[:pivot])
right_count, r = partition(nums[pivot:])
temp_count, temp_list = merge(l, r)
return (temp_count + left_count + right_count, temp_list)
return partition(nums)[0]
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# PM 2Ring
def merge_PM2R(seq):
seq, count = merge_sort_count_PM2R(seq)
return count
def merge_sort_count_PM2R(seq):
mid = len(seq) // 2
if mid == 0:
return seq, 0
left, left_total = merge_sort_count_PM2R(seq[:mid])
right, right_total = merge_sort_count_PM2R(seq[mid:])
total = left_total + right_total
result = []
i = j = 0
left_len, right_len = len(left), len(right)
while i < left_len and j < right_len:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
total += left_len - i
result.extend(left[i:])
result.extend(right[j:])
return result, total
def rank_sum_PM2R(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total
# Fenwick tree functions adapted from C code on Wikipedia
def fen_sum(tree, i):
''' Return the sum of the first i elements, 0 through i-1 '''
total = 0
while i:
total += tree[i-1]
i -= i & -i
return total
def fen_add(tree, delta, i):
''' Add delta to element i and thus
to fen_sum(tree, j) for all j > i
'''
size = len(tree)
while i < size:
tree[i] += delta
i += (i+1) & -(i+1)
def fenwick_PM2R(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += fen_sum(counts, i)
fen_add(counts, 1, i)
return total
def fenwick_inline_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total
def bruteforce_loops_PM2R(a):
total = 0
for i in range(1, len(a)):
u = a[i]
for j in range(i):
if a[j] > u:
total += 1
return total
def bruteforce_sum_PM2R(a):
return sum(1 for i in range(1, len(a)) for j in range(i) if a[j] > a[i])
# Using binary tree counting, derived from C++ code (?) by prasadvk
# https://stackoverflow.com/a/16056139
def ltree_count_PM2R(a):
total, root = 0, None
for u in a:
# Store data in a list-based tree structure
# [data, count, left_child, right_child]
p = [u, 0, None, None]
if root is None:
root = p
continue
q = root
while True:
if p[0] < q[0]:
total += 1 + q[1]
child = 2
else:
q[1] += 1
child = 3
if q[child]:
q = q[child]
else:
q[child] = p
break
return total
# Counting based on radix sort, recursive version
def radix_partition_rec(a, L):
if len(a) < 2:
return 0
if len(a) == 2:
return a[1] < a[0]
left, right = [], []
count = 0
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
L >>= 1
if L:
count += radix_partition_rec(left, L) + radix_partition_rec(right, L)
return count
# The following functions determine swaps using a permutation of
# range(len(a)) that has the same inversion count as `a`. We can create
# this permutation with `sorted(range(len(a)), key=lambda k: a[k])`
# but `sorted(range(len(a)), key=a.__getitem__)` is a little faster.
# Counting based on radix sort, iterative version
def radix_partition_iter(seq, L):
count = 0
parts = [seq]
while L and parts:
newparts = []
for a in parts:
if len(a) < 2:
continue
if len(a) == 2:
count += a[1] < a[0]
continue
left, right = [], []
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
if left:
newparts.append(left)
if right:
newparts.append(right)
parts = newparts
L >>= 1
return count
def perm_radixR_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_rec(b, 1 << n)
def perm_radixI_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_iter(b, 1 << n)
# Plain sum of the counts of the permutation
def perm_sum_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
total += sum(counts[:i])
counts[i] = 1
return total
# Fenwick sum of the counts of the permutation
def perm_fenwick_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# All the inversion-counting functions
funcs = (
solution_TimBabych,
solutionE_TimBabych,
solution_python,
count_inversion_mkso,
count_inversions_NiklasB,
merge_count_BM,
inv_cnt_ZheHu,
reversePairs_nomanpouigt,
fenwick_PM2R,
fenwick_inline_PM2R,
merge_PM2R,
rank_sum_PM2R,
bruteforce_loops_PM2R,
bruteforce_sum_PM2R,
ltree_count_PM2R,
perm_radixR_PM2R,
perm_radixI_PM2R,
perm_sum_PM2R,
perm_fenwick_PM2R,
)
def time_test(seq, loops, verify=False):
orig = seq
timings = []
for func in funcs:
seq = orig.copy()
value = func(seq) if verify else None
t = Timer(lambda: func(seq))
result = sorted(t.repeat(3, loops))
timings.append((result, func.__name__, value))
assert seq==orig, 'Sequence altered by {}!'.format(func.__name__)
first = timings[0][-1]
timings.sort()
for result, name, value in timings:
result = ', '.join([format(u, '.5f') for u in result])
print('{:24} : {}'.format(name, result))
if verify:
# Check that all results are identical
bad = ['%s: %d' % (name, value)
for _, name, value in timings if value != first]
if bad:
print('ERROR. Value: {}, bad: {}'.format(first, ', '.join(bad)))
else:
print('Value: {}'.format(first))
print()
#Run the tests
size, loops = 5, 1 << 12
verify = True
for _ in range(7):
hi = size // 2
print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
seq = [randrange(hi) for _ in range(size)]
time_test(seq, loops, verify)
loops >>= 1
size <<= 1
#size, loops = 640, 8
#verify = False
#for _ in range(5):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1
#size, loops = 163840, 4
#verify = False
#for _ in range(3):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1
Utilisateur non enregistré
Points
0
J'avais une question similaire à celle-ci pour un devoir en fait. On m'a restreint qu'il devait avoir une efficacité O(nlogn).
J'ai utilisé l'idée que vous avez proposée d'utiliser Mergesort, puisqu'elle est déjà d'une efficacité correcte. J'ai juste inséré un peu de code dans la fonction de fusion qui était en principe : Chaque fois qu'un nombre du tableau de droite est ajouté au tableau de sortie, j'ajoute au nombre total d'inversions, le nombre de nombres restant dans le tableau de gauche.
Cela a beaucoup de sens pour moi maintenant que j'y ai suffisamment réfléchi. Tu comptes le nombre de fois où un nombre plus grand précède un nombre quelconque.
hth.
B. M.
Points
5323
Le nombre d'inversions peut être trouvé en analysant le processus de fusion dans le tri par fusion : 
Lorsqu'on copie un élément du deuxième tableau vers le tableau de fusion (le 9 dans cet exemple), il garde sa place par rapport aux autres éléments. Quand on copie un élément du premier tableau vers le tableau de fusion (le 5 ici), il est inversé et tous les éléments restent dans le deuxième tableau (2 inversions avec le 3 et le 4). Donc une petite modification du tri par fusion peut résoudre le problème en O(n ln n).
Par exemple, il suffit de décommenter les deux # lignes dans le code python de mergesort ci-dessous pour avoir le compte.
def merge(l1,l2):
l = []
# global count
while l1 and l2:
if l1[-1] <= l2[-1]:
l.append(l2.pop())
else:
l.append(l1.pop())
# count += len(l2)
l.reverse()
return l1 + l2 + l
def sort(l):
t = len(l) // 2
return merge(sort(l[:t]), sort(l[t:])) if t > 0 else l
count=0
print(sort([5,1,2,4,9,3]), count)
# [1, 2, 3, 4, 5, 9] 6EDIT 1
La même tâche peut être réalisée avec une version stable de quick sort, connue pour être légèrement plus rapide :
def part(l):
pivot=l[-1]
small,big = [],[]
count = big_count = 0
for x in l:
if x <= pivot:
small.append(x)
count += big_count
else:
big.append(x)
big_count += 1
return count,small,big
def quick_count(l):
if len(l)<2 : return 0
count,small,big = part(l)
small.pop()
return count + quick_count(small) + quick_count(big)En choisissant le pivot comme dernier élément, les inversions sont bien comptabilisées, et le temps d'exécution est 40% meilleur que celui de la fusion ci-dessus.
EDIT 2
Pour les performances en python, une version numpy & numba :
D'abord la partie numpy, qui utilise argsort O (n ln n) :
def count_inversions(a):
n = a.size
counts = np.arange(n) & -np.arange(n) # The BIT
ags = a.argsort(kind='mergesort')
return BIT(ags,counts,n)Et la partie numba pour l'efficace Approche TIB :
@numba.njit
def BIT(ags,counts,n):
res = 0
for x in ags :
i = x
while i:
res += counts[i]
i -= i & -i
i = x+1
while i < n:
counts[i] -= 1
i += i & -i
return res
user1465038
Points
41
Notez que la réponse de Geoffrey Irving est fausse.
Le nombre d'inversions dans un tableau est égal à la moitié de la distance totale que les éléments doivent parcourir pour trier le tableau. Par conséquent, il peut être calculé en triant le tableau, en conservant la permutation résultante p[i], puis en calculant la somme de abs(p[i]-i)/2. Cela prend O(n log n) temps, ce qui est optimal.
Une méthode alternative est donnée à http://mathworld.wolfram.com/PermutationInversion.html . Cette méthode est équivalente à la somme de max(0, p[i]-i), qui est égale à la somme de abs(p[i]-i])/2 puisque la distance totale de déplacement des éléments vers la gauche est égale à la distance totale de déplacement des éléments vers la droite.
Prenons la séquence { 3, 2, 1 } comme exemple. Il y a trois inversions : (3, 2), (3, 1), (2, 1), donc le nombre d'inversion est 3. Cependant, selon la méthode citée, la réponse aurait été 2.
Hafsa
Points
41
Regarde ça : http://www.cs.jhu.edu/~xfliu/600.363_F03/hw_solution/solution1.pdf
J'espère qu'il vous donnera la bonne réponse.
- 2-3 Inversion partie (d)
- Son temps d'exécution est de O(nlogn).
