sortedArrayUsingComparator 是随机化 NSArray 的安全方法吗?

Question

我之前弄乱了NSArray函数，我想我可能遇到了随机化NSArray的最简单方法：

NSArray *randomize(NSArray *arr)
{
    return [arr sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return arc4random_uniform(3) - 1; // one of -1, 0, or 1
    }];
}

从理论上讲，这应该彻底随机化 NSArray。然而，经过大量的思考，我想知道这是否可能是不安全的，理论上会变成一个无限循环，这取决于NSArray使用的排序算法。

我在大小为 10 - 100000 的数组上对此进行了测试，我看到了线性性能差异（每次随机化大约 N * (log10(N) + 2) 次比较），这还不错。

但是，是否会出现NSArray理论上永远无法自行排序并导致应用程序崩溃的情况？在我看来，这不应该发生，但你永远不知道。

Answer 1

我认为这取决于底层排序算法。

考虑如果基础排序是气泡排序会发生什么。 这意味着，每当您比较一对元素时，您都有 1/3 的机会交换它们（如果比较使它们看起来无序）。 因此，如果要使用此比较函数对 n 个元素的数组进行排序，则算法在每一步终止的概率等于没有任何比较计算结果为"无序"的概率。 由于每次比较都以 1/3 的概率表示"无序"，这意味着算法在每次迭代中终止的概率为 （2/3）ⁿ。 这意味着算法终止前的预期迭代次数为 （3/2）n = 3 n/2ⁿ。 如果您尝试为大小合理的数组（例如，n = 1000）运行此算法，那么预期的迭代次数将非常大;n = 1000 给出 1.233840597×10¹⁷⁶ 次预期迭代！ 此算法最终将终止，但预期的运行时间太长，从实际角度来看，它实际上是无限的。

另一方面，如果您尝试使用不同的算法，例如选择排序，则无法保证获得均匀分布。 例如，考虑算法的第一遍，它将找到要放在位置 1 的元素。 数组中的每个元素都应该（如果分布确实是均匀的）有 1/n 的概率被放在第一位。 但事实并非如此。 请注意，第一个元素将保留在第一个位置，除非它与某些东西交换。 仅当在第一次扫描期间的任何时候比较显示 +1（或 -1，取决于内部结构）时，才会发生这种情况。 所有比较返回不同值的概率是 （2/3）^n-1，它与 1/n 不同。 事实上，一旦你完成排序，序列中的第一个元素就不太可能出现在前面。 因此，即使算法将终止，也不能保证您获得均匀随机分布。

如果您尝试使用快速排序、堆排序或合并排序之类的东西，那么算法最终会终止，但我不确定它是否保证是随机的。 我会考虑一下这是否是均匀随机的，然后更新我的答案。

希望这有帮助！

Answer 2

假设 NSArray 使用或多或少的标准稳定合并排序算法。比较器只返回 -1 和 1 可能是最好的，因为 mergesort 不会将元素与自身进行比较。

对于四元素数组 1 2 3 4，mergesort 随机化前半部分和后半部分，然后合并。如果 L = [a b] = [1 2] 或 [2 1]，并且 R = [c d] = [3 4] 或 [4 3]，则合并决策树（抑制非决策）如下所示

       [a b c d]   [a c b d]
      /           /
   [a]-------[a c]-[a c d b]
  /
[]
     
   [c]-------[c a]-[c a b d]
                 
       [c d a b]   [c a d b]

形式为 [L L R R]（例如，[1 2 3 4]、[2 1 3 4]、[1 2 4 3]

、[2 1 4 3]）形式的序列应该是总概率 1/6（每个 1/24），但概率为 1/4。同上，[R R L L]。形式为 [L R L R] 的序列应该是总概率 1/6，但概率为 1/8。同上，[L R R L]， [R L L R]， [R L R L].这是不统一的。

更重要的是，你违反了合同（显然隐含在我阅读的文档中，但这个合同的紧密变体非常普遍），比较器给出了与总顺序一致的确定性答案。这意味着Apple的代码可以通过抛出异常或不终止来自由地违反其合同结束。它真的会永远运行吗？可能不是，但如果确实如此，并且您向Apple提交了错误报告，他们会笑着不会修复您。我想大多数程序员都会同意他们的观点。依赖软件库的未指定方面不是一个好习惯。

Answer 3

这个问题已经解决了。 http://en.wikipedia.org/wiki/Knuth_shuffle

TemplateTypeDef也对此发表了评论。

费舍尔-耶茨 洗牌mutableCopy速度很快，而且随机化更好。对于小数组（10 个元素），您的建议比 Fisher-Yates shuffle 略快，如下所示。对于大型数组（1000000 个元素），Fisher_Yates比您的快 4 倍。如果您可以返回您制作的可变副本，那么 Fisher-Yates 对于 10 个元素也更快。

我会选择高级随机播放算法，它对于小尺寸和大尺寸都很快。

这是程序 - 您知道如何使用仪器！

#import <Foundation/Foundation.h>
static NSArray * imp_RandomizeUsingSortedArrayUsingComparator(NSArray * arr) {
    return [arr sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return arc4random_uniform(3) - 1; // one of -1, 0, or 1
    }];
}
__attribute__((__noinline__)) static void RandomizeUsingSortedArrayUsingComparator(NSArray * arr) {
    @autoreleasepool { imp_RandomizeUsingSortedArrayUsingComparator(arr); }
}
static NSArray * imp_RandomizeUsingMutableCopy(NSArray * arr) {
    if (1 >= arr.count) {
        return [arr.copy autorelease];
    }
    NSMutableArray * cp = [arr.mutableCopy autorelease];
    u_int32_t i = (u_int32_t)cp.count;
    while (i > 1) {
        --i;
        const u_int32_t j = arc4random_uniform(i);
        [cp exchangeObjectAtIndex:i withObjectAtIndex:j];
    }
    // you may not favor creating the concrete copy
    return [cp.copy autorelease];
}
__attribute__((__noinline__)) static void RandomizeUsingMutableCopy(NSArray * arr) {
    @autoreleasepool { imp_RandomizeUsingMutableCopy(arr); }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSMutableArray * filled = [NSMutableArray array];
        for (NSUInteger i = 0; i < 1000000; ++i) {
            [filled addObject:@""];
        }
        NSArray * concrete = filled.copy;
        for (NSUInteger i = 0; i < 100; ++i) {
            RandomizeUsingSortedArrayUsingComparator(concrete);
            RandomizeUsingMutableCopy(concrete);
        }
        [concrete release];
    }
    return 0;
}