x404.co.uk - View topic - Recursive methods and concurrency

View unanswered posts | View active topics It is currently Tue Jun 10, 2025 1:53 pm

Recursive methods and concurrency

Moderators: saspro, HeatherKay, timark_uk, Blue_Nowhere, l3v1ck

Page 1 of 1

[ 3 posts ]

Print view

Previous topic | Next topic

Recursive methods and concurrency

Author

Message

forquare1

I haven't seen my friends in so long

Joined: Thu Apr 23, 2009 6:36 pm
Posts: 5150
Location: /dev/tty0

Recursive methods and concurrency

Evening all,

Using Obj-C, I'm working out all the permutations of 0 and 1 for a given number of elements in an array. For example, if you had an array length of 4, the permutations would be:


	Code: 2012-08-19 01:26:46.528 Permutation Creator[9822:303] 0000 2012-08-19 01:26:46.530 Permutation Creator[9822:303] 0001 2012-08-19 01:26:46.530 Permutation Creator[9822:303] 0010 2012-08-19 01:26:46.530 Permutation Creator[9822:303] 0011 2012-08-19 01:26:46.531 Permutation Creator[9822:303] 0100 2012-08-19 01:26:46.531 Permutation Creator[9822:303] 0101 2012-08-19 01:26:46.532 Permutation Creator[9822:303] 0110 2012-08-19 01:26:46.532 Permutation Creator[9822:303] 0111 2012-08-19 01:26:46.532 Permutation Creator[9822:303] 1000 2012-08-19 01:26:46.533 Permutation Creator[9822:303] 1001 2012-08-19 01:26:46.533 Permutation Creator[9822:303] 1010 2012-08-19 01:26:46.533 Permutation Creator[9822:303] 1011 2012-08-19 01:26:46.534 Permutation Creator[9822:303] 1100 2012-08-19 01:26:46.534 Permutation Creator[9822:303] 1101 2012-08-19 01:26:46.534 Permutation Creator[9822:303] 1110 2012-08-19 01:26:46.535 Permutation Creator[9822:303] 1111

Now, I'm trying to do the same with an array with the size 49152, and it's going to take a while...I've got four cores in this iMac, so why not use them?
It's been ages since I've done anything about concurrency, and it was only really touched on in Java with regards to GUI programming.

The methods I'm using looks something like this:


	Code: #define FALSE 0 #define TRUE 1 #define ARRAY_SIZE 49152 #define LAST_ARRAY_ELEMENT ARRAY_SIZE - 1 @interface PermutationCreator : NSObject{ NSMutableArray *permutations; int position; //Hold position in array int holder; //Hold value to be changed int end_not_reached; } @end @implementation PermutationCreator -(void)calculate{ [self print]; position = LAST_ARRAY_ELEMENT; [self addOne]; if(end_not_reached){ [self calculate]; }else{ [self print]; } } -(void)addOne{ holder = [[permutations objectAtIndex:position] intValue]; //Test if the end has been reached if((position == 0) && (holder == 1)){ end_not_reached = FALSE; return; } //If holder == 0, change to 1 and leave the rest as is if(holder == 0){ holder = 1; [permutations replaceObjectAtIndex:position withObject:[NSNumber numberWithInt:holder]]; return; } //If holder == 1, change to 0 and rerun this method if(holder == 1){ holder = 0; [permutations replaceObjectAtIndex:position withObject:[NSNumber numberWithInt:holder]]; position--; [self addOne]; } } @end

So, two questions:
1) Is this type of work possible to do concurrently?
2) How might a concurrent way look? I'm presumably going to be doing some blocks/GCD stuff...

Many thanks,
Ben

Sun Aug 19, 2012 12:55 am

Fogmeister

I haven't seen my friends in so long

Joined: Thu Apr 23, 2009 7:35 pm
Posts: 6580
Location: Getting there

Recursive methods and concurrency

The first thing I would ask is what is the underlying problem you are trying to solve.

With recursive functions of that size you might find you run into problems of memory overflow.

There could possibly be another way around the problem.

If not I'll try to find the WWDC that explains what you need.

_________________
Oliver Foggin - iPhone Dev


	JJW009 wrote: The count will go up until they stop counting. That's the way counting works.

Doodle Sub!
Game Of Life

Sun Aug 19, 2012 7:52 am

forquare1

I haven't seen my friends in so long

Joined: Thu Apr 23, 2009 6:36 pm
Posts: 5150
Location: /dev/tty0

Re: Recursive methods and concurrency

I'm just sort of fiddling around with permutations. Thought it could be fun programming idea, then perhaps choose a random permutation and colour in the pixels, with 0 being one colour, and 1 being a different colour. 49152 is the amount of pixels in an image sized 256x192.
So there would be two separate programs, the second is only sort of a thought.

Recursion seemed a fun way to do it, but without thinking too much, a two loops, one inside the other, in calculate() would probably do a good job.

Thanks for taking a look though

Sun Aug 19, 2012 11:45 am

Page 1 of 1

[ 3 posts ]

Who is online

Users browsing this forum: No registered users and 14 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum