Strange Behavior of `partialSort`

[julmb]

I have the following code:

module Main (main) where

import Data.Vector
import Data.Vector.Algorithms.Heap

go :: Vector Int -> Vector Int
go = modify $ \ v -> partialSort v 2

main :: IO ()
main = print $ go $ fromList [4, 3, 2, 1, 5]

The documentation of partialSort says:

Moves the lowest k elements to the front of the array, sorted.
The remaining values of the array will be in no particular order.

From this, I would expect this to give me [1, 2, ...]. However, I get [1, 3, 4, 5, 2].

Is this a bug or am I doing something wrong?

[erikd]

I am not the original author of the, just the current maintainer.

The Data.Vector.Algorithms.Heap.partialSort function was added in commit b193602 in 2008 and does not seem to have changed since. There is a property test for Data.Vector.Algorithms.Heap.partialSort which seems to have been added in 2011.

However, I get the same result as you but do agree that I would expect the result to be [1, 2, ...] .

Maybe @dolio (original author) has some insight.

[erikd]

Running the original test on 3 different examples:

[4, 3, 2, 1]                         -> [1,2,3,4]                    # Good
[4, 3, 2, 1, 5]                      -> [1,3,4,5,2]                  # Bad
[2, 4, 3, 5, 8, 9, 10, 6, 7, 0, 1 ]  -> [0,3,5,8,1,9,10,6,7,2,4]     # Bad

[erikd]

Ah, ok, found an clue.

Doing partialSort v 2 results in the 1st position being right, but the second being wrong.

Doing partialSort v 3 results in the 1st two positions being right, but the third being wrong.

Doing partialSort v 4 results in the 1st three positions being right, but the fourth being wrong.

[erikd]

Applying a trivial patch:

-partialSortBy cmp a k = partialSortByBounds cmp a k 0 (length a)
+partialSortBy cmp a k = partialSortByBounds cmp a (k + 1) 0 (length a)

it now does the right thing and passes all tests. Obviously there is room for a property test to catch this.

Yes, @julmb I think this is a bug.

[julmb]

I feel like this patch is not enough, because then if we use partialSortByBounds directly, it still gives the wrong result:

>>> V.modify (\ v -> partialSortByBounds compare v 2 0 5) $ V.fromList [4, 3, 2, 1, 5]
[1,3,4,5,2]

I also took a look at the implementation of partialSortByBounds and an invocation partialSortByBounds compare v 2 0 5 leads to a call to sortHeap compare v 0 (0 + 4) (0 + 2) = sortHeap compare v 0 4 2. The documentation does not explicitly state that the last three parameters l, m, and u of sortHeap have to be non-decreasing, but I somewhat suspect that they should be in order for sortHeap to work correctly, since m is supposed to be an interior index between l and u.

It seems to me that the case distinction in partialSortByBounds does not take into account the case where k is less than 4 but the interval u - l is greater than 4, but I am not super confident since I do not 100% understand what that code is trying to do. Given this, I am also surprised that the k + 1 trick fixes the issue, maybe there is some accidental way things line up with powers of 2 less than 4 or something.

[julmb]

Obviously there is room for a property test to catch this.

It looks like the current test only checks if the prefix is sorted after the operation. It does not seem to check that the k first elements are actually the k smallest from the original vector, nor does it seem to check that the new vector has the same elements as the original vector.

[erikd]

I feel like this patch is not enough, because then if we use partialSortByBounds directly, it still gives the wrong result:

This was just an experiment. Yes, obviously partialSortByBounds needs fixing as well.

[erikd]

I have not written a QuickCheck test in years. I have been using Hedgehog for property testing.

[erikd]

Added a test to the PR above.