两个数组中查找唯一元素的Pythonic方式

Question

我有两个已排序的numpy数组，类似于这些：

x = np.array([1, 2, 8, 11, 15])
y = np.array([1, 8, 15, 17, 20, 21])

每个数组中的元素不会重复。我想要找出一种 Pythonic 的方法，来确定包含相同元素的位置的数组索引列表。

例如，在索引0 中既存在于x中又存在于y中的是1。在x中不存在于y中的2是不重要的。但是，8 在两个数组中都存在 - 在x的索引2处，而在y的索引1处。类似地，15 在两个数组中都存在，在x的索引4处，而在y的索引2处。因此，我的函数的输出将是一个列表，在这种情况下返回[[0, 0], [2, 1], [4, 2]]。

到目前为止，我正在做以下工作:

def get_indexes(x, y):
    indexes = []
    for i in range(len(x)):
        # Find index where item x[i] is in y:
        j = np.where(x[i] == y)[0]

        # If it exists, save it:
        if len(j) != 0:
            indexes.append([i, j[0]])

    return indexes

但问题在于数组x和y非常大（数百万个项目），因此需要花费相当长的时间。是否有更好的Pythonic方式来完成这件事呢？

- Néstor

---

这回答解决了您的问题吗？'in'用于两个已排序列表的最低复杂度 - Tomerikoo

嗨，@Tomerikoo，感谢您提供的指针！我认为这与我的兴趣点不同，我对“索引”感兴趣，而不仅仅是它们是否存在于两个对象中。我相信这增加了这个问题的复杂性？ - Néstor

@Tomerikoo--看起来那个链接中的所有答案都使用了显式的Python循环，这会比一些避免使用循环的答案慢。 - DarrylG

那个问题的提问者实际上提到了索引，但每个人都优雅地选择忽略它。确实不一样。我会取消我的关闭投票，但会保留评论，因为它们是相关的。 - Tomerikoo

Answer 1

不使用Python循环

代码

def get_indexes_darrylg(x, y):
    ' darrylg answer '
    # Use intersect to find common elements between two arrays
    overlap = np.intersect1d(x, y)
    
    # Indexes of common elements in each array
    loc1 = np.searchsorted(x, overlap)
    loc2 = np.searchsorted(y, overlap)
    
    # Result is the zip two 1d numpy arrays into 2d array
    return np.dstack((loc1, loc2))[0]

使用方法

x = np.array([1, 2, 8, 11, 15])
y = np.array([1, 8, 15, 17, 20, 21])
result = get_indexes_darrylg(x, y)

# result[0]: array([[0, 0],
                    [2, 1],
                    [4, 2]], dtype=int64)

发布的解决方案的时间

结果显示，darrlg代码具有最快的运行时间。

代码调整

• 将每个发布的解决方案作为一个函数。
• 轻微修改，使每个解决方案输出一个numpy数组。
• 曲线以发布者命名

代码

import numpy as np
import perfplot

def create_arr(n):
    ' Creates pair of 1d numpy arrays with half the elements equal '
    max_val = 100000     # One more than largest value in output arrays
    
    arr1 = np.random.randint(0, max_val, (n,))
    arr2 = arr1.copy()
    
    # Change half the elements in arr2
    all_indexes = np.arange(0, n, dtype=int)
    indexes = np.random.choice(all_indexes, size = n//2, replace = False) # locations to make changes
    
    
    np.put(arr2, indexes, np.random.randint(0, max_val, (n//2, )))        # assign new random values at change locations
   
    arr1 = np.sort(arr1)
    arr2 = np.sort(arr2)
    
    return (arr1, arr2)

def get_indexes_lllrnr101(x,y):
    ' lllrnr101 answer '
    ans = []
    i=0
    j=0
    while (i<len(x) and j<len(y)):
        if x[i] == y[j]:
            ans.append([i,j])
            i += 1
            j += 1
        elif (x[i]<y[j]):
            i += 1
        else:
            j += 1
    return np.array(ans)

def get_indexes_joostblack(x, y):
    'joostblack'
    indexes = []
    for idx,val in enumerate(x):
        idy = np.searchsorted(y,val)
        try:
            if y[idy]==val:
                indexes.append([idx,idy])
        except IndexError:
            continue  # ignore index errors
            
    return np.array(indexes)

def get_indexes_mustafa(x, y):
    indices_in_x = np.flatnonzero(np.isin(x, y))                 # array([0, 2, 4])
    indices_in_y = np.flatnonzero(np.isin(y, x[indices_in_x]))   # array([0, 1, 2]
    
    return np.array(list(zip(indices_in_x, indices_in_y)))

def get_indexes_darrylg(x, y):
    ' darrylg answer '
    # Use intersect to find common elements between two arrays
    overlap = np.intersect1d(x, y)
    
    # Indexes of common elements in each array
    loc1 = np.searchsorted(x, overlap)
    loc2 = np.searchsorted(y, overlap)
    
    # Result is the zip two 1d numpy arrays into 2d array
    return np.dstack((loc1, loc2))[0]

def get_indexes_akopcz(x, y):
    ' akopcz answer '
    return np.array([
        [i, j]
        for i, nr in enumerate(x)
        for j in np.where(nr == y)[0]
    ])

perfplot.show(
    setup = create_arr,  # tuple of two 1D random arrays
    kernels=[
        lambda a: get_indexes_lllrnr101(*a),
        lambda a: get_indexes_joostblack(*a),
        lambda a: get_indexes_mustafa(*a),
        lambda a: get_indexes_darrylg(*a),
        lambda a: get_indexes_akopcz(*a),
    ],
    labels=["lllrnr101", "joostblack", "mustafa", "darrylg", "akopcz"],
    n_range=[2 ** k for k in range(5, 21)],
    xlabel="Array Length",
    # More optional arguments with their default values:
    # logx="auto",  # set to True or False to force scaling
    # logy="auto",
    equality_check=None, #np.allclose,  # set to None to disable "correctness" assertion
    # show_progress=True,
    # target_time_per_measurement=1.0,
    # time_unit="s",  # set to one of ("auto", "s", "ms", "us", or "ns") to force plot units
    # relative_to=1,  # plot the timings relative to one of the measurements
    # flops=lambda n: 3*n,  # FLOPS plots
)

- DarrylG

Answer 2

你正在做的是O(nlogn)的算法，已经足够好了。
如果你想的话，你可以使用两个指针迭代两个数组来实现O(n)的算法，由于它们是有序的，所以应该增加较小对象数组的指针。
请看下面：

x = [1, 2, 8, 11, 15]
y = [1, 8, 15, 17, 20, 21]

def get_indexes(x,y):
    ans = []
    i=0
    j=0
    while (i<len(x) and j<len(y)):
        if x[i] == y[j]:
            ans.append([i,j])
            i += 1
            j += 1
        elif (x[i]<y[j]):
            i += 1
        else:
            j += 1
    return ans

print(get_indexes(x,y))

它给了我：

[[0, 0], [2, 1], [4, 2]]

- lllrnr101

Answer 3

尽管此函数将搜索y数组中所有出现的x[i]，但如果y不允许重复，它将仅找到x[i]一次。

def get_indexes(x, y):
    return [
        [i, j]
        for i, nr in enumerate(x)
        for j in np.where(nr == y)[0]
    ]

- akocz

Answer 4

你可以使用 numpy.searchsorted:

def get_indexes(x, y):
    indexes = []
    for idx,val in enumerate(x):
        idy = np.searchsorted(y,val)
        if y[idy]==val:
            indexes.append([idx,idy])
    return indexes

- joostblack

Answer 5

一个解决方案是先从 x 的角度出发，通过使用 np.isin 和 np.flatnonzero 获取它们的索引来查看包含在 y 中的值，然后从另一侧使用相同的过程；但是，与其完全给出 x，我们只提供已经找到的交集元素以节省时间。

indices_in_x = np.flatnonzero(np.isin(x, y))                 # array([0, 2, 4])
indices_in_y = np.flatnonzero(np.isin(y, x[indices_in_x]))   # array([0, 1, 2])

现在，你可以使用zip将它们压缩以得到结果：

result = list(zip(indices_in_x, indices_in_y))               # [(0, 0), (2, 1), (4, 2)]

- Mustafa Aydın