检测距离 k 处相等元素的有效函数

Question

我正在寻找一个有效的函数来查找列表中距离 k 处的相等元素。

输入示例：

v=['a','c','d','e','a','c','e','e','e','d']
k=4

期望的输出：

['a', 'c', 'e']

原因： 'a'同时在位置0和4 [4-0=k]，'c'同时在位置1和5 [5-1=k]，'e'都在位置3和 7 [7-3=k]

如果可能的话，我正在寻找比使用 for 循环逐个元素循环更有效的方法。也就是说，我正在寻找比以下更好的东西：

def dist_k(k, v):
    v_len = len(v)
    out = []
    for i in range(0,v_len,1):
        if i+k < v_len:
            if v[i] == v[i+k]:
                out.append(v[i])
    print(out)

Answer 1

编辑

我找到了一种更快的聪明方法，不需要 np.roll，并且不会将数组视为循环数组：

>>> import numpy as np
>>> v = ['a','c','d','e','a','c','e','e','e','d']
>>> v_np = np.array(v)
>>> k = 4
>>> v_init = v_np[:-k]
>>> v_init[v_init == v_np[k:]]
array(['a', 'c', 'e'])

我的想法是存储数组的开头，但没有最后 k 个元素（我不需要，因为它们后面的元素少于 k 个）。我存储数组，因为我需要它两次。

>>> v_init = v_np[:-k]
>>> v_init
array(['a', 'c', 'd', 'e', 'a', 'c'])

然后我使用没有前 k 个元素的数组的第二部分：

>>> v_np[k:]
array(['a', 'c', 'e', 'e', 'e', 'd'])

然后我可以比较两个数组：

>>> v_init == v_np[k:]
array([ True,  True, False,  True, False, False])

最后我可以从 v_init 中获取对应于索引的元素（不是从 v 中获取，因为数组的长度不匹配）：

>>> v_init[v_init == v_np[k:]]
array(['a', 'c', 'e'])

表演因为它使用 numpy（它使用 C 进行计算），所以这种方法对于大数组会更快。但是，由于转换为 numpy 数组，对于小列表，它可能会更慢（甚至不确定，请尝试解决您的问题）：

def list_comprehension(v, k):
    return [v[i] for i in range(len(v)-k) if v[i] == v[i+k]]

def using_numpy(v, k):
    v_np = np.array(v)
    v_init = v[:-k]
    return v_init[v_init == v[k:]]

>>> from timeit import timeit
>>> v = np.random.rand(100000).tolist()  # I consider that the input is a simple list
>>> timeit(lambda: list_comprehension(v,k), number=1000)
7.875344538999343
>>> timeit(lambda: using_numpy(v,k), number=1000)
3.646597085000394

原始答案，用于圆形数组

import numpy as np
v = np.array(['a','c','d','e','a','c','e','e','e','d'])
k = 4
v[v == np.roll(v,-k)]

基本上 np.roll 将数组移动 k 个元素，然后我只需将初始数组与移动后的数组进行比较，并保留它们相等的元素：

>>> np.roll(v, -k)
array(['a', 'c', 'e', 'e', 'e', 'd', 'a', 'c', 'd', 'e'])
>>> v == np.roll(v,-k)
array([ True,  True, False,  True, False, False, False, False, False,
       False])
>>> v[v == np.roll(v,-k)]
array(['a', 'c', 'e'])

请注意，此方法会将数组视为循环数组，即它会将数组的第一个值和最后一个值视为相邻的：

>>> v=np.array(['a','c','d','e','a','c','e','e','e','d', 'a'])
>>> v[v == np.roll(v,-k)]
array(['a', 'c', 'e', 'd'])

Answer 2

您可以试试下面的代码：

    v=['a','c','d','e','a','c','e','e','e','d']
    k=4 

    result = [v[i] for i in range(len(v)-k) if v[i] == v[i+k] ]

Answer 3

我不知道这是否比其他建议更有效，但这是另一种选择：

v = ['a', 'c', 'd', 'e', 'a', 'c', 'e', 'e', 'e', 'd']
k = 4
print([e for e, f in zip(v, v[k:]) if e == f])

输出：

['a', 'c', 'e']

检测距离 k 处相等元素的有效函数

Efficient function to detect equal elements at distance k

python

loops

list

编辑

原始答案，用于圆形数组