phân vùng một bộ sưu tập thành "k" close-to-bằng mảnh (Scala, nhưng ngôn ngữ bất khả tri)

Question

Defined trước khối mã này:

• dataset có thể là một Vector hoặc List
• numberOfSlices là một Int biểu thị số lượng "thời gian" để chia tập dữ liệu

Tôi muốn chia tập dữ liệu thành numberOfSlices lát, phân phối đồng đều nhất có thể. Bằng cách "phân chia", tôi đoán tôi có nghĩa là "phân vùng" (giao điểm của tất cả nên được sản phẩm nào, công đoàn của tất cả phải là bản gốc) để sử dụng các thuật ngữ tập lý ngữ, mặc dù điều này không nhất thiết phải là một tập hợp, chỉ cần một bộ sưu tập tùy ý.

ví dụ:

dataset = List(1, 2, 3, 4, 5, 6, 7) 
numberOfSlices = 3 
slices == ListBuffer(Vector(1, 2), Vector(3, 4), Vector(5, 6, 7)) 

Có cách nào tốt hơn để làm điều đó hơn những gì tôi có bên dưới không? (mà tôi thậm chí không chắc chắn là tối ưu ...) Hoặc có lẽ đây không phải là một nỗ lực khả thi về mặt thuật toán, trong trường hợp nào có bất kỳ chẩn đoán tốt nào được biết đến?

val slices = new ListBuffer[Vector[Int]] 
val stepSize = dataset.length/numberOfSlices 
var currentStep = 0 
var looper = 0 
while (looper != numberOfSlices) { 
    if (looper != numberOfSlices - 1) { 
    slices += dataset.slice(currentStep, currentStep + stepSize) 
    currentStep += stepSize 
    } else { 
    slices += dataset.slice(currentStep, dataset.length) 
    } 
    looper += 1 
} 

Answer 1

Nếu hành vi của xs.grouped(xs.size/n) không làm việc cho bạn, nó rất dễ dàng để xác định chính xác những gì bạn muốn. Các thương là kích thước của các mảnh nhỏ hơn, và phần còn lại là số lượng các mảnh lớn hơn:

def cut[A](xs: Seq[A], n: Int) = { 
    val (quot, rem) = (xs.size/n, xs.size % n) 
    val (smaller, bigger) = xs.splitAt(xs.size - rem * (quot + 1)) 
    smaller.grouped(quot) ++ bigger.grouped(quot + 1) 
} 

Answer 2

Khi Kaito đề cập đến grouped chính xác là những gì bạn đang tìm kiếm. Nhưng nếu bạn chỉ muốn biết làm thế nào để thực hiện một phương pháp như vậy, có rất nhiều cách ;-). Bạn có thể ví dụ như làm điều đó như thế này:

def grouped[A](xs: List[A], size: Int) = { 
    def grouped[A](xs: List[A], size: Int, result: List[List[A]]): List[List[A]] = { 
    if(xs.isEmpty) { 
     result 
    } else { 
     val (slice, rest) = xs.splitAt(size) 
     grouped(rest, size, result :+ slice) 
    } 
    } 
    grouped(xs, size, Nil) 
} 

Answer 3

tôi muốn tiếp cận nó theo cách này: Với n yếu tố và m phân vùng (n> m), một trong hai n mod m == 0 trong trường hợp này, mỗi phân vùng sẽ có các phần tử n/m hoặc n mod m = y, trong trường hợp này bạn sẽ có mỗi phân vùng với các thành phần n/m và bạn phải phân phối y trên một số m.

Bạn sẽ có y vị trí với n/m+1 yếu tố và (m-y) vị trí có n/m. Cách bạn phân phối chúng là lựa chọn của bạn.

Answer 4

Các điển hình phân vùng "tối ưu" tính toán chiều dài phân đoạn chính xác sau khi cắt và sau đó vòng để tìm số thực tế để thực hiện:

def cut[A](xs: Seq[A], n: Int):Vector[Seq[A]] = { 
    val m = xs.length 
    val targets = (0 to n).map{x => math.round((x.toDouble*m)/n).toInt} 
    def snip(xs: Seq[A], ns: Seq[Int], got: Vector[Seq[A]]): Vector[Seq[A]] = { 
    if (ns.length<2) got 
    else { 
     val (i,j) = (ns.head, ns.tail.head) 
     snip(xs.drop(j-i), ns.tail, got :+ xs.take(j-i)) 
    } 
    } 
    snip(xs, targets, Vector.empty) 
} 

Bằng cách này dài hơn và khối ngắn hơn sẽ được xen kẽ, trong đó thường xuyên hơn là mong muốn cho ngang nhau:

scala> cut(List(1,2,3,4,5,6,7,8,9,10),4) 
res5: Vector[Seq[Int]] = 
    Vector(List(1, 2, 3), List(4, 5), List(6, 7, 8), List(9, 10)) 

bạn thậm chí có thể cắt nhiều lần so với bạn có các yếu tố:

scala> cut(List(1,2,3),5) 
res6: Vector[Seq[Int]] = 
    Vector(List(1), List(), List(2), List(), List(3)) 

Answer 5

Đây là một lớp lót thực hiện công việc cho tôi, sử dụng thủ thuật Scala quen thuộc của hàm đệ quy trả về Stream. Lưu ý việc sử dụng (x+k/2)/k để làm tròn kích thước đoạn, xen các khối nhỏ hơn và lớn hơn trong danh sách cuối cùng, tất cả đều có kích thước với nhiều nhất một phần tử của sự khác biệt.Thay vào đó, nếu bạn làm tròn, với (x+k-1)/k, bạn di chuyển các khối nhỏ hơn đến cuối và x/k sẽ di chuyển chúng đến đầu.

def k_folds(k: Int, vv: Seq[Int]): Stream[Seq[Int]] = 
    if (k > 1) 
     vv.take((vv.size+k/2)/k) +: k_folds(k-1, vv.drop((vv.size+k/2)/k)) 
    else 
     Stream(vv) 

Demo:

scala> val indices = scala.util.Random.shuffle(1 to 39) 

scala> for (ff <- k_folds(7, indices)) println(ff) 
Vector(29, 8, 24, 14, 22, 2) 
Vector(28, 36, 27, 7, 25, 4) 
Vector(6, 26, 17, 13, 23) 
Vector(3, 35, 34, 9, 37, 32) 
Vector(33, 20, 31, 11, 16) 
Vector(19, 30, 21, 39, 5, 15) 
Vector(1, 38, 18, 10, 12) 

scala> for (ff <- k_folds(7, indices)) println(ff.size) 
6 
6 
5 
6 
5 
6 
5 

scala> for (ff <- indices.grouped((indices.size+7-1)/7)) println(ff) 
Vector(29, 8, 24, 14, 22, 2) 
Vector(28, 36, 27, 7, 25, 4) 
Vector(6, 26, 17, 13, 23, 3) 
Vector(35, 34, 9, 37, 32, 33) 
Vector(20, 31, 11, 16, 19, 30) 
Vector(21, 39, 5, 15, 1, 38) 
Vector(18, 10, 12) 

scala> for (ff <- indices.grouped((indices.size+7-1)/7)) println(ff.size) 
6 
6 
6 
6 
6 
6 
3 

Chú ý cách grouped không cố gắng thậm chí ra kích thước của tất cả các tiểu danh sách.