• A.6 更多有关排序的话题
    • 间接排序:argsort和lexsort
    • 其他排序算法
    • 部分排序数组
    • numpy.searchsorted:在有序数组中查找元素

    A.6 更多有关排序的话题

    跟Python内置的列表一样,ndarray的sort实例方法也是就地排序。也就是说,数组内容的重新排列是不会产生新数组的:

    1. In [160]: arr = np.random.randn(6)
    2. In [161]: arr.sort()
    3. In [162]: arr
    4. Out[162]: array([-1.082 , 0.3759, 0.8014, 1.1397, 1.2888, 1.8413])

    在对数组进行就地排序时要注意一点,如果目标数组只是一个视图,则原始数组将会被修改:

    1. In [163]: arr = np.random.randn(3, 5)
    2. In [164]: arr
    3. Out[164]:
    4. array([[-0.3318, -1.4711, 0.8705, -0.0847, -1.1329],
    5. [-1.0111, -0.3436, 2.1714, 0.1234, -0.0189],
    6. [ 0.1773, 0.7424, 0.8548, 1.038 , -0.329 ]])
    7. In [165]: arr[:, 0].sort() # Sort first column values in-place
    8. In [166]: arr
    9. Out[166]:
    10. array([[-1.0111, -1.4711, 0.8705, -0.0847, -1.1329],
    11. [-0.3318, -0.3436, 2.1714, 0.1234, -0.0189],
    12. [ 0.1773, 0.7424, 0.8548, 1.038 , -0.329 ]])

    相反,numpy.sort会为原数组创建一个已排序副本。另外,它所接受的参数(比如kind)跟ndarray.sort一样:

    1. In [167]: arr = np.random.randn(5)
    2. In [168]: arr
    3. Out[168]: array([-1.1181, -0.2415, -2.0051, 0.7379, -1.0614])
    4. In [169]: np.sort(arr)
    5. Out[169]: array([-2.0051, -1.1181, -1.0614, -0.2415, 0.7379])
    6. In [170]: arr
    7. Out[170]: array([-1.1181, -0.2415, -2.0051, 0.7379, -1.0614])

    这两个排序方法都可以接受一个axis参数,以便沿指定轴向对各块数据进行单独排序:

    1. In [171]: arr = np.random.randn(3, 5)
    2. In [172]: arr
    3. Out[172]:
    4. array([[ 0.5955, -0.2682, 1.3389, -0.1872, 0.9111],
    5. [-0.3215, 1.0054, -0.5168, 1.1925, -0.1989],
    6. [ 0.3969, -1.7638, 0.6071, -0.2222, -0.2171]])
    7. In [173]: arr.sort(axis=1)
    8. In [174]: arr
    9. Out[174]:
    10. array([[-0.2682, -0.1872, 0.5955, 0.9111, 1.3389],
    11. [-0.5168, -0.3215, -0.1989, 1.0054, 1.1925],
    12. [-1.7638, -0.2222, -0.2171, 0.3969, 0.6071]])

    你可能注意到了,这两个排序方法都不可以被设置为降序。其实这也无所谓,因为数组切片会产生视图(也就是说,不会产生副本,也不需要任何其他的计算工作)。许多Python用户都很熟悉一个有关列表的小技巧:values[::-1]可以返回一个反序的列表。对ndarray也是如此:

    1. In [175]: arr[:, ::-1]
    2. Out[175]:
    3. array([[ 1.3389, 0.9111, 0.5955, -0.1872, -0.2682],
    4. [ 1.1925, 1.0054, -0.1989, -0.3215, -0.5168],
    5. [ 0.6071, 0.3969, -0.2171, -0.2222, -1.7638]])

    间接排序:argsort和lexsort

    在数据分析工作中,常常需要根据一个或多个键对数据集进行排序。例如,一个有关学生信息的数据表可能需要以姓和名进行排序(先姓后名)。这就是间接排序的一个例子,如果你阅读过有关pandas的章节,那就已经见过不少高级例子了。给定一个或多个键,你就可以得到一个由整数组成的索引数组(我亲切地称之为索引器),其中的索引值说明了数据在新顺序下的位置。argsort和numpy.lexsort就是实现该功能的两个主要方法。下面是一个简单的例子:

    1. In [176]: values = np.array([5, 0, 1, 3, 2])
    2. In [177]: indexer = values.argsort()
    3. In [178]: indexer
    4. Out[178]: array([1, 2, 4, 3, 0])
    5. In [179]: values[indexer]
    6. Out[179]: array([0, 1, 2, 3, 5])

    一个更复杂的例子,下面这段代码根据数组的第一行对其进行排序:

    1. In [180]: arr = np.random.randn(3, 5)
    2. In [181]: arr[0] = values
    3. In [182]: arr
    4. Out[182]:
    5. array([[ 5. , 0. , 1. , 3. , 2. ],
    6. [-0.3636, -0.1378, 2.1777, -0.4728, 0.8356],
    7. [-0.2089, 0.2316, 0.728 , -1.3918, 1.9956]])
    8. In [183]: arr[:, arr[0].argsort()]
    9. Out[183]:
    10. array([[ 0. , 1. , 2. , 3. , 5. ],
    11. [-0.1378, 2.1777, 0.8356, -0.4728, -0.3636],
    12. [ 0.2316, 0.728 , 1.9956, -1.3918, -0.2089]])

    lexsort跟argsort差不多,只不过它可以一次性对多个键数组执行间接排序(字典序)。假设我们想对一些以姓和名标识的数据进行排序:

    1. In [184]: first_name = np.array(['Bob', 'Jane', 'Steve', 'Bill', 'Barbara'])
    2. In [185]: last_name = np.array(['Jones', 'Arnold', 'Arnold', 'Jones', 'Walters'])
    3. In [186]: sorter = np.lexsort((first_name, last_name))
    4. In [187]: sorter
    5. Out[187]: array([1, 2, 3, 0, 4])
    6. In [188]: zip(last_name[sorter], first_name[sorter])
    7. Out[188]: <zip at 0x7fa203eda1c8>

    刚开始使用lexsort的时候可能会比较容易头晕,这是因为键的应用顺序是从最后一个传入的算起的。不难看出,last_name是先于first_name被应用的。

    笔记:Series和DataFrame的sort_index以及Series的order方法就是通过这些函数的变体(它们还必须考虑缺失值)实现的。

    其他排序算法

    稳定的(stable)排序算法会保持等价元素的相对位置。对于相对位置具有实际意义的那些间接排序而言,这一点非常重要:

    1. In [189]: values = np.array(['2:first', '2:second', '1:first', '1:second',
    2. .....: '1:third'])
    3. In [190]: key = np.array([2, 2, 1, 1, 1])
    4. In [191]: indexer = key.argsort(kind='mergesort')
    5. In [192]: indexer
    6. Out[192]: array([2, 3, 4, 0, 1])
    7. In [193]: values.take(indexer)
    8. Out[193]:
    9. array(['1:first', '1:second', '1:third', '2:first', '2:second'],
    10. dtype='<U8')

    mergesort(合并排序)是唯一的稳定排序,它保证有O(n log n)的性能(空间复杂度),但是其平均性能比默认的quicksort(快速排序)要差。表A-3列出了可用的排序算法及其相关的性能指标。大部分用户完全不需要知道这些东西,但了解一下总是好的。

    表A-3 数组排序算法

    部分排序数组

    排序的目的之一可能是确定数组中最大或最小的元素。NumPy有两个优化方法,numpy.partition和np.argpartition,可以在第k个最小元素划分的数组:

    1. In [194]: np.random.seed(12345)
    2. In [195]: arr = np.random.randn(20)
    3. In [196]: arr
    4. Out[196]:
    5. array([-0.2047, 0.4789, -0.5194, -0.5557, 1.9658, 1.3934, 0.0929,
    6. 0.2817, 0.769 , 1.2464, 1.0072, -1.2962, 0.275 , 0.2289,
    7. 1.3529, 0.8864, -2.0016, -0.3718, 1.669 , -0.4386])
    8. In [197]: np.partition(arr, 3)
    9. Out[197]:
    10. array([-2.0016, -1.2962, -0.5557, -0.5194, -0.3718, -0.4386, -0.2047,
    11. 0.2817, 0.769 , 0.4789, 1.0072, 0.0929, 0.275 , 0.2289,
    12. 1.3529, 0.8864, 1.3934, 1.9658, 1.669 , 1.2464])

    当你调用partition(arr, 3),结果中的头三个元素是最小的三个,没有特定的顺序。numpy.argpartition与numpy.argsort相似,会返回索引,重排数据为等价的顺序:

    1. In [198]: indices = np.argpartition(arr, 3)
    2. In [199]: indices
    3. Out[199]:
    4. array([16, 11, 3, 2, 17, 19, 0, 7, 8, 1, 10, 6, 12, 13, 14, 15, 5,
    5. 4, 18, 9])
    6. In [200]: arr.take(indices)
    7. Out[200]:
    8. array([-2.0016, -1.2962, -0.5557, -0.5194, -0.3718, -0.4386, -0.2047,
    9. 0.2817, 0.769 , 0.4789, 1.0072, 0.0929, 0.275 , 0.2289,
    10. 1.3529, 0.8864, 1.3934, 1.9658, 1.669 , 1.2464])

    numpy.searchsorted:在有序数组中查找元素

    searchsorted是一个在有序数组上执行二分查找的数组方法,只要将值插入到它返回的那个位置就能维持数组的有序性:

    1. In [201]: arr = np.array([0, 1, 7, 12, 15])
    2. In [202]: arr.searchsorted(9)
    3. Out[202]: 3

    你可以传入一组值就能得到一组索引:

    1. In [203]: arr.searchsorted([0, 8, 11, 16])
    2. Out[203]: array([0, 3, 3, 5])

    从上面的结果中可以看出,对于元素0,searchsorted会返回0。这是因为其默认行为是返回相等值组的左侧索引:

    1. In [204]: arr = np.array([0, 0, 0, 1, 1, 1, 1])
    2. In [205]: arr.searchsorted([0, 1])
    3. Out[205]: array([0, 3])
    4. In [206]: arr.searchsorted([0, 1], side='right')
    5. Out[206]: array([3, 7])

    再来看searchsorted的另一个用法,假设我们有一个数据数组(其中的值在0到10000之间),还有一个表示“面元边界”的数组,我们希望用它将数据数组拆分开:

    1. In [207]: data = np.floor(np.random.uniform(0, 10000, size=50))
    2. In [208]: bins = np.array([0, 100, 1000, 5000, 10000])
    3. In [209]: data
    4. Out[209]:
    5. array([ 9940., 6768., 7908., 1709., 268., 8003., 9037., 246.,
    6. 4917., 5262., 5963., 519., 8950., 7282., 8183., 5002.,
    7. 8101., 959., 2189., 2587., 4681., 4593., 7095., 1780.,
    8. 5314., 1677., 7688., 9281., 6094., 1501., 4896., 3773.,
    9. 8486., 9110., 3838., 3154., 5683., 1878., 1258., 6875.,
    10. 7996., 5735., 9732., 6340., 8884., 4954., 3516., 7142.,
    11. 5039., 2256.])

    然后,为了得到各数据点所属区间的编号(其中1表示面元[0,100)),我们可以直接使用searchsorted:

    1. In [210]: labels = bins.searchsorted(data)
    2. In [211]: labels
    3. Out[211]:
    4. array([4, 4, 4, 3, 2, 4, 4, 2, 3, 4, 4, 2, 4, 4, 4, 4, 4, 2, 3, 3, 3, 3, 4,
    5. 3, 4, 3, 4, 4, 4, 3, 3, 3, 4, 4, 3, 3, 4, 3, 3, 4, 4, 4, 4, 4, 4, 3,
    6. 3, 4, 4, 3])

    通过pandas的groupby使用该结果即可非常轻松地对原数据集进行拆分:

    1. In [212]: pd.Series(data).groupby(labels).mean()
    2. Out[212]:
    3. 2 498.000000
    4. 3 3064.277778
    5. 4 7389.035714
    6. dtype: float64