Python - 对数组进行排序以在其中进行搜索的最有效方法

Question

我有一个非常大的 numpy 数组，如下所示(前 5 个条目):

[[ 1.    0.01  0.02  0.6   0.01  0.5   0.01  0.5   0.5   0.5 ]
 [ 0.5   0.01  0.01  0.6   0.01  0.5   0.5   0.5   0.5   0.6 ]
 [ 0.6   0.01  0.5   0.5   0.5   0.5   0.7   0.01  0.01  0.  ]
 [ 0.01  0.5   0.8   0.02  0.02  0.81  0.01  0.77  0.02  0.01]
 [ 0.5   0.02  0.5   0.    0.5   0.5   0.01  0.6   0.01  0.  ]]

我搜索该数组以查找长度也是 10 个值的特定序列。因此，我在没有特殊规则的情况下存储传入序列，只需 0 1 2 3 ...，并且我搜索该数组也是如此。这是我的搜索方法(silo_arrays[][]是上面的数组，array_pattern[]是我搜索silo_arrays的一维numpy 10值长数组):

   new_pattern=True
   for z in range(0, self.silo_arrays_c):
    eq_rate = 0
    for y in range(0, self.length):
        if(self.silo_arrays[z][y] != array_pattern[y]):
            break
        else:
            eq_rate += 1

    if(eq_rate == self.length):
     new_pattern = False
     break

如果 silo_arrays 的长度约为 1585 个条目，则大约需要 0.006257 秒。有人知道如何通过某种排序或结构更改来加速此搜索过程吗？感谢您的支持:)

Answer 1

在数据优化方面，您经常需要权衡，而不是整体加速。

因此，在使用以下解决方案之前，请确保您了解它所带来的限制，即增加的写入时间。

一种流行的算法是实现二分搜索。如果您不熟悉这个概念:

给定一个有序的数字列表L和一个数字v，您必须检查是否 v in L 。为此，您可以将列表分成两半，然后将这两个间隔的中间值与您的值 v 进行比较。假设升序排列，您将根据以下规则选择一个间隔I:if v < L[middleindex]: I = lower_half else I = upper_half然后您可以通过重复继续搜索。这样您就可以将搜索空间减少到最低限度。

为了在项目中使用二分搜索，您需要在将数组插入数组时对其进行排序。要比较的值是按降序排列的数组元素。这样您可能会提高搜索速度。

使用二分查找的优点是在两种情况下(最坏和最好的情况)它的性能相同，即O(log n)。这使得它相当可靠。

请原谅格式设置，我在移动设备上。