Use Python's bisect in C/Objective-C

Question

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 experienced with Python, so how would one implement that in C/obj-c?

It's a [binary search](http://en.wikipedia.org/wiki/Binary_search_algorithm). The documentation is [here](http://docs.python.org/2/library/bisect.html#bisect.bisect_right). You can find or write a C/Objective-C binary search, right? — user2357112, Mar 07 '14 at 06:06
Ok I think I get how that works. It looks like a wheel and someone somewhere probably already invented that... — Jonny, Mar 07 '14 at 06:09
`NSSet` could pull this off maybe... http://stackoverflow.com/a/18140167/129202 — Jonny, Mar 07 '14 at 06:14

Jonny · Accepted Answer · 2014-03-07T07:06:51.533

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>

@interface Mjweightedtuple2 : 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"

@interface Valueandlength : NSObject
@property (nonatomic, retain) id value;
@property NSInteger high;
@end
@implementation Valueandlength
@synthesize value; // retain
-(void)dealloc {
    self.value = nil;
    [super dealloc];
}
@end

@interface Mjweightedtuple2 ()
@property (nonatomic, retain) NSArray* thearray;
@property NSInteger length;
@end

@implementation Mjweightedtuple2
@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];
            const NSInteger 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;
    }
    return self;
}
-(id)randomValue {
    const NSInteger INDEXTOLOOKFOR = arc4random_uniform(self.length);

    for (Valueandlength* val in self.thearray) {
        if (INDEXTOLOOKFOR < val.high)
            return val.value;
    }
    return nil;
}
@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];
}
const NSInteger 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];
}
const double DTIMES = TIMES;
for (NSString* key in dicresult.allKeys) {
    const NSInteger 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%

Use Python's bisect in C/Objective-C

1 Answers1

Linked