[ruby-core:70477] [Ruby trunk - Bug #11471] [Open] min, min_by, max, max_by with optional parameter return a wrong value

[ruby-core:70477] [Ruby trunk - Bug #11471] [Open] min, min_by, max, max_by with optional parameter return a wrong value

[sawadatsuyoshi]

Issue #11471 has been reported by Tsuyoshi Sawada.

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]



-- 
https://bugs.ruby-lang.org/

[ruby-core:70479] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[lcorr005]

Issue #11471 has been updated by 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.



----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53880

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70480] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[helfper]

Issue #11471 has been updated by Helder Pereira.


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

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

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53881

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70481] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[helfper]

Issue #11471 has been updated by 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](https://github.com/ruby/ruby/blob/trunk/enum.c#L1327) 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 look into all elements that are on the right-side of the last pivot to calculate the limit.

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53882

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70482] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[lcorr005]

Issue #11471 has been updated by 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]


----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53885

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70483] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[lcorr005]

Issue #11471 has been updated by Leo Correa.

File enum_bug_fix.patch added

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53886

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)
enum_bug_fix.patch (2.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70484] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[helfper]

Issue #11471 has been updated by 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);
    }
~~~

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53887

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)
enum_bug_fix.patch (2.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70485] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[yasuhiro6194]

Issue #11471 has been updated by Yasuhiro NAKAMURA.


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

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53889

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70487] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[helfper]

Issue #11471 has been updated by Helder Pereira.

File enum_nmin_filter_fix.patch added

Here is my fix.

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

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53890

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
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]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)
enum_nmin_filter_fix.patch (2.42 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70681] [Ruby trunk - Bug #11471] [Assigned] min, min_by, max, max_by with optional parameter return a wrong value

[nagachika00]

Issue #11471 has been updated by Tomoyuki Chikanaga.

Status changed from Open to Assigned
Assignee set to 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

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-54071

* Author: Tsuyoshi Sawada
* Status: Assigned
* Priority: Normal
* Assignee: Akira Tanaka
* ruby -v: 
* Backport: 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: REQUIRED
----------------------------------------
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]

---Files--------------------------------
enum_nmin_filter_fix.patch (2.42 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70698] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[funny.falcon]

Issue #11471 has been updated by Yura Sokolov.


Algorithm should be based on a heap.

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-54090

* Author: Tsuyoshi Sawada
* Status: Assigned
* Priority: Normal
* Assignee: Akira Tanaka
* ruby -v: 
* Backport: 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: REQUIRED
----------------------------------------
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]

---Files--------------------------------
enum_nmin_filter_fix.patch (2.42 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:70978] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

[nagachika00]

Issue #11471 has been updated by 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.

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-54354

* Author: Tsuyoshi Sawada
* Status: Closed
* Priority: Normal
* Assignee: Akira Tanaka
* ruby -v: 
* Backport: 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: DONE
----------------------------------------
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]

---Files--------------------------------
enum_nmin_filter_fix.patch (2.42 KB)


-- 
https://bugs.ruby-lang.org/