Github user shubhamchopra commented on a diff in the pull request:
https://github.com/apache/spark/pull/13932#discussion_r108204165
--- Diff:
core/src/main/scala/org/apache/spark/storage/BlockReplicationPolicy.scala ---
@@ -53,6 +53,46 @@ trait BlockReplicationPolicy {
numReplicas: Int): List[BlockManagerId]
}
+object BlockReplicationUtils {
+ // scalastyle:off line.size.limit
+ /**
+ * Uses sampling algorithm by Robert Floyd. Finds a random sample in
O(n) while
+ * minimizing space usage. Please see <a
href="http://math.stackexchange.com/questions/178690/whats-the-proof-of-correctness-for-robert-floyds-algorithm-for-selecting-a-sin";>
+ * here</a>.
+ *
+ * @param n total number of indices
+ * @param m number of samples needed
+ * @param r random number generator
+ * @return list of m random unique indices
+ */
+ // scalastyle:on line.size.limit
+ private def getSampleIds(n: Int, m: Int, r: Random): List[Int] = {
+ val indices = (n - m + 1 to
n).foldLeft(mutable.LinkedHashSet.empty[Int]) {case (set, i) =>
+ val t = r.nextInt(i) + 1
+ if (set.contains(t)) set + i else set + t
+ }
+ indices.map(_ - 1).toList
+ }
+
+ /**
+ * Get a random sample of size m from the elems
+ *
+ * @param elems
+ * @param m number of samples needed
+ * @param r random number generator
+ * @tparam T
+ * @return a random list of size m. If there are fewer than m elements
in elems, we just
+ * randomly shuffle elems
+ */
+ def getRandomSample[T](elems: Seq[T], m: Int, r: Random): List[T] = {
+ if (elems.size > m) {
+ getSampleIds(elems.size, m, r).map(elems(_))
+ } else {
+ r.shuffle(elems).toList
--- End diff --
I completely agree with you here. Except I was told earlier that iterating
through a list the size of the executors was a concern. So this was to address
time complexity.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
