frumos

frumos

Even load distribution function, how to implement in Elixir?

Hello,

I need to write an Elixir function which will evenly distribute unbalanced load over set of tasks (nodes). Lets say I have following input:

number_nodes = 3
weighted_tasks = [10, 10, 10, 7, 6, 5, 5, 2, 2, 1, 1, 1]
node_capacity = 20 # as sum of all tasks/number_nodes

and I need to get this output (one of other possible combinations)

[[10, 10], [10, 7, 2, 1], [6, 5, 5, 2, 1, 1]]

which mean that load weight per node is 20 for all 3 nodes and balanced.

I am trying Enum.chunck_by() function but not able implement it correctly, here is my attempt:

  def chuck_f(node_capacity) do
    chunk_fun = fn element, acc ->
      acc_capacity = Enum.sum(acc)
      pending_capacity = acc_capacity + element

      if pending_capacity < node_capacity do
        # do not yet emit given chuck, but remove this element from the input list as it
        # is added to the chuck, but how to do that?
        {:cont, [element | acc]}
      else
        # if no more element in input list present emit chunck
        # if there are some element just skip current one and do not emit chunck
        # but how to get it?
        {:cont, [acc], []}
      end
    end
    chunk_fun
  end


  def after_iteration_fun() do
    after_fun = fn acc ->
        case acc do
          [] -> {:cont, []}
          acc -> {:cont, acc, []}
        end
      end
    after_fun
  end

  def distribute_load do
    input = [10, 10, 10, 7, 6, 5, 5, 2, 2, 1, 1, 1]
    node_capacity = 20
    input |> Enum.chunk_while([], chuck_f(node_capacity), after_iteration_fun())
  end

which producing result:

iex(109)> distribute_load
[[[10]], [[7, 10]], [1, 1, 1, 2, 2, 5, 5]]

which is not what I need.

I have this algorithm implement in Java with this pseudo code:

partitions_list = compute_list_of_partiton_with_load_sort_desc # this is already done in Elixir
cluster_load = compute_total_cluster_load
one_node_load = cluster_load/num_of_nodes


#for all nodes in cluster
for node in node_list {
    
    # initiate node with no partitions yet and full capacity
    node.partion_list = []
    node.capacity = one_node_load

    for partion in partition_list {

        if partion.load <= node.capacity {	
            node.partion_list.add(partition)
            recompute_node_capacity(node, partition)
            partition_list.remove(partition)

        } 
    }
}


def recompute_node_capacity(node, partitions) do
    new_capacit = node.capacity - partition.load
    
    node.capacity = new_capacity # ugly node's state mutation
end

and this actual draft Java impl where I can easily mutate map/list just in place which give me ability to achieve the goal:

@Test
    public void balanceLoad() {
        
        List<Integer> tasks = new ArrayList<>(); 
        tasks.add(10);
        tasks.add(10);
        tasks.add(10);
        tasks.add(7);
        tasks.add(6);
        tasks.add(5);
        tasks.add(5);
        tasks.add(2);
        tasks.add(2);
        tasks.add(1);
        tasks.add(1);
        tasks.add(1);        
        
        Map<Integer, List<Integer>> nodes = new HashMap<>();
        nodes.put(1, new ArrayList<>());
        nodes.put(2, new ArrayList<>());
        nodes.put(3, new ArrayList<>());
        
        
        System.out.println("Before: " + nodes);
                
        for (int nodeKey : nodes.keySet()) {
            List<Integer> nodeList = new ArrayList<>(tasks);
            List<Integer> nodeTasks = nodes.get(nodeKey);
            
            for (Iterator<Integer> iterator = nodeList.iterator(); iterator.hasNext();) {
                Integer task = iterator.next();
         
                if(task <= nodeCapacity(nodeTasks, 20)) {
                    nodeTasks.add(task);
                    iterator.remove();
                    tasks.remove(task);
                }
            }
        }
        System.out.println("After: " + nodes);
    }
    
    
    private int nodeCapacity(List<Integer> nodeTasks, int nodeCapCapacity) {
        int current = nodeTasks.stream().reduce(0, Integer::sum);
        return nodeCapCapacity - current;
    }

giving me this result:

Before: {1=, 2=, 3=}
After: {1=[10, 10], 2=[10, 7, 2, 1], 3=[6, 5, 5, 2, 1, 1]}

Can anybody assist to achieve similar in Elixir? Thank you for your time.

Marked As Solved

fuelen

fuelen

Hello,
here is my rewriting your pseudo code

number_nodes = 3
weighted_tasks = [10, 10, 10, 7, 6, 5, 5, 2, 2, 1, 1, 1]
node_capacity = trunc(Enum.sum(weighted_tasks) / number_nodes)

1..number_nodes
|> Enum.map(fn index -> {index, %{capacity: node_capacity, tasks: []}} end)
|> Enum.map_reduce(
  weighted_tasks,
  fn {node_index, node}, tasks ->
    {node, tasks} =
      Enum.reduce(tasks, {node, []}, fn task, {node, new_tasks} ->
        if task <= node.capacity do
          {%{capacity: node.capacity - task, tasks: [task | node.tasks]}, new_tasks}
        else
          {node, [task | new_tasks]}
        end
      end)

    {{node_index, node}, Enum.reverse(tasks)}
  end
)
|> IO.inspect(charlists: :as_lists)
# output:
{[
   {1, %{capacity: 0, tasks: [10, 10]}},
   {2, %{capacity: 0, tasks: [1, 2, 7, 10]}},
   {3, %{capacity: 0, tasks: [1, 1, 2, 5, 5, 6]}}
 ], []}

Where Next?

Popular in Questions Top

aadeshere1
I have a another noob question about loop. Since elixir is immutable, while loop is not directly possible. total = 10 while total != 0 ...
New
9mm
I am constructing a JSON object (map) and I need to conditionally set a field. I’m trying to write proper elixir-way code… and I’m at a l...
New
lastday4you
I wanted to check elixir version in phoenix because i found that my elixir is 1.5 but when i use Enum.chunk_by it said the function is un...
New
skosch
To my knowledge, put_in, Map.update etc. all have the one limitation of not automatically creating intermediate keys when needed (for exa...
New
ovidiubadita
Hey all, I discovered Elixir and I love it. I always wanted to learn a functional programming and I intended to go for Haskell, but afte...
New
jaysoifer
Is there a way to rollback a specific migration and only that one (“skipping” all the other ones)? Would mix ecto.rollback -v 200809061...
New
vegabook
I’m brand new to Phoenix and I have stripped one of the demo applications to the bone. I just want to get an svg up on the screen. Here i...
New
pmjoe
I have a relationship of love and hate with Elixir. Lots of things are just absolutely right, but there are some things that are kind of ...
New
lucidguppy
I have a super simple question about elixir - how would I take a file like this foo bar baz and output a new file that enumerates th...
New
PeterCarter
There are pre-rolled solutions for other frameworks that do work. However, Phoenix does not seem to have these. Have people had good expe...
New

Other popular topics Top

albydarned
Hello all! I am typing this post from my new MacBook Pro with the M1 chip. I’m loving it so far, and will probably use it as my daily dr...
New
lessless
I believe there are people here who are dealing with CSV files import on the daily basis, and since Excel is a really popular tool there ...
New
gshaw
What is the idiomatic way of matching for not nil in Elixir? E.g., First way: defp halt_if_not_signed_in(conn, signed_in_account) when...
New
shahryarjb
Hello, I have map which I want to convert it to string like this: the map: %{last_name: "tavakkoli", name: "shahryar"} the string I ne...
New
JorisKok
I have a server on AWS, and was running a load test using artillery. When looking at the Phoenix dashboard I see the Ports going to 100% ...
New
AngeloChecked
What learn first? Rust or Elixir Hi Elixir community! I’m here because i want learn a new language. I’m a junior developer and mainly i ...
New
gausby
I asked this very same question on twitter and got some interesting feedback, but I thought it would be a good question to ask here as we...
1207 39297 209
New
jason.o
In the code below, if the create action is not set to accept “extra_key” as an input, it errors out with a message shown above. Is there ...
New
Qqwy
Update: How to use the Blogs &amp; Podcasts section You can post links to your blog posts or podcasts either in one of the Official Blog...
3271 126479 1222
New
vonH
In asking this question I am more interested about the expressiveness of the language itself and less concerned about the availability of...
New

We're in Beta

About us Mission Statement