Home > Archive > Fortran > February 2007 > I need some guideance regarding parallel processing
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
I need some guideance regarding parallel processing
|
|
|
| Hey Folks,
I am involved in a large image processing project at work. I am using
Lahey FORTRAN v6.2 pro on linux (I have 6 machines for sure and
possibly a whole lab full of diskless clients awaiting).
I'll be looping through large arrays (~36000000 by >6), basically
comparing each element with ALL other elements in the array. Initial
runs suggest it will take about 600 days to complete (a large part of
this is due to my programming; I'm working on optimizing the code)...
Regardless of my programming skills, I need some guidance on what type
of distributed system I should implement. In a previous post on this
list, I was turned on to openMP. But I am open to learning MPI, PVM,
etc if that will facilitate getting the job done.
I guess my question to you folks working with large datasets is:
1) What standard have you implemented to network machines together?
2) What message passing standard do you use?
3) Other than 'turn back now', do you have any other guidance to how I
should set up the cluster?
I am open to any and all suggestions.
Thanks for your time.
Tripp
GIS Lab Manager
The Univ. of GA
WSFNR
| |
| Richard Maine 2007-02-03, 4:13 am |
| tripp <tripplowe@gmail.com> wrote:
> I'll be looping through large arrays (~36000000 by >6), basically
> comparing each element with ALL other elements in the array. Initial
> runs suggest it will take about 600 days to complete (a large part of
> this is due to my programming; I'm working on optimizing the code)...
One of the first principles of optimization: first work on getting good
algorithms before optimizing code. That's such a classic piece of advice
as to be a cliche. You can sometimes get many orders of magnitude
improvement from better algorithms. Yes, I mean the many orders of
magnitude literally.
I don't know enough about your application to say for sure, but I'd bet
a modest sum that there are better algorithms than comparing each
element with all the others.
I'm not the best person to answer your more specific questions about
parallel processing.
--
Richard Maine | Good judgement comes from experience;
email: last name at domain . net | experience comes from bad judgement.
domain: summertriangle | -- Mark Twain
| |
| Brooks Moses 2007-02-03, 4:13 am |
| Richard Maine wrote:
> tripp <tripplowe@gmail.com> wrote:
>
> One of the first principles of optimization: first work on getting good
> algorithms before optimizing code. That's such a classic piece of advice
> as to be a cliche. You can sometimes get many orders of magnitude
> improvement from better algorithms. Yes, I mean the many orders of
> magnitude literally.
Seconded.
Also, it sounds like from that description of the algorithm that your
proposed algorithm can be broken up into relatively independent chunks
-- compare the first N numbers to all the other elements, compare the
second N, and so on. If this is the case, then the best strategy for
parallelism is to write a program that compares only the Mth set of N
numbers, and run multiple copies of it independently on multiple
computers with different values for M, until the array is covered. Then
the only communication you need is copying out the input data files at
the beginning, and copying the result files back onto one computer at
the end and running whatever program collates the results.
- Brooks
--
The "bmoses-nospam" address is valid; no unmunging needed.
| |
| Tobias Burnus 2007-02-03, 4:13 am |
| Hi,
On 3 Feb., 05:37, "tripp" <trippl...@gmail.com> wrote:
> comparing each element with ALL other elements in the array.
Depending what you need, you could reduce the number of comparisons to
half, by only comparing "A with B" and not "B with A"; or if you need
also the "B with A" entries, it might be faster to assign the "A with
B" result rather than comparing again. (Whether it is faster depends
a lot on the fastness of the comparison routine.)
Additionally, think of the memory layout
do i=1,N
B = myfunc(A(i,:))
end do
is slower than
do i=1,N
B = myfunc(A(:,i))
end do
since in the second case, one passes a contiguous chunk of memory
whereas in the first case it is not contiguous and the compiler might
create a contiguous temporary array, which costs precious CPU time.
> Regardless of my programming skills, I need some guidance on what type
> of distributed system I should implement. In a previous post on this
> list, I was turned on to openMP. But I am open to learning MPI, PVM,
> etc if that will facilitate getting the job done.
Well, as Brooks suggested, the easiest would be to run the program
multiple times on different parts of the data, if possible.
The Advantage of OpenMP is that it is comparably easy to parallelize a
program, starting from the most time consuming loops and without
thinking of comunicating the global arrays. Di vantage is that you
need shared memory for OpenMP.*
MPI is much more flexible, works well with distributed-memory systems
(and also shared-memory systems), but is harder to program. (One needs
to communicate all the data explicitly as there is no concept of
global memory.) Additionally, one has to setup the MPI implementation
(e.g. OpenMPI, MPICH, ...) before one can start.
PVM: I never used that one, but my feeling is that OpenMP and MPI are
more widely used.
Thus: Running the same, serial program on different (chunks) of the
data should be prefered (more simple).
Otherwise MPI as you seem to have several computers which don't share
their memory.
General advise: Make sure the serial program works well and uses a
good algorithm before you start to parallelizing. Especially, in case
of MPI, program such that the program also works (identically) in
serial mode - this makes developing and debugging easier. And try hard
to keep the only-MPI parts in sync with the only-serial parts of the
program.
Tobias
* At least Intel offers a Fortran compiler which allows you to used
OpenMP on a distributed-memory systems.
| |
| glen herrmannsfeldt 2007-02-03, 4:13 am |
| tripp wrote:
> I am involved in a large image processing project at work. I am using
> Lahey FORTRAN v6.2 pro on linux (I have 6 machines for sure and
> possibly a whole lab full of diskless clients awaiting).
> I'll be looping through large arrays (~36000000 by >6), basically
> comparing each element with ALL other elements in the array. Initial
> runs suggest it will take about 600 days to complete (a large part of
> this is due to my programming; I'm working on optimizing the code)...
If this is still the closest pair problem, I am 99.999% sure that there
is a better way to do it.
http://www.cs.mcgill.ca/~cs251/Clos...sestPairDQ.html
Describes O(n log n) algorithms for the closest pair of points in
one and two dimensions. I believe it isn't hard to generalize to
six dimensions, and to the six points nearest each point.
That was one of the first that came up when I put
minimum pair distance algorithm
into Google. It might be that other hits are closer to what
you need, or a different query. Specifically, I would look at
divide and conquer algorithms. I believe one will be O(n log n),
or about 1000000 times faster than an O(n**2) algorithm.
-- glen
| |
| Gordon Sande 2007-02-03, 7:07 pm |
| On 2007-02-03 00:37:36 -0400, "tripp" <tripplowe@gmail.com> said:
> Hey Folks,
>
> I am involved in a large image processing project at work. I am using
> Lahey FORTRAN v6.2 pro on linux (I have 6 machines for sure and
> possibly a whole lab full of diskless clients awaiting).
>
> I'll be looping through large arrays (~36000000 by >6), basically
> comparing each element with ALL other elements in the array. Initial
> runs suggest it will take about 600 days to complete (a large part of
> this is due to my programming; I'm working on optimizing the code)...
You provide no hint of why you need to compare ALL pairs. If these are in
any sense metric based then you need to find out about nearest neigbour
searching, range searching, associative searching and all the other
variants on the general theme that have been developed in the many years
since computer science became concerned with efficiency of use. The
abstract field is call concrete computational complexity. Searching
is a well worked subfield. Parallel and distributed searching have been
considered.
If you are doing metric comparisons then a typical algorithm of this
class will have an n log ( n ) setup cost with a log ( n ) cost for
each query. That makes finding the nearest neighbours of all elements
only n log ( n ). Even lousy code will run circles around a highly
polished n^2 code at your sizes.
Any effort on optimizing code done before you work on choosing better
algorithms is a total complete waste of time unless you are a salesman
selling machine time. It is hard to be more emphatic on the issue of
getting good algorithms before you try to optimize things.
If your comparisons are not metric based then maybe you need to try
for a more general notion of metric. If that also fails then run to talk
a complexity type to see what is known about whatever you problem is.
If you work on the alogithms then you will be able to move onto REALLY BIG
prblems and you will not even have to buy your own computer company.
> Regardless of my programming skills, I need some guidance on what type
> of distributed system I should implement. In a previous post on this
> list, I was turned on to openMP. But I am open to learning MPI, PVM,
> etc if that will facilitate getting the job done.
>
> I guess my question to you folks working with large datasets is:
> 1) What standard have you implemented to network machines together?
> 2) What message passing standard do you use?
> 3) Other than 'turn back now', do you have any other guidance to how I
> should set up the cluster?
>
> I am open to any and all suggestions.
>
> Thanks for your time.
> Tripp
> GIS Lab Manager
> The Univ. of GA
> WSFNR
| |
| glen herrmannsfeldt 2007-02-03, 7:07 pm |
| Gordon Sande wrote:
(snip)
> You provide no hint of why you need to compare ALL pairs.
(snip)
> If you are doing metric comparisons then a typical algorithm of this
> class will have an n log ( n ) setup cost with a log ( n ) cost for
> each query. That makes finding the nearest neighbours of all elements
> only n log ( n ). Even lousy code will run circles around a highly
> polished n^2 code at your sizes.
In at least one post he mentions Euclidean distance. I am pretty
darn sure that there is an O(n log n) algorithm for that, even in
six dimensions. I am not sure if it gets faster or slower in more
dimensions.
> Any effort on optimizing code done before you work on choosing better
> algorithms is a total complete waste of time unless you are a salesman
> selling machine time. It is hard to be more emphatic on the issue of
> getting good algorithms before you try to optimize things.
My quick calculation is that n/log2(n) is about 1,000,000, though it
might be a factor of two or three slower than that, but from centuries
down to minutes or hours is pretty good.
At 1 microsecond each, n log2 n for n=3.6e7 is 15 minutes. Maybe
another factor of six since he wants the six closest point for each.
-- glen
| |
| Gordon Sande 2007-02-03, 7:07 pm |
| On 2007-02-03 13:39:33 -0400, glen herrmannsfeldt <gah@ugcs.caltech.edu> said:
> Gordon Sande wrote:
>
> (snip)
>
> (snip)
>
>
> In at least one post he mentions Euclidean distance. I am pretty
> darn sure that there is an O(n log n) algorithm for that, even in
> six dimensions. I am not sure if it gets faster or slower in more
> dimensions.
The original paper on k-d trees by "Freidman, J. H., Bentley, J. L., and
Finkel, R. A. 1977. An Algorithm for Finding Best Matches in Logarithmic
Expected Time. ACM Trans. Math. Softw. 3, 3 (Sep. 1977), 209-226" was
for Euclidean as well as all the Minkowski metrics. There is lots of
literature since then. I have used k-d trees on ranks under the max
norm (L_infinity) n more than six dimensions so I know it works. The
coefficients grow a bit.
>
> My quick calculation is that n/log2(n) is about 1,000,000, though it
> might be a factor of two or three slower than that, but from centuries
> down to minutes or hours is pretty good.
Algorithm change is often much better than just a few orders of
magnitude. It is a story that deserves to be repeated often and loudly.
> At 1 microsecond each, n log2 n for n=3.6e7 is 15 minutes. Maybe
> another factor of six since he wants the six closest point for each.
>
> -- glen
| |
| Michael Metcalf 2007-02-03, 7:07 pm |
|
"Gordon Sande" <g.sande@worldnet.att.net> wrote in message
news:2007020314122916807-gsande@worldnetattnet...
>
> Algorithm change is often much better than just a few orders of
> magnitude. It is a story that deserves to be repeated often and loudly.
>
An example I found in a book(!) once, to sum (-1)**i * i from 1 to n, was to
replace
s = 0.
do i = 1, n
s = s + (-1)**i * i
end do
by
s = 0.
do i = 1, n, 2
s = s - i
end do
do i = 2, n, 2
s = s + i
end do
thereby saving the exponations (20 times faster for n=100000, it was
claimed, and for DP s). Of course, it is also possible to write:
s = n/2
if (mod(n, 2) == 1) s = s - real(n)
Regards,
Mike Metcalf
| |
| Rich Townsend 2007-02-03, 7:07 pm |
| glen herrmannsfeldt wrote:
> tripp wrote:
>
>
>
> If this is still the closest pair problem, I am 99.999% sure that there
> is a better way to do it.
>
> http://www.cs.mcgill.ca/~cs251/Clos...sestPairDQ.html
>
> Describes O(n log n) algorithms for the closest pair of points in
> one and two dimensions. I believe it isn't hard to generalize to
> six dimensions, and to the six points nearest each point.
From an extremely-brief scan through, this looks like a space partitioning
approach. There exists a large body of literature on this. I myself have used an
octree method to find nearest neighbors in 3D, and the speedups were impressive.
cheers,
Rich
| |
| Gordon Sande 2007-02-03, 7:07 pm |
| On 2007-02-03 14:46:49 -0400, Rich Townsend <rhdt@barVOIDtol.udel.edu> said:
> glen herrmannsfeldt wrote:
>
> From an extremely-brief scan through, this looks like a space
> partitioning approach. There exists a large body of literature on this.
> I myself have used an octree method to find nearest neighbors in 3D,
> and the speedups were impressive.
>
> cheers,
>
> Rich
Quadtrees in 2D and octtrees in 3D are "kith and kin" to k-d trees and the
whole collection of range searching, etc, etc methods. Quadtrees and octtrees
are specialized to makes some things in graphics easier.
All tend to be n log ( n ) setup as they do some variant on "sorting" their
inputs and then provide log ( n ) queries. If there are any number of queries
the speedup is of the "blow your socks off" variety.
| |
| Walter Spector 2007-02-03, 7:07 pm |
| Michael Metcalf wrote:
> ...
> An example I found in a book(!) once...
I did too. "Fortran Optimization"...
Any chance that "Fortran Optimization" could be brought up to
modern times? A lot of folks would really enjoy it.
W.
| |
| Michael Metcalf 2007-02-04, 7:05 pm |
|
"Walter Spector" <w6ws_xthisoutx@earthlink.net> wrote in message
news:45C50B59.462A7A29@earthlink.net...
> Michael Metcalf wrote:
>
> I did too. "Fortran Optimization"...
>
No, that's the point, the two first attempts were in another book, the third
was mine.
> Any chance that "Fortran Optimization" could be brought up to
> modern times? A lot of folks would really enjoy it.
>
I would imagine it's much harder to do than it was when CDC and IBM
dominated the high-end computing scene. I've been asked but declined.
Thanks for the thought,
Mike Metcalf
| |
| Walter Spector 2007-02-04, 7:05 pm |
| Michael Metcalf wrote:
>
> "Walter Spector" <w6ws_xthisoutx@earthlink.net> wrote in message
> news:45C50B59.462A7A29@earthlink.net...
> No, that's the point, the two first attempts were in another book, the third
> was mine.
As a historical note, my copy has penciled into it the timings of the first
two loops. Since I bought the book right after it was published in 1982(*),
we were probably running a Cyber 730 at the time, and most likely used FTN5.
For whatever value of N I used, the times were:
Opt Version 1 Version 2
0 2.387 sec 2.142 sec
1 2.141 0.367
2 2.138 0.370
3 2.137 0.373
So one lesson here is to try letting the compiler do some level of optimization.
But many compilers default to no optimization. I've encountered quite a number
of users over the years who needed to be shown how to turn optimization on...
Your version 3 was O(1), so of course was independant of N and executes in almost
zero time. Obviously the best version and the point of the lesson.
W.
(*) I ordered it directly from Academic Press. However they returned (or backordered?)
my order. When I called them about it, she claimed they had a warehouse fire which
destroyed a lot of the early copies. (No idea if this was true or not.) After a bit
of begging, they somehow they found a copy to send me.
| |
| Michael Metcalf 2007-02-04, 7:05 pm |
|
"Walter Spector" <w6ws_xthisoutx@earthlink.net> wrote in message
news:45C659C5.D3157D42@earthlink.net...
>
> (*) I ordered it directly from Academic Press. However they returned (or
> backordered?)
> my order. When I called them about it, she claimed they had a warehouse
> fire which
> destroyed a lot of the early copies. (No idea if this was true or not.)
Well, I've never heard that story before!
Regards,
Mike Metcalf
| |
|
| I should have known I was in for it when I asked ya'll how to paralyze
my code before optimizing it. Thanks for getting me back on the right
track.
Glen, you are right, this is still the closest pair problem. To be
more exact, this is a KNN-type problem. I'm using the k-nearest
neighbors to
calculate a metric... For each record, I have to calculate the
Euclidean distance to all other records in order to find the 'closest'
neighbors. I did
not phrase my question in those terms because I was in the middle of
trying to make my KNN code faster and had 'coded my self into a
corner'
and needed some help (not specific to KNN algorithms).
I beleive I will try to follow up with k-d trees. That looks
promising.
Mr. Metcalf, Glen, Tobias, and others, thank you for your time. All
of ya'll have been a great help.
Tripp Lowe
UGA
Warnell School of Forestry and Natural Resources
Athens, Georgia
| |
| Beliavsky 2007-02-05, 7:05 pm |
| On Feb 5, 9:07 am, "tripp" <trippl...@gmail.com> wrote:
> I should have known I was in for it when I asked ya'll how to paralyze
> my code before optimizing it. Thanks for getting me back on the right
> track.
I think you mean "parallelize", not "paralyze" :).
| |
| gary.l.scott@lmco.com 2007-02-05, 7:05 pm |
| On Feb 5, 10:01 am, "Beliavsky" <beliav...@aol.com> wrote:
> On Feb 5, 9:07 am, "tripp" <trippl...@gmail.com> wrote:
>
>
> I think you mean "parallelize", not "paralyze" :).
I "paralyze" code all the time...its unavoidable with the win32 api.
| |
| Gordon Sande 2007-02-05, 7:05 pm |
| On 2007-02-05 12:01:30 -0400, "Beliavsky" <beliavsky@aol.com> said:
> On Feb 5, 9:07 am, "tripp" <trippl...@gmail.com> wrote:
>
> I think you mean "parallelize", not "paralyze" :).
Probably too much reliance on a "spill chucker" followed by minimal
proof reading.
| |
| glen herrmannsfeldt 2007-02-05, 7:05 pm |
| tripp wrote:
(snip)
> For each record, I have to calculate the
> Euclidean distance to all other records in order to find the 'closest'
> neighbors.
The ideas behind the algorithms mentioned (or not yet mentioned) is
that you don't have to find the distances to all to know that you
have the k nearest. If you know some are close enough to a point
that is known to be far enough away, then you can know that the all
in that group are farther away than the k that you have.
It might not be quite as easy to see as for O(n log n) sorting
algorithms, which also don't have to compare each element to all
other elements in order to properly sort them. It is somewhat
harder to visualize in three or six dimensions, but for most of
them it isn't hard to prove that the algorithm is correct.
There are also algorithms that approximate the solution to many
problems, especially NP-hard problems where the true solution
is exponential in problem size. That doesn't seem to be the
case with this problem.
(snip)
-- glen
| |
|
| Snippet from Dictionary.com
'par=B7a=B7lyze :
1=2E to affect with paralysis.
2=2E to bring to a condition of helpless stoppage, inactivity, or
inability to act: The strike paralyzed communications. '
Ah, that was the problem. I Googled for "Paralyze FORTRAN Code", not
"Parallelize FORTRAN Code". I think that
describes my code exactly, thank you...
Thanks Again.
Tripp
| |
|
| On Feb 5, 10:58 am, Gordon Sande <g.sa...@worldnet.att.net> wrote:
....
> Probably too much reliance on a "spill chucker" ...
In that vain^h^hne^h^h^hein my favorite follows--
I have a spelling checker.
It came with my PC.
It plane lee marks four my revue
Miss steaks aye can knot see.
Eye ran this poem threw it.
Your sure real glad two no.
Its very polished in its weigh,
My checker tolled me sew.
A checker is a blessing.
It freeze yew lodes of thyme.
It helps me right awl stiles two reed,
And aides me when aye rime.
Each frays come posed up on my screen
Eye trussed too bee a joule.
The checker pours o'er every word
To cheque sum spelling rule.
Bee fore a veiling checkers
Hour spelling mite decline,
And if we're laks oar have a laps,
We wood bee maid too wine.
Butt now bee cause my spelling
Is checked with such grate flare,
There are know faults with in my cite,
Of nun eye am a wear.
Now spelling does not phase me,
It does knot bring a tier.
My pay purrs awl due glad den
With wrapped words fare as hear.
To rite with care is quite a feet
Of witch won should be proud,
And wee mussed dew the best wee can,
Sew flaws are knot aloud.
Sow ewe can sea why aye dew prays
Such soft wear four pea seas,
And why eye brake in two averse
Buy righting want too please.
[source unknown]
| |
| Gib Bogle 2007-02-05, 7:05 pm |
| tripp wrote:
> Hey Folks,
>
> I am involved in a large image processing project at work. I am using
> Lahey FORTRAN v6.2 pro on linux (I have 6 machines for sure and
> possibly a whole lab full of diskless clients awaiting).
>
> I'll be looping through large arrays (~36000000 by >6), basically
> comparing each element with ALL other elements in the array. Initial
> runs suggest it will take about 600 days to complete (a large part of
> this is due to my programming; I'm working on optimizing the code)...
>
> Regardless of my programming skills, I need some guidance on what type
> of distributed system I should implement. In a previous post on this
> list, I was turned on to openMP.
I think that to use OpenMP you must have a shared-memory multi-processor
machine. But as has been pointed out, you probably have no need to go
parallel.
| |
|
| Hi Tripp,
I guess you get to be the lucky one this w . Here is a link to code
that uses k-d trees to find nearest neighbors in n-dimensional
Euclidean space. There are two versions, one written in F95 and the
other in C++. It appears that these programs will do almost exactly
what you want.
http://adsabs.harvard.edu/abs/2004physics...8067K
This link will take you directly to the source code package:
ftp://lyapunov.ucsd.edu/pub/nonline.../kdtree2.tar.gz
Enjoy,
Brian
On Feb 2, 8:37 pm, "tripp" <trippl...@gmail.com> wrote:
> Hey Folks,
>
> I am involved in a large image processing project at work. I am using
> Lahey FORTRAN v6.2 pro on linux (I have 6 machines for sure and
> possibly a whole lab full of diskless clients awaiting).
>
> I'll be looping through large arrays (~36000000 by >6), basically
> comparing each element with ALL other elements in the array. Initial
> runs suggest it will take about 600 days to complete (a large part of
> this is due to my programming; I'm working on optimizing the code)...
>
> Regardless of my programming skills, I need some guidance on what type
> of distributed system I should implement. In a previous post on this
> list, I was turned on to openMP. But I am open to learning MPI, PVM,
> etc if that will facilitate getting the job done.
>
> I guess my question to you folks working with large datasets is:
> 1) What standard have you implemented to network machines together?
> 2) What message passing standard do you use?
> 3) Other than 'turn back now', do you have any other guidance to how I
> should set up the cluster?
>
> I am open to any and all suggestions.
>
> Thanks for your time.
> Tripp
> GIS Lab Manager
> The Univ. of GA
> WSFNR
| |
| Michael Metcalf 2007-02-06, 7:06 pm |
|
"dpb" <dpbozarth@swko.net> wrote in message
news:1170701371.586483.310620@j27g2000cwj.googlegroups.com...
>
> [source unknown]
>
Candidate for a Pullet Surprise
Often called "An Owed to the Spelling Checker")
by Jerrold H. Zar
Google is your fiend.
Regards,
Mike Metcalf
| |
|
| On Feb 5, 7:49 pm, "dpb" <dpboza...@swko.net> wrote:
> On Feb 5, 10:58 am, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> I have a spelling checker.
> It came with my PC.
> It plane lee marks four my revue
> Miss steaks aye can knot see.
[...]
> [source unknown]
It is a beauty, and quite hard to read for a non-native speaker...
according to
http://bdb.co.za/shackle/articles/pullet_surprise.htm
credit goes to Professor Jerrold Zar.
| |
|
| Brian,
That's great. I've integrated the k-d routines, though, I've just now
gotten a chance to run them (sick child). I'll update ya'll how it
works out.
Thanks for the lead (and for not making fun of my spellin').
Tripp
| |
|
| Brian, you were right. It was my lucky day...
I finally got a chance to implement the K-D routines Brian linked to a
few posts
back, and figured I would follow up.
- 66 seconds to build the tree from a 10,000,000 element array
- 3 seconds to search for the 7 nearest neighbors for 10,000 elements
in the array
(I copied the first 10,000 elements to 7 other records in the array,
not overwriting
one of the first 10k. This ensures there are at least 7 exact
matches and I knew where
they were located in the array.)
These are the results:
# of exact matches % correct
7 of 7: 98.27% (9827 / 10000)
6 of 7: 1.71% (171 / 10000)
5 of 7: remaining (2 / 10000)
note: This routine returns the current search vector as one of the
nearest neighbors
Some good stuff.
Thanks.
Tripp
| |
| Brooks Moses 2007-02-14, 4:12 am |
| tripp wrote:
> Brian, you were right. It was my lucky day...
>
> I finally got a chance to implement the K-D routines Brian linked to a
> few posts
> back, and figured I would follow up.
>
> - 66 seconds to build the tree from a 10,000,000 element array
> - 3 seconds to search for the 7 nearest neighbors for 10,000 elements
> in the array
This is the same problem that was going to take 600 days in your
original version? (Well, ok, it looks like the original version was
36,000,000 elements, and it was an n^2 algorithm, so 60 days there.)
That's pretty impressive! I think you've just become the poster child
for "optimize by getting a better algorithm." Thanks for following up;
it's good to be reminded of just how much of a difference it can make.
- Brooks
--
The "bmoses-nospam" address is valid; no unmunging needed.
|
|
|
|
|