保持数组的排序——在设置、获取或之后

Question

作为学习objective c/oop的辅助，我正在设计一个iOS应用程序来存储和显示定期的体重测量值。我有一个singleton返回一个共享存储的可变数组。每次测量至少有一个日期和一个体重，我希望能够添加历史测量值。

我想按日期顺序显示测量值。最好的方法是什么?就我所能看到的选项如下:1)添加度量时-每次添加度量后，我重写addobject对共享存储进行排序，2)检索mutablearray时对其进行排序，或者3)我以任何顺序检索mutablearray碰巧在共享存储中，然后在显示表/图表时对其进行排序。

很可能数据被检索的频率比添加新数据的频率要高，所以选项1将减少共享存储的冗余排序——所以这是最好的方法，对吗?

Answer 1

您可以使用(1)的修改版本。在每次插入新对象时，不是对整个数组进行排序，而是使用这里描述的方法:https://stackoverflow.com/a/8180369/1187415将新对象插入到数组的正确位置。

那么对于每次插入，你只需要一个二分查找来找到新对象的正确索引，并且数组总是处于正确的顺序。

由于您说数据检索比新数据添加更频繁，因此这似乎更有效。

Answer 2

如果我忘了你的特殊情况，这个问题就不那么容易回答了。有两种基本的解决方案:

1. 保持数组未排序，当您尝试访问元素且数组未排序时，则对其进行排序。我们称之为"惰性排序"。

2. 插入元素时保持数组排序。注意，这并不是在末尾添加新元素，然后对整个数组进行排序。这是关于找到元素应该在哪里(二进制搜索)，并把它放在那里。

两种技术都是正确和有用的，决定哪一种更好取决于你的用例。

的例子:

1. 您想要插入数百个元素到数组中，然后访问这些元素，然后再次插入数百个元素，然后访问。总之，您将在大块中插入值。

2. 您将经常插入单个元素，并且您将经常访问这些元素。

3. 中间位置(插入1和插入数十个元素之间)。您可能并不关心将使用哪一个方法。

(注意，你也可以使用特殊的结构来保持数组排序，而不是基于NSArray，例如基于平衡树的结构，同时保持子树中的元素数量)