Trick để shuffle một array
Scala
50
Spark
4
White

huydx viết ngày 21/09/2015

Vừa đọc được trong source code của spark một đoạn code để shuffle một array khá thú vị

Bài toán

Bạn có một array, ví dụ là {0,1,2,3,4,5,6,7} (thứ tự không quan trọng)
Bạn muốn shuffle array đó giống như bạn tráo bài trong đánh bạc vậy. Làm thế nào để shuffle array sao cho "đẹp" nhất, hay cụ thể hơn tỉ lệ xuất hiện của mỗi một phần tử trong array tại mỗi vị trí là ngang nhau

Cách giải quyết

Với đoạn code dưới đây (được viết bằng scala) thì bạn có thể shuffle array độ dài N với O(N) space và O(1) memory:

  def randomizeInPlace[T](arr: Array[T], rand: Random = new Random): Array[T] = {
    for (i <- (arr.length - 1) to 1 by -1) {
      val j = rand.nextInt(i)
      val tmp = arr(j)
      arr(j) = arr(i)
      arr(i) = tmp
    }
    arr
  }

Concept của đoạn code trên khá dễ hiểu: bạn loop từ đầu đến cuối, với mỗi phần tử loop đến bạn random ra một vị trí và swap vị trí của phần tử đó với vị trí random ra, rất dễ hiểu đúng không.

Ứng dụng

Trong spark có hàm gọi tên là takeSample , với ý nghĩa là truyền vào một data buffer (RDD), hàm này sẽ trả về một subset là một vài mẫu random được lấy từ data buffer truyền vào. Hàm takeSample có logic như dưới đây

  def takeSample(
      withReplacement: Boolean,
      num: Int,
      seed: Long = Utils.random.nextLong): Array[T] = withScope {
    val numStDev = 10.0

    require(num >= 0, "Negative number of elements requested")
    require(num <= (Int.MaxValue - (numStDev * math.sqrt(Int.MaxValue)).toInt),
      "Cannot support a sample size > Int.MaxValue - " +
      s"$numStDev * math.sqrt(Int.MaxValue)")

    if (num == 0) {
      new Array[T](0)
    } else {
      val initialCount = this.count()
      if (initialCount == 0) {
        new Array[T](0)
      } else {
        val rand = new Random(seed)
        if (!withReplacement && num >= initialCount) {
          Utils.randomizeInPlace(this.collect(), rand)
        } else {
          val fraction = SamplingUtils.computeFractionForSampleSize(num, initialCount,
            withReplacement)
          var samples = this.sample(withReplacement, fraction, rand.nextInt()).collect()

          // If the first sample didn't turn out large enough, keep trying to take samples;
          // this shouldn't happen often because we use a big multiplier for the initial size
          var numIters = 0
          while (samples.length < num) {
            logWarning(s"Needed to re-sample due to insufficient sample size. Repeat #$numIters")
            samples = this.sample(withReplacement, fraction, rand.nextInt()).collect()
            numIters += 1
          }
          Utils.randomizeInPlace(samples, rand).take(num)
        }
      }
    }
  }

Và đoạn code để shuffle Array được thực thi trong hàm Utils.randomizeInPlace(samples, rand) với logic như mình vừa nói ở trên. Sau khi shuffle xong sẽ lấy mẫu ra num phần tử.
Có một điểm chú ý nhỏ là biến rand được truyền vào ở mỗi một lần gọi hàm takeSample với cùng một seed, tức là ý đồ của tác giả là muốn việc sampling được thực hiện với cùng một khuynh hướng giống nhau với mỗi một RDD.

Happy code-reading :smile:

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

116 bài viết.
945 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
148 14
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết gần 2 năm trước
148 14
White
118 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
118 15
White
95 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết 3 năm trước
95 10
Bài viết liên quan
White
1 0
Mở đầu Như đã nói ở bài trước, mình đang nghiên cứu về Spark nên cần log lại một số thứ để dành sau này dùng đến :smile: Đối tượng hướng đến vẫn ...
Phạm Quốc Thắng viết hơn 2 năm trước
1 0
White
3 0
Tuning memory Về cơ bản thì để tuning memory trong java hay scala nói chung thì bạn chỉ cần nhớ rõ một vài điều: Tận dụng primitive object bất c...
huydx viết gần 3 năm trước
3 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
116 bài viết.
945 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!