Reply to topic  [ 3 posts ] 
Recursive methods and concurrency 
Author Message
I haven't seen my friends in so long
User avatar

Joined: Thu Apr 23, 2009 6:36 pm
Posts: 5150
Location: /dev/tty0
Reply with quote
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
Profile WWW
I haven't seen my friends in so long
User avatar

Joined: Thu Apr 23, 2009 7:35 pm
Posts: 6580
Location: Getting there
Reply with quote
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

Image Image


Sun Aug 19, 2012 7:52 am
Profile WWW
I haven't seen my friends in so long
User avatar

Joined: Thu Apr 23, 2009 6:36 pm
Posts: 5150
Location: /dev/tty0
Reply with quote
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
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.