Closest-pair problem/Objective-C: Difference between revisions
Content added Content deleted
(moved from Closest pair problem) |
m (Fixed syntax highlighting.) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 4: | Line 4: | ||
{{works with|Cocoa}} |
{{works with|Cocoa}} |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
#import <math.h> |
#import <math.h> |
||
Line 10: | Line 10: | ||
double xCoord, yCoord; |
double xCoord, yCoord; |
||
} |
} |
||
+ ( |
+ (instancetype)x: (double)x y: (double)y; |
||
- ( |
- (instancetype)initWithX: (double)x andY: (double)y; |
||
- (double)x; |
- (double)x; |
||
- (double)y; |
- (double)y; |
||
Line 21: | Line 21: | ||
@implementation Point |
@implementation Point |
||
+ ( |
+ (instancetype)x: (double)x y: (double)y { |
||
return |
return [[self alloc] initWithX: x andY: y]; |
||
} |
} |
||
- ( |
- (instancetype)initWithX: (double)x andY: (double)y { |
||
if ( |
if ((self = [super init])) { |
||
xCoord = x; |
|||
yCoord = y; |
|||
} |
|||
yCoord = y; |
|||
return self; |
return self; |
||
} |
} |
||
Line 52: | Line 51: | ||
else return NSOrderedSame; |
else return NSOrderedSame; |
||
} |
} |
||
@end</ |
@end</syntaxhighlight> |
||
< |
<syntaxhighlight lang="objc">@interface ClosestPair : NSObject |
||
+ (NSArray *)closestPairSimple: (NSArray *)pts; |
+ (NSArray *)closestPairSimple: (NSArray *)pts; |
||
+ (NSArray *)closestPair: (NSArray *)pts; |
+ (NSArray *)closestPair: (NSArray *)pts; |
||
Line 64: | Line 63: | ||
+ (NSArray *)closestPairSimple: (NSArray *)pts { |
+ (NSArray *)closestPairSimple: (NSArray *)pts { |
||
if ( [pts count] < 2 ) return @[ @HUGE_VAL ]; |
|||
⚫ | |||
double c = [ pts[0] dist: pts[1] ]; |
|||
if ( [pts count] < 2 ) return [NSArray arrayWithObject: [NSNumber numberWithDouble: HUGE_VAL]]; |
|||
NSArray *r; |
NSArray *r = @[ @(c), pts[0], pts[1] ]; |
||
for(int i=0; i < ([pts count] - 1); i++) { |
|||
⚫ | |||
r = [NSArray |
|||
double t = [ pts[i] dist: pts[j] ]; |
|||
arrayWithObjects: [NSNumber numberWithDouble: c], |
|||
[pts objectAtIndex: 0], |
|||
[pts objectAtIndex: 1], nil]; |
|||
for(i=0; i < ([pts count] - 1); i++) { |
|||
⚫ | |||
double t; |
|||
t = [[pts objectAtIndex: i] dist: [pts objectAtIndex: j]]; |
|||
if ( t < c ) { |
if ( t < c ) { |
||
c = t; |
c = t; |
||
r = [ |
r = @[ @(t), pts[i], pts[j] ]; |
||
arrayWithObjects: [NSNumber numberWithDouble: t], |
|||
[pts objectAtIndex: i], |
|||
[pts objectAtIndex: j], nil]; |
|||
} |
} |
||
} |
} |
||
Line 95: | Line 85: | ||
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP { |
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP { |
||
⚫ | |||
NSArray *pR, *pL, *minR, *minL; |
|||
NSMutableArray *yR, *yL, *joiningStrip, *tDist, *minDist; |
|||
double middleVLine; |
|||
int i, nP, k; |
|||
if ( [xP count] <= 3 ) { |
if ( [xP count] <= 3 ) { |
||
Line 104: | Line 91: | ||
} else { |
} else { |
||
int midx = ceil([xP count]/2.0); |
int midx = ceil([xP count]/2.0); |
||
pL = [xP subarrayWithRange: NSMakeRange(0, midx)]; |
NSArray *pL = [xP subarrayWithRange: NSMakeRange(0, midx)]; |
||
pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)]; |
NSArray *pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)]; |
||
yL = [[NSMutableArray alloc] init]; |
NSMutableArray *yL = [[NSMutableArray alloc] init]; |
||
yR = [[NSMutableArray alloc] init]; |
NSMutableArray *yR = [[NSMutableArray alloc] init]; |
||
middleVLine = [[ |
double middleVLine = [pL[midx-1] x]; |
||
for(i=0; i < [yP count]; i++) { |
for(int i=0; i < [yP count]; i++) { |
||
if ( |
if ( [yP[i] x] <= middleVLine ) { |
||
[yL addObject: |
[yL addObject: yP[i]]; |
||
} else { |
} else { |
||
[yR addObject: |
[yR addObject: yP[i]]; |
||
} |
} |
||
} |
} |
||
minR = [ClosestPair closestPairPriv: pR and: yR]; |
NSArray *minR = [ClosestPair closestPairPriv: pR and: yR]; |
||
minL = [ClosestPair closestPairPriv: pL and: yL]; |
NSArray *minL = [ClosestPair closestPairPriv: pL and: yL]; |
||
minDist = [ClosestPair minBetween: minR and: minL]; |
NSMutableArray *minDist = [ClosestPair minBetween: minR and: minL]; |
||
joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]]; |
NSMutableArray *joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]]; |
||
for(i=0; i < [yP count]; i++) { |
for(int i=0; i < [yP count]; i++) { |
||
if ( fabs( |
if ( fabs([yP[i] x] - middleVLine) < |
||
[minDist[0] doubleValue] ) { |
|||
[joiningStrip addObject: |
[joiningStrip addObject: yP[i]]; |
||
} |
} |
||
} |
} |
||
tDist = minDist; |
NSMutableArray *tDist = minDist; |
||
nP = [joiningStrip count]; |
int nP = [joiningStrip count]; |
||
for(i=0; i < (nP - 1); i++) { |
for(int i=0; i < (nP - 1); i++) { |
||
k = i + 1; |
int k = i + 1; |
||
while( (k < nP) && |
while( (k < nP) && |
||
( ( |
( ([joiningStrip[k] y] - [joiningStrip[i] y]) < [minDist[0] doubleValue] ) ) { |
||
double d = [joiningStrip[i] dist: joiningStrip[k]]; |
|||
[[joiningStrip objectAtIndex: i] y]) < [[minDist objectAtIndex: 0] doubleValue] ) ) { |
|||
⚫ | |||
double d = [[joiningStrip objectAtIndex: i] dist: [joiningStrip objectAtIndex: k]]; |
|||
tDist = @[ @(d), joiningStrip[i], joiningStrip[k] ]; |
|||
tDist = [NSArray arrayWithObjects: [NSNumber numberWithDouble: d], |
|||
[joiningStrip objectAtIndex: i], |
|||
[joiningStrip objectAtIndex: k], nil]; |
|||
} |
} |
||
k++; |
k++; |
||
} |
} |
||
} |
} |
||
[yL release]; [yR release]; |
|||
return tDist; |
return tDist; |
||
} |
} |
||
Line 148: | Line 131: | ||
+ (id)minBetween: (id)minA and: (id)minB { |
+ (id)minBetween: (id)minA and: (id)minB { |
||
if ( |
if ( [minA[0] doubleValue] < [minB[0] doubleValue] ) { |
||
⚫ | |||
return minA; |
return minA; |
||
} else { |
} else { |
||
Line 156: | Line 138: | ||
} |
} |
||
@end</ |
@end</syntaxhighlight> |
||
'''Testing''' |
'''Testing''' |
||
< |
<syntaxhighlight lang="objc">#define NP 10000 |
||
int main() |
int main() |
||
{ |
{ |
||
@autoreleasepool { |
|||
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; |
|||
NSMutableArray *p = [[NSMutableArray alloc] init]; |
NSMutableArray *p = [[NSMutableArray alloc] init]; |
||
srand(0); |
srand(0); |
||
for(int i = 0; i < NP; i++) { |
for(int i = 0; i < NP; i++) { |
||
[p addObject: |
[p addObject: |
||
[Point x: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0 |
[Point x: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0 |
||
y: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0] |
y: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0] |
||
]; |
]; |
||
} |
} |
||
//NSArray *r1 = [ClosestPair closestPairSimple: p]; |
//NSArray *r1 = [ClosestPair closestPairSimple: p]; |
||
NSArray *r2 = [ClosestPair closestPair: p]; |
NSArray *r2 = [ClosestPair closestPair: p]; |
||
//NSLog(@"%lf", |
//NSLog(@"%lf", [r1[0] doubleValue]); |
||
NSLog(@"%lf", |
NSLog(@"%lf", [r2[0] doubleValue]); |
||
} |
|||
[p release]; |
|||
[pool drain]; |
|||
return EXIT_SUCCESS; |
return EXIT_SUCCESS; |
||
}</ |
}</syntaxhighlight> |
||
Timing (with the <tt>time</tt> command): |
Timing (with the <tt>time</tt> command): |
Latest revision as of 13:57, 1 September 2022
Closest-pair problem/Objective-C is part of Closest pair problem. You may find other members of Closest pair problem at Category:Closest pair problem.
#import <Foundation/Foundation.h>
#import <math.h>
@interface Point : NSObject {
double xCoord, yCoord;
}
+ (instancetype)x: (double)x y: (double)y;
- (instancetype)initWithX: (double)x andY: (double)y;
- (double)x;
- (double)y;
- (double)dist: (Point *)pt;
- (NSComparisonResult)compareX: (Point *)pt;
- (NSComparisonResult)compareY: (Point *)pt;
@end
@implementation Point
+ (instancetype)x: (double)x y: (double)y {
return [[self alloc] initWithX: x andY: y];
}
- (instancetype)initWithX: (double)x andY: (double)y {
if ((self = [super init])) {
xCoord = x;
yCoord = y;
}
return self;
}
- (double)x { return xCoord; }
- (double)y { return yCoord; }
- (double)dist: (Point *)pt {
return hypot([self x] - [pt x], [self y] - [pt y]);
}
- (NSComparisonResult)compareX: (Point *)pt {
if ( [self x] < [pt x] ) return NSOrderedAscending;
else if ( [self x] > [pt x] ) return NSOrderedDescending;
else return NSOrderedSame;
}
- (NSComparisonResult)compareY: (Point *)pt {
if ( [self y] < [pt y] ) return NSOrderedAscending;
else if ( [self y] > [pt y] ) return NSOrderedDescending;
else return NSOrderedSame;
}
@end
@interface ClosestPair : NSObject
+ (NSArray *)closestPairSimple: (NSArray *)pts;
+ (NSArray *)closestPair: (NSArray *)pts;
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP;
+ (id)minBetween: (id)minA and: (id)minB;
@end
@implementation ClosestPair
+ (NSArray *)closestPairSimple: (NSArray *)pts {
if ( [pts count] < 2 ) return @[ @HUGE_VAL ];
double c = [ pts[0] dist: pts[1] ];
NSArray *r = @[ @(c), pts[0], pts[1] ];
for(int i=0; i < ([pts count] - 1); i++) {
for(int j=i+1; j < [pts count]; j++) {
double t = [ pts[i] dist: pts[j] ];
if ( t < c ) {
c = t;
r = @[ @(t), pts[i], pts[j] ];
}
}
}
return r;
}
+ (NSArray *)closestPair: (NSArray *)pts {
return [self closestPairPriv: [pts sortedArrayUsingSelector: @selector(compareX:)]
and: [pts sortedArrayUsingSelector: @selector(compareY:)]
];
}
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP {
int nP, k;
if ( [xP count] <= 3 ) {
return [self closestPairSimple: xP];
} else {
int midx = ceil([xP count]/2.0);
NSArray *pL = [xP subarrayWithRange: NSMakeRange(0, midx)];
NSArray *pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)];
NSMutableArray *yL = [[NSMutableArray alloc] init];
NSMutableArray *yR = [[NSMutableArray alloc] init];
double middleVLine = [pL[midx-1] x];
for(int i=0; i < [yP count]; i++) {
if ( [yP[i] x] <= middleVLine ) {
[yL addObject: yP[i]];
} else {
[yR addObject: yP[i]];
}
}
NSArray *minR = [ClosestPair closestPairPriv: pR and: yR];
NSArray *minL = [ClosestPair closestPairPriv: pL and: yL];
NSMutableArray *minDist = [ClosestPair minBetween: minR and: minL];
NSMutableArray *joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]];
for(int i=0; i < [yP count]; i++) {
if ( fabs([yP[i] x] - middleVLine) <
[minDist[0] doubleValue] ) {
[joiningStrip addObject: yP[i]];
}
}
NSMutableArray *tDist = minDist;
int nP = [joiningStrip count];
for(int i=0; i < (nP - 1); i++) {
int k = i + 1;
while( (k < nP) &&
( ([joiningStrip[k] y] - [joiningStrip[i] y]) < [minDist[0] doubleValue] ) ) {
double d = [joiningStrip[i] dist: joiningStrip[k]];
if ( d < [tDist[0] doubleValue] ) {
tDist = @[ @(d), joiningStrip[i], joiningStrip[k] ];
}
k++;
}
}
return tDist;
}
}
+ (id)minBetween: (id)minA and: (id)minB {
if ( [minA[0] doubleValue] < [minB[0] doubleValue] ) {
return minA;
} else {
return minB;
}
}
@end
Testing
#define NP 10000
int main()
{
@autoreleasepool {
NSMutableArray *p = [[NSMutableArray alloc] init];
srand(0);
for(int i = 0; i < NP; i++) {
[p addObject:
[Point x: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0
y: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0]
];
}
//NSArray *r1 = [ClosestPair closestPairSimple: p];
NSArray *r2 = [ClosestPair closestPair: p];
//NSLog(@"%lf", [r1[0] doubleValue]);
NSLog(@"%lf", [r2[0] doubleValue]);
}
return EXIT_SUCCESS;
}
Timing (with the time command):
d&c: 0.22user 0.00system 0:00.41elapsed brute force: 13.53user 0.06system 0:13.87elapsed