Evenly filter a list down by a certain percentage

2019-08-10 20:45发布

问题:

I'm looking for an most efficient way in Kotlin/Java to filter a List down by a certain percentage and with the removal of filtered elements will be applied across the collection in a uniformed fashion (i.e. - the elements to be removed span across the entire collection evenly);

For Example

  • filter the following by 50% [0,1,2,3,4,5,6,7,8,9] = [0,2,4,6,8]
  • filter the following by 10% [1,100,1000,10000] = [1,100,10000]

I came up with the following Kotlin extension function & it works great when the percentage < 50% and the collection is large but when the collection >50% then this approach falls over as it only handles integer division.

private fun <E> List<E>.filterDownBy(perc: Int): List<E> {
val distro = this.size / ((perc * this.size) / 100)
if (perc == 0 || distro >= this.size)
    return this
return this.filterIndexed { index, _ -> (index % distro) != 0 }

Is there a better way to do this & will also work when the percentage is >50%?

回答1:

I don't think there's much in the standard library that will help, but I've come up with this ‘manual’ approach:

fun <T> List<T>.takeProportion(prop: Double): List<T> {
    if (prop < 0 || prop > 1)
        throw IllegalArgumentException("prop ($prop) must be between 0 and 1")
    val result = ArrayList<T>()
    var tally = 0.5
    for (i in this) {
        tally += prop
        if (tally >= 1.0) {
            result += i
            tally -= 1
        }
    }
    return result
}

It uses a sort of error-diffusion way to ensure that the values are taken evenly across the list, and uses floating-point so that it copes smoothly with any proportion from 0.0 (giving an empty list) to 1.0 (taking every element).

(There's probably a way of doing it using only integer arithmetic, but using floating-point is probably simpler to code and understand.)

(You could probably make it more functional-looking by using filter(), but that's not really appropriate because the lambda would have to use, and update, external state.)