You are almost correct.
I believe you are interpreting the performance as \$O(n²*logn)\$ because you are looping over (most of) the items in the input array (length = n) and you are using a sort to compute your median.
However, sorted's performance is actually determined by the size of the window parameter, D, which is a constant, and its log is a constant, too! So your performance is technically \$O(n*DlogD)\$, which is \$O(n × C)\$ which is \$O(n)\$.
But you can do better!
Assume for a moment that you have the window sorted. You now receive a sequence of pairs (a, z) where value a is to be removed from the window and value z inserted. Once this is done, you will need to recompute the median.
Also, you have two cases: one where the window size D is an odd number and thus the median is one of the values in the window; and the other case where the window size is an even number and the median must be computed as the mean of the central values.
I think that if you separate your code into two functions at the top level - one for even windows, one for odd windows, you can write code that updates the sorted window without having to invoke the sorted function each time through. Thus, instead of D log D you can perform one removal and one insert in a single pass, having time proportional to D.
You'll still pass over nearly all the items in the list, so your time will still be \$O(n)\$, but it won't be times quite so large a constant.
Edit for @hjpotter92:
You are traversing an unsorted sequence of numbers, using a sliding window:
D = 4
[a, b, c, d,] e, f, g, h
a, [b, c, d, e,] f, g, h
a, b, [c, d, e, f,] g, h
Each time you advance, your window adds one number (I called it z) on the right side, and loses one number (I called it a) from the left side. So instead of pretending that each window is a whole new bunch of numbers that have to be put into order, using sort, you can write your code to remove one number, insert one number, and then recompute the median.
In some cases (D is odd), the median is just window[D//2]. In other cases (D is even), the median is (window[D//2-1] + window[D//2]) / 2. This is because of how the median is computed. You can see OP doing this computation in the original code. However, there's no reason to keep checking D for odd/even, since it never changes in the function. Instead, it's better to split the function at the top level, and proceed from there:
def func(sequence, d):
if d % 2 == 0: # D is even
# code for scanning with even window size
else: # D is odd
# code for scanning with odd window size
Edit 2: Comprehensive performance test
I made some changes to your code to test various performance enhancements. Here is one set of results run on my 2011 MacBook Pro (numbers are seconds, lower is better):
$ python -V
Python 3.5.4
$ python test.py
With n=10 inputs, d=4
replsort 0.925
replsort2 1.063
linsert 1.549
insbisect 1.102
noparity 0.965
orig 1.129
With n=1000 inputs, d=4
replsort 3.945
replsort2 4.268
linsert 5.210
insbisect 4.280
noparity 4.431
orig 5.324
With n=1000 inputs, d=50
replsort 7.384
replsort2 7.156
linsert 8.763
insbisect 4.736
noparity 10.172
orig 10.854
With n=1000 inputs, d=500
replsort 10.447
replsort2 10.590
linsert 8.184
insbisect 6.641
noparity 50.901
orig 49.458
The orig function is your code. The noparity function is your code with the parity check hoisted to the top. The replsort functions maintain the window by replacing the a value with the z value (as discussed above) and then sorting the window. The linsert and insbisect functions work by doing a linear scan of the window, or by calling bisect.insort_left, respectively, to get the z value in place.
Important: your example is bad. You've got a short list of input numbers, with a small window size. That means the "fixed costs" will tend to dominate your performance.
What does that mean? It means that things like calling the function, initializing count = 0, setting up and tearing down the for loop, and executing the return statement will make a difference.
It also means that the difference between \$O(n)\$ and \$O(log\ n)\$ and \$O(n\ log\ n)\$ don't seem to matter.
But when I switched to generating 1000 random numbers, instead of 10 fixed numbers, things changed! Notice the linsert function goes from being 50% slower, to being something like 25% slower when n=1000. Also, notice that all the other functions beat noparity. I believe this is because noparity always recomputes the entire slice before sorting it. That computation got added in 990 more times (for d=4) and it started to be a drag on the performance.
Finally, I started increasing the window size. This is where the magic really happens, because this affects the performance of the sort, the bisect, the window search and removes. Essentially, this is the number that really determines the differences in performance. For a small window size, again the upfront costs of calling sorted or remove or bisect are dominating. But when the window size goes up, suddenly the differences in algorithmic efficiency start to matter.
And look what happens with d=500. First, realize that setting d=500 means the code only does half the work! Because the input of 1000 minus a 500 window size leaves 500 checks to run, rather than 996 (d=4) or 950 (d=50). But when that change is made, suddenly linsert (which is \$O(d)\$) and insbisect (which is \$O(log\ d)\$) outperform everybody. Because "setup costs" and "written in C" no longer cover up \$O(d\ log\ d)\$!
# test.py
import bisect
def orig(expenditure, d):
""" Worst-case: O( n^2 * logn ) """
num_of_trans = len(expenditure) - 1
count = 0
for i in range(d, num_of_trans):
prev_trans = sorted(expenditure[i - d:i])
if d % 2 == 0:
left_i = (d - 1) // 2
right_i = left_i + 1
median = prev_trans[left_i] + prev_trans[right_i]
else:
median = prev_trans[d - 1]
if expenditure[i] >= median:
count += 1
return count
def noparity(expenditure, d):
"""Hoist parity check out of loop"""
num_of_trans = len(expenditure) - 1
count = 0
left_i = (d - 1) // 2
right_i = left_i + 1
if d % 2 == 0:
for i in range(d, num_of_trans):
prev_trans = sorted(expenditure[i - d:i])
median_x2 = prev_trans[left_i] + prev_trans[right_i]
if expenditure[i] >= median_x2:
count += 1
else:
for i in range(d, num_of_trans):
prev_trans = sorted(expenditure[i - d:i])
median_x2 = prev_trans[d // 2] * 2
if expenditure[i] >= median_x2:
count += 1
return count
def linsert(expenditure, d):
"""Hoisted median, using linear insertion instead of sort"""
count = 0
len_exp = len(expenditure)
window = sorted(expenditure[:d])
winremove = window.remove
winsert = window.insert
winappend = window.append
if d % 2 == 0:
m1 = d // 2
m0 = m1 - 1
ai = 0
for zi in range(d, len_exp):
median_x2 = window[m0] + window[m1]
a, z = expenditure[ai], expenditure[zi]
ai += 1
if z >= median_x2:
count += 1
winremove(a)
for i in range(d-1): # d-1 because .remove
if window[i] <= z:
winsert(i, z)
break
else:
winappend(z)
else:
raise NotImplementedError("I haven't written this code.")
return count
def insbisect(expenditure, d):
"""Hoisted median, using bisect for insertion."""
count = 0
len_exp = len(expenditure)
window = sorted(expenditure[:d])
winremove = window.remove
if d % 2 == 0:
m1 = d // 2
m0 = m1 - 1
ai = 0
for zi in range(d, len_exp):
median_x2 = window[m0] + window[m1]
a, z = expenditure[ai], expenditure[zi]
ai += 1
if z >= median_x2:
count += 1
winremove(a)
bisect.insort_left(window, z)
else:
raise NotImplementedError("I haven't written this code.")
return count
def replsort(expenditure, d):
"""Hoisted median, using replacement via index, then sort."""
count = 0
window = sorted(expenditure[:d])
windex = window.index
winsort = window.sort
if d % 2 == 0:
m1 = d // 2
m0 = m1 - 1
for a, z in zip(expenditure, expenditure[d:]):
median_x2 = window[m0] + window[m1]
if z >= median_x2:
count += 1
# Note: do not write `window =` anywhere, or you invalidate
# windex and winsort.
window[windex(a)] = z
winsort()
else:
raise NotImplementedError("I haven't written this code.")
return count
def replsort2(expenditure, d):
"""Hoisted median, using replacement via index, then sort."""
count = 0
len_exp = len(expenditure)
window = sorted(expenditure[:d])
windex = window.index
winsort = window.sort
if d % 2 == 0:
m1 = d // 2
m0 = m1 - 1
ai = 0
for zi in range(d, len_exp):
median_x2 = window[m0] + window[m1]
a, z = expenditure[ai], expenditure[zi]
ai += 1
if z >= median_x2:
count += 1
# Note: do not write `window =` anywhere, or you invalidate
# windex and winsort.
window[windex(a)] = z
winsort()
else:
raise NotImplementedError("I haven't written this code.")
return count
if __name__ == "__main__":
from timeit import timeit
from random import randrange as rr
results =[line.strip().split() for line in """
replsort 9.730
replsort2 11.538
linsert 17.954
insbisect 10.970
noparity 10.574
orig 11.801
""".splitlines() if line.strip()]
print("\nWith n=10 inputs, d=4")
for funcname, time_for_me in results:
print(" {:20s} {:5.3f}".format(funcname,
timeit('{}([2,3,4,2,3,6,8,4,5], 4)'.format(funcname),
setup='from __main__ import {}'.format(funcname),
number=100000)))
print("\nWith n=1000 inputs, d=4")
for funcname, time_for_me in results:
print(" {:20s} {:5.3f}".format(funcname,
timeit('{}([rr(1, 16) for _ in range(1000)], 4)'.format(funcname),
setup='from __main__ import rr, {}'.format(funcname),
number=1000)))
print("\nWith n=1000 inputs, d=50")
for funcname, time_for_me in results:
print(" {:20s} {:5.3f}".format(funcname,
timeit('{}([rr(1, 16) for _ in range(1000)], 50)'.format(funcname),
setup='from __main__ import rr, {}'.format(funcname),
number=1000)))
