Sorting CCArray « cocos2d for iPhone

cocos2d for iPhone » Programming » Programming - Everything else

Sorting CCArray

(15 posts) (7 voices)

Started 1 year ago by itlgames
Latest reply from zaaroth

Tags:

Has any one come with a solution to sort the CCArray? So far we can't use the sortUsingSelector, I think, so I had to do my own sorting method:

void merge(CCArray *a, CCArray *b, int lo, int mi, int hi)
{
	int i, i1 = lo, i2 = mi + 1; // sub-array indexes
	for (i = lo; i <= hi; i++) // for each element in destination b
	{
		if (i1 > mi) // if i1 is out of bounds, copy from i2
			[b replaceObjectAtIndex: i withObject: [a objectAtIndex: i2++]];
		else if (i2 > hi) // if i2 is out of bounds, copy from i1
			[b replaceObjectAtIndex: i withObject: [a objectAtIndex: i1++]];
		else if ((int)([[a objectAtIndex: i1] performSelector:compareFunction
			withObject: [a objectAtIndex: i2]])
				 == NSOrderedAscending) // if (a[i1] < a[i2]) copy from i1
			[b replaceObjectAtIndex: i withObject: [a objectAtIndex: i1++]];
		else // if (a[i1] >= a[i2]) copy from i2
			[b replaceObjectAtIndex: i withObject: [a objectAtIndex: i2++]];
	}
	// copy back b into a --> same as [a setArray: b];
	for (i = lo; i <= hi; i++)
		[a replaceObjectAtIndex: i withObject: [b objectAtIndex: i]];
}

void divideAndMerge(CCArray *a, CCArray *b, int lo, int hi)
{
	int mi = (lo + hi) / 2; // calculate middle point
	if (lo >= hi) return; // size is 1 or less --> done
	divideAndMerge(a, b, lo, mi); // sort lower half
	divideAndMerge(a, b, mi+1, hi); // sort upper half
	merge(a, b, lo, mi, hi); // merge back sorted halves
}

void mergeSort(CCArray *array, SEL selector)
{
	compareFunction = selector;

	CCArray *buffer = [array copy]; // helper buffer
	int n = [array count]; // number of items in array
	divideAndMerge(array, buffer, 0, n-1); // sort everything
	[buffer release]; // release the helper buffer
}

To use it, just:

mergeSort(objects, @selector(compare:));

I also had to add one new method to the latest version of CCArray:

- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(id)anObject {
	[self insertObject:anObject atIndex:index];
	[self removeObjectAtIndex: index+1];
}

Problem is, part of my bottleneck performance is on the sorting, so I'm wondering if there is a better way of doing this.

Posted 1 year ago #

riq
Key Master
CCArray internally uses an array, so moving objects inside the array is not a cheap operation.

If possible try to optimize this piece of code:
```
// copy back b into a --> same as [a setArray: b];
for (i = lo; i <= hi; i++)
	[a replaceObjectAtIndex: i withObject: [b objectAtIndex: i]];
```
with a memcpy
Posted 1 year ago #

wasabibit
Member

I got this from somewhere(i don't know now). (I can't get credit since it was not created by me though).

Sorry. This is for NSDictionary, not CCArray you are looking for. You should be able to convert it easily though.

+(NSMutableArray*)bubbleSortDictionaryByKeys:(NSDictionary*)dict
{
	//this method takes an NSDictionary and performs a basic bubblesort
	//on its keys. It then returns those ordered keys as an NSMutableArray.
	//You can then traverse the original NSDictionary and retrive its
	//ordered objects by simply stepping through each key in the NSMutableArray.

	if(!dict)
		return nil;
	NSMutableArray *sortedKeys = [NSMutableArray arrayWithArray: [dict allKeys]];
	if([sortedKeys count] <= 0)
		return nil;
	else if([sortedKeys count] == 1)
		return sortedKeys; //no sort needed

	//perform bubble sort on keys:
	int n = [sortedKeys count] -1;
	int i;
	BOOL swapped = YES;

	NSString *key1,*key2;
	NSComparisonResult result;

	while(swapped)
	{
		swapped = NO;
		for(i=0;i<n;i++)
		{
			key1 = [sortedKeys objectAtIndex: i];
			key2 = [sortedKeys objectAtIndex: i+1];

			//here is where we do our basic NSString comparison
			//This can be easily customized.
			//See the options for -compare: in NSString docs
			result = [key1 compare: key2 options: NSCaseInsensitiveSearch];
			if(result == NSOrderedDescending)
			{
				//we retain for good form, but these
				//objects should still be safely
				//retained by the dictionary:
				[key1 retain];
				[key2 retain];

				//pop the two keys out of the array
				[sortedKeys removeObjectAtIndex: i]; // key1
				[sortedKeys removeObjectAtIndex: i]; // key2
				//replace them
				[sortedKeys insertObject: key1 atIndex: i];
				[sortedKeys insertObject: key2 atIndex: i];

				[key1 release];
				[key2 release];

				swapped = YES;
			}
		}
	}

	return sortedKeys;
}

Posted 1 year ago #

JonKean
Member

have you looked into using the qsort method? It should be as simple as implementing a compare function for your objects.

Posted 1 year ago #
itlgames
Moderator

Thanks guys,

@riq, that sounds like a good idea, will try.

@wasabi, it shouldn't be difficult to adapt to CCArray and a compare function, unfortunately bubble sort is time expensive compared with merge sort or quick sort (thanks @JonKean for the suggestion).

Because I call this ordering every frame to reorder my isometric sprites (bit complicated zordering logic as I support altitudes and map heights), this is part of my bottleneck. To be honest it doesn't affect much when running on a iPhone 3GS or iPhone 4G, or even iPad, but performance drops on iPhone 3G and iPods 1st generation.

Posted 1 year ago #
Eko Mirhard
Member

Sorry to interrupt you guys, but just wanna ask something. Will it be faster to use the usual array (NSMutableArray) when it comes to this case (sorting) compared to using CCArray ? I know that for many cases, CCArray is certainly better, but how about in sorting? :)

Posted 1 year ago #
itlgames
Moderator

Really depends of your particular case, run instruments and see if the bottleneck is that bit of code. But If you need to sort the CCArray you can use the functions I posted, as I believe they are still faster than NSMutableArray/sorting.

Posted 1 year ago #
Eko Mirhard
Member

Yup, i got a little problem in terms of speed when sorting a huge array over and over again. And looks like CCArray is still faster compared to NSMutableArray where sorting is needed. Yes, i think i will stick to CCArray :)

Thanks :)

Posted 1 year ago #
itlgames
Moderator

Then use the merge function I posted here, they work fine to me, but at some point I tried to optimize even better. But anyway I believe it will be faster than NSMutableArray.

Posted 1 year ago #

itlgames
Moderator

Small optimization in case anyone interested, I implemented the insertion sort method, seems a bit faster than merge when the array is not too big:

void insertionSort(CCArray *array, SEL selector)
{
    for (int i=1; i<[array count]; i++ ) {
        int j = i-1;
        BOOL done = NO;
        while (done == NO) {
			if ((int)([[array objectAtIndex: j] performSelector:selector
				 withObject:[array objectAtIndex: j+1]]) == NSOrderedDescending) {
				SWAP(array, j, j+1);

                j = j-1;
                if (j<0) {
                    done = YES;
                }
            } else {
                done = YES;
            }
        }
    }
}

Posted 1 year ago #

manucorporat
Member

hey @itlgames
what's the SWAP() code?

Posted 1 year ago #

manucorporat
Member

I have improved your code:
I haven't tested it, but I think it should work equal that the old code.

void insertionSort(CCArray *array, SEL selector)
{
	ccArray *data = array->data;
    for (int i = 1; i<data->num; i++) {
        int j = i-1;
        while (YES) {
			if ((int)([data->arr[j] performSelector:selector withObject:data->arr[j+1]]) == NSOrderedDescending)
			{
				//SWAP
				id temp = data->arr[j];
				data->arr[j] = data->arr[j+1];
				data->arr[j+1] = temp;

                j = j-1;
                if (j<0)
					break;
            }else
				break;
        }
    }
}

Posted 1 year ago #

itlgames
Moderator

Thanks manu! yeah sorry forgot to add the SWAP:

#define SWAP(arr, x, y) do { \
id oldX = [arr objectAtIndex: (x)]; \
[arr replaceObjectAtIndex: (x) withObject: [arr objectAtIndex: (y)]]; \
[arr replaceObjectAtIndex: (y) withObject: oldX]; \
} while (0)

But your change looks brilliant, I'm sure is faster, going to test now.

I found insertion sorting method works faster than merge when the array is not too big, like 50 items or so, for huge arrays I think merge is faster.

Posted 1 year ago #
itlgames
Moderator

Hi manu, I tested your code an initially crashes, it doesn't say much the error really, can't see anything even with bt, will be trying tonight to see if I can find the problem, but looks promising!

Posted 1 year ago #

zaaroth
Member

Hey @riq, perhaps this would be useful for someone else as well:

#import "CCArray+Additions.h"

@implementation CCArray (Additions)

- (void) sortUsingCFuncComparator:(int(*)(const void *, const void *))compar {
    qsort(data->arr, data->num, sizeof(id), compar);
}

@end

It would be good to embed qsort on CCArray. I have seen the threads regarding sorting and no one suggested this yet.

An example of comparator for nodes:

int bumpLowYToTop(const void *a, const void *b) {
    id iA = ((id *) a)[0];
    id iB = ((id *) b)[0];
    CCNode *nA = (CCNode *)iA;
    CCNode *nB = (CCNode *)iB;

//    ZTLOG(@"A class is %@ and B class is %@", [iA class], [iB class]);

    return (int)nB.position.y - (int)nA.position.y;
}

Sorting CCArray

Reply