views:

968

answers:

3

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.

+2  A: 
e.James
I understand this, but I don't think this answers the question. I am not sorting by name, I need to rank and group the names based on what's the smallest time value for a given name.
Jaanus
Ah. Now I see. That's much more interesting.
e.James
Do you define the type of object that gets stored in the original array? i.e. is it a custom class that you can add ivars to?
e.James
Yes, it is my custom class and I could add ivars. I can't see myself how that could help though. The data is volatile and new values may arrive at runtime. At any given time, I just have a snapshot of the data I need to sort this way.
Jaanus
Out of all the answers so far, I like these the best, especially the groups approach, will report back. I think this has O(n) complexity, much better than my current naive O(n*n). Assigning out of the gate would be great, but the actual situation is more complicated and depends on the environment that is not known at save time.
Jaanus
How are you getting the original list of data? Do you start with an empty array, add items (name and time) on the fly, sort the results and then empty the array and start over, or do items get randomly added and removed from the array during runtime?
e.James
The original list gets loaded from a Core Data backend. Additional entries will arrive at runtime from network, and their "time" is not current time, but rather, when they were created in some other system.
Jaanus
Hmm. Yes, that makes it difficult to set the groups ahead of time. I'm sure there is still a way to do it, but it is probably not worth the effort. How did the testing go?
e.James
Might not be able to test before the weekend, will comment when I get to it.
Jaanus
+1  A: 

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.

mjdth
I think this is doing mostly the same as Benedict Cohen's response, but on your own instead of sort and predicates.
Jaanus
+5  A: 

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.

Benedict Cohen
This does not answer the question: my situation is more complicated than simply sorting by name.
Jaanus
@Jaanus. Ohhh I see. I didn't notice that the order of the groups is dependent on the time.
Benedict Cohen
@Jaanus. I've updated the code so that it actually answer the question!
Benedict Cohen
Thanks, this looks like what I need. I will try out several approaches from the answers and report back.
Jaanus
Upvoted the answer. Wish I could deduct a quarter point for the performance implications comment though. It's not premature optimization to consider the efficiency of your algorithms. That phrase is getting tossed around more and more, and this is not what it's about. Taking the time to consider the complexity of your algorithms, and whether there's a better way, is just good engineering.
DougW