Skip to content Skip to sidebar Skip to footer

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"