从m x n的np.array中找到m个“最小”的元素

Question

从m x n的np.array中找到m个“最小”的元素

pythonarrayselementmultidimensional-array

3

我有一个大小为 m x n（其中 m <= n）的二维 ndarray，如下所示：

a = [ [1, 2, 3], 
      [4, 5, 6] ]

现在我想贪心地从数组中找到 m 个“最小”的元素，限制条件是每行和每列只能选择一个元素，并且每次都选择全局最小值。我的代码如下：

for k in xrange(m):
    index = np.argmin(a)
    i, j = divmod(index, n-k)
    result.append(a[i][j])
    a = np.delete(np.delete(a, i, 0), j, 1)

所以我会得到result = [1, 5]，有没有更好的方式来表示输入数组a，以及更好的算法来提高速度找到这些元素？

- Rain Lee

5

1和5在某些方面是否比2和4更好？只是想了解您在“最小”的概念中究竟在寻求什么。您总是贪心地寻找最低可能的元素以删除吗？ - Joachim Isaksson

1

我同意@JoachimIsaksson的观点，所提出的问题并没有明确定义。 - shx2

@JoachimIsaksson，观察得很好。但是，要找到满足指定限制条件的全局最小元素将会非常昂贵，首先需要找到所有可能的m元素组合，n*(n-1)...(n-m+1)=n!/m!，然后计算每种情况的平均值，并最终选择给出最小平均值的最佳方案。在这里，我正在进行大规模处理，只想使用这个贪心算法快速给出一个不错的结果，这可能不是最好的结果。但如果有一种有效的算法可以找到全局最小值，那将不胜感激。 - Rain Lee

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Petr Vepřek · Accepted Answer

我刚刚尝试了一种替代方法：

import numpy as np
import timeit

nmin = 2000 # number of the smallest values to find in a matrix with unique row and column indexes
nrows = 2000 # number of rows
ncols = 2000 # number of columns
print "Select {} smallest values from {} x {} matrix".format(nmin, nrows, ncols)

matrix = np.random.uniform(0, 1, size = nrows * ncols).reshape(nrows, ncols) # sample 2D array
#print matrix

# ALTERNATIVE: sort once and track-and-skip visited rows and columns
startedat = timeit.default_timer()
seenrows = set()
seencols = set()
order = (divmod(index, ncols) for index in np.argsort(matrix, None))
for iter in xrange(nmin):
    while True:
        try:
            current = order.next()
        except:
            break
        if current[0] not in seenrows and current[1] not in seencols:
            #print iter, current, matrix[current[0]][current[1]]
            seenrows.add(current[0])
            seencols.add(current[1])
            break
alternative = timeit.default_timer() - startedat
print "Alternative approach took: ", alternative

# ORIGINAL: repeatedly find minimum and update matrix
startedat = timeit.default_timer()
for k in xrange(nmin):
    index = np.argmin(matrix)
    i, j = divmod(index, np.shape(matrix)[1])
    #print k, (i, j), matrix[i][j]
    matrix = np.delete(np.delete(matrix, i, 0), j, 1)
    if matrix.size == 0: break
original = timeit.default_timer() - startedat
print "   Original approach took: ", original, "WINNER" if original < alternative else "TIE" if original == alternative else "LOOSER"

以下是结果：

Select 2 smallest values from 2000 x 2000 matrix
Alternative approach took:  0.737312265981
   Original approach took:  0.0572765855289 WINNER

Select 20 smallest values from 2000 x 2000 matrix
Alternative approach took:  0.732718787079
   Original approach took:  0.564769882057 WINNER

Select 200 smallest values from 2000 x 2000 matrix
Alternative approach took:  0.736015078962
   Original approach took:  5.14679721535 LOOSER

Select 2000 smallest values from 2000 x 2000 matrix
Alternative approach took:  6.46196502191
   Original approach took:  19.2116744154 LOOSER

Select 20000 smallest values from 2000 x 2000 matrix
Alternative approach took:  7.90157398272
   Original approach took:  19.189003763 LOOSE