基於C數組值排序`NSArray`

我有一個NSArray與對象和一個C數組與雙打。我想根據C數組值排序NSArray對象。基於C數組值排序`NSArray`

我能想到的唯一的辦法是以下（基於this SO question）：

NSArray *sortedArray; 
sortedArray = [origArray sortedArrayUsingComparator:^NSComparisonResult(id a, id b) 
{ 
    // Getting c array values at the same indices as the objects being compared 
    NSNumber *aValue = @(cArray[[origArray indexOfObject:a]]); 
    NSNumber *bValue = @(cArray[[origArray indexOfObject:b]]); 
    // Returning comparison result 
    return [aValue compare:bValue]; 
}];

但我認爲indexOfObject:部分是有點昂貴。是這樣嗎？

如果是這樣，有沒有更快的方法來做到這一點？

編輯：

爲了提供更多的背景下，此排序是優化算法健身評估的一部分。在我的計劃中，我做了一個基本的分析，並且健身評估代碼變成了瓶頸。因此，我試圖優化它。

此外，陣列中元素的數量預計將從大約100到10k最大。

來源

2013-10-15 insys

沒有真正的潛在性能問題，沒有任何意義。

如果您可以測量您的代碼的實際問題（例如通過在樂器中使用Time Profiler），您會了解瓶頸的位置。在你的代碼中有幾個點可能會減慢排序（裝箱每個數字來計算NSComparisonResult，保留/釋放ARC的開銷，僅僅用於訪問數組中的對象，...）。

有幾種方法可以提高性能，但它們取決於實際數據（origArray中的對象數量，C數組的雙精度數據源......）。

如果我猜測可能看起來是性能增強的候選人，我會說兩個數組形成一個元組而不是一個元組數組應該被消除。下面是該陣列與一個小的開銷排序C函數：

NSArray *sortedObjects(double valuesArray[], NSArray *objects) 
{ 
    NSUInteger count = [objects count]; 
    struct tuple { 
     double value; 
     __unsafe_unretained id object; 
    } tupleArray[count]; 

    for (NSUInteger i = 0; i < count; ++i) 
     tupleArray[i] = (struct tuple){ valuesArray[i], objects[i] }; 

    qsort_b(tupleArray, count, sizeof tupleArray[0], ^int(const void *a, const void *b) { 
     double v = ((const struct tuple *)a)->value - ((const struct tuple *)b)->value; 
     return v == 0 ? 0 : v > 0 ? 1 : -1; 
    }); 

    __unsafe_unretained id objectsArray[count]; 
    for (NSUInteger i = 0; i < count; ++i) 
     objectsArray[i] = tupleArray[i].object; 

    return [[NSArray alloc] initWithObjects:objectsArray count:count]; 
}

來源

2013-10-15 10:16:11

謝謝你的回答和清晰優雅的例子。我在我的問題中添加了一些信息以供澄清。如果我理解正確，這裏的一般方法會以某種方式創建一個元組（通過結構或通過關聯對象或常規對象，如@JeremyP建議的）來創建對象排序值對。 – insys

直到你知道這是一個問題之前，不要優化排序。首先你需要回答一些問題。數組中會有多少個值？用戶可以等待多長時間？

之後，您應該測試當前的解決方案。排序期望值的數量時，用戶是否需要等待太久？

接下來，回答其他架構問題。例如，您可以在用戶正在做其他工作的同時在後臺對數組進行排序嗎？

如果你做了所有這些，你發現一個問題，那麼你可以開始考慮如何優化。

首先想到的是將數組映射到字典中，對字典進行排序，然後映射回已排序的數組。首先得到一個映射類別（這裏是我在NSArray Equivalent of Map找到的一個）。

@interface NSArray (Map) 
- (NSArray *)mapObjectsUsingBlock:(id (^)(id obj, NSUInteger idx))block; 
@end 

@implementation NSArray (Map) 
- (NSArray *)mapObjectsUsingBlock:(id (^)(id obj, NSUInteger idx))block { 
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:[self count]]; 
    [self enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { 
     [result addObject:block(obj, idx)]; 
    }]; 
    return result; 
} 
@end

一旦你有你選擇的映射方法，然後運行新的排序。

// Step 1) Map into an array of a dictionaries 
NSArray *dicts = [origArray mapObjectsUsingBlock:^(id obj, NSUInteger idx) { 
    return @{ @"value": obj, @"sortValue": @(cArray[idx]) }; 
}]; 

// Step 2) Sort the dictionaries 
NSArray *sortedDicts = [dicts sortedArrayUsingComparator:^NSComparisonResult(id a, id b) 
{ 
    return [a[@"sortValue"] compare:b[@"sortValue"]]; 
}]; 

// Step 3) Map back to the sorted array 
sortedArray = [sortedDicts mapObjectsUsingBlock:^(id obj, NSUInteger idx) { 
    return obj[@"value"]; 
}];

了這一切之後，你需要重複的測試來回答這個問題，「是否有用戶排序值的預期數量時等待太久？」如果答案仍然是肯定的，用戶必須等待太久，那麼您需要再次尋找新的解決方案。

來源

2013-10-15 10:14:03

感謝您的答案和有趣的方法。 – insys

如果是這樣，有沒有這樣做的任何更快的方法？

那麼顯而易見的問題是爲什麼不是你的對象的雙值屬性？

如果絕對不能有一個屬性是double值（實際上，您始終可以通過使用associated objects），您可以創建包裝對象，其中一個屬性是原始對象，另一個屬性是雙倍屬性值並對這些數組進行排序。然而，這是相當昂貴的（大量分配），所以你一定要先做另外兩個答案建議的分析。

來源

2013-10-15 10:31:50 JeremyP

謝謝你參考相關的對象，我沒有意識到它。關於答案的第二部分，我想避免創建包裝器對象，因爲每次都需要使用不同的排序值排序不同的對象（因此包裝器不能被緩存）。因此，我認爲（正如你所指出的那樣）這種方法會產生很大的開銷。 – insys

另一方面，我相信它仍然會比我在問題中提出的方法更好。 – insys

如果您的單一關注點是indexOfObject:的開銷，您可能需要使用indexOfObjectIdenticalTo:。它省略了每個元素的isEqual:消息，如果數組有很多元素，可能會更快。

來源

2013-10-15 10:46:16

基於C數組值排序`NSArray`

回答

相關問題