Use Python's Bisect In C/objective-c
I'm looking to port this class written in Python https://stackoverflow.com/a/4113400/129202 into Objective-C, or C. It uses something called bisect.bisect_right. I'm not terribly e
Solution 1:
This is the class I came up with. I just tested it one million times and it gives expected results. Not exactly binary search I guess but it does the job. No outside libraries needed.
The header file:
//// Mjweightedtuple2.h// orixnknk//// Created by Jonny Bergström on 3/7/14.// Copyright (c) 2014 Jonny Bergstrom. All rights reserved.//#import <Foundation/Foundation.h>@interfaceMjweightedtuple2 : NSObject
-(id)initWithItems:(NSDictionary*)items;
-(id)randomValue;
@end
The implementation file:
//// Mjweightedtuple2.m// orixnknk//// Created by Jonny Bergström on 3/7/14.// Copyright (c) 2014 Jonny Bergstrom. All rights reserved.//#import "Mjweightedtuple2.h"@interfaceValueandlength : NSObject@property (nonatomic, retain) id value;
@propertyNSInteger high;
@end@implementationValueandlength@synthesize value; // retain
-(void)dealloc {
self.value = nil;
[super dealloc];
}
@end@interfaceMjweightedtuple2 ()@property (nonatomic, retain) NSArray* thearray;
@propertyNSInteger length;
@end@implementationMjweightedtuple2@synthesize thearray;
@synthesize length; // assign
-(void)dealloc {
self.thearray = nil;
[super dealloc];
}
-(id)initWithItems:(NSDictionary*)items {
self = [super init];
if (self) {
// NSDictionary items = @{// @"pear": [NSNumber numberWithInteger:1],// @"banana": [NSNumber numberWithInteger:100],// @"apple": [NSNumber numberWithInteger:15],// };NSMutableArray* temparray = [NSMutableArray array];
//NSMutableSet* tempset = [NSMutableSet set];NSInteger maxval = 0;
Valueandlength* val;
NSNumber* numberValue;
for (NSString* key in items.allKeys) {
numberValue = items[key];
constNSInteger VALUE = [numberValue integerValue];
maxval += VALUE;
val = [[Valueandlength alloc] init];
val.value = key;
val.high = maxval;
[temparray addObject:val];
[val release];
}
self.thearray = [NSArray arrayWithArray:temparray];
self.length = maxval;
}
returnself;
}
-(id)randomValue {
constNSInteger INDEXTOLOOKFOR = arc4random_uniform(self.length);
for (Valueandlength* val inself.thearray) {
if (INDEXTOLOOKFOR < val.high)
return val.value;
}
returnnil;
}
@end
This is how I tested:
NSDictionary* items = @{
@"pear": [NSNumber numberWithInteger:1],
@"banana": [NSNumber numberWithInteger:1],
@"apple": [NSNumber numberWithInteger:1],
};
Mjweightedtuple2* r = [[Mjweightedtuple2 alloc] initWithItems:items];
DLog(@"Mjweightedtuple2 test");
NSMutableDictionary* dicresult = [NSMutableDictionary dictionary];
for (NSString* key in items.allKeys) {
[dicresult setObject:[NSNumber numberWithInteger:0] forKey:key];
}
constNSInteger TIMES = 1000000;
for (NSInteger i = 0; i < TIMES; i++) {
//DLog(@"%d: %@", i + 1, [r randomValue]);NSString* selectedkey = [r randomValue];
NSNumber* number = dicresult[selectedkey];
[dicresult setObject:[NSNumber numberWithInteger:1 + number.integerValue] forKey:selectedkey];
}
constdouble DTIMES = TIMES;
for (NSString* key in dicresult.allKeys) {
constNSInteger FINALCOUNT = [dicresult[key] integerValue];
DLog(@"%@: %d = %.1f%%", key, FINALCOUNT, ((double)FINALCOUNT / DTIMES) * 100.0);
}
Results:
banana: 333560 = 33.4% apple: 333540 = 33.4% pear: 332900 = 33.3%
Then I prefer bananas 90% of the times...
NSDictionary* items = @{
@"pear": [NSNumber numberWithInteger:5000],
@"banana": [NSNumber numberWithInteger:90000],
@"apple": [NSNumber numberWithInteger:5000],
};
banana: 899258 = 89.9% apple: 50362 = 5.0% pear: 50380 = 5.0%
Post a Comment for "Use Python's Bisect In C/objective-c"