Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Incrementally improving the performance of a Python script

mycode.doesnot.run

Post reply on HN
Print view View original

1–10 of 24 posts

Re: Incrementally improving the performance of a Python script

#4

Post by smaccona »

monochromatic wrote: post #3

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).

Re: Incrementally improving the performance of a Python script

#5

Post by jonathankoren »

monochromatic wrote: post #3

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?

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)

For [2, 1, 3, 5, 4] there is only 1 (3).

Re: Incrementally improving the performance of a Python script

#7

Post by monochromatic »

jonathankoren wrote: post #5
monochromatic wrote: post #3

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?

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 a…

That makes more sense. Thanks.

Re: Incrementally improving the performance of a Python script

#9

Post by acqq »

indweller wrote: post #6

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? 1. https://imgur.com/a/u8O65AF 2. https://imgur.com/a/uHniZof

Is the input valid per definition of the problem?

Re: Incrementally improving the performance of a Python script

#10

Post by Yxogenium »

indweller wrote: post #6

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? 1. https://imgur.com/a/u8O65AF 2. https://imgur.com/a/uHniZof

> 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.

Post reply on HN