Skip to main content
added 2647 characters in body
Source Link

If we were allowedOk, I'm changing the answer now that I understand what you are doing.

The main problem here is @/ -- while Scala people, in general, don't mind special operators, they don't add operators just because they can either. You can replace @/ with the existing / just by adding .toFloat to leave candies outany one of the terms.

Views aren't often used either, and it's important to have a very good understanding of how they work if you are going to use them, and it's not that easy to gain performance with them, since the machinery they use to support non-strictness is quite heavy, and not everything takes advantage of it. For example, this would sufficesortBy will create a new collection before take and map are applied.

Views can gain when you have many mapping/slicing steps, and few elements of it are ever used. Most of the time, iterators will gain you much more performance, at the cost of the mutability problems iterators have.

If you want to reduce the number of times you iterate through the list of proportions, there's at least one place where you can simplify:

def divide(candies: Int, prop: Seq[Int]):val Seq[Int]remainders = {(
  val quantum = candies.toDouble / prop approximations.sumview.zipWithIndex
  prop      map { x => if (_lowValuesIndices *contains quantumx._2) map1 else 0 }
    ).force

    (byDifect, remainders).zipped map { _ + _ }

Can be reduced to

    byDifect.toIntzipWithIndex map {
      case (bd, i) => bd + (if (lowValuesIndices contains i) 1 else 0)
    }

I imagineOne could also keep byDifect a Float, then either use it alone when computing approximation (instead of zipping stuff), or skip that altogether and put that computation on sortBy -- incurring the problemcost of computation O(nlogn) times instead of O(n) times. It would make the code shorter, but whether it would be faster or not is something I'd leave to a benchmark with a real application -- I'm guessing it would depend on actual sizes for proportions.

So, let's talk a bit about performance. Before Scala 2.10, if you want performance you should avoid methods added through implicits on critical paths. The code you wrote will probably get inlined by JIT. You can also reduce the number of computations by pre-computing amount / sum, and if you make that weamount.toFloat / sum, then you don't need /@.

More specifically, views are not. However guarantees of speed, particularly if the computations are light, such as I remarkedhere. I'd not use them at all, unless I'm specifically optimizing the solution you gave doesn't fitcode.

Doing a fixed size of multiple passes on small data structures is often not a problem. You are not changing the complexity, just losing memory locality. If the proportionsdata is bigger, you can incur in gc overheads, which are 5more substantial.1 If maximum performance is required, 3.4just drop immutability and 8go to mutable arrays.5

Finally, so 4contains is farther away from 3.4faster on Set than 9 is from 8Seq -- and, in this particular case, a BitSet would be way faster.5 Call it apply, however, since contains is a general method on traversables, while set's apply is a fundamental operation. If you can explain the criteria for distributing the left oversone of them is less than optimized, I can go fromit will be contains.

This is the most idiomatic beginner's code above to something elseI have ever seen... do you come from another functional language?

If we were allowed to leave candies out of it, this would suffice:

def divide(candies: Int, prop: Seq[Int]): Seq[Int] = {
  val quantum = candies.toDouble / prop.sum
  prop map (_ * quantum) map (_.toInt)
}

I imagine the problem is that we are not. However, as I remarked, the solution you gave doesn't fit... the proportions are 5.1, 3.4 and 8.5, so 4 is farther away from 3.4 than 9 is from 8.5. If you can explain the criteria for distributing the left overs, I can go from the code above to something else.

Ok, I'm changing the answer now that I understand what you are doing.

The main problem here is @/ -- while Scala people, in general, don't mind special operators, they don't add operators just because they can either. You can replace @/ with the existing / just by adding .toFloat to any one of the terms.

Views aren't often used either, and it's important to have a very good understanding of how they work if you are going to use them, and it's not that easy to gain performance with them, since the machinery they use to support non-strictness is quite heavy, and not everything takes advantage of it. For example, sortBy will create a new collection before take and map are applied.

Views can gain when you have many mapping/slicing steps, and few elements of it are ever used. Most of the time, iterators will gain you much more performance, at the cost of the mutability problems iterators have.

If you want to reduce the number of times you iterate through the list of proportions, there's at least one place where you can simplify:

    val remainders = (
        approximations.view.zipWithIndex
        map { x => if (lowValuesIndices contains x._2) 1 else 0 }
    ).force

    (byDifect, remainders).zipped map { _ + _ }

Can be reduced to

    byDifect.zipWithIndex map {
      case (bd, i) => bd + (if (lowValuesIndices contains i) 1 else 0)
    }

One could also keep byDifect a Float, then either use it alone when computing approximation (instead of zipping stuff), or skip that altogether and put that computation on sortBy -- incurring the cost of computation O(nlogn) times instead of O(n) times. It would make the code shorter, but whether it would be faster or not is something I'd leave to a benchmark with a real application -- I'm guessing it would depend on actual sizes for proportions.

So, let's talk a bit about performance. Before Scala 2.10, if you want performance you should avoid methods added through implicits on critical paths. The code you wrote will probably get inlined by JIT. You can also reduce the number of computations by pre-computing amount / sum, and if you make that amount.toFloat / sum, then you don't need /@.

More specifically, views are not guarantees of speed, particularly if the computations are light, such as here. I'd not use them at all, unless I'm specifically optimizing the code.

Doing a fixed size of multiple passes on small data structures is often not a problem. You are not changing the complexity, just losing memory locality. If the data is bigger, you can incur in gc overheads, which are more substantial. If maximum performance is required, just drop immutability and go to mutable arrays.

Finally, contains is faster on Set than Seq -- and, in this particular case, a BitSet would be way faster. Call it apply, however, since contains is a general method on traversables, while set's apply is a fundamental operation. If one of them is less than optimized, it will be contains.

This is the most idiomatic beginner's code I have ever seen... do you come from another functional language?

Source Link

If we were allowed to leave candies out of it, this would suffice:

def divide(candies: Int, prop: Seq[Int]): Seq[Int] = {
  val quantum = candies.toDouble / prop.sum
  prop map (_ * quantum) map (_.toInt)
}

I imagine the problem is that we are not. However, as I remarked, the solution you gave doesn't fit... the proportions are 5.1, 3.4 and 8.5, so 4 is farther away from 3.4 than 9 is from 8.5. If you can explain the criteria for distributing the left overs, I can go from the code above to something else.