[Closed] Challenge! and Fun 🙂

here is brute force but “IDEAL” distribution:

	fn distributeBeads threads num_beads:10000 = 
	(
		all = num_beads
		num_threads = threads.count
		thread_data = #()
		all_len = 0
		for i=1 to num_threads do
		(
			len = getshapelength threads[i]
			all_len += len
			append thread_data [i, 0, len, len]
		)

		qsort thread_data sort3
		for i = 1 to amin num_beads num_threads do
		(
			local v = thread_data[i]
			v[2] = 1
			v[3] = v[4] / (v[2] + 2)
		)
		for i = 1 to (num_beads - num_threads) do 
		(
			qsort thread_data sort3
			local v = thread_data[1]
			v[2] += 1
			v[3] = v[4] / (v[2] +[B]2[/B])
		)
		
		all_beads = 0
		for i = 1 to num_threads do 
		(
			all_beads += (thread_data[i][2] = int thread_data[i][2])
		)
		format "% beads: %
" all all_beads
	)

fn sort4 a1 a2 = if a1[4] < a2[4] then 1 else if a1[4] > a2[4] then -1 else 0   
fn sort3 a1 a2 = if a1[3] < a2[3] then 1 else if a1[3] > a2[3] then -1 else (sort4 a1 a2)

I am trying it and the distribution isn’t good at all in my opinion.
For example, it does not always split the thread with longest segments. Also, one curious case I just found:
Min Radius = 5
Threads = 10
Spacing = 10

Try beads 289,290,291. It just adds 3 consecutive beads to the shortest thread.

it was a bug in my ‘ideal’ code … it should be v[4] / (v[2] + 2) as i told above

#38 is very close to ‘ideal’. there are two things which doesn’t work well.

#1 it uses finditem which is slower than “bsearch” in common case. i use in my c++ algorithm c++ implementation of:

fn sort4 a1 a2 = if a1[4] < a2[4] then 1 else if a1[4] > a2[4] then -1 else 0  
fn sort3 a1 a2 = if a1[3] < a2[3] then 1 else if a1[3] > a2[3] then -1 else (sort4 a1 a2) 

fn qsort3 tab index:1 end: = 
(
	local p = tab[index]
	
	deleteitem tab index

	local i = 1
	local j = if end == unsupplied then tab.count else amax end 1
 	local pivot = 1
	
	local k = 
	(
		if (sort3 p tab[i] < 1) then i
		else if (sort3 p tab[j] > -1) then j
		else
		(
			while (j - i > 1) do
			(
				pivot = (i + j)/2 
				
				--format "% % % == % %
" i j pivot p tab[pivot]
				
				if (sort3 p tab[pivot] < 0) then j = pivot
				else if (sort3 p tab[pivot] > 0) then i = pivot
				else i = j
			)
			if (sort3 p tab[pivot] < 1) then pivot else (pivot + 1)
		)
	)
	insertitem p tab k
)  

it’s bsearch method which is much faster.

#2 in case if current segments are equal for multiple thread a random thread will be taken instead of the longest. here is a difference:

1-4, 6-14, 9-20, (num beads of N-length thread)

– length of segments all the same:
4./2
14./7
20./10
2.0
2.0
2.0

– add to first
4./3
14./8
20./10
1.33333
1.75
2.0

– add to second
4./2
14./9
20./10
2.0
1.55556
2.0

– add to third
4./2
14./8
20./11
2.0
1.75
1.81818

do you see the difference?

i will try the idea with an ‘average’ segment again…
i remember you’ve tried to go from this side.

for now in my plugin i’m using Brute Force algorithm which works good for me and i can 100% trust it.
my typical configuration 1000s beads on 100s threads:

example

#1. I was talking about the results it produces. The performance is not good, but in C++ or C# there are many ways to make it fast.

#2. Yes, I found it a few days ago by accident.

Also there may be issues with float precision when numbers are too close, even using double. But I think it could be sorted at some point to catch the longest thread. I am mo concerned about the result, as it produces perfect distribution, always looks for the longest segment and split it. But in your last code you defined “idela” in a different way, so I got confused.

So, fixing this minor issue of splitting the shortest thread, does the #38 algorithm produce the results you want? If so, the fastest and closer I got is the last one I proposed. It is not 100% perfect, but very close and considering it’s performance I think it is a good solution.

I am not sure if a 100% perfect solution can be sone in O(n) for the number of threads. I would think it can, but I always find some issue with different solutions.

usually all problems are noticeable in range (num threads * n == num beads).

i have another example where about 30000 “beads” on 5000 “threads”. if growing process is wrong it looks pretty bad.

originally i’ve used sorting. and i was slow for this amount. after i changed to “bsearch” it takes almost nothing.

I have my own ‘stand’ for testing and debugging too…

the task becomes a millennium problem

new version! :argh:

	fn distributeBeads threads num_beads:10000 = 
	(
		fn sort3 a1 a2 = if a1[3] < a2[3] then 1 else if a1[3] > a2[3] then -1 else 0
			
		num_threads = threads.count
		thread_data = #()
		all_len = 0
		for i=1 to num_threads do
		(
			len = getshapelength threads[i]
			all_len += len
			append thread_data [i, 0, len, 0]
		)
		
		num_segs = num_threads + num_beads
		qsort thread_data sort3
		for i = 1 to amin num_beads num_threads do thread_data[i][2] = 1 

		beads = num_beads
		for i = num_threads to 1 by -1 do
		(
			local v = thread_data[i]
			num = amax (v[2]+1) (int (v[3]/all_len * num_segs + 0.5))
			all_len -= v[3]
			num_segs -= num 
			v[2] = num - 1
			beads -= v[2]	
		)
		if beads != 0 do thread_data[num_threads][1] += beads
		
		all_beads = 0
		for i = 1 to num_threads do 
		(
			all_beads += thread_data[i][2]
			thread_data[i][4] = thread_data[i][3] / (thread_data[i][2] + 1)
		)

		qsort thread_data sort1
		format "% == all beads: % >> %
" num_beads (int all_beads) thread_data
	)