Эффективно перемещающийся массив, соответствующий логическому состоянию?

Question

Это еще один вопрос от Scala for the Impatient который говорит

Написать функцию lteqgt (значения: Array [Int], v: Int), который возвращает тройные содержащие отсчеты значений меньше, чем у, равна V, и больше, чем против.

как я сделал это

scala> def lteqgt(values: Array[Int], v: Int): (Int, Int, Int) = (values.count(_ < v), values.count(_ == v), values.count(_ > v)) 
lteqgt: (values: Array[Int], v: Int)(Int, Int, Int) 

scala> lteqgt(Array(0,0,1,1,1,2,2), 1) 
res47: (Int, Int, Int) = (2,3,2) 

проблема?
Я перемещаю массив 3 раз, чтобы собрать подсчеты. Есть ли способ собирать значения в первый раз? идиоматический путь?

Answer 1

Это идеальный случай для использования foldLeft. Он будет проходить вашу коллекцию ровно один раз, не создавая другой коллекции (как это делает groupBy), и это более красноречиво по сравнению с более общим aggregate.

def lteqgt(values: Array[Int], v: Int): (Int, Int, Int) = 
    values.foldLeft((0, 0, 0)) { 
    case ((lt, eq, gt), el) => 
     if (el < v) (lt + 1, eq, gt) 
     else if (el == v) (lt, eq + 1, gt) 
     else (lt, eq, gt + 1) 
    } 

Если вы хотите достичь конечной эффективности, избегая при этом императивный подход, то хвост рекурсии путь:

def lteqgt(values: Array[Int], v: Int): (Int, Int, Int) = { 
    def rec(i:Int, lt:Int, eq:Int, gt:Int):(Int, Int, Int) = 
    if (i == values.length) (lt, eq, gt) 
    else if (values(i) < v) rec(i + 1, lt + 1, eq, gt) 
    else if (values(i) == v) rec(i + 1, lt, eq + 1, gt) 
    else rec(i + 1, lt, eq, gt + 1) 
    rec(0, 0, 0, 0) 
} 

Это позволяет избежать строительства Tuple и коробочных Ints на каждой итерации. Все это составляет while цикл в java (here is the transpiled output, если вам это интересно).

Answer 2

Хотя функциональное решение, возможно, более элегантное, давайте не будем забывать о «скучном», но эффективном императивном решении.

def lteqgt(values: Array[Int], v: Int): (Int, Int, Int) = { 
    var lt = 0 
    var eq = 0 
    var gt = 0 
    values.foreach (i => { 
     if  (i<v) lt += 1 
     else if (i==v) eq += 1 
     else   gt += 1 
    }) 
    (lt,eq,gt) 
    } 

Вышеупомянутое может генерировать один вызов функции за цикл, как указывает Aivean ниже. Для большей эффективности мы можем удалить крышку вручную. (Жаль, что такая оптимизация еще не сделано компилятором, хотя)

def lteqgt(values: Array[Int], v: Int): (Int, Int, Int) = { 
    var lt = 0 
    var eq = 0 
    var gt = 0 
    var i = 0 
    while (i < values.length) { 
    if  (values(i) < v) lt += 1 
    else if (values(i) == v) eq += 1 
    else      gt += 1 
    i += 1 
    } 
    (lt,eq,gt) 
    } 

Answer 3

Подобно @ Чи, но давайте превышать проектную спецификацию чуть-чуть, чтобы мы могли сравнить другие данные, кроме Ints. И название говорит «Traversing», поэтому давайте использовать Traversable, чтобы мы могли анализировать все остальные коллекции. Аппарат может не выполнять это быстрее, но он может быть эффективным для программиста.

def lteqgt[T](values:Traversable[T], v:T)(implicit cmp: Ordering[T]):(Int,Int,Int) = { 
      var l = 0; 
      var e = 0; 
      var g = 0; 
      for(x <- values){ 
       if (cmp.equiv(v,x)) e += 1 
       else if (cmp.gt(x,v)) g += 1 
       else l += 1 
      } 
     (l,e,g); 
}; 

Использование:

scala> lteqgt(List(1.0,2.0,3.0,2.5), 2.5) 
res0: (Int, Int, Int) = (2,1,1) 

scala> lteqgt(Array(1.0,2.0,3.0,2.5), 2.5) 
res1: (Int, Int, Int) = (2,1,1) 

scala> lteqgt(Vector(1.0,2.0,3.0,2.5), 2.5) 
res2: (Int, Int, Int) = (2,1,1) 

scala> lteqgt(Set(1.0,2.0,3.0,2.5), 2.5) 
res3: (Int, Int, Int) = (2,1,1) 

scala> lteqgt(1 to 100, 45) 
res4: (Int, Int, Int) = (44,1,55) 

scala> lteqgt(Range(0,100,3), 50) 
res5: (Int, Int, Int) = (17,0,17) 

scala> lteqgt(List("fee","fie","foe","fum"), "foo") 
res6: (Int, Int, Int) = (3,0,1) 

scala> lteqgt(None, 1) 
res7: (Int, Int, Int) = (0,0,0) 

scala> lteqgt(Some(2), 1) 
res8: (Int, Int, Int) = (0,0,1)