Latest 0.1.0
Homepage https://github.com/modocache/MDCQuickSelect
License MIT
Authors

Build Status

Categories to quickly select the "n-th most" element, or the "n most"
elements (unsorted) in an array.

For example, if you need to find the tenth smallest number in an array of 100,000:

#import <MDCQuickSelect/MDCQuickSelect.h>

// 79% faster than sorting the numbers and accessing -objectAtIndex:10
NSNumber *tenth = [numbers mdc_objectAtIndex:10
                    inSortedArrayUsingComparator:^NSComparisonResult(NSNumber *left, NSNumber *right) {
                        return [left compare: right];
                    }];

Or to find the ten smallest numbers in an array of 100,000:

// 71% faster than sorting the numbers and accessing -subarrayWithRange:NSMakeRange(0, 10)
[numbers mdc_subarrayWithRange:NSMakeRange(0, 10)
 inSortedArrayUsingComparator:^NSComparisonResult(NSNumber *left, NSNumber *right){
                                  return [left.numberOfFriends compare:right.numberOfFriends];
                              }];

The improved performance is achieved by using the quickselect algorithm, developed by
Tony Hoare, inventor of quicksort.

Performance is infinitesimally worse when array size is less than 150 elements. For arrays
larger than 150 elements, MDCQuickSelect outperforms the naive approach, sometimes by vast margins.
Run the benchmarking tests and see for yourself!

Latest podspec

{
    "name": "MDCQuickSelect",
    "version": "0.1.0",
    "summary": "Categories to quickly select the "n-th most" element, or the "n most" elements in an array.",
    "description": "                   Categories to quickly select the "n-th most" element, or the "n most"n                   elements (unsorted) in an array.nn                   For example, if you need to find the tenth smallest number in an array of 100,000:nn                   ```objcn                   #import nn                   // 79% faster than sorting the numbers and accessing -objectAtIndex:10n                   NSNumber *tenth = [numbers mdc_objectAtIndex:10n                                       inSortedArrayUsingComparator:^NSComparisonResult(NSNumber *left, NSNumber *right) {n                                           return [left compare: right];n                                       }];n                   ```nn                   Or to find the ten smallest numbers in an array of 100,000:nn                   ```objcn                   // 71% faster than sorting the numbers and accessing -subarrayWithRange:NSMakeRange(0, 10)n                   [numbers mdc_subarrayWithRange:NSMakeRange(0, 10)n                    inSortedArrayUsingComparator:^NSComparisonResult(NSNumber *left, NSNumber *right){n                                                     return [left.numberOfFriends compare:right.numberOfFriends];n                                                 }];n                   ```nn                   The improved performance is achieved by using the quickselect algorithm, developed byn                   Tony Hoare, inventor of quicksort.nn                   Performance is infinitesimally worse when array size is less than 150 elements. For arraysn                   larger than 150 elements, MDCQuickSelect outperforms the naive approach, sometimes by vast margins.n                   Run the benchmarking tests and see for yourself!n",
    "homepage": "https://github.com/modocache/MDCQuickSelect",
    "license": {
        "type": "MIT",
        "file": "LICENSE"
    },
    "authors": {
        "modocache": "[email protected]"
    },
    "social_media_url": "http://twitter.com/modocache",
    "source": {
        "git": "https://github.com/modocache/MDCQuickSelect.git",
        "tag": "v0.1.0"
    },
    "source_files": "MDCQuickSelect/**/*.{h,m}",
    "xcconfig": {
        "OTHER_LDFLAGS": "-all_load"
    },
    "requires_arc": true
}

Pin It on Pinterest

Share This