numpy数组中非连续元素的距离

Question

使用 numpy 或 itertools，有没有什么高效的方法来计算到下一个不连续元素的距离呢？

> import numpy as np 
> a=np.array(['a','b','b','c','d','a','b','b','c','c','c','d'])

我希望输出结果是这样的。

[1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1]

进一步说，我想知道到两个新元素的距离。预期的输出应该是

[3, 3, 2, 2, 2, 3, 5, 4]

因为在 a 后面的两个新元素是 b（两个）和 c，依此类推。

编辑 1 我有两个版本来寻找下一个新元素：

import numpy as np                                                           
a = np.array(['a', 'b', 'b', 'c', 'd', 'a', 'b', 'b', 'c', 'c', 'c', 'd'])  

# Using numpy
u, idx = np.unique(a, return_inverse=True)                                                      
idx = np.diff(idx)                                                      
idx[idx < 0] = 1
idx[idx > 1] = 1 
count = 1
while 0 in idx:                                                                    
    idx[np.diff(idx) == count] = count+1
    count += 1                                                                                  │                                                                                           
print idx  

# Using loop
oldElement = a[0]
dist = []
count = 1
for elm in a[1:]:
    if elm == oldElement:
        count += 1
    else:
        dist.extend(range(count, 0, -1))
        count = 1
        oldElement = elm
print dist

不过，这种方法不能简单地扩展到寻找两个新元素。

Answer 1

这是我对一个元素距离的尝试。

import numpy as np
a=np.array(['a','b','b','c','d','a','b','b','c','c','c','d'])
out = []
for i in range(len(a)):
    count = 0
    for j in range(len(a) - i):
        if a[i] != a[j+i]:
            out.append(count)
            break
        else:
            count += 1

结果

>>> out
[1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1]

Answer 2

这里有个想法，如果独特元素不太多的话，可以考虑把这个过程变得更高效。这个方法可能不够通用，只能解决你提到的序列 a 的问题 :)（我试着调整数组，直到它能正常工作）。最后的那个循环应该是可以优化的地方：

import numpy as np
a = np.array(['a','b','b','c','d','a','b','b','c','c','c','d'])

aa = a[:, np.newaxis] == np.unique(a)
aaa = np.cumsum(aa[::-1], axis=0)[::-1] * aa

# this is where it gets messy

negative_jump = True
while negative_jump:
    d = np.diff(aaa, axis=0)
    correction = (d + 1) * (d < -1)
    negative_jump = (correction != 0).any()
    aaa[:-1] += correction
result = aaa[:-1].sum(axis=1)

解释一下：在循环开始之前，看看 aaa。它会包含一些离0很远的数字。在这种数据的处理方式中，从一行跳到另一行时，减少的值永远不能小于 < -1。如果小于这个值，说明上面的数字太大了。这个循环会不断减少这个数字，直到它变成 -1 或 0。再次强调，这个方法并不是最优的，肯定还有更好的办法。

Answer 3

很遗憾，我没有找到一个使用numpy或向量化的方法来解决这个一般问题。

这里有一个通用解决方案，适用于任何深度。你问题的第一部分对应的是深度=1，第二部分对应的是深度=2。这个解决方案同样适用于更高的深度。

显然，如果你只想解决深度=1的情况，可以找到一个简单得多的解决方案。不过，对于这个问题来说，通用性会增加一些复杂性。

from itertools import groupby, chain, izip

ilen = lambda it: sum(1 for dummy in it)

def get_squeezed_counts(a):
    """
    squeeze a sequence to a sequnce of value/count.
    E.g. ['a', 'a', 'a', 'b'] --> [['a',3], ['b',1]]
    """
    return [ [ v, ilen(it) ] for v, it in groupby(a) ]

def get_element_dist(counts, index, depth):
    """
    For a given index in a "squeezed" list, return the distance (in the
    original-array) with a given depth, or None.
    E.g.
    get_element_dist([['a',1],['b',2],['c',1]], 0, depth=1) --> 1     # from a to first b
    get_element_dist([['a',1],['b',2],['c',1]], 1, depth=1) --> 2     # from first b to c
    get_element_dist([['a',1],['b',2],['c',1]], 0, depth=2) --> 3     # from a to c
    get_element_dist([['a',1],['b',2],['c',1]], 1, depth=2) --> None  # from first b to end of sequence
    """
    seen = set()
    sum_counts = 0
    for i in xrange(index, len(counts)):
        v, count = counts[i]
        seen.add(v)
        if len(seen) > depth:
            return sum_counts
        sum_counts += count
    # reached end of sequence before finding the next value
    return None

def get_squeezed_dists(counts, depth):
    """
    Construct a per-squeezed-element distance list, by calling get_element_dist()
    for each element in counts.
    E.g.
    get_squeezed_dists([['a',1],['b',2],['c',1]], depth=1) --> [1,2,None]
    """
    return [ get_element_dist(counts, i, depth=depth) for i in xrange(len(counts)) ]

def get_dists(a, depth):
    counts = get_squeezed_counts(a)
    squeezed_dists = get_squeezed_dists(counts, depth=depth)
    # "Unpack" squeezed dists:
    return list(chain.from_iterable(
        xrange(dist, dist-count, -1)
        for (v, count), dist in izip(counts, squeezed_dists)
        if dist is not None
    ))

print get_dists(['a','b','b','c','d','a','b','b','c','c','c','d'], depth = 1)
# => [1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1]
print get_dists(['a','a','a'], depth = 1)
# => []
print get_dists(['a','b','b','c','d','a','b','b','c','c','c','d'], depth = 2)
# => [3, 3, 2, 2, 2, 3, 5, 4]
print get_dists(['a','b','a', 'b'], depth = 2)
# => []

在python3中，把xrange->range和izip->zip替换掉。