optimizing for/while loops...?

This will only work if the objects in your array are ordered from low to high.
If they're ordered like that, it will definately make a difference. I think hash-tables (or whatever they are called, never used them myself) should be a good solution to your problem.

Depends on your intention.

Are you after a searching algorithm?
http://en.wikipedia.org/wiki/Binary_search

Or are you comparing value with every element of the array?

What is the application of this?

Quote:

Original post by Rasmadrak I'm wondering how expensive a loop is? If I have, say 20000 objects, that each need to be checked against the others and the array is sorted by some value, would I gain performance by doing something like this.

What exactly are you trying to do? If you need to perform some operation on each pair of objects, then you need to do a nested iteration:

for(i=0;i<objects;i++)for(j=i+1;j<objects;j++) check(object,object[j]);

There's no way (that I know of) to speed that up in any way.

I thought of doing something similar to this...

pseudo, of course.. ;)

for every object
for every obstacle
if object collide with obstacle
Solve();


And since all objects, obstacles etc are sorted in a descending (or ascending) order, I thought that I could do a simple check to find the first object within the boundries of the current objects radius, or rather it's potential collision radius...

:)

Anyway, I think I'll drop the whole idea and go for an octree solution or something similar. :)
But I thought that it should be quite a performance boost to easily skip half or more of a big array... :D

What's ascending order in 2D/3D? Sounds like you want something like an AABB tree.

Ascending order is (for me) distance to the viewer, or any other "fixed" origin... since all objects in my game are calculating their distance to the camera, I thought that I could do it the easy way and check all objects in the list that are currentobject+-currentobject.size away from the object.

of course this solution would generate some faulty searches, i.e stuff on the opposite of the camera and so on, but rather checking those than all! :D

Quote:

Original post by FlowingOoze Quote: Original post by Rasmadrak I'm wondering how expensive a loop is? If I have, say 20000 objects, that each need to be checked against the others and the array is sorted by some value, would I gain performance by doing something like this. What exactly are you trying to do? If you need to perform some operation on each pair of objects, then you need to do a nested iteration: for(i=0;i<objects;i++)for(j=i+1;j<objects;j++) check(object,object[j]); There's no way (that I know of) to speed that up in any way.

Actually there often is! For example if you're doing duplicate detection, most people would first think of comparing every item to every other item right? However you can simply hash every item and then only compare those with an identical hash. Basically that takes an O(n*n) algorithm and turns it into an O(n) algorithm. The same kind of thing can be done for a few other situations.

What Rasmadrak wants is a simple binary search.
The code below is the most optimal way of performing a binary search (returns -1 if not found):

template <class T, class TKey>int BinarySearch(const T a[], int n, const TKey &find) {	int l = 0, r = n;	while (l < r) {		int m = (l + r)>>1; //midpoint		if (a[m] < find)			l = m + 1;		else			r = m;	}	if (a[l] == find)		return l;	else		return -1; //NOT FOUND}

Quote:

Original post by iMalc However you can simply hash every item and then only compare those with an identical hash. Basically that takes an O(n*n) algorithm and turns it into an O(n) algorithm. The same kind of thing can be done for a few other situations.

Not quite. You still have to search your collection of hashes as part of the insertion and duplicate detection. The whole operation is an O(n log n) algorithm, not O(n). Not that it matters much. [grin]

Quote:

Original post by frob Quote: Original post by iMalc However you can simply hash every item and then only compare those with an identical hash. Basically that takes an O(n*n) algorithm and turns it into an O(n) algorithm. The same kind of thing can be done for a few other situations. Not quite. You still have to search your collection of hashes as part of the insertion and duplicate detection. The whole operation is an O(n log n) algorithm, not O(n). Not that it matters much. [grin]

No It's NOT!

The whole operation has absolutely nothing to do with the log of the number of items. That's utter nonsense. There's just nothing log(n) about it!
The average number of items in each bucket is exactly equal to the number of items divided by the number of buckets. i.e. a constant factor.

More accurately it's more like Average = O(n*k*k) where k is the average number of items per bucket, but the table size is normally chosen so that k is about 1. I would have written the theta symbol above in place of the O if possible, as techinically it's still Worse case = O(n*n) (k being equal to n), when all items give the same hash. But that isn't the usual case.

Enough mere propoganda.

He is thinking, I assume, of tree-based std::map being used for hashing. Complexity for real hashing is tricky; it rather depends on how intelligently you can set the bucket count and the quality of the hashing function (for absolute worst-case complexity, everything collides no matter what you do, and you effectively just have a linked list).

Okay, we are totally away from the OP comment. He has already decided to go with a spatial solution to his distance-sorting problem.


Just for your own notes, I left the game industry several years ago to persue less stressful and more lucrative work. I have been working with (including performing corporate research on) large data sets (GB to TB range) since 1999. I stick around here because I like to comment on algorithmic topics.

In other words, I know this subject. I'm not like so many of the 15-year-old game programmer wannabe kids we get on this site.

On to the technical debate. [grin]

Quote:

Original post by iMalc The whole operation has absolutely nothing to do with the log of the number of items. That's utter nonsense. There's just nothing log(n) about it! The average number of items in each bucket is exactly equal to the number of items divided by the number of buckets. i.e. a constant factor.

Different operations on hash tables have different algorithmic complexity.

Please look up in Knuth's TAOCP volume 3 for a copmlete discussion of of hash tables.

Also, remember that big-O notation is the asymptotic worst case, not the normal use case. Quicksort is the best example of this problem. Quicksort is O(N^2), even though the average complexity is roughly n log n. Saying that quicksort is O(n log n) is incorrect, according to Knuth who came up with the notation (See Knuth's discussion on Big Omicron, Big Omega and Big Theta).

Since we don't have unbounded memory we can skip a bunch of Knuth's 'ideal' hash table issues.

Given a grow-able hash table like most people use today:

Storing an entry has either constant or linear time, depending on if the table must grow, becoming linear in the asymptotic case. Adding to a hash table is O(N).

Both retrieving and searching for an entry are an algorithmic complexity of O(n log n) as the asymptotic case. An ideal infinitely sized table has constant complexity (O(1)), but we don't live in that world. The average complexity is implementation dependant and varies based on the clustering of hash keys.

Quote:

Original post by iMalcFor example if you're doing duplicate detection, most people would first think of comparing every item to every other item right? However you can simply hash every item and then only compare those with an identical hash. Basically that takes an O(n*n) algorithm and turns it into an O(n) algorithm.

Duplicate detection is a well-studied and ongoing research problem. It has many other names, including data cleaning, data scrubbing, instance identification, record matching, and so on.

This type of all-to-all record search has at best a complexity of (m) * N^2, where (m) is the complexity of the comparison and N is the number of data elements. There are statistical methods that can be used to prune the records in N to dramatically smaller sizes, including using record hashes to cluster the data.

The method you propose is one of those pruning techniques, not the actual record search. It works well on small data sets where a complete hash table will fit nicely into memory. Unfortunately, it fails miserably on any significantly sized data set.

If you do come up with some way to convert all-to-all data cleaning into an O(N) algorithm, I look forward to reading it.

frob.

The best known way to optimize this kind of loops, is loop unrolling. Look here: http://www.codemaestro.com/reviews/review00000102.html

Quote:

Original post by frob Okay, we are totally away from the OP comment. He has already decided to go with a spatial solution to his distance-sorting problem. Just for your own notes, I left the game industry several years ago to persue less stressful and more lucrative work. I have been working with (including performing corporate research on) large data sets (GB to TB range) since 1999. I stick around here because I like to comment on algorithmic topics. In other words, I know this subject. I'm not like so many of the 15-year-old game programmer wannabe kids we get on this site. On to the technical debate. [grin] Quote: Original post by iMalc The whole operation has absolutely nothing to do with the log of the number of items. That's utter nonsense. There's just nothing log(n) about it! The average number of items in each bucket is exactly equal to the number of items divided by the number of buckets. i.e. a constant factor. Different operations on hash tables have different algorithmic complexity. Please look up in Knuth's TAOCP volume 3 for a copmlete discussion of of hash tables. Also, remember that big-O notation is the asymptotic worst case, not the normal use case. Quicksort is the best example of this problem. Quicksort is O(N^2), even though the average complexity is roughly n log n. Saying that quicksort is O(n log n) is incorrect, according to Knuth who came up with the notation (See Knuth's discussion on Big Omicron, Big Omega and Big Theta). Since we don't have unbounded memory we can skip a bunch of Knuth's 'ideal' hash table issues. Given a grow-able hash table like most people use today: Storing an entry has either constant or linear time, depending on if the table must grow, becoming linear in the asymptotic case. Adding to a hash table is O(N). Both retrieving and searching for an entry are an algorithmic complexity of O(n log n) as the asymptotic case. An ideal infinitely sized table has constant complexity (O(1)), but we don't live in that world. The average complexity is implementation dependant and varies based on the clustering of hash keys. Quote: Original post by iMalcFor example if you're doing duplicate detection, most people would first think of comparing every item to every other item right? However you can simply hash every item and then only compare those with an identical hash. Basically that takes an O(n*n) algorithm and turns it into an O(n) algorithm. Duplicate detection is a well-studied and ongoing research problem. It has many other names, including data cleaning, data scrubbing, instance identification, record matching, and so on. This type of all-to-all record search has at best a complexity of (m) * N^2, where (m) is the complexity of the comparison and N is the number of data elements. There are statistical methods that can be used to prune the records in N to dramatically smaller sizes, including using record hashes to cluster the data. The method you propose is one of those pruning techniques, not the actual record search. It works well on small data sets where a complete hash table will fit nicely into memory. Unfortunately, it fails miserably on any significantly sized data set. If you do come up with some way to convert all-to-all data cleaning into an O(N) algorithm, I look forward to reading it. frob.

Very sorry for being slightly off topic but...

Adding to a hash table has amortized O(1) i.e. constant time! Proper implementations double in size when they grow, meaning that as the work required to grow the table increases, the frequency of the growing decreases accordingly, meaning that on average the amount of work is about the same. This is what amortized complexity means.
One beauty of using hashing for duplicate detection though, is that you know in advance the table size require, thus no growing is required.

That's absolute bollucks about the hashing failing on a significantly sized data set. I've optimised a duplicate detection algorithm from the obvious n*n approach to using hashing and it went from over 20 minutes on a fast PC, to 7 seconds on a P90. This was with about 6000 items. For any set larger than that you're basically saying the hashing wont help? WTF! The truth is that if the data sets a lot larger than that (i.e. significantly sized) such that a hash table wont fit into PC memory, then it would take weeks, months, years, or decades using the obvious n*n algorithm.

You can simply read about hashing yourself if you want to understand how it is proportional to n, the number of items. Here's some interesting reading on it. I suggest you don't post again until you've read it.
Be prepared to actually learn something instead of spouting propaganda.

Quote:

Also, remember that big-O notation is the asymptotic worst case, not the normal use case. Quicksort is the best example of this problem. Quicksort is O(N^2), even though the average complexity is roughly n log n. Saying that quicksort is O(n log n) is incorrect, according to Knuth who came up with the notation (See Knuth's discussion on Big Omicron, Big Omega and Big Theta).

Gargh, this is totally wrong. "big-O" is one of the Landau Symbols, which are simply a notation saying something about a function; this function can describe complexity of an algorithm in best case, worst case or average case; or space requirements etc. They predate Knuth by decades.
And yes indeed, expected complexity of (randomized pivot) quicksort is bounded by O(n*logn). Proof: moderately simple recurrence relation.

Quote:

Storing an entry has either constant or linear time, depending on if the table must grow, becoming linear in the asymptotic case. Adding to a hash table is O(N).

Wrong. To expand on iMalc's statement, growing the table takes O(n) time, but only needs to happen after n steps; adding therefore has amortized complexity O(n / n) = O(1).

Now not everyone sat through CS class or still remembers it, but prefixing a post containing such glaring errors with "I am teh master, look up to me!!1" just makes you look pompous and/or foolish.

Quote:

The best known way to optimize this kind of loops, is loop unrolling. Look here: http://www.codemaestro.com/reviews/review00000102.html

This was invented in 1983 and was relevant for many years, but loop unrolling can nowadays even hurt performance. 7th generation CPUs can branch with zero overhead; manual unrolling tends to increase register pressure and require spilling to memory (coder has a limited amount of architectural regs at his disposal, but CPU can just rename physical registers during each iteration); you don't want to fill the precious P4 trace cache with unrolled crap.
Recommendation: do not worry about loop overhead.

Okay, I've realised the fact that your mention of a log(n) factor may be in reference to the fact that items are often not distributed very evenly amoung the buckets. In a totally random distribution, the largest bucket size may be somehow related to log(n). Is this somewhat like your explanation? Factors such as a low load factor can make this less likely, with typically 1 or 2 items per bucket, and very rarely more than 3.

Also, if a bucket contained enough items (say 20), then a rehash into a new table with just those items could furthur reduce the effort required to process the bucket, though in practicality this is not worth it.

It's also true that if there are duplicates then the number of items per bucket will be much larger, though processing them should be quick if they are equal. However I'm mostly concerned with the worst case where there is at most 1 duplicate pair.

I appologise for my harshness earlier.

OP: SRL has a binary search function in the algorithm header I believe, you might be best to use that.