使用 NumPy 从矩阵中获取最小/最大 n 值和索引的有效方法 [英] Efficient way to take the minimum/maximum n values and indices from a matrix using NumPy

问题描述

给定 NumPy 矩阵(二维数组)，返回数组中最小/最大 n 值(及其索引)的有效方法是什么?

What's an efficient way, given a NumPy matrix (2D array), to return the minimum/maximum n values (along with their indices) in the array?

目前我有:

def n_max(arr, n):
    res = [(0,(0,0))]*n
    for y in xrange(len(arr)):
        for x in xrange(len(arr[y])):
            val = float(arr[y,x])
            el = (val,(y,x))
            i = bisect.bisect(res, el)
            if i > 0:
                res.insert(i, el)
                del res[0]
    return res

这比 pyopencv 生成我想在其上运行的数组所用的图像模板匹配算法长三倍，我认为这很愚蠢.

This takes three times longer than the image template matching algorithm that pyopencv does to generate the array I want to run this on, and I figure that's silly.

推荐答案

自从其他答案的时候，NumPy 已经添加了 numpy.partition 和 numpy.argpartition 函数用于部分排序，允许您在 O(arr.size) 时间，或者 O(arr.size+n*log(n)) 如果您需要按排序顺序的元素.

Since the time of the other answer, NumPy has added the numpy.partition and numpy.argpartition functions for partial sorting, allowing you to do this in O(arr.size) time, or O(arr.size+n*log(n)) if you need the elements in sorted order.

numpy.partition(arr, n) 返回一个大小为 arr 的数组，其中第 n 个元素是如果数组已排序.所有较小的元素都在该元素之前，所有较大的元素都在其后.

numpy.partition(arr, n) returns an array the size of arr where the nth element is what it would be if the array were sorted. All smaller elements come before that element and all greater elements come afterward.

numpy.argpartition 是 numpy.partition 就像 numpy.argsort 是 numpy.sort.

numpy.argpartition is to numpy.partition as numpy.argsort is to numpy.sort.

以下是如何使用这些函数来查找二维 arr 的最小 n 元素的索引:

Here's how you would use these functions to find the indices of the minimum n elements of a two-dimensional arr:

flat_indices = numpy.argpartition(arr.ravel(), n-1)[:n]
row_indices, col_indices = numpy.unravel_index(flat_indices, arr.shape)

如果您需要按顺序排列索引，那么 row_indices[0] 是最小元素的行，而不是 n 最小元素之一:

And if you need the indices in order, so row_indices[0] is the row of the minimum element instead of just one of the n minimum elements:

min_elements = arr[row_indices, col_indices]
min_elements_order = numpy.argsort(min_elements)
row_indices, col_indices = row_indices[min_elements_order], col_indices[min_elements_order]

<小时>

一维情况要简单得多:

---

The 1D case is a lot simpler:

# Unordered:
indices = numpy.argpartition(arr, n-1)[:n]

# Extra code if you need the indices in order:
min_elements = arr[indices]
min_elements_order = numpy.argsort(min_elements)
ordered_indices = indices[min_elements_order]

这篇关于使用 NumPy 从矩阵中获取最小/最大 n 值和索引的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！