uros-b commented on code in PR #57528:
URL: https://github.com/apache/spark/pull/57528#discussion_r3839334619
##########
core/src/test/scala/org/apache/spark/util/UtilsSuite.scala:
##########
@@ -1892,6 +1893,79 @@ class UtilsSuite extends SparkFunSuite with
ResetSystemProperties {
assert(new String(Files.readAllBytes(new File(dir, "file2.txt").toPath),
UTF_8) === "world")
}
}
+
+ test("SPARK-48290: nthSmallest returns the same elements as sorting") {
+ val inputs = Seq(
+ Array(1L),
+ Array(2L, 1L),
+ Array(5L, 4L, 3L, 2L, 1L),
+ Array(1L, 1L, 1L, 1L),
+ Array.tabulate(1000)(i => i.toLong),
+ Array.tabulate(1000)(i => (1000 - i).toLong),
+ Array.tabulate(1000)(_ => 7L),
+ Array.tabulate(1000)(i => math.min(i, 999 - i).toLong),
+ Array.fill(1000)(Random.nextLong()))
+ inputs.foreach { input =>
+ val expected = input.sorted
+ for (n <- input.indices) {
+ assert(Utils.nthSmallest(input.clone(), n) === expected(n))
+ }
+ }
+ }
+
+ test("SPARK-48290: nthSmallest is not quadratic on an organ pipe
distribution") {
+ // Sizes that rise and then fall defeat any fixed pivot choice, so a plain
quickselect needs
+ // more than 10^11 comparisons for these selections and does not finish in
any reasonable
+ // time. Sorting the range still under consideration keeps each selection
in the millisecond
+ // range, so the time limit only has to be generous enough to be free of
flakiness.
+ val length = 1 << 20
+ val input = Array.tabulate(length)(i => math.min(i, length - 1 - i).toLong)
+ val expected = input.sorted
+ failAfter(60.seconds) {
+ Seq(0, 1, length / 2 - 1, length / 2, length - 100, length - 1).foreach
{ n =>
+ assert(Utils.nthSmallest(input.clone(), n) === expected(n))
+ }
+ }
+ }
+
+ test("SPARK-48290: nthSmallest partitions the array around the returned
element") {
+ // HighlyCompressedMapStatus counts the block sizes above the cutoff by
scanning only the tail
Review Comment:
Nit: Factually wrong test comment at UtilsSuite.scala:1932-1933 claims
HighlyCompressedMapStatus "scans only the tail of the array," but the shipped
apply iterates the original uncompressedSizes(i) against the scalar skewCutoff
and never scans the partitioned tail. Kept as a concern (not demoted) because
it's a factual inaccuracy in shipped code, not just PR prose. The test itself
is fine, only its stated reason is wrong.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
