Help sorting an NSArray across two properties (with NSSortDescriptor?)

Question

I'm a bit of a NSSortDescriptor n00b. I think, though, it is the right tool for what I need to do:

I have an NSArray consisting of objects with keys, say, "name" and "time". Instead of verbalizing it, here's an example:

input:

name: time
B: 4
C: 8
B: 5
C: 4
A: 3
C: 2
A: 1
A: 7
B: 6


desired output:

name: time
A: 1 <---
A: 3
A: 7
C: 2 <---
C: 4
C: 8
B: 4 <---
B: 5
B: 6

So the values are sorted by "time" and grouped by "name". A comes first because he had the smallest time value, and all values for A come after one another. Then comes C, he had the second smallest time value out of all his values. I have indicated the values that determine how the names are sorted; within each name group, sorting is by time.

How do I get from input to output NSArray in the most efficient way? (cpu- and memory-wise, not necessarily code-wise.) How would I construct the NSSortDescriptors for this, or use any other method? I don't want to roll my own unless it's the most efficient way.

Answer 1

My solution is:

    NSSortDescriptor *sortDescriptor1 = [[NSSortDescriptor alloc] initWithKey:@"name" ascending:YES];
    NSSortDescriptor *sortDescriptor2 = [[NSSortDescriptor alloc] initWithKey:@"time" ascending:YES];
    NSArray *sortDescriptors = [[NSArray alloc] initWithObjects:sortDescriptor1, sortDescriptor2, nil];

You can try it

Answer 2

The sortedArrayUsingDescriptors: NSArray method does most of what you need:

The first descriptor specifies the primary key path to be used in sorting the receiver’s contents. Any subsequent descriptors are used to further refine sorting of objects with duplicate values. See NSSortDescriptor for additional information.

Some filtering with NSPredicate is required too:

NSSortDescriptor *timeSD = [NSSortDescriptor sortDescriptorWithKey: @"time" ascending: YES];

NSMutableArray *sortedByTime = [UnsortedArray sortedArrayUsingDescriptors: timeSD];
NSMutableArray *sortedArray = [NSMutableArray arrayWithCapacity:[sortedByTime count]];

while([sortedByTime count]) 
{
        id groupLead = [sortedByTime objectAtIndex:0];  
        NSPredicate *groupPredicate = [NSPredicate predicateWithFormat:@"name = %@", [groupLead name]];

        NSArray *group = [sortedByTime filteredArrayUsingPredicate: groupPredicate];

        [sortedArray addObjectsFromArray:group];
        [sortedByTime removeObjectsInArray:group];
}

I have no idea if this is the most efficient method, but until you have reason to believe that it is causing problems there's no need to worry the performance implications. It's premature optimisation. I wouldn't have any concerns about the performance of this method. You've got to trust the framework otherwise you'll end up rewriting it (thus undermine the point of the framework) due to an unfounded paranoia.

Answer 3

I would create a new class called ItemGroup, and then add an extra ivar called group to your item class:

@interface ItemGroup : NSObject
{
    NSNumber * time;
}
@property (nonatomic, copy) time;
@end

@interface ItemClass : NSobject
{
    NSString * name;
    NSNumber * time;
    ItemGroup * group;
}
@property (nonatomic, copy) NSString * name;
@property (nonatomic, copy) NSNumber * time;
@property (nonatomic, assign) ItemClass * group; // note: must be assign
@end

Then, you could do the following:

NSMutableDictionary * groups = [NSMutableDictionary dictionaryWithCapacity:0];
for (ItemClass * item in sourceData)
{
    ItemGroup * group = [groups objectForKey:item.name];
    if (group == nil)
    {
        group = [[ItemGroup alloc] init];
        [groups setObject:group forKey:item.name];
        [group release];

        group.time = item.time;
    }
    else if (item.time < group.time)
    {
        group.time = item.time;
    }
    item.group = group;
}

This code loops through the unsorted array, keeping track of the minimum time for each group, and also setting the group for each item. With that complete, you simply sort on group.time and time:

NSSortDescriptor * groupSorter;
groupSort = [NSSortDescriptor sortDescriptorWithKey:@"group.time" ascending:YES];

NSSortDescriptor * timeSorter;
timeSort = [NSSortDescriptor sortDescriptorWithKey:@"time" ascending:YES];

NSArray * sortDescriptors = [NSArray arrayWithObjects:groupSort, timeSort, nil];

NSArray * sorted = [sourceData sortedArrayUsingDescriptors:sortDescriptors];

And that should do the trick!

UPDATE: Note that you could get much better performance if you were able to assign the groups straight out of the gate. Something like this:

@interface ItemGroup : NSObject
{
    NSString * name;
    NSNumber * time;
}
@property (nonatomic, copy) NSString * name;
@property (nonatomic, copy) NSSNumber * time;
@end

@interface ItemClass : NSObject
{
    ItemGroup * group;
    NSNumber * time;
}
@property (nonatomic, retain) ItemGroup * group;
@property (nonatomic, copy) NSNumber * time;
@end

Now, if you maintain a list of groups somewhere (they could even go in an array somewhere, if need be):

ItemGroup * group_A = [[ItemGroup alloc] init];
group_A.name = @"A";
ItemGroup * group_B = [[ItemGroup alloc] init];
group_B.name = @"B";
...

And instead of setting the names of your data items, you set their group:

someItem.group = group_A;
someItem.time = GetSomeRandomTimeValue();
[sourceData addObject:someItem];
....

This would greatly simplify the loop used to set group times:

for (ItemClass * item in sourceData)
{
    if (item.time < group.time) { group.time = item.time; }
}

And, if you really wanted to be blazing fast about it, you could even modify the property setter for your time property to set the group times on the fly:

@implementation ItemClass
- (void)setTime:(NSNumber *)newTime
{
    if (newTime < group.time) { group.time = newTime; }
    time = [newTime copy];
}
@end

Note that you would have to be sure that group had been set before you set the time. With this in place, you wouldn't need that sorting loop at all. The sortDescriptors would be enough.

Answer 4

I went through to make a little code (didn't try running it or really go over it so there might be a couple of mistakes, but it has the general idea) to do what you're looking for. Performance wise, it probably won't be the best if you start running into huge amounts of data. I'm sure there's a better way to do this, but I felt like doing it the most basic way as a "temporary fix" answer.

NSMutableArray *copiedarray = [YourFirstArray mutableCopy];
NSMutableArray *sortedarray = [[NSMutableArray alloc] init];
NSMutableArray *tempgroup = nil;
NSSortDescriptor * groupSorter = [NSSortDescriptor sortDescriptorWithKey:@"time" ascending:YES];

NSInteger i;
NSInteger savedlowest = -1;
NSString *savedname = @"";


while ([copiedarray count] > 0) {
    ///reset lowest time and group
    savedlowest = -1;
    savedname = @"";

    ///grab the lowest time and group name
    for (ii = 0;ii < [copiedarray count]; ii++) {
        if (savedlowest==-1 || ((YourClass *)([copiedarray objectAtIndex:ii])).time<savedlowest)) {
            savedname = ((YourClass *)([copiedarray objectAtIndex:ii])).name;
            savedlowest = ((YourClass *)([copiedarray objectAtIndex:ii])).time;
        }
    }

    //we have the lowest time and the type so we grab all those items from the group
    tempgroup = [[NSMutableArray alloc] init];
    for (ii = [copiedarray count]-1;ii > -1; ii--) {
        if ([((YourClass *)([copiedarray objectAtIndex:ii])).name isEqualToString:savedname]) {
            ///the item matches the saved group so we'll add it to our temporary array
            [tempgroup addObject:[copiedarray objectAtIndex:ii]];
            ///remove it from the main copied array for "better performance"
            [copiedarray removeObjectAtIndex:ii];
        }
    }

    [tempgroup sortUsingDescriptors:[NSArray arrayWithObject:groupSorter]];
    [sortedarray addObjectsFromArray:tempgroup];

    [tempgroup release];
    tempgroup = nil;

}

In the end you'll end up with what you're looking for in sortedarray.