Finding the lowest value and corresponding key in a large NSDictionary

Question

I have a NSDictionary with NSString as keys and NSNumber as values such as the following

NSDictionary *dictionary = @{@"Apple" : [NSNumber numberWithInt: 6],
                             @"Banana" : [NSNumber numberWithInt: 1],
                             @"Peach" : [NSNumber numberWithInt: 14],
                             @"Lychee" : [NSNumber numberWithInt: 1]};

Here, I would like to find the lowest key and value, which in this example would be tie between Lychee : 1 and Banana: 1. Ordinarlly for a smaller dictionary, I would just sort through all the values as suggested by this answer and retrieve the first (or the tied) object in the array based on the ranking. However, I was wondering if there is a way to do it if the NSDictionary is very large, where I could just pluck the lowest key-value pairs?

Thanks!

Could the person who has downvoted this question let me know how I could improve upon it? Thanks. — daspianist, Jun 15 '14 at 22:34
Seems like a reasonable question to me. I up-voted it to compensate. — Duncan C, Jun 16 '14 at 00:57

score 6 · Accepted Answer · answered Jun 15 '14 at 22:40

6

As @Tommy said, there's no option other than to do a linear search. Sorting the dictionary will impose a function of O(n log(n)), while a linear search is obviously O(n). You'd need to use the following:

NSDictionary *dictionary = @{@"Apple" : [NSNumber numberWithInt: 6],
                             @"Banana" : [NSNumber numberWithInt: 1],
                             @"Peach" : [NSNumber numberWithInt: 14],
                             @"Lychee" : [NSNumber numberWithInt: 1]};
NSString *lowestKey = nil;
int lowestValue = 0;
for (NSString *key in dictionary)
{
    int value = [dictionary[key] intValue];
    if (!lowestKey || value < lowestValue)
    {
        lowestKey = key;
        lowestValue = value;
    }
}
NSLog(@"Lowest: %@: %d", lowestKey, lowestValue);

answered Jun 15 '14 at 22:40

Guy Kogus

7,251
1
27
32

The comparison between sorting and linear search was helpful to note, as the answer. Thanks! – daspianist Jun 15 '14 at 22:42
1

Good answer. (voted). It might be worth explaining the performance in layman's terms, as unless you've had formal computer science training, "Big O" notation isn't going to mean anything. (Lots of the people reading these boards are self-starters.) – Duncan C Jun 16 '14 at 01:35
2

For those reading who don't understand what Guy meant by `O(n log(n))` and `O(n)`, the performance of an algorithm usually depends on the number of input elements (n). A really good sort algorithm has to do n•log(n) comparisons. This is written as `O(n log(n))`. A linear pass through an array of n elements does n comparisons. That's knowns as `O(n)` performance. (The number of operations goes up directly with the number of input elements.) Note that a really **BAD** sort algorithm might do N^2 (n squared) comparisons. That's written as `O(n^2)`. – Duncan C Jun 16 '14 at 01:41

score 3 · Answer 2 · answered Jun 16 '14 at 00:43

This code has several advantages: enumerateKeysAndObjectsUsingBlock: doesn't need to lookup any keys but accesses the keys and values directly from the dictionary's data structures, avoiding expensive lookups. Using an NSNumber compare operation makes the code work for large integers, fractional numbers and NSDecimalNumber.

__block NSString* lowestKey = nil;
__block NSNumber* lowestNumber = nil; 

[dictionary enumerateKeysAndObjectsUsingBlock:^(id key, NSNumber* obj, BOOL *stop) {
    if ([lowestNumber == nil || [obj compare:lowestNumber] == NSOrderedAscending)
    {
        lowestKey = key;
        lowestNumber = obj;
    }
}];

This is a great suggestion - thanks for the insight about using the block. — daspianist, Jun 16 '14 at 00:59

score 2 · Answer 3 · edited Jun 15 '14 at 22:58

2

If there's no structure in place to avoid a linear search then you'll have to do a linear search.

E.g.

NSNumber *minValue = [[dictionary allValues] valueForKeyPath:@"@min.self"];

NSString *aLowestKey = [dictionary allKeysForObject:minValue][0];

That'll actually likely be two such searches; it'd be faster manually to iterate the keys and latch on the least key. But it'd be more and slightly more opaque code so pick based on where this code falls on the speed versus maintainability requirement curve.

(typed on an iPhone from a cafe; please forgive slight errors)

edited Jun 15 '14 at 22:58

Guy Kogus

7,251
1
27
32

answered Jun 15 '14 at 22:33

Tommy

99,986
12
185
204

1

Replace `minValue` with `NSNumber *minValue = [[dictionary allValues] valueForKeyPath:@"@min.self"];` – Guy Kogus Jun 15 '14 at 22:45
@GuyKogus I don't suppose you could quickly do it, could you? I've marked it as community wiki. It's very hard to do anything with only my phone to hand. – Tommy Jun 15 '14 at 22:58
Done. But as you mentioned, this is performing 2 searches, one for getting `minValue` and another for calculating the array of `allKeysForObject:`. – Guy Kogus Jun 15 '14 at 22:59

Finding the lowest value and corresponding key in a large NSDictionary

3 Answers3