我正在设计一个算法来执行以下操作:给定数组A[1... n],对于每个i < j,找到所有的反转对A[i] > A[j].我正在使用合并排序并将数组A复制到数组B,然后比较两个数组,但我很难看到如何使用它来查找反转次数.任何提示或帮助将不胜感激.
所以这是java中的O(n log n)解决方案.
long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i+j] = right[j];
j++;
} else if (j == right.length) {
arr[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i+j] = left[i];
i++;
} else {
arr[i+j] = right[j];
count += left.length-i;
j++;
}
}
return count;
}
long invCount(int[] arr) {
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return invCount(left) + invCount(right) + merge(arr, left, right);
}
这几乎是正常的合并排序,整个魔术隐藏在合并功能中.请注意,虽然排序算法会删除反转.虽然合并算法会计算删除的反转次数(可能会说出一个可能会被解析).
删除反转的唯一时刻是算法从数组的右侧获取元素并将其合并到主数组.此操作删除的反转次数是要合并的左数组剩余的元素数.:)
希望它足够解释.
我通过以下方法在O(n*log n)时间内找到它.
合并排序数组A并创建副本(数组B)
取A [1]并通过二分搜索在排序数组B中找到它的位置.此元素的反转次数将比其在B中的位置的索引号少一个,因为在A的第一个元素之后出现的每个较低的数字都将是反转.
2A.累计反转变量num_inversions的反转次数.
2B.从数组A中删除A [1],并从数组B中的相应位置删除
从第2步重新运行,直到A中没有更多元素.
以下是此算法的示例运行.原始数组A =(6,9,1,14,8,12,3,2)
1:合并排序并复制到数组B.
B =(1,2,3,6,8,9,12,14)
2:进行A [1]和二分搜索,在数组B中找到它
A [1] = 6
B =(1,2,3,6,8,9,12,14)
在图6中,在阵列B的第4位置,因此存在3次反转.我们知道这是因为6位于数组A中的第一个位置,因此随后出现在数组A中的任何较低值元素将具有j> i的索引(因为在这种情况下i是1).
2.b:从数组A中删除A [1],并从数组B中的相应位置删除(粗体元素被删除).
A =(6,9,1,14,8,12,3,2)=(9,1,14,8,12,3,2)
B =(1,2,3,6, 8,9,12,14)=(1,2,3,8,9,12,14)
3:在新的A和B阵列上从第2步重新运行.
A [1] = 9
B =(1,2,3,8,9,12,14)
9现在处于阵列B的第5位置,因此有4个反转.我们知道这是因为9位于数组A的第一个位置,因此随后出现的任何较低值元素将具有j> i的索引(因为在这种情况下i再次为1).从数组A中删除A [1],也从数组B中的相应位置删除(粗体元素被删除)
A =(9,1,14,8,12,3,2)=(1,14,8,12,3,2)
B =(1,2,3,8,9,12,14)=(1,2,3,8,12,14)
继续这种情况将在循环完成后为我们提供阵列A的反转总数.
步骤1(合并排序)将执行O(n*log n).步骤2将执行n次,并且在每次执行时将执行二进制搜索,该搜索使O(log n)运行总共O(n*log n).因此总运行时间为O(n*log n)+ O(n*log n)= O(n*log n).
谢谢你的帮助.在一张纸上写出样本数组确实有助于可视化问题.
在Python中
# O(n log n)
def count_inversion(lst):
return merge_count_inversion(lst)[1]
def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = int( 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
#test code
input_array_1 = [] #0
input_array_2 = [1] #0
input_array_3 = [1, 5] #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5] #5
input_array_7 = [4, 1, 3, 2, 9, 1] #8
print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)
我想知道为什么没有人提到二进制索引树.您可以使用一个来维护排列元素值的前缀和.然后你可以从右到左继续计算每个元素的元素数量比右边小:
def count_inversions(a):
res = 0
counts = [0]*(len(a)+1)
rank = { v : i+1 for i, v in enumerate(sorted(a)) }
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
复杂度为O(n log n),常数因子非常低.
实际上,我有一个与家庭作业类似的问题.我被限制为必须具有O(nlogn)效率.
我使用了你提出的使用Mergesort的想法,因为它已经具有正确的效率.我刚刚在合并函数中插入了一些代码:基本上,当右边数组中的数字被添加到输出数组时,我会添加反转的总数,即左数组中剩余的数字量.
这对我来说很有意义,因为我已经考虑过了.你计算在任何数字之前有多少次数.
心连心.
通过分析合并排序中的合并过程可以找到反转次数:
将元素从第二个数组复制到合并数组(此示例中为9)时,它会相对于其他元素保持其位置.将元素从第一个数组复制到合并数组(此处为5)时,它将被反转,所有元素都保留在第二个数组中(2与3和4反转).因此,对合并排序的一点修改可以解决O(n ln n)中的问题.
例如,只需取消注释下面mergesort python代码中的两个#行即可获得计数.
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] 6
编辑1
使用稳定版本的快速排序可以实现相同的任务,已知速度稍快:
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)
选择pivot作为最后一个元素,反转计算得很好,执行时间比合并上面的要好40%.
编辑2
对于python中的性能,numpy和numba版本:
首先使用argsort O(n ln n)的numpy部分:
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)
和有效的BIT方法的numba部分:
@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
请注意,杰弗里欧文的回答是错误的.
数组中的反转次数是必须移动元素的总距离的一半,以便对数组进行排序.因此,可以通过对数组进行排序,维持得到的置换p [i],然后计算abs(p [i] -i)/ 2的和来计算它.这需要O(n log n)时间,这是最佳的.
另一种方法在http://mathworld.wolfram.com/PermutationInversion.html上给出.此方法等于max(0,p [i] -i)之和,它等于abs(p [i] -i])/ 2之和,因为向左移动的总距离等于总距离元素向右移动.
以序列{3,2,1}为例.有三个反转:(3,2),(3,1),(2,1),因此反转数为3.但是,根据引用的方法,答案应该是2.
这个答案的主要目的是比较这里找到的各种Python版本的速度,但我也有一些自己的贡献.(FWIW,我刚刚在执行重复搜索时发现了这个问题).
CPython中实现的算法的相对执行速度可能与对算法的简单分析和其他语言的经验所期望的相反.这是因为Python提供了许多在C中实现的功能强大的函数和方法,它们可以以接近完全编译语言的速度在列表和其他集合上运行,因此这些操作的运行速度比使用Python"手动"实现的等效算法快得多码.
利用这些工具的代码通常可以胜过理论上优越的算法,这些算法试图通过Python操作对集合的各个项目执行所有操作.当然,正在处理的实际数据量也会对此产生影响.但是对于适量的数据,使用以C速度运行的O(n²)算法的代码可以很容易地胜过O(n log n)算法,该算法通过单独的Python操作完成大部分工作.
这个反演计数问题的许多发布的答案都使用基于mergesort的算法.从理论上讲,这是一种很好的方法,除非阵列大小非常小.但是Python内置的TimSort(混合稳定排序算法,从合并排序和插入排序派生)以C速度运行,而Python手工编写的mergesort无法与它竞争速度.
这里有一个比较有趣的解决方案,在Niklas B发布的答案中,使用内置排序来确定数组项的排名,并使用二进制索引树(又名Fenwick树)来存储计算反转所需的累积总和.计数.在尝试理解这个数据结构和Niklas的算法的过程中,我写了一些我自己的变体(在下面发布).但我也发现,对于中等列表大小,使用Python的内置函数实际上比可爱的Fenwick树更快sum.
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 total
最终,当列表大小达到500左右时,sum在该for循环内调用的O(n²)方面会出现丑陋的头部,并且性能开始下降.
Mergesort不是唯一的O(nlogn)排序,其他几个可用于执行反转计数.prasadvk的答案使用二叉树排序,但他的代码似乎是C++或其衍生产品之一.所以我添加了一个Python版本.我最初使用一个类来实现树节点,但发现dict明显更快.我最终使用了list,它甚至更快,尽管它确实使代码的可读性降低了一些.
treeort的一个好处是,它比mergesort更容易迭代实现.Python没有优化递归,它有一个递归深度限制(尽管如果你真的需要它可以增加).当然,Python函数调用相对较慢,因此当您尝试优化速度时,最好避免函数调用.
Another O(nlogn) sort is the venerable radix sort. It's big advantage is that it doesn't compare keys to each other. It's disadvantage is that it works best on contiguous sequences of integers, ideally a permutation of integers in range(b**m) where b is usually 2. I added a few versions based on radix sort after attempting to read Counting Inversions, Offline Orthogonal Range Counting, and Related Problems which is linked in calculating the number of "inversions" in a permutation.
为了有效地使用基数排序来计算seq长度为n 的一般序列中的反转,我们可以创建range(n)具有相同反转次数的排列seq.我们可以通过TimSort在(最坏的)O(nlogn)时间做到这一点.诀窍是seq通过排序来置换索引seq.用一个小例子来解释这个更容易.
seq = [15, 14, 11, 12, 10, 13] b = [t[::-1] for t in enumerate(seq)] print(b) b.sort() print(b)
产量
[(15, 0), (14, 1), (11, 2), (12, 3), (10, 4), (13, 5)] [(10, 4), (11, 2), (12, 3), (13, 5), (14, 1), (15, 0)]
通过对(值,索引)对进行排序,seq我们已经排列了seq具有相同数量的交换的索引,这些交换是seq从其排序顺序放入其原始顺序所需的.我们可以通过range(n)使用合适的键函数进行排序来创建排列:
print(sorted(range(len(seq)), key=lambda k: seq[k]))
产量
[4, 2, 3, 5, 1, 0]
我们能够避免lambda使用seq的.__getitem__方法:
sorted(range(len(seq)), key=seq.__getitem__)
This is only slightly faster, but we're looking for all the speed enhancements we can get. ;)
The code below performs timeit tests on all of the existing Python algorithms on this page, plus a few of my own: a couple of brute-force O(n²) versions, a few variations on Niklas B's algorithm, and of course one based on mergesort (which I wrote without referring to the existing answers). It also has my list-based treesort code roughly derived from prasadvk's code, and various functions based on radix sort, some using a similar strategy to the mergesort approaches, and some using sum or a Fenwick tree.
This program measures the execution time of each function on a series of random lists of integers; it can also verify that each function gives the same results as the others, and that it doesn't modify the input list.
每次timeit调用都会给出一个包含3个结果的向量,我将其排序.这里要看的主要值是最小值,其他值仅表示最小值的可靠性,如模块文档中的注释所述timeit.
不幸的是,这个程序的输出太大而不能包含在这个答案中,所以我将它发布在自己的(社区维基)答案中.
输出来自我在古老的32位单核2GHz机器上的3次运行,在旧的Debian衍生发行版上运行Python 3.6.0.因人而异.在测试期间,我关闭了我的Web浏览器并断开与路由器的连接,以最大限度地减少其他任务对CPU的影响.
第一次运行测试列表大小从5到320的所有函数,循环大小从4096到64(随着列表大小加倍,循环大小减半).用于构造每个列表的随机池的大小是列表本身的一半,因此我们可能会获得大量重复项.一些反转计数算法对重复数据比其他算法更敏感.
第二次运行使用较大的列表:640到10240,固定循环大小为8.为了节省时间,它从测试中消除了几个最慢的函数.我的蛮力O(N²)函数只是方式太在这些大小慢,而且正如前面提到的,我的代码使用sum,它这样做很好的小到中列出,只是不能跟上的大名单.
The final run covers list sizes from 20480 to 655360, and a fixed loop size of 4, with the 8 fastest functions. For list sizes under 40,000 or so Tim Babych's code is the clear winner. Well done Tim! Niklas B's code is a good all-round performer too, although it gets beaten on the smaller lists. The bisection-based code of "python" also does rather well, although it appears to be a little slower with huge lists with lots of duplicates, probably due to that linear while loop it uses to step over dupes.
However, for the very large list sizes, the bisection-based algorithms can't compete with the true O(nlogn) algorithms.
#!/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 /sf/ask/17360801/
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 /sf/ask/17360801/
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
# /sf/ask/17360801/
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
Please see here for the output
看看这个:http://www.cs.jhu.edu/~xfliu/600.363_F03/hw_solution/solution1.pdf
我希望它会给你正确的答案.
2-3反转部分(d)
它的运行时间是O(nlogn)
京公网安备 11010802040832号 | 京ICP备19059560号-6 