在字符串列表中迭代字符的最快方法是什么？

Question

我是一位有用的助手，可以为您翻译文本。

我正在遍历一个单词列表，以查找单词之间最常使用的字符（即在列表 `[hello，hank]` 中，`'h'` 计为出现两次，而`'l'` 计为出现一次）。Python 列表可正常工作，但我还在研究NumPy (dtype array?) 和 Pandas。看起来 NumPy 可能是最好的选择，但还有其他要考虑的软件包吗？还有什么方法可以使这个函数更快？

疑问中的代码：

def mostCommon(guessed, li):
    count = Counter()
    for words in li:
          for letters in set(words):
              count[letters]+=1
    return count.most_common()[:10]

感谢您的选择。

- ZtoYi

---

你能解释一下“最常见的唯一字符”是什么意思吗？并提供一些输入和输出数据的示例。 - Chris_Rands

@Chris_Rands 编辑了一个示例，请告诉我是否需要更多。 - ZtoYi

你只需要最常见的字符还是所有字符的频率？ - Chris_Rands

Answer 1

Option 1（选项1）

def pir1(li):
    sets = [set(s) for s in li]
    ul = np.array(list(set.union(*sets)))
    us = np.apply_along_axis(set, 1, ul[:, None])
    c = (sets >= us).sum(1)
    a = c.argsort()[:-11:-1]
    return ul[a]

Option 2

选项2

def pir2(li):
    return Counter(chain.from_iterable([list(set(i)) for i in li])).most_common(10)

假设有一个单词列表 li。

import pandas as pd
import numpy as np
from string import ascii_lowercase

li = pd.DataFrame(
    np.random.choice(list(ascii_lowercase), (1000, 10))
).sum(1).tolist()

包括Divakar和OP的函数

def tabulate_occurrences(a):
    chars = np.asarray(a).view('S1')
    valid_chars = chars[chars!='']
    unqchars, count = np.unique(valid_chars, return_counts=1)
    return pd.DataFrame({'char':unqchars, 'count':count})

def topNchars(a, N = 10):
    s = np.core.defchararray.lower(a).view('uint8')
    unq, count = np.unique(s[s!=0], return_counts=1)
    sidx = count.argsort()[-N:][::-1]
    h = unq[sidx]
    return [str(chr(i)) for i in h]

def mostCommon(li):
    count = Counter()
    for words in li:
          for letters in set(words):
              count[letters]+=1
    return count.most_common()[:10]

---

测试

---

import pandas as pd
import numpy as np
from string import ascii_lowercase
from timeit import timeit

results = pd.DataFrame(
    index=pd.RangeIndex(5, 405, 5, name='No. Words'),
    columns=pd.Index('pir1 pir2 mostCommon topNchars'.split(), name='Method'),
)

np.random.seed([3,1415])
for i in results.index:    
    li = pd.DataFrame(
        np.random.choice(list(ascii_lowercase), (i, 10))
    ).sum(1).tolist()
    for j in results.columns:
        v = timeit(
            '{}(li)'.format(j),
            'from __main__ import {}, li'.format(j),
            number=100
        )
        results.set_value(i, j, v)

ax = results.plot(title='Time Testing')
ax.set_ylabel('Time of 100 iterations')

- piRSquared

---

那么，最终的输出就是出现次数最多的字符，对吧？ - Divakar

@Chris_Rands / ZtoYi 是的，我看到了。正在处理中。 - piRSquared

@piRSquared，Option1似乎比我最初发布的解决方案慢，你认为它是更好的实现方式吗？至于选项2/3，我对pandas/numpy不太了解，所以我正在努力弄清楚如何仅获取字符列表，然后我会测试并告诉你加速情况！ - ZtoYi

@ZtoYi，旧答案中提到了“更好”。我现在故意省略了它。我正在继续尝试优化这些内容。 - piRSquared

@piRSquared 很棒的图表，总结了结果 :) 谢谢！ - ZtoYi

Answer 2

这是一个使用NumPy的视图概念的方法 -

def tabulate_occurrences(a):           # Case sensitive
    chars = np.asarray(a).view('S1')
    valid_chars = chars[chars!='']
    unqchars, count = np.unique(valid_chars, return_counts=1)
    return pd.DataFrame({'char':unqchars, 'count':count})

def topNchars(a, N = 10):               # Case insensitive
    s = np.core.defchararray.lower(a).view('uint8')
    unq, count = np.unique(s[s!=0], return_counts=1)
    sidx = count.argsort()[-N:][::-1]
    h = unq[sidx]
    return [str(unichr(i)) for i in h]

样例运行 -

In [322]: a = ['er', 'IS' , 'you', 'Is', 'is', 'er', 'IS']

In [323]: tabulate_occurrences(a) # Case sensitive
Out[323]: 
  char  count
0    I      3
1    S      2
2    e      2
3    i      1
4    o      1
5    r      2
6    s      2
7    u      1
8    y      1

In [533]: topNchars(a, 5)         # Case insensitive
Out[533]: ['s', 'i', 'r', 'e', 'y']

In [534]: topNchars(a, 10)        # Case insensitive
Out[534]: ['s', 'i', 'r', 'e', 'y', 'u', 'o']

- Divakar

---

嗯，我刚刚计时了一下，似乎比普通列表解决方案慢。 - ZtoYi

只需要字符即可。 - ZtoYi

@ZtoYi 另外，你只处理小写字母吗？ - Divakar

@ZtoYi 试试最新的 topNchars？ - Divakar

让我们在聊天中继续这个讨论：点击此处进入聊天室。 - ZtoYi

Answer 3

假设您只想要每个单词中仅计算一次的最常见字符：

>>> from itertools import chain
>>> l = ['hello', 'hank']
>>> chars = list(chain.from_iterable([list(set(word)) for word in l]))
>>> max(chars, key=chars.count)
'h'

使用list.count和max结合使用，由于其C级别的实现，比使用Counter更快。

- Chris_Rands

---

如果我想要下一个最常见的字母呢？ - ZtoYi

@ZtoYi 那么您可能不想使用这种方法；虽然仍然有可能，但您可以使用 heapq 或对 chars 列表进行排序，但这两种方法都会增加相当多的开销。 - Chris_Rands

Answer 4

看起来已经非常快了，而且以 O(n) 的速度运行。我唯一看到的真正改进的机会是通过将 li 分成多个部分并行化该过程。

- A. Sokol

---

这是一个O(n)问题，但我在想是否使用不同的对象可以提高速度。（例如这篇帖子https://dev59.com/8nNA5IYBdhLWcg3wWseK） - ZtoYi

Answer 5

这是一个纯Python解决方案，它独特地处理每个字符串，将集合连接起来，然后计算结果（使用Divakar的示例列表）。

>>> li=['er', 'IS' , 'you', 'Is', 'is', 'er', 'IS']
>>> Counter(e for sl in map(list, map(set, li)) for e in sl)
Counter({'I': 3, 'e': 2, 's': 2, 'S': 2, 'r': 2, 'o': 1, 'i': 1, 'u': 1, 'y': 1})

如果您希望将大写和小写字母视为同一字符：

>>> Counter(e for sl in map(list, map(set, [s.lower() for s in li])) for e in sl)
Counter({'i': 4, 's': 4, 'e': 2, 'r': 2, 'o': 1, 'u': 1, 'y': 1})

现在让我们计时：

from __future__ import print_function
from collections import Counter
import numpy as np
import pandas as pd

def dawg(li):
    return Counter(e for sl in map(list, map(set, li)) for e in sl)

def nump(a):
    chars = np.asarray(a).view('S1')
    valid_chars = chars[chars!='']
    unqchars, count = np.unique(valid_chars, return_counts=1)
    return pd.DataFrame({'char':unqchars, 'count':count})

if __name__=='__main__':
    import timeit  
    li=['er', 'IS' , 'you', 'Is', 'is', 'er', 'IS'] 
    for f in (dawg, nump):
        print("   ",f.__name__, timeit.timeit("f(li)", setup="from __main__ import f, li", number=100) )  

结果：

dawg 0.00134205818176
nump 0.0347728729248

在这种情况下，Python的解决方案明显更快。

- dawg

Answer 6

只需做

counter = Counter(''.join(li))
most_common = counter.most_common()

完成了

- blue_note