5
\$\begingroup\$

I wrote a small utility function that divides a total into n parts in the ratio given in load_list. Numbers in each part should be positive integers. It supports an optional min_num argument that, when specified, puts at least min_num in each of the n parts before distributing the rest. Please review.

def reduce_ratio(load_list, total_num, min_num=1):
  """
  Returns the distribution of `total_num` in the ratio of `load_list` in the best possible way
  `min_num` gives the minimum per entry
  >>> reduce_ratio([5, 10, 15], 12)
  [2, 4, 6]
  >>> reduce_ratio([7, 13, 30], 6, 0)
  [1, 2, 3]
  >>> reduce_ratio([7, 13, 50], 6)
  [1, 1, 4]
  >>> reduce_ratio([7, 13, 50], 6, 3)
  Traceback (most recent call last):
    ...
  ValueError: Could not satisfy min_num
  >>> reduce_ratio([7, 13, 50], 100, 15)
  [15, 18, 67]
  >>> reduce_ratio([7, 13, 50], 100)
  [10, 19, 71]
  """
  num_loads = [ [load, min_num] for  load in load_list ]
  yet_to_split = total_num - ( len(num_loads) * min_num )
  if yet_to_split < 0:
    raise ValueError('Could not satisfy min_num')
  for _ in range(yet_to_split):
    min_elem = min(num_loads, key=lambda (load, count): (float(count)/load, load))
    min_elem[1] += 1
  reduced_loads = map(itemgetter(1), num_loads)
  if sum(reduced_loads) != total_num:
    raise Exception('Could not split loads to required total')
  return reduced_loads
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

Because the problem is not quite formalised and is mostly defined by the way your code currently works, I must confess that I find it quite hard to make thinds more efficient/concise.

A few point however:

  • using ( len(num_loads) * min_num ) un-necessarly relies on the way you have populated num_loads. You could something more generic like : yet_to_split = total_num - sum(num for _,num in num_loads) so that things work no matter what.
  • at the moment, I don't think it is possible for the condition sum(reduced_loads) != total_num to be true. Indeed, at the beginning, the definition of yet_to_split leads to the following property : yet_to_split + sum_of_loads = total_num. Then as we iterate over yet_to_split, sum_of_loads gets increased one by one. Because the condition cannot be true, it's not really wise to expect anyone to expect and catch this exception. If you want to perform the verification, assert is what you should be using : assert(sum(reduced_loads) == total_num).
  • in order to avoid any troubles while processing the input, you might want to add more checks.

My suggestions are the following :

if not load_list:
    raise ValueError('Cannot distribute over an empty container')
if any(l <= 0 for l in load_list):
    raise ValueError('Load list must contain only stricly positive elements')
  • A bit of a naive question but couldn't the min_num logic be extracted out by processing the load_list normally and only at the end (in a potentially different function) check that min(return_array) >= min_num ? This makes performance slightly worse for cases leading to failures but makes this usual case a bit clearer.

For instance, the code would be like :

num_loads = [ [load, 0] for  load in load_list ]
for _ in range(total_num):
    min_elem = min(num_loads, key=lambda (load, count): (float(count)/load, load))
    min_elem[1] += 1
reduced_loads = [num for _,num in num_loads]
assert(sum(reduced_loads) == total_num)
return reduced_loads
  • Just a suggestion but instead of recomputing the minimal element by reprocessing the whole array every-time, maybe you could use an appropriate data structure like heapq to get the minimal element quickly and then re-add it to the structure once updated.
\$\endgroup\$
2
\$\begingroup\$

So in terms of code layout this is a little hard to follow, but apart form that is fine and the docstring is good. However, I'm not sure that your code gives the right result. Also it could also be sped up by at least a factor of four.

Take the example:

In [22]: reduce_ratio([1,50,23],32,6)
Out[22]: [6, 18, 8] 

so the first thing the code should do is put 6 in each output as this is min_num, this should give:

[6, 6, 6]

So this removes 3*6=18 from total_num leaving 14 to distribute according to your load_list.

This gives:

In [3]: [14*float(load)/sum(load_list) for load in load_list]
Out[3]: [0.1891891891891892, 9.4594594594594597, 4.3513513513513518]

Now obviously 0.1891891891891892 rounds to zero, so we pop that from the list and move on. We now have to split 14 with load_list=[50,23]. This gives:

In [6]: [14*float(load)/sum(load_list) for load in load_list]
Out[6]: [9.5890410958904102, 4.4109589041095889]

Rounding this obviously gives [10,4]. So we have successfully split the number 14 into [0,10,4] with load_list=[50,23]. Adding this to our list of min_num ([6,6,6]) gives:

[6, 16, 10]

and [6, 16, 10] != [6, 18, 8].

Apologies if I have missed something in the code and [6, 18, 8] was the desired result. Below is the code I used to get my answer:

def new_reduce_ratio(load_list, total_num, min_num=1):
    output = [min_num for _ in load_list]
    total_num -= sum(output)
    if total_num < 0:
        raise Exception('Could not satisfy min_num')
    elif total_num == 0:
        return output

    nloads = len(load_list)
    for ii in range(nloads):
        load_sum = float( sum(load_list) )
        load = load_list.pop(0)
        value = int( round(total_num*load/load_sum) )
        output[ii] += value
        total_num -= value
    return output

This code also has some speed benefits over your current implementation:

In [2]: %timeit reduce_ratio([1,50,23],32,6)
10000 loops, best of 3: 44 us per loop

In [3]: %timeit new_reduce_ratio([1,50,23],32,6)
100000 loops, best of 3: 9.21 us per loop

here we get a speed up of a factor of ~4.8.

\$\endgroup\$
6
  • \$\begingroup\$ I think OP's code chooses 18 and 8 because 50/18 is approximately equal to 23/8. \$\endgroup\$ Apr 4, 2014 at 12:03
  • \$\begingroup\$ Disclaimer : I have no idea what I am doing. I have defined the 2 following functions to compare results - this is pretty arbitrary so one shouldn't rely too much on its results : def normalise(l): return [float(e)/min(l) for e in l] ; def evaluate_ratio(l1,l2): return sum((e1-e2)**2 for e1,e2 in zip(normalise(l1),normalise(l2))) and I get : evaluate_ratio([1,50,23],[1,50,23]) -> 0.0 evaluate_ratio([1,50,23],[6,16,10]) ->2695.5555555555557 evaluate_ratio([1,50,23],[6,18,8]) -> 2678.4444444444443 so this might be a justification for OP's results anyway. Have my upvote anyway! \$\endgroup\$
    – SylvainD
    Apr 4, 2014 at 12:09
  • \$\begingroup\$ @JanneKarila I agree. I can see how the result is obtained, I'm just not sure it is the right way to do it. \$\endgroup\$
    – ebarr
    Apr 4, 2014 at 12:13
  • \$\begingroup\$ @Josay: The OP says that you first put min_num in each output and then distribute what remains from total_num. So really you should be evaluating evaluate_ratio([1,50,23],[0,10,4]) and evaluate_ratio([1,50,23],[0,12,2]) \$\endgroup\$
    – ebarr
    Apr 4, 2014 at 12:25
  • \$\begingroup\$ Indeed, that's a way to see it (even though it would make my functions crash :'(). \$\endgroup\$
    – SylvainD
    Apr 4, 2014 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.