☰

なぜ [20, ..., 13, 14].min(2) => [13, 20] なのでしょうか? 質問する

tag-icon • tag-icon ruby min
なぜ [20, ..., 13, 14].min(2) => [13, 20] なのでしょうか? 質問する 
[20, 32, 32, 21, 30, 25, 29, 13, 14].min(2)
# => [13, 20]

なぜそうではないのか[13, 14]？そしてどうしてする欲しいもの、つまり最小の 2 つの要素 (線形時間) が得られますか?

ドクの文章「n 引数が指定された場合、最小 n 個の要素が配列として返されます」よく分かりませんが、min(2)最小の2つの要素を返すと書いてあると思います。これについてはあまり見つけられませんでしたが、このスレッドおそらく原点である は、 と同じものを返すはずだと言っているようですがsort.first(n)、実際にはそうではありません。

[20, 32, 32, 21, 30, 25, 29, 13, 14].sort.first(2)
# => [13, 14]

愚かな質問で申し訳ありません。また、「大きな」例で申し訳ありませんが、これはすでに縮小されています。もう 1 つの数字 (13 または 14 以外) を削除すると、 になります[13, 14]。

ベストアンサー1

バグの説明を投稿しましたRuby 問題追跡システム:

問題を見つけたと思います。最初の例を見てみましょう。

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

これはファイル「enum.c」の関数「nmin_run」を呼び出し、「bufmax」を必要な最小値の数（n）の4倍に設定します（例ではbufmaxは8です）。そして、次の行で1327元の配列の各要素に対して関数「nmin_i」を呼び出します。

関数「nmin_i」では、バッファがいっぱいになると（「data->curlen == data->bufmax」）、関数「nmin_filter」が呼び出されます。この例では、curlen が 8 のときにこれが発生し、バッファは [20, 32, 32, 21, 30, 25, 29, 13] になります。「nmin_filter」は、これまでの最小の n 個の要素がバッファの左端に来るまでクイックソートを実行し、残りの要素を破棄します。バッファには [20, 13] が残ります。

ここで問題が始まります。「nmin_filter」の最後で、制限 (明らかにバッファー内の最大値を格納する目的で) がバッファー内の最後の値 (例では 13) に設定されていますが、これは正しくありません。次に、その値に基づいて、「nmin_i」はそれより大きい残りの要素をすべて破棄します (例では 14 を破棄します)。次にバッファーがソートされ、次の結果が返されます。

[13, 20]

したがって、解決策としては、制限に関連する部分をすべて削除するか、最後のピボットを制限として採用します。

おすすめ記事