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

Question

我正在寻找移植用 Python 编写的此类 https://stackoverflow.com/a/4113400/129202进入 Objective-C，或 C。

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

Answer 1

这是我想出的类(class)。我刚刚测试了它一百万次，它给出了预期的结果。我猜这不完全是二分搜索，但它确实可以完成工作。不需要外部库。

头文件:

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

实现文件:

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

结果:

banana: 333560 = 33.4% apple: 333540 = 33.4% pear: 332900 = 33.3%

那么90%的时候我更喜欢香蕉......

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%