Github user sameeragarwal commented on a diff in the pull request:
https://github.com/apache/spark/pull/13932#discussion_r107970944
--- 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 --
Given that you're already shuffling the sample here anyways, just out of
curiosity is there any advantage of using Robert Floyd's algorithm over (say)
Fisher-Yates? Also, more generally, is space complexity really a concern here?
Can't we just use `r.shuffle(totalSize).take(sampleSize)` for easy readability?
---
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]
