小编use*_*160的帖子

使用Python 3,我有一个包含超过100,000个字符串(list1)的列表,每个字符串最多300个字符.我还有一个包含超过900万个子串的列表(list2) - 我想计算list2中子串的元素数量.例如,

list1 = ['cat', 'caa', 'doa', 'oat']
list2 = ['at', 'ca', 'do']

我希望函数返回(映射到list2):

[2, 2, 1]

通常,这非常简单,只需要很少.但是,由于列表的大小,我有效率问题.我想找到返回该计数器列表的最快方法.

我已经尝试过列表推导,生成器,地图,各种循环,我还没有找到一种快速的方法来完成这项简单的任务.理论上什么是完成这个目标的最快方法,最好O(len(list2))是快速采取措施？

对于在函数下关闭的集合,有一种明确的方法可以将二进制递归转换为尾递归,即为Fibonacci序列添加整数:

(使用Haskell)

fib :: Int -> Int
fib n = fib' 0 1 n

fib' :: Int -> Int -> Int
fib' x y n
    | n < 1 = y  
    | otherwise = fib' y (x + y) (n - 1)

这工作,因为我们有我们的期望值y,而我们的操作,x + y其中x + y返回一个整数,就像y做.

但是,如果我想使用未在函数下关闭的集合,该怎么办？我想采用一个将列表拆分为两个列表的函数,然后对这两个列表执行相同的操作(例如递归创建二叉树),当另一个函数神奇地说明何时停止查看结果分割时,我停止:

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

那是,

splitList :: [Int] -> [[Int]]
splitList …

假设我们在Haskell中有一个简单的树创建算法:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

makeTree :: Tree Int -> Tree Int
makeTree (Node 0 l r) = Node 0 EmptyTree EmptyTree
makeTree (Node n l r) = Node n (makeTree $ newTree (n - 1))
                               (makeTree $ newTree (n - 1))
  where
    newTree n = Node n EmptyTree EmptyTree

对于非常大的数字,我们希望此算法失败并出现"堆栈大小溢出"错误.这是因为算法是二进制递归,而不是尾递归.我可以用爆炸模式(对得到的左子树"(makeTree $ NEWTREE(N - 1))"),引导二进制递归到尾递归,因为递归现在应该由于严格定向？

编辑:

事实证明,真正的问题不是树的创建,而是消耗树的功能.还有另一个用于展平树的函数,其实例如下:

import qualified Data.Foldable as F

instance F.Foldable Tree where
    foldMap f …