ENOUGH!
here is what i have with my c++ mxs extension:
>>>>>>>> beads:1000000 -> threads:1000 1000 = time:8 heap:64L
>>>>>>>> beads:10000000 -> threads:10000 10000 = time:71 heap:64L
with this “challenge” i’ve added ~20 new methods to mxs ext. mostly sortings and get/set tab elements
Thank everyone who was participated.
I am glad all these was of any help.
Whenever I try to help someone, I do effort myself to give a good answer, but being it you I double the effort because you deserve it.
Having contributed to this community and to my own knowledge of MXS so insensibly, the least I can do is to try to help. Sometimes it works, other simply not, but it well worth the effort if you can get something useful out of it.
BTW, don’t think I gave up on this. I am still trying to tweek my last algorithm.
Very funny, at the same time very serious I’m really very impressed of your knowledge. DenisT and Jorge, you’re really masters.
I’ve already told that is kind of magic… every time when i put myself in any challenge it’s magically comes back to me with my tasks, problems…
I’ve been playing a little with the last algorithm I proposed and although it can be modified to produce correct results, it would need at least two sorting and so it would be slower than what I think this should be.
So, I went back to a previous algorithm (#60 ) and fixed it. As none of the algorithm shown here produce a balanced distribution (except the brute force), I think this new version is a good solution.
Some algorithms tend to distribute more beads towards the shortest threads, mine does the opposite, but in the long run the result is very similar to the brute force solution, so the distribution is very even. The greater the amount of beads the more even the distribution.
It runs pretty fast and most of the time goes to the sorting part. If the input array is already sorted, then it is as fast as it can get I think.
The result is the following for 10K threads and any number of beads:
beads:10000000 >> threads:10000 >> time:141ms heap:3076336L
Collecting data = 18ms
QSort = 104ms
So, the algorithmic part (in bold), which is very simple, is just 19ms
fn DistributePointsInShapes splines points:0 =
(
fn SortByLength a b = if a[3]<b[3] then -1 else if a[3]>b[3] then 1 else 0
d = 0.0
r = for j in splines collect
(
l = (curvelength j) as double
d += l
#(j, 1, l)
)
qsort r SortByLength
[B] if points <= r.count then
(
for j = 1 to (r.count-points) do r[j][2] = 0
)else(
for j in r do
(
j[2] = amax 1 (int (j[3]/d * points))
d -= j[3]
points -= j[2]
)
)[/B]
return r
)
This is another version, which tends to accumulate more beads towards the shortest threads. The previous version works better in my opinion.
fn DistributePointsInShapes splines points:0 =
(
fn SortByLength a b = if a[3]<b[3] then -1 else if a[3]>b[3] then 1 else 0
d = 0.0
r = for j in splines collect
(
l = (curvelength j) as double
d += l
#(j, 1, l)
)
qsort r SortByLength
if points <= r.count then
(
for j = 1 to (r.count-points) do r[j][2] = 0
)else(
points -= r.count
for j in r do
(
j[2] = int (j[3]/d * points)+1
d -= j[3]
points -= j[2]-1
)
)
return r
)
In C++, this should take 10ms or less.
it’s fast, but it doesn’t do what i expect. i want to have more or less equal distribution, when spacing between beads on all thread is close to average…
both your algorithms don’t match this criteria. the difference between shortest and longest might be more than 2 times
Yours also produces this difference, but towards the shortest thread.
Just to mention one sinple example, check both algorithms with:
Beads = 30
Threads = 5
Min Radius = 5
Spacing = 10
Another one (among the millions of them)
Beads = 80
Threads = 8
Min Radius = 10
Spacing = 5
With larger amount of beads, the solution I am proposing produces much even results, as far as I could measure. For a few beads, the brute force could be used, but I think if this is for scattering, things gets interesting with large amount of data.
What routine are you using to validate the output?
I am validating the resulting segments against the result produced by the brute force algorithm, average of segments lengths per thread, minimum and maximum segments.
Here is a new version based on the last algorithm. This one produces a much better distribution.
beads:10000000 >> threads:10000 >> time:167ms heap:3656584L
fn DistributePointsInShapes splines points:0 =
(
fn SortByLength a b = if a[3]<b[3] then -1 else if a[3]>b[3] then 1 else 0
d = 0.0
r = for j in splines collect
(
l = (curvelength j) as double
d += l
#(j, 1, l)
)
qsort r SortByLength
if points <= r.count then
(
for j = 1 to (r.count-points) do r[j][2] = 0
)else(
p = r[1]
for j in r do
(
j[2] = amax 1 (int (j[3]/d * points))
if (p[3]/(p[2]+1)) > (j[3]/(j[2]+1)) do
(
if p[2]+1 <= points-1 do
(
p[2] += 1
j[2] -= 1
points -= 1
)
)
d -= j[3]
points -= j[2]
p = j
)
)
return r
)
SUPER! distribution is very good!
couple things:
#1: a bug(?)
for j = 1 to (r.count-points) do r[j][2] = 0
probably has to be like:
for j = 1 to points do r[r.count-j+1][2] = 1
#2: suggestion – change to:
if (p[3]/(p[2]+[B]2[/B])) > (data[3]/(data[2]+[B]2[/B])) do
it will be “in advance” splitting (after split the segment should be the longest).
Not really. I had it the way you say in previous versions, but I was bored and changed it to a clean way
I am setting the values to 1 when collecting data, then just cero out from the shortest thread.
#2: suggestion – change to:
if (p[3]/(p[2]+[B]2[/B])) > (data[3]/(data[2]+[B]2[/B])) doit will be “in advance” splitting (after split the segment should be the longest).
Tried it before but it produced several errors in different situations, so I went back to +1.
i see a problem at:
threads 10
min radius 1
spacing 10
number beads 10…11…12…