在C / Objective-C中使用Python的bisect

我希望将这个用Python编写的类https://stackoverflow.com/a/4113400/12920移植到Objective-C或C中。

它使用了一种名为bisect.bisect_right东西。 我对Python没有太多经验，那么如何在C / obj-c中实现呢？

Answer 1

这是我提出的课程。 我只测试了一百万次，它给出了预期的结果。 我猜不完全是二进制搜索，但它完成了这项工作。 不需要外部库。

头文件：

 // // Mjweightedtuple2.h // orixnknk // // Created by Jonny Bergström on 3/7/14. // Copyright (c) 2014 Jonny Bergstrom. All rights reserved. // #import  @interface Mjweightedtuple2 : NSObject -(id)initWithItems:(NSDictionary*)items; -(id)randomValue; @end 

实施文件：

 // // 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 

这是我测试的方式：

 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); } 

结果：

香蕉：333560 = 33.4％苹果：333540 = 33.4％梨：332900 = 33.3％

然后我更喜欢90％的香蕉...

 NSDictionary* items = @{ @"pear": [NSNumber numberWithInteger:5000], @"banana": [NSNumber numberWithInteger:90000], @"apple": [NSNumber numberWithInteger:5000], }; 

香蕉：899258 = 89.9％苹果：50362 = 5.0％梨：50380 = 5.0％