Like fetching top N elements from a sequence of comparable elements, patching numeric sequence is also a common need, especially when processing data that isn’t complete or clean. By “patching”, I mean interpolating missing spots in a list of numbers. A simplistic patch or interpolation is to fill a missing number with the average of the previous few numbers.
For example, given the following list of numbers:
60, 10, 50, (), 20, 90, 40, 80, (), (), 70, 30
we would like to replace each of the missing numbers with the average of, say, its previous 3 numbers. In this case, the leftmost missing number should be replace with 40 (i.e. (60 + 10 + 50) / 3).
Below is a simple snippet that patches missing numbers in a Double-type sequence with the average of the previous N numbers. The missing (or bad) numbers in the original sequence are represented as Double.NaN.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Patching Double-type numbers with average of previous N numbers def patchAvgLastN(n: Int)(list: List[Double]) = { def patchCurrElem(i: Int)(l: List[Double], e: Double) = { val avgLastN = if (e.isNaN) l match { case Nil => 0.0 case _ => val lastN = l.take(i) lastN.sum / lastN.size } else e avgLastN :: l } list.foldLeft( List[Double]() )( patchCurrElem(n) ).reverse } val list: List[Double] = List(60, 10, 50, Double.NaN, 20, 90, 40, 80, Double.NaN, Double.NaN, 70, 30) patchAvgLastN(3)(list) // res1: List[Double] = List(60.0, 10.0, 50.0, 40.0, 20.0, 90.0, 40.0, 80.0, 70.0, 63.3, 70.0, 30.0) |
As shown in the code, method ‘patchCurrElem’ is created to prepend the calculated average of the previous N numbers to the supplied list. Its signature fits well to be a function taken by ‘foldLeft’ to traverse the entire sequence for applying the patch. Since ‘patchCurrElem’ prepends the sub-sequence for optimal operations in Scala List, the final list requires a reversal.
Note that ‘lastN.size’ rather than the literal ‘N’ is used to handle cases when there is less than N prior numbers available for average calculation. And ‘case Nil’ will cover cases when there is no prior number.
Generalizing the patch method
In deriving a generic method for ‘patchAvgLastN’, We’re not going to generalize it for Scala Numeric, as ‘average’ isn’t quite meaningful for non-fractional numbers such as integers. Instead, we’ll generalize it for Scala Fractional, which provides method ‘mkNumericOps’ for access to FractionalOps that consists of division operator (i.e. ‘/’) necessary for average calculation.
Since we’re no longer handling Double-type number, ‘-999’ is used as the default value (of type Int) to replace Double.Nan as the missing (or bad) number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Patching sequence of generic numbers with average of previous N numbers def patchAvgLastN[T](n: Int, badNum: Int = -999)(list: List[T])(implicit num: Fractional[T]) = { def patchCurrElem(i: Int)(l: List[T], e: T) = { import num.mkNumericOps val unk = num.fromInt(badNum) val avgLastN = if (e == unk) l match { case Nil => num.zero case _ => val lastN = l.take(i) lastN.reduce(_ + _) / num.fromInt(lastN.size) } else e avgLastN :: l } list.foldLeft( List[T]() )( patchCurrElem(n) ).reverse } val list: List[Double] = List(60, 10, 50, -999, 20, 90, 40, 80, -999, -999, 70, 30) patchAvgLastN[Double](3)(list) // res1: List[Double] = List(60.0, 10.0, 50.0, 40.0, 20.0, 90.0, 40.0, 80.0, 70.0, 63.3, 70.0, 30.0) val list: List[Float] = List(60, 10, 50, -999, 20, 90, 40, 80, -999, -999, 70, 30) patchAvgLastN[Float](3)(list) // res2: List[Float] = List(60.0, 10.0, 50.0, 40.0, 20.0, 90.0, 40.0, 80.0, 70.0, 63.3, 70.0, 30.0) val list: List[BigDecimal] = List(60, 10, 50, -999, 20, 90, 40, 80, -999, -999, 70, 30) patchAvgLastN[BigDecimal](3)(list) // res3: List[BigDecimal] = List(60, 10, 50, 40, 20, 90, 40, 80, 70, 63.33, 70, 30) |
Work-arounds for patching integer sequences
A quick work-around for interpolating a list of integers (type Int, Long or BigInt) would be to transform the integers to a Fractional type, apply the patch and transform back to the original type. Note that in some cases, rounding or truncation might occur in the transformations. For example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// A work-around for patching integer sequences val list: List[Int] = List(60, 10, 50, -999, 20, 90, 40, 80, -999, -999, 70, 30) patchAvgLastN[Double](3)(list.map(_.toDouble)).map(_.toInt) // res1: List[Int] = List(60, 10, 50, 40, 20, 90, 40, 80, 70, 63, 70, 30) val list: List[Long] = List(60, 10, 50, -999, 20, 90, 40, 80, -999, -999, 70, 30) patchAvgLastN[Double](3)(list.map(_.toDouble)).map(_.toLong) // res2: List[Long] = List(60, 10, 50, 40, 20, 90, 40, 80, 70, 63, 70, 30) val list: List[BigInt] = List(60, 10, 50, -999, 20, 90, 40, 80, -999, -999, 70, 30) patchAvgLastN[BigDecimal](3)(list.map(BigDecimal(_))).map(_.toBigInt) // res3: List[scala.math.BigInt] = List(60, 10, 50, 40, 20, 90, 40, 80, 70, 63, 70, 30) |