Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value

• Status: Closed
• Assignee: akr (Akira Tanaka)
• Target version: -
• Backport: 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: DONE

[sawa (Tsuyoshi Sawada)]

This is reported in StackOverflow: http://stackoverflow.com/questions/32121749/why-20-13-14-min2-13-20. Sometimes min, min_by, max, max_by with an optional parameter return a wrong value.

[20, 32, 32, 21, 30, 25, 29, 13, 14].min(2) # => [13, 20]
[20, 32, 32, 21, 30, 25, 29, 13, 14].min_by(2, &:itself) # => [13, 20]
[0, 0, 0, 0, 0, 0, 1, 3, 2].max(2) # => [3, 1]
[0, 0, 0, 0, 0, 0, 1, 3, 2].max_by(2, &:itself) # => [3, 1]

[tonkpils (Leo Correa)]

• File enum_bug_fix.patch added

I have made a patch that seems to fix the issue for these cases. I'm not entirely sure why there was a multiplier for data.bufmax in the first place but it seemed to be the cause.

[helfper (Helder Pereira)]

Leo Correa, I think your patch will fail for this example:

[2, 4, 8, 6, 7].min(4) #=> [2, 4, 6, 8]

[helfper (Helder Pereira)]

I suppose I found the problem. Taking the first example:

[20, 32, 32, 21, 30, 25, 29, 13, 14].min(2)

This will call the function "nmin_run" in the file "enum.c", which sets "bufmax" to 4 times the number of minimums (n) we want (for the example, bufmax is 8), and then in the line 1327 will call the function "nmin_i" for each element of the original array.

In the function "nmin_i", when the buffer is full ("data->curlen == data->bufmax"), the function "nmin_filter" is called. In the example, that happens when curlen is 8, and so the buffer is [20, 32, 32, 21, 30, 25, 29, 13]. The "nmin_filter" will do a quicksort until the n smallest elements so far are on the leftmost part of the buffer, and will discard the rest of the elements, which leaves us with [20, 13] in the buffer.

And now starts the problem. At the end of "nmin_filter" the limit (apparently with the intention of storing the greatest value in the buffer) is set to the last value in the buffer (in the example, 13), which is not true. And then based on that value "nmin_i" will discard all remaining elements greater than that (in the example, discarding the 14). The buffer is then sorted and it returns:

[13, 20]

So the solution is either remove all the limit-related part, or take the last pivot as the limit.

[tonkpils (Leo Correa)]

Helder Pereira wrote:

Leo Correa, I think your patch will fail for this example:

[2, 4, 8, 6, 7].min(4) #=> [2, 4, 6, 8]

I made a test case for that and passed with [2, 4, 6, 7]

[tonkpils (Leo Correa)]

• File enum_bug_fix.patch added

[helfper (Helder Pereira)]

Yes, I was wrong. I missed this check in "nmin_filter":

    if (data->curlen <= data->n)
        return;

Which means that your patch will never execute the "nmin_filter" (that is where the bug lays) until it is called in "nmin_run", and consequently the buffer will grow until the size of the original array (and will not be proportionally to the number of elements we want anymore).

Because your patch makes this piece of code in "nmin_i" useless:

    if (data->curlen == data->bufmax) {
        nmin_filter(data);
    }

[tonkpils (Leo Correa)]

• File deleted (enum_bug_fix.patch)

[nkmrya (Yasuhiro Nakamura)]

I found the ticket which to request and discuss this feature. Thicket is #8887.

[helfper (Helder Pereira)]

• File enum_nmin_filter_fix.patch enum_nmin_filter_fix.patch added

Here is my fix.

I also created a pull request:
https://github.com/ruby/ruby/pull/1005

[tonkpils (Leo Correa)]

• File deleted (enum_bug_fix.patch)

[nagachika (Tomoyuki Chikanaga)]

• Status changed from Open to Assigned
• Assignee set to akr (Akira Tanaka)
• Backport changed from 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN to 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: REQUIRED

Thank you for your report and patches.

I've confirmed that the issue exists in ruby-2.2.3 too.

akr san, please review the PR? https://github.com/ruby/ruby/pull/1005

[funny_falcon (Yura Sokolov)]

Algorithm should be based on a heap.

[akr (Akira Tanaka)]

• Status changed from Assigned to Closed

Applied in changeset r52026.

---

• enum.c (nmin_filter): Fix limit value.
  patch by Helder Pereira.
  [Bug #11471] [ruby-core:70477]

[nagachika (Tomoyuki Chikanaga)]

• Backport changed from 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: REQUIRED to 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: DONE

Backported into ruby_2_2 branch at r52032.