I have not been able to spend much time programming since ages, but I thought I would be sad not to put my new mac pro and xcode 3 to some use... (Automatic completion is a pleasure to use, and looks much easier than xcode 2 for what I can remember, but I do not intend to use garbage collection before I understand proper memory management...)
As far as cocoa goes, I certainly do qualify as a newbie, although I did my homework (I spent some time with the Hillegass book, and browsing documentation on the web...)
(But I did previously some Assembly, Pascal, C++)
I tackled a small exercice to get a little more accustomed to cocoa memory management, as well as NSSet, NSArray classes. The problem is to write a little procedure taking one NSSet as an argument, and return the set of all subsets of this argument. (Exemple : the subsets of {a,b} are {},{a},{b} and {a,b}...)
First algorithm is a recursive one : you remove one element in E, you <<calculate>> the subsets of that new set, then the result is obtained by duplicating each subset adding, or not, the element you first substracted.
After many trials, I came to this procedure :
It works, but the performance is ridiculously poor. Granted : the design of this procedure using NSMutableSet is quite bad, as each time you add an object to a NSMutableSet, it has to be checked against every other one.
Still, I was very surprised when I saw that the time needed to obtain the subsets of a 16 elements set (65536 of them of course, which should not frighten my macpro) was over 2 minutes !
The same exercise done with Maple V with the same algorithm takes, on the same computer less than half a sec...
Here is the relevant maple procedure :
Note that the Maple code I quoted is interpreted so the former Objective-C code I pasted should have a big advantage (although certainly not concision!), and it looks to me the work being done behind the scenes by Maple is the same than what is being done with the objective-c code I pasted before.
In my experience, Maple is quite slow, so the results of these tests were a huge surprise.
Do you see an obvious misstake in the code I pasted that could explain how slow it runs ? (Except in the algorithm itself of course...)
Note that to minimize the effects of NSMutableSet addObject checkings, I tried another procedure :
and this second procedure, this is no surprise, is much faster...
Any comment is welcome,
phjo
As far as cocoa goes, I certainly do qualify as a newbie, although I did my homework (I spent some time with the Hillegass book, and browsing documentation on the web...)
(But I did previously some Assembly, Pascal, C++)
I tackled a small exercice to get a little more accustomed to cocoa memory management, as well as NSSet, NSArray classes. The problem is to write a little procedure taking one NSSet as an argument, and return the set of all subsets of this argument. (Exemple : the subsets of {a,b} are {},{a},{b} and {a,b}...)
First algorithm is a recursive one : you remove one element in E, you <<calculate>> the subsets of that new set, then the result is obtained by duplicating each subset adding, or not, the element you first substracted.
After many trials, I came to this procedure :
Code:
NSMutableSet * subsets(NSSet * set)
{
id element;
if (element = [set anyObject])
{
NSMutableSet * setMinusOneElement = [[NSMutableSet alloc] initWithSet: set];
[setMinusOneElement removeObject:element];
NSMutableSet * subsetsOfSetMinusOneElement = [subsets(setMinusOneElement) retain];
NSMutableSet * output = [[[NSMutableSet alloc] initWithSet:subsetsOfSetMinusOneElement] autorelease];
NSEnumerator * enumerateSet = [subsetsOfSetMinusOneElement objectEnumerator];
id setObject;
while (setObject = [enumerateSet nextObject])
{
NSMutableSet * newSubset = [[NSMutableSet alloc] initWithSet:setObject];
[newSubset addObject:element];
[output addObject:newSubset];
[newSubset release];
}
[subsetsOfSetMinusOneElement release];
[setMinusOneElement release];
return output;
}
else
{
NSMutableSet * output = [[[NSMutableSet alloc] init] autorelease];
[output addObject: [[NSMutableSet alloc] init]];// The subsets set of the empty set is { {} }
return output;
}
}It works, but the performance is ridiculously poor. Granted : the design of this procedure using NSMutableSet is quite bad, as each time you add an object to a NSMutableSet, it has to be checked against every other one.
Still, I was very surprised when I saw that the time needed to obtain the subsets of a 16 elements set (65536 of them of course, which should not frighten my macpro) was over 2 minutes !
The same exercise done with Maple V with the same algorithm takes, on the same computer less than half a sec...
Here is the relevant maple procedure :
Code:
subsets:=proc(S :: set) local i,ret;
if nops(S)=0 then return({ {} }); fi;
ret:=subsets(S minus {op(1,S)});
{seq(op(i,ret),i=1..nops(ret)),seq(op(i,ret) union {op(1,S)},i=1..nops(ret))};
end;Note that the Maple code I quoted is interpreted so the former Objective-C code I pasted should have a big advantage (although certainly not concision!), and it looks to me the work being done behind the scenes by Maple is the same than what is being done with the objective-c code I pasted before.
In my experience, Maple is quite slow, so the results of these tests were a huge surprise.
Do you see an obvious misstake in the code I pasted that could explain how slow it runs ? (Except in the algorithm itself of course...)
Note that to minimize the effects of NSMutableSet addObject checkings, I tried another procedure :
Code:
NSMutableArray * nonRecursiveSubsets(NSSet * set)
{
int n = 1 << [set count];
NSMutableArray * output = [[[NSMutableArray alloc] init] autorelease];
int i;
for (i=0; i<n; i++)
{
NSEnumerator * enumerateSet = [set objectEnumerator];
NSMutableSet * newSubset = [[NSMutableSet alloc] init];
id element;
int j=i;
while (j) {
element = [enumerateSet nextObject];
if (j & 1) {
[newSubset addObject:element];
}
j >>= 1;
}
[output addObject:newSubset];
[newSubset release];
}
return(output);
}and this second procedure, this is no surprise, is much faster...
Any comment is welcome,
phjo
