I don’t think I understand the problem. We have n distinct integers, and the array has already been partitioned. Why isn’t the answer just that there was exactly one pivot that could generate that partition?
Take the trivial example where A is [1, 3, 2, 4]. We can pivot around 2 to get A' = [1, 2, 3, 4], but we can also pivot around 3 to get A' = [1, 2, 3, 4]. So given A', both 2 and 3 are valid pivots.
Edit: in fact, 1 and 4 may be valid pivots too for this example, if empty subarrays are allowed (remember that we don't necessarily know A, so A = [4, 1, 2, 3] with a pivot of 4 will yield the same A' = [1, 2, 3, 4], as will A = [2, 3, 4, 1] with a pivot of 1).
I didin't really understand it either. I think the problem is taking in an array that's already been partitioned around a pivot, and then trying to figure out how many numbers could have been the pivot. The reason why this isn't just the length of the array is because the array is already pivoted. The reason why you have to use a linear scan is because the array is still in unsorted order.
For [1, 2, 3, 4, 5] there are 5 pivots.
For [1, 2, 3, 5, 4] there are 3 pivots (1, 2, and 3)
Found something weird with codes posted in the links. I am getting different outputs for the intermediate and the final codes for the input of "5; 1,2,3,4,4". Can someone help?
> Starting from an array A that has n distinct integers
I don't know in what ways they are differents, but these programs were not designed to work with duplicates in the input. This probably explains the results.
Python has some unusual performance behaviors. IIRC you can also speed up the performance of your program a lot by assigning intermediate variables instead of referencing properties, for example:
Unfortunately, Python being hopelessly dynamic, `A.b` could involve executing arbitrary code and side effects depending on what `A` is. So hoisting `A_b = A.b` out of the loop may produce different results and thus can't be done automatically without some kind-of incredibly (impossibly?) smart static analysis :(
(though perhaps a JIT could perform this optimization for the usual, non-surprising path)
I'm not sure about other implementations, but "optimizing" CPython ends up being optimizing against counter-intuitive interpreter internals rather than time-complexity of the code.
For example, in CPython 3.6,
n = 0
d = 100
for i in range(10**6):
n += i
if n >= d:
n %= d
is slower than
n = (n + i) % d
This counter to lower level languages, where dividing by a variable is costly, and the CPU can predict the pipeline to be false most of the time in the conditional and thus skip it.
Properties are not the same thing as attributes though. If `A.b` is a property (has a __get__ method associated with it), then this could easily break your code because `A.b` is supposed to change values. If it's an attribute that stays the same, then yeah I'll grant you that it could speed things up if it's being accessed frequently in a loop. There's not really any way for Python to tell if it can be optimized statically.
This is just a reflection from recent work on interpreter internals, but I figured it could be relevant to someone walking the same paths.
Allocating registers for all local vars statically means scopes have different sizes, which in turn complicates slab allocation and/or reuse. In return for being easier to reason about (except for the main scope issue) and saving space.
I opted for a fixed number of linearly assigned registers per scope in Snigl [0]; once the limit is reached, remaining variables are stored in a table. Which means I sort of get both, since additional scopes may be added using {} (it could make sense to add a scope: keyword to Python) if that becomes an issue.
Slightly OT from the main takeaway, but I wonder if this could be sped up further by only doing a single pass, and maintaining a stack (implicitly sorted) of elements which are greater than everything seen so far, and popping them off when they're greater than the current element.
23 comments
[ 2.7 ms ] story [ 54.2 ms ] threadEdit: in fact, 1 and 4 may be valid pivots too for this example, if empty subarrays are allowed (remember that we don't necessarily know A, so A = [4, 1, 2, 3] with a pivot of 4 will yield the same A' = [1, 2, 3, 4], as will A = [2, 3, 4, 1] with a pivot of 1).
For [1, 2, 3, 4, 5] there are 5 pivots.
For [1, 2, 3, 5, 4] there are 3 pivots (1, 2, and 3)
For [2, 1, 3, 5, 4] there is only 1 (3).
1. https://imgur.com/a/u8O65AF
2. https://imgur.com/a/uHniZof
I don't know in what ways they are differents, but these programs were not designed to work with duplicates in the input. This probably explains the results.
[A.b[i] for i in range(100)]
is a lot slower than:
B = A.b
[B[i] for i in range (100)]
It is something that compilers do for you, in this context, in most programming environments.
(though perhaps a JIT could perform this optimization for the usual, non-surprising path)
For example, in CPython 3.6,
is slower than This counter to lower level languages, where dividing by a variable is costly, and the CPU can predict the pipeline to be false most of the time in the conditional and thus skip it.I think there's a bug in the code then. It will be skipped a few times, but for i between 100 and 10^6, the condition is guaranteed true every time.
https://ideone.com/4R0suA
Allocating registers for all local vars statically means scopes have different sizes, which in turn complicates slab allocation and/or reuse. In return for being easier to reason about (except for the main scope issue) and saving space.
I opted for a fixed number of linearly assigned registers per scope in Snigl [0]; once the limit is reached, remaining variables are stored in a table. Which means I sort of get both, since additional scopes may be added using {} (it could make sense to add a scope: keyword to Python) if that becomes an issue.
It's all compromises, all the way down.
[0] https://gitlab.com/sifoo/snigl