2

如果我想右填充一个 Haskell 整数列表，我可以执行以下操作：

rpad m xs = take m $ xs ++ repeat 0

无需获取列表的长度。我认为它会非常高效。

有没有类似的方法可以定义lpad，在左侧填充列表，而不会产生计算长度等的成本？

4

4 回答 4

6

所以首先值得说的是，不要太担心性能的细节。这段代码不太可能出现在占用 80% 运行时间的代码的 20% 中。

话虽如此，性能在哪里真正重要，在这里？重要m的是小而length xs大或无限。我的意思是，如果很大的话，获得良好的性能也会很好m（就像你有的那样rpad，如果你只处理k列表的第一项，你只k为一些工作k << m），但当然问题描述要求你可能会m努力看到最好的结果。（如果您提供了一个无限列表，您需要查看m项目甚至知道是否返回0第一个元素。）

在这种情况下，您真的想要零填充take m xs而不是xs. 这就是全部技巧：

lpad m xs = replicate (m - length ys) 0 ++ ys
    where ys = take m xs
于 2015-03-19T19:44:44.713 回答
5

右填充只需要检查输入列表（或）中的第一个构造函数即可生成输出列表的第一个元素。这是一个流式操作（可以用 来完成）。:[]foldr

左填充需要检查整个输入列表以生成输出列表的第一个元素。也就是说，第一个元素是否是0取决于列表的尾部（假设它不以 开头0）。这不能以流的方式完成。O(min(m,length)) 是你能得到的最好的，仅适用于第一个元素。

m另外，要小心，因为如果您的输入列表比这长，您的填充函数会丢弃 -th 之后的元素。这可能是不需要的——有时填充被定义为只能添加元素，而不能删除。

于 2015-03-19T19:40:18.823 回答
0

这是一组（未经测试但正在编译）填充/修剪功能（Unlicence d）：

padL :: a -> Int -> [a] -> [a]
padL p s l
    | length l >= s = l
    | otherwise     = replicate (s - length l) p ++ l
{-# INLINABLE padL #-}

padR :: a -> Int -> [a] -> [a]
padR p s l = take s $ l ++ repeat p
{-# INLINABLE padR #-}

trimL :: Int -> [a] -> [a]
trimL s l
    | length l <= s = l
    | otherwise     = drop (length l - s) l
{-# INLINABLE trimL #-}

trimR :: Int -> [a] -> [a]
trimR = take
{-# INLINE trimR #-}

resizeL :: a -> Int -> [a] -> [a]
resizeL p s l
    | length l == s = l
    | length l < s  = padL p s l
    | otherwise     = trimL s l
{-# INLINABLE resizeL #-}

resizeR :: a -> Int -> [a] -> [a]
resizeR p s l
    | length l == s = l
    | length l < s  = padR p s l
    | otherwise     = trimR s l
{-# INLINABLE resizeR #-}
于 2019-04-11T02:22:29.390 回答
0

@Solomon Ucko

为什么要打length两次电话padL（其他人也一样）？怎么样

padL :: a -> Int -> [a] -> [a]
padL p s l
    | length' >= s = l
    | otherwise    = replicate (s - length') p ++ l
      where length' = length l
于 2021-01-25T18:07:23.203 回答