Delphi Division with equal splitting of the rest (MOD)

Question

I have a math question which I try to solve with a Delphi function. I am trying to split up an integer into (nearly) equal pieces. Example:

You have 10 testcases and you want to execute them in 3 parts. So the best way to balance the workload would be to execute 3, 3, and 4 rather than 1, 1 and 8.

procedure calc_stream_numbers;
var div_res,rest:double;
    total,streams:integer;
begin
total := 10; 
streams := 3;
 div_res := total DIV streams;
 rest := total MOD streams;
 showmessage('Items: '  +IntToStr(total)+#13#10+
              'Streams: '+IntToStr(streams)+#13#10+
              'Result: '+FloatToStr(div_res)+
              'Rest: '+FloatToStr(rest));
end;

This gives me the division result of 10 / 3 = 3 (Rest 1) So I could execute 3 x 3 Testcases which makes 9 in total. To execute all 10 of them, I have to add the remaining one to any of the 3 streams. But If you have a more complicated example..

I am sure there is a mathematical expression for this but I must admit, I have noe clue. Maybe you are able to enlighten me how such a division is called and if there is any built-in delphi function.

score 3 · Answer 1 · edited May 23 '17 at 12:22

3

Here it is: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

One dimension is the amount of workloads, another one is amount of workers

Well, 2D Graphics is targeted at being eye-candy, so at fairly distributing "long" segments throughout "short" ones. In your case we can bias all the "long" ones to one end.

function SplitIntoEqualParts(Total, Count: Integer): TArray<Integer>;
var
  i: Integer;
  delta, delta1, extra: Word;
begin
  Assert( Count < High(Word) ); // RTL DivMod limitation
  SetLength(Result, Count);

  DivMod(Total, Count, delta, extra); 
  // one division operation is 2 times faster than two separate operations :-D
  delta1 := Succ(delta);      

  for i := 0 to extra-1 do 
    Result[i] := delta1;    
  for i := extra to Count-1 do 
    Result[i] := delta;    
end;

edited May 23 '17 at 12:22

Community

1
1

answered Jun 11 '15 at 13:57

Arioch 'The

15,799
35
62

I did not said my code is Bresenham's algorithm, quite the contrary i explicitly told it is made for different requirements! I really took the function declaration from your answer though. As for LURD's answer, my code went through 3 iterations. #2 really happened to be identical, but it came naturally for the - explicitly told in the comments - goal to remove conditional branching from #1 approach. The #3 iteration combines both goals into a new algorithm that is not LURD's one – Arioch 'The Jun 11 '15 at 14:29
Fair enough. I did not read closely enough. It's nice to top up the ones at the end. Interesting to see the different approaches. – David Heffernan Jun 11 '15 at 14:31
It was also the "rubber duck effect". As i was speaking out the cons and pros, i realized there is no "this or that" dilemma at all :-) Perhaps the topic-starter can learn a bit for himself if he would read the previous variant of my answer with #1 and #2 algorithms. – Arioch 'The Jun 11 '15 at 14:34
#1 was did not make it into history, i see. It obviously was `for i := 0 to Count-1 do begin Result[i] := delta; if i < extra then Inc(Result[i]); end;` - single-pass (thus no expectation of L1 cache) but with few pipeline stalls before branch prediction re-adjusts itself – Arioch 'The Jun 11 '15 at 14:38

David Heffernan · Accepted Answer · 2015-06-11T14:17:52.687

2

You can code it like this:

function BalancedWorkload(Total, Count: Integer): TArray<Integer>;
var
  i: Integer;
begin
  SetLength(Result, Count);
  for i := 0 to Count-1 do
  begin
    Result[i] := Total div Count;
    dec(Total, Result[i]);
    dec(Count);
  end;
end;

You have Total units to split up into Count parts. We start with Total div Count for the first item. Then we have Total - (Total div Count) units left which need to be split into Count - 1 parts. Continue in this way until there's nothing left to do.

This algorithm could easily be written in a recursive way, but the iterative approach above somehow seems simpler to me.

Your entire approach assumes that you can predict ahead of time how long each task will take. But what if, for whatever reason, some tasks take longer than others? Then your approach will not be efficient. A better approach is to have a threadsafe queue of tasks. Let each consumer pull tasks off the queue and process them until there are no tasks left.

edited Jun 11 '15 at 14:17

answered Jun 11 '15 at 13:55

David Heffernan

601,492
42
1,072
1,490

Hello David, You are totally right. In fact the tasks are not equal in their complexity, so it could happen that one thread is idle while the others are still busy. Since I struggled with the basics of this problem, I do not know how an intelligent workload distribution should be programmed. I am trying to test this with a simple example. I'll write a delphi application, which has a queue of 20 URLs to call. This should be performed by 3 threads which distribute the workload among each other. – Mr. Ajin Jun 12 '15 at 09:19
1

What you want is as follows: 1. Put the tasks into a threadsafe queue. 2. Make sure that the tasks that you think will take the longest go in first. 3. Have consumer threads that pull tasks from the queue. 4. When the queue is empty, the job is done. You would do worse than to use something like OTL for this. – David Heffernan Jun 12 '15 at 09:37

LU RD · Answer 3 · 2015-06-11T14:08:42.730

This function will calculate an array of integer containing the balanced workloads for each testcase.

function SplitInteger(Value: Integer; divisor: Integer): TArray<Integer>;
var
  d,i : Integer;
begin
  SetLength(Result,divisor);
  if (divisor = 0) then
    Exit;
  d := Value div divisor;
  for i := 0 to divisor - 1 do
    Result[i] := d;
  // Fill up with the remains
  for i := 0 to (value mod divisor) - 1 do
    Inc(Result[i]); 
end;

Delphi Division with equal splitting of the rest (MOD)

3 Answers3