What are the general ways to optimize an algorithm taking quadratic or worse time?

[onodera]

I have an algorithm that generates N random points and connects them with line segments having smallest possible total length. It works, but its scalability is atrocious.

Pts	ms
10	8
15	25
20	45
25	75
30	112
35	164
40	232
45	293
50	377
55	456
60	564
65	680
70	796
75	922
80	1083
85	1257
90	1412
95	1546
100	1800
105	1949
110	2264
115	2529
120	2732
125	2985
130	3241
135	3582
140	3825
145	4195
150	4475
155	5060
160	5454
165	5774

O(n^2*log n) isn't something I'm happy with. I don't think I could do this in linear time, but even O(n log n) would be nice.

What are the generic steps towards improving the algorithm's efficiency? Using more appropriate data structures?

[KrazyHorse]

a) Do you mean connects pairwise, or connects with a chain?
b) I don't know very much discrete math (or compsci in general) but isn't this just the traveling salesman problem?

[KrazyHorse]

Also, what space do these N points live in? 2-d euclidean? Is it 100% necessary that you get the exact best linking or can you live with suboptimal if it drastically reduces the computation time?

[onodera]

a) Do you mean connects pairwise, or connects with a chain?
b) I don't know very much discrete math (or compsci in general) but isn't this just the traveling salesman problem?

No, it's not a TS problem. TS builds a straight path that connects all points and is the shortest possible, I build a treelike graph (see the attachment). I'm almost sure this is a known problem, but my google-fu failed me.
UPD: Yes, 2-d euclidian.

[onodera]

Yay, found what it is. It's a minimum spanning tree, now let's Google it.

[Winston]

What are the general ways to optimize an algorithm taking quadratic or worse time?

Cool, I was just about to ask this myself.

Spoiler:

Sorry.

[loinburger]

Somewhere or another I've got a nifty paper I downloaded on optimization techniques, but I can't find it at the moment and suspect it died along with the destruction of my hard drive. However, google suggests that this may be a handy article. The bottom line to optimizing most programs (assuming you're stuck with O(n^2) or O(n^3) or whatever, though this is also applicable to algorithms with better complexity) is to improve memory performance - tile your loops, throw in some pre-fetching, keep the working set managable, etc. Most of the non-memory optimizations are performed adequately by the compiler and over-optimizing will leave you with an unreadable mess. A few tweaks that the compiler may not be performing for you are some forms of strength reduction (if you're dividing the elements of a floating point array by a float constant, then instead generate a new constant equal to the reciprocal of the divisor and multiply the array elements by the result - multiplication is cheaper than division) and (related to memory optimization) pool allocation where rather than repeatedly allocating and freeing (or leaving for the GC to clean up) temporary data structures you instead generate a static pool of data structures that you take care of initializing and dismantling without bothering with the memory management subsystem.

Be careful about inlining, you may inadvertently increase the number of instruction cache misses if you start generating uber-methods. I also advise you steer clear of multithreading unless you know what you're doing - lock overhead tends to make naively multithreaded programs run slower than their single-threaded counterparts.

[BlackCat]

I'm not sure he's got to the point where he needs that kind of optimization yet - to me it looks like it's the algorithm that needs optimization.

With such jumps in performance, I guess that you check connections unnessecary.

I would only check neighvours until I found vertical/horizontical distances that was greater than the shortest.

[loinburger]

If he knows that it's a minimum spanning tree problem then he's already finished with that part of the optimization. Now he's just got to implement the thing (assuming he can't find any decent source code that's already done so).

[BlackCat]

Oh, missed that Yeah, guess that he is busy hunting.

[onodera]

I can't find any decent source code, because in my case my graph is more or less a complete graph (as I have no predefined edges. Therefore I'm going to first define enough edges (using Delaunay triangulation) and then use one of the non-viral open source MST algorithm implementations.
I'm sure CGAL has a good Delaunay implementation, but ripping it out of there is bloody hard. And I'm not going to interface with a C++ library from .NET, no.

[Asher]

We need more threads like this.

I only skimmed the article as I need to run out now. But it sounds like you got the algo part solved and now you wanna optimize the code to run like a ***** with her hair on fire, and I can help with that (I love that ****).

So if that's what you're looking for, what platform are you running this on (Windows/Linux/Mac/Unix) and is it running in a VM (.NET, Java, etc) and are you restricted to C++. As much as I hate to admit it some functional programming languages can solve these problems pretty efficiently.

And what kind of hardware are you running it on? Can we split this bad boy up into threads and make all the CPU cores hot?

[Kuciwalker]

I have an algorithm that generates N random points and connects them with line segments having smallest possible total length. It works, but its scalability is atrocious.

*snip*

O(n^2*log n) isn't something I'm happy with. I don't think I could do this in linear time, but even O(n log n) would be nice.

What are the generic steps towards improving the algorithm's efficiency? Using more appropriate data structures?

Wiki Kruskal's algorithm.

edit: ah, you realized it was MST. Assuming you can get your algorithmic complexity as low as possible, just try to optimize your loops to minimize jumps and cache misses.

[onodera]

I've spent this Saturday debugging my divide-and-conquer Delaunay triangulation algorithm, and it definitely runs in O(n*log n) time now.
I still have to implement a better data structure for the MST algoritm itself, because it's still O(n^2) and slows the whole thing down.