Yea. It drives me crazy too. Because I believe there is a simple solution which we just can’t find.
check the new one… it still doesn’t work right and slow for mxs but maybe it gives you new ideas:
fn distributeBeads threads num_beads:10000 =
(
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 cosort: = if a1[3] < a2[3] then 1 else if a1[3] > a2[3] then -1 else (cosort a1 a2)
num_threads = threads.count
thread_data = #()
for i=1 to num_threads do
(
len = getsplineshapelength threads[i]
append thread_data [i, 0, len, len]
)
if num_beads <= num_threads then
(
qsort thread_data sort4
for i = 1 to num_beads do
(
local v = thread_data[i]
v[2] += 1
thread_data[i] = v
)
)
else
(
num_beads -= num_threads
new_len = all_len
while num_beads > 0 do
(
qsort thread_data sort3 cosort:sort4
missed = num_beads
all_len = 0
for i = 1 to amin num_beads num_threads do all_len += thread_data[i][4]
for i = 1 to amin num_beads num_threads do
(
local v = thread_data[i]
num = amax 1 (int (v[4]/all_len * num_beads))
num = amin num missed
v[2] += num
v[3] = v[4] / (v[2]+1)
missed -= num
thread_data[i] = v
)
format ">> missed: %
" missed
num_beads = missed
)
for i = 1 to num_threads + num_beads do
(
local v = thread_data[i]
v[2] += 1
thread_data[i] = v
)
)
all_beads = 0
for i = 1 to num_threads do all_beads += thread_data[i][2]
format "beads: %
" (int all_beads)
)
edited… i’ve tweaked it a little. it seems working right now.
No luck 🙁
Check threads=10, min radius=1. The shortest one gets crowded too quickly.
Also the distribution favors too much the shortest treads for low number of beads.
another attempt (some bug was fixed):
fn q_sort tab index:1 =
(
p = tab[1]
val = p[index]
deleteitem tab 1
i = 1
j = tab.count
k =
(
if (val >= tab[i][index]) then i
else if (val <= tab[j][index]) then j
else
(
local pivot
while (j - i > 1) do
(
pivot = (i + j)/2
if (val > tab[pivot][index]) then j = pivot
else if (val < tab[pivot][index]) then i = pivot
else i = j
)
if (val >= tab[pivot][index]) then pivot else (pivot + 1)
)
)
insertitem p tab k
)
fn sort4 a1 a2 = if a1[4] < a2[4] then 1 else if a1[4] < a2[4] then -1 else 0
fn sort2 a1 a2 = if a1[2] < a2[2] then 1 else if a1[2] < a2[2] then -1 else (sort4 a1 a2)
fn sort3 a1 a2 = if a1[3] < a2[3] then 1 else if a1[3] > a2[3] then -1 else (sort2 a1 a2)
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[4] /= all_len
thread_data[i] = v
)
if num_beads > num_threads do
(
num_beads -= num_threads
beads = num_beads
for i = 1 to num_threads do
(
local v = thread_data[i]
num = (v[4] * num_beads)
v[2] += int num
v[3] = v[4] / v[2]
beads -= int num
thread_data[i] = v
)
format ">> missed: % %
" beads num_beads
qsort thread_data sort3
for i = 1 to beads do
(
--qsort thread_data sort3
local v = thread_data[1]
v[2] += 1
v[3] = v[4] / v[2]
thread_data[1] = v
q_sort thread_data index:3
)
)
all_beads = 0
for i = 1 to num_threads do
(
all_beads += thread_data[i][2]
)
format "% beads: %
" all all_beads
)
>>>>>>>> beads:1e+006 -> threads:10000 10000 = time:395 heap:2342096L
>>>>>>>> beads:1e+006 -> threads:1000 1000 = time:34 heap:232144L
I get some errors:
- With 3 threads I get undefined for index with some beads values, for example 4,5,10,11,16,17.
- Create 11 threads with default settings and see the results for 67 and 68 beads.
This post was deleted.
this is the last… (i have to stop doing it :))
>>>>>>>> beads:1000000 -> threads:10000 10000 = time:313 heap:560064L
>>>>>>>> beads:1000000 -> threads:1000 1000 = time:27 heap:56008L
sorters:
fn sort4 a1 a2 = if a1[4] < a2[4] then 1 else if a1[4] < a2[4] then -1 else 0
fn sort2 a1 a2 = if a1[2] < a2[2] then 1 else if a1[2] < a2[2] then -1 else (sort4 a1 a2)
fn sort3 a1 a2 = if a1[3] < a2[3] then 1 else if a1[3] > a2[3] then -1 else (sort2 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
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
)
method:
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[4] /= all_len
)
if num_beads > num_threads do
(
num_beads -= num_threads
beads = num_beads
for i = 1 to num_threads do
(
local v = thread_data[i]
num = int (v[4] * num_beads)
v[2] += num
v[3] = v[4] / v[2]
beads -= num
)
format ">> missed: % %
" beads num_beads
qsort thread_data sort3
for i = 1 to beads do
(
local v = thread_data[1]
v[2] += 1
v[3] = v[4] / v[2]
qsort3 thread_data end:beads
)
)
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
)
Yea, is time to let it go.
I haven’t tried this version yet. Just out of curiosity, are these two sorting functions correct?
fn sort4 a1 a2 = if [B]a1[4] < a2[4][/B] then 1 else if [B]a1[4] < a2[4][/B] then -1 else 0
fn sort2 a1 a2 = if [B]a1[2] < a2[2][/B] then 1 else if [B]a1[2] < a2[2][/B] then -1 else (sort4 a1 a2)
no… they are not correct. i’ve copied them from wrong place. it should be:
fn sort4 a1 a2 = if a1[4] < a2[4] then 1 else if a1[4] > a2[4] then -1 else 0
fn sort2 a1 a2 = if a1[2] < a2[2] then -1 else if a1[2] > a2[2] then 1 else (sort4 a1 a2)
no doubts for the sort by 4th. (the longer thread has to get extra bead first) .
the sort by 2nd is questionable – the thread with less number of beads has to get first.
because sort by 2nd works with integers, the comparing expression could be:
sort2 a1 a2 = (a1[2] - a2[2])
it can be faster. but in this case we have to change alternative sorting order from 3-2-4 to 3-4-2 to keep advantage of simpler expression
It seems to work well.
It is still a little unbalanced and tends to favor the shortest thread, but I think is not that bad. After all it is much faster than the brute force approach.
qsort3 makes the difference. instead of sorting all array i just move the first at the right sorted position.
i’ve added this method to my mxs extension as well.
it’s like
bsearch
but searches an index in sorted array