20-21 and 26-27 works fine for me. But I see what you mean with other numbers, for example 37-38. With 37 beads the last thread gets 8 and with 38 it gets just 4.
I guess that in order to redistribute the beads, some thread must lose and some must gain to keep it as even as possible. :curious:
That’s what I described earlier, that I have some missing beads and I take or add it to the shortest thread. Idealy I would have to search which thread “deserves” to get one or to take one from it.
try(destroydialog BeadsAndThreads) catch()
global BeadsAndThreadsPos = if BeadsAndThreadsPos == undefined then unsupplied else BeadsAndThreadsPos
global BeadsAndThreadsParams = if BeadsAndThreadsParams == undefined then #(0,1,20,5,10) else BeadsAndThreadsParams
rollout BeadsAndThreads "Beads And Threads" width:250
(
fn p_sort p1 p2 index:1 = if p1[index] < p2[index] then 1 else if p1[index] > p2[index] then -1 else 0
fn mod_f val &int_part =
(
int_part = val as integer
flt_part = val - int_part
)
local xx = BeadsAndThreadsParams
local threads = #()
local thread_data = #()
local all_len
local min_len
spinner num_beads_sp "Beads: " type:#integer range:[0,1000000,xx[1]] fieldwidth:56 align:#right offset:[4,8]
spinner num_threads_sp "Threads: " type:#integer range:[1,100,xx[2]] fieldwidth:56 align:#right offset:[4,0]
group "Create: "
(
spinner min_radius_sp "Min Radius: " type:#integer range:[1,100,xx[3]] fieldwidth:56 align:#right offset:[4,0]
spinner bead_radius_sp "Bead Radius: " type:#integer range:[1,100,xx[4]] fieldwidth:56 align:#right offset:[4,0]
spinner threads_space_sp "Spacing: " type:#integer range:[1,100,xx[5]] fieldwidth:56 align:#right offset:[4,0]
button create_bt "Create" width:232 align:#center offset:[0,8]
)
group ""
(
button distribute_bt "Distribute" width:232 align:#center offset:[0,-6]
button distribute2_bt "Distribute 2" width:232 align:#center offset:[0,6]
)
local cc = #(num_beads_sp, num_threads_sp, min_radius_sp, bead_radius_sp, threads_space_sp)
fn updateParams =
(
for k=1 to cc.count do xx[k] = cc[k].value
)
fn createThreads =
(
delete objects
all_len = 0
min_len = 1e9
num_threads = num_threads_sp.value
thread_data = #()
for i = 1 to num_threads do
(
thread = arc name:"thread" radius:(min_radius_sp.value + threads_space_sp.value*(i-1)) from:180 to:0 wirecolor:orange
rotate thread (eulerangles 90 0 0)
converttosplineshape thread
len = curvelength thread --getshapelength thread
if len < min_len do min_len = len
all_len += len
append thread_data [gethandlebyanim thread, len, 0, 0]
)
--for i = 1 to num_threads do thread_data[i].y = thread_data[i].y / all_len
)
on create_bt pressed do undo "Create" on createThreads()
fn updateBeads = if thread_data.count == num_threads_sp.value do
(
delete (getnodebyname #bead all:on)
num_beads = num_beads_sp.value
num_threads = num_threads_sp.value
t = timestamp()
h = heapfree
count = 0
if num_beads > 0 do
(
qsort thread_data p_sort index:2
--psort thread_data index:2 dir:-1
for i = 1 to num_threads while i <= num_beads do
(
thread_data[i].z = 1
thread_data[i].w = (thread_data[i].y)/(thread_data[i].z + 1)
count += 1
)
beads = num_beads - count
for k=1 to beads do
(
qsort thread_data p_sort index:4
--psort thread_data index:4 dir:-1
thread_data[1].z += 1
thread_data[1].w = (thread_data[1].y)/(thread_data[1].z + 1)
)
count = 0
for i = 1 to num_threads do
(
thread = getanimbyhandle thread_data[i].x
seed (finditem (shapes as array) thread) --(getnodeindex shapes thread)
col = random white black
num = thread_data[i].z
for k = 1 to num do
(
b = geosphere name:"bead" radius:bead_radius_sp.value segments:2 wirecolor:col
p = k/(num + 1.0)
b.pos = interpCurve3D thread 1 p
count += 1
)
)
)
format "% >>>>>>>> % - % = time:% heap:%
" num_threads num_beads count (timestamp() - t) (h - heapfree)
)
on distribute_bt pressed do updateBeads()
on BeadsAndThreads close do
(
updateParams()
BeadsAndThreadsPos = getdialogpos BeadsAndThreads
)
on BeadsAndThreads open do
(
threads = getnodebyname #thread all:on
)
fn DistributePointsInShapes mShapes numPoints:0 =
(
fn SortByLength t1 t2 = t2[2] - t1[2]
totalLength = 0
result = for j in mShapes collect
(
length = curvelength j
totalLength += length
#(j, length)
)
qsort result SortByLength
if numPoints <= result.count then
(
result.count = numPoints
for j in result do j[2] = 1
)else(
numPoints -= result.count
done = 0
for j in result do
(
amount = int ((j[2] / (totalLength/numPoints)) + 0.5)
j[2] = amount + 1
done += amount
)
result[1][2] += (numPoints-done)
)
return result
)
fn DistributePointsAlongShapes &mShapes =
(
for j in mShapes do
(
mmin = 1.0/(j[2]+1)
j[2] = for i = 1 to j[2] collect interpCurve3D j[1] 1 (i*mmin)
)
)
on distribute2_bt pressed do
(
st = timestamp()
sh = heapfree
num_beads = num_beads_sp.value
result = DistributePointsInShapes (shapes as array) numPoints:num_beads
DistributePointsAlongShapes &result
count = 0
for j in result do count += j[2].count
format "% % >> time:% heap:%
" num_beads count (timestamp()-st) (sh-heapfree)
gc()
delete $bead*
for j in result do
(
for i in j[2] do
(
geosphere pos:i name:"bead" radius:bead_radius_sp.value segments:2 wirecolor:green
count += 1
)
)
)
--on num_beads_sp changed val do distribute2_bt.pressed() --updateBeads()
on num_beads_sp changed val do updateBeads()
)
createdialog BeadsAndThreads pos:BeadsAndThreadsPos
this algorithm works absolutely correct (IMHO). but it needs sorting after every bead distribution
I like the results of yours, but the performance is not good if you need 100K beads. There must be an inbetween solution from both algorithms that gives good results and performance.
we don’t need to do full sort… we need to shift first element in the right position in the array. with quick-search for already sorted array it should be quick
Here is a new algorithm. It produces a slightly different pattern than your last algorithm, yet I consider it produces a very good distribution. It could be modified to produce the same pattern as yours, but I am not sure if that is necessary.
Also, an adaptive threshold could be introduced to produce different patterns.
As you can see, it runs in O(n) time and is pretty fast. According to what I could test is between 10 and 100 times faster. Memory usage is a little larger with lower values, but I don’t think it is a big concern.
(
fn DistributePointsInShapes splines points:0 =
(
fn SortByLength t1 t2 = t2[2] - t1[2]
d = for j in splines collect 0
l = for j in splines collect 0
s = for j in splines collect #(j, curvelength j)
qsort s SortByLength
for j = 1 to (amin s.count points) do
(
d[j] = 1
l[j] = s[j][2] / 1.0
)
for j = 1 to points-s.count do
(
idx = finditem l (amax l)
d[idx] += 1
l[idx] = s[idx][2] / d[idx]
)
for j = 1 to d.count do
(
mmin = 1.0/(d[j]+1)
s[j][2] = for i = 1 to d[j] collect interpcurve3d s[j][1] 1 (i*mmin)
)
return s
)
gc()
st=timestamp(); sh=heapfree
result = DistributePointsInShapes (shapes as array) points:100000
format "time:% heap:%
" (timestamp()-st) (sh-heapfree)
)
Here are some results against your last algorithm:
10 Threads
1000 Beads >> time:38 vs time:4
10000 Beads >> time:416 vs time:37
100000 Beads >>time:4401 vs time:412
==========================
20 Threads
1000 Beads >> time:95 vs time:5
10000 Beads >> time:1016 vs time:38
100000 Beads >> time:10663 vs time:422
==========================
50 Threads
1000 Beads >> time:313 vs time:5
10000 Beads >> time:3241 vs time:41
100000 Beads >> time:39898 vs time:460
==========================
100 Threads
1000 Beads >> time:694 vs time:6
10000 Beads >> time:7817 vs time:46
100000 Beads >> time:95091 vs time:491
Here is a modified version that produces the exact same result as your last algorithm:
(
fn DistributePointsInShapes splines points:0 =
(
fn SortByLength t1 t2 = t2[2] - t1[2]
d = for j in splines collect 0
l = for j in splines collect 0
s = for j in splines collect #(j, curvelength j)
qsort s SortByLength
for j = 1 to (amin s.count points) do
(
d[j] = 2
l[j] = s[j][2] / 2.0
)
for j = 1 to points-s.count do
(
idx = finditem l (amax l)
d[idx] += 1
l[idx] = s[idx][2] / d[idx]
)
for j = 1 to d.count do
(
mmin = 1.0/d[j]
s[j][2] = for i = 1 to d[j]-1 collect interpcurve3d s[j][1] 1 (i*mmin)
)
return s
)
)
And here is one last version with a variable Threshold.
A value of 1 produces the pattern of your algorithm.
(
fn DistributePointsInShapes splines points:0 threshold:1 =
(
fn SortByLength t1 t2 = t2[2] - t1[2]
d = for j in splines collect 0
l = for j in splines collect 0
s = for j in splines collect #(j, curvelength j)
qsort s SortByLength
for j = 1 to (amin s.count points) do
(
d[j] = threshold + 1
l[j] = s[j][2] / (threshold + 1.0)
)
for j = 1 to points-s.count do
(
idx = finditem l (amax l)
d[idx] += 1
l[idx] = s[idx][2] / d[idx]
)
for j = 1 to d.count do
(
mmin = 1.0 / (d[j]+(1.0-threshold))
s[j][2] = for i = 1 to d[j]-threshold collect interpcurve3d s[j][1] 1 (i*mmin)
)
return s
)
)
your algorithm works very well… i don’t see any problems.
BTW
being re-written on my mxs extension it looks like:
local dtab = floattab()
local stab = floattab()
local thread_data = point3tab()
fn distributeBeads num_beads: =
(
if num_beads == unsupplied do num_beads = count
local num_threads = numsplineshapesplines thread
t = timestamp()
h = heapfree
reset dtab value:0 count:num_threads
reset stab value:0 count:num_threads
thread_data.count = num_threads
for i = 1 to num_threads do
(
len = getsplineshapelength thread shape:i
thread_data[i] = [i, len, 0]
)
sort thread_data index:#z
for j = 1 to (amin num_threads num_beads) do
(
dtab[j] = 1
stab[j] = thread_data[[j, 2]]
)
for j = 1 to num_beads - num_threads do
(
x = contains stab stab.max
dtab[x] = dtab[x] + 1
stab[x] = thread_data[[x, 2]] / dtab[x]
)
for j=1 to dtab.count do thread_data[[j,3]] = dtab[j]
sort thread_data index:#x
format "% <<<<<<< % - % = time:% heap:%
" num_threads num_beads count (timestamp() - t) (h - heapfree)
)
and performs:
100 Threads
100000 Beads >> time:130
good job!
However, I still think an O(n) on the number of Threads (shapes) should be possible, and so it would be a lot faster.
I can’t follow you…
What is finaly your ‘fair’ distribution description?
Surely I’m wrong, but if I had to do a ‘fair’ scatter in a set of splines, I won’t prioritize to give a bead to every thread. My fair distribution should be based on having spline segments as short as possible (as the probability to ‘fall’ in a longer spline is higher).
For example, with three threads of 30m, 9m and 6m, with 4 beads, i’ll put 3 in the first one (7,5m segments) and 1 in the second one (4.5m segments).
5th bead would go to first spline again (5m segments) and 6th bead to third spline (3m segments).
I don’t know if I have explained myself well.
Moreover, it depends on what threads and beads represent:
- If threads are roads and beads vehicles, I won’t worry about beads dimensions.
- But if theads represent necklaces and beads are pearls, i’ll substract pearls dimensions to the spline length (in this case, having at least a bead make sense, as a necklace without pearls is a really poor necklace!)
new version! just pure mxs:
fn distributeBeads num_beads:10000 num_threads:100 =
(
fn p_sort p1 p2 index:1 = if p1[index] < p2[index] then 1 else if p1[index] > p2[index] then -1 else 0
fn mod_f val &int_part =
(
int_part = val as integer
flt_part = val - int_part
)
seed 0
all_len = 0
t = timestamp()
h = heapfree
thread_data = for i=1 to num_threads collect
(
len = random 10.0 200.0
all_len += len
[i, len, 0, len]
)
qsort thread_data p_sort index:4
all_beads = 0
count = amin num_threads num_beads
new_len = 0
for k=1 to count do
(
num_beads -= 1
thread_data[k][3] += 1
thread_data[k][4] -= (thread_data[k][2]/(thread_data[k][3]+1))
new_len += thread_data[k][4]
)
all_beads += count
while num_beads > 0 do -- and not keyboard.escpressed
(
count = 0
all_len = new_len
new_len = 0
for i=1 to num_threads do
(
num = thread_data[i][4]/all_len * num_beads + 0.5
thread_data[i][4] = len = mod_f num &num
if (num > 0) do
(
thread_data[i][3] += num
thread_data[i][4] -= (thread_data[i][2]/(thread_data[i][3]+1))
new_len += num
count += num
)
)
if count == 0 then
(
qsort thread_data p_sort index:4
thread_data[1][3] += 1
thread_data[1][4] -= (thread_data[1][2]/(thread_data[1][3]+1))
new_len += thread_data[1][4]
count = 1
)
num_beads -= count
all_beads += count
)
--all_beads = 0
--for i=1 to num_threads do all_beads += thread_data[i][3]
format "% >>>>>>>> beads:% -> threads:% = time:% heap:%
" num_beads all_beads num_threads (timestamp() - t) (h - heapfree)
)
/*
distributeBeads num_beads:100000 num_threads:1000
*/
0 >>>>>>>> beads:100000 – threads:1000 = time:14 heap:286232L