考虑以下列表 short_list
和 long_list
short_list = list('aaabaaacaaadaaac')
np.random.seed([3,1415])
long_list = pd.DataFrame(
np.random.choice(list(ascii_letters),
(10000, 2))
).sum(1).tolist()
如何按唯一值计算累计计数?
我想使用 numpy 并在线性时间内完成。我希望这可以将时间与我的其他方法进行比较。用我第一个提出的解决方案来说明可能是最简单的
def pir1(l):
s = pd.Series(l)
return s.groupby(s).cumcount().tolist()
print(np.array(short_list))
print(pir1(short_list))
['a' 'a' 'a' 'b' 'a' 'a' 'a' 'c' 'a' 'a' 'a' 'd' 'a' 'a' 'a' 'c']
[0, 1, 2, 0, 3, 4, 5, 0, 6, 7, 8, 0, 9, 10, 11, 1]
我一直在折磨自己尝试使用 np.unique
,因为它会返回一个计数数组、一个逆数组和一个索引数组。我确信我可以通过这些来找到解决方案。我得到的最好的是在 pir4
下面,它以二次时间缩放。另请注意,我不关心计数是从 1 还是从 0 开始,因为我们可以简单地加或减 1。
以下是我的一些尝试(没有一个能回答我的问题)
%%cython
from collections import defaultdict
def get_generator(l):
counter = defaultdict(lambda: -1)
for i in l:
counter[i] += 1
yield counter[i]
def pir2(l):
return [i for i in get_generator(l)]
def pir3(l):
return [i for i in get_generator(l)]
def pir4(l):
unq, inv = np.unique(l, 0, 1, 0)
a = np.arange(len(unq))
matches = a[:, None] == inv
return (matches * matches.cumsum(1)).sum(0).tolist()
最佳答案
设置
short_list = np.array(list('aaabaaacaaadaaac'))
函数
dfill
获取一个数组并返回数组更改的位置并重复该索引位置直到下一次更改。# dfill # # Example with short_list # # 0 0 0 3 4 4 4 7 8 8 8 11 12 12 12 15 # [ a a a b a a a c a a a d a a a c] # # Example with short_list after sorting # # 0 0 0 0 0 0 0 0 0 0 0 0 12 13 13 15 # [ a a a a a a a a a a a a b c c d]
argunsort
返回撤消给定argsort
数组的排序所需的排列。我知道了这种方法的存在via this post. .有了这个,我可以获得argsort
数组并用它对我的数组进行排序。然后我可以撤消排序而无需再次排序。cumcount
将对一个数组进行排序,找到dfill
数组。np.arange
lessdfill
会给我累积计数。然后我取消排序# cumcount # # Example with short_list # # short_list: # [ a a a b a a a c a a a d a a a c] # # short_list.argsort(): # [ 0 1 2 4 5 6 8 9 10 12 13 14 3 7 15 11] # # Example with short_list after sorting # # short_list[short_list.argsort()]: # [ a a a a a a a a a a a a b c c d] # # dfill(short_list[short_list.argsort()]): # [ 0 0 0 0 0 0 0 0 0 0 0 0 12 13 13 15] # # np.range(short_list.size): # [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15] # # np.range(short_list.size) - # dfill(short_list[short_list.argsort()]): # [ 0 1 2 3 4 5 6 7 8 9 10 11 0 0 1 0] # # unsorted: # [ 0 1 2 0 3 4 5 0 6 7 8 0 9 10 11 1]
foo
函数由@hpaulj 推荐使用defaultdict
div
@Divakar 推荐的函数(旧的,我相信他会更新它)
代码
def dfill(a):
n = a.size
b = np.concatenate([[0], np.where(a[:-1] != a[1:])[0] + 1, [n]])
return np.arange(n)[b[:-1]].repeat(np.diff(b))
def argunsort(s):
n = s.size
u = np.empty(n, dtype=np.int64)
u[s] = np.arange(n)
return u
def cumcount(a):
n = a.size
s = a.argsort(kind='mergesort')
i = argunsort(s)
b = a[s]
return (np.arange(n) - dfill(b))[i]
def foo(l):
n = len(l)
r = np.empty(n, dtype=np.int64)
counter = defaultdict(int)
for i in range(n):
counter[l[i]] += 1
r[i] = counter[l[i]]
return r - 1
def div(l):
a = np.unique(l, return_counts=1)[1]
idx = a.cumsum()
id_arr = np.ones(idx[-1],dtype=int)
id_arr[0] = 0
id_arr[idx[:-1]] = -a[:-1]+1
rng = id_arr.cumsum()
return rng[argunsort(np.argsort(l))]
演示
cumcount(short_list)
array([ 0, 1, 2, 0, 3, 4, 5, 0, 6, 7, 8, 0, 9, 10, 11, 1])
时间测试
代码
functions = pd.Index(['cumcount', 'foo', 'foo2', 'div'], name='function')
lengths = pd.RangeIndex(100, 1100, 100, 'array length')
results = pd.DataFrame(index=lengths, columns=functions)
from string import ascii_letters
for i in lengths:
a = np.random.choice(list(ascii_letters), i)
for j in functions:
results.set_value(
i, j,
timeit(
'{}(a)'.format(j),
'from __main__ import a, {}'.format(j),
number=1000
)
)
results.plot()
关于python - 如何使用 numpy 在线性时间内通过唯一值获取累积计数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40602269/