输出L形矩阵时避免双重遍历

发布于 01-17 11:02 字数 1432 浏览 3 评论 0原文

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

哥,最终变帅啦 2025-01-24 11:02:23

我们可以编写 initAndLast,但它对性能没有太大帮助
因为每个元素仍然需要做很多工作
结果。

我们真的希望在列表的开头工作,这样我们就可以
只需付出恒定的工作量即可获得元素。我们可以
通过使用map reverse从左到右翻转矩阵来排列它。
现在我们总是使用第一行和第一列。我们只需要
请记住在我们生产行部分时取消反转它们。

-- L shapes from top left to top right then down to bottom right
lShaped :: [[a]] -> [[a]]
lShaped = lShaped' . map reverse

-- L shapes from top right backwards to top left then down to bottom left
lShaped' :: [[a]] -> [[a]]
lShaped' [] = []
lShaped' ([]:_) = []
lShaped' (xs:xss) = (reverse xs ++ map head xss) : lShaped' (map tail xss)

我们需要两个基本情况来处理比它们高的矩形
宽并且比高度还宽 - 你的代码缺少一个
这些。

或者,我们可以尝试使用库函数而不是这样做
手动递归。

该函数沿向上倾斜的线将矩形切成两部分。 n
上/左部分第一行的长度,或者如果 n 更大
比矩形的宽度你必须把它想象成一个坐标
在定义切割右上角点的矩形之外
行,这样一些完整的行就会出现在之前的上/左部分
我们开始讨论。

slice :: Int -> [[a]] -> ([[a]], [[a]])
slice n xss = unzip (zipWith splitAt [n,n-1 ..] xss)

使用切片可以很好地分割元素的水平和
L 的垂直部分,但垂直部分没有排列成
有用的方法。我们可以再次使用切片,而不是尝试重新排列它们
对矩阵进行转置以使它们进入正确的列表。
最后我们将水平和垂直部分放在一起
zipWith (++)

lShaped'' :: [[a]] -> [[a]]
lShaped'' [] = []
lShaped'' xss = zipWith (++) rowParts (reverse colParts)
  where
    (rowParts, _) = slice width xss
    (_, colParts) = slice width (transpose xss)
    width = length (head xss)

我不知道我是否比手动递归更喜欢这个解决方案
但它就在那里。引入长度总是有点遗憾
和数字到列表算法中,但我没有看到更干净的方法
片刻。

We could write initAndLast, but it wouldn't help performance very
much because that would still be a lot of work to do for each element
of the result.

We really want to be working at the beginning of the lists so we can
get at the elements with only a constant amount of work. We can
arrange this by flipping the matrix left-to-right with map reverse.
Now we always work with the first row and column. We just have to
remember to un-reverse the row parts as we produce them.

-- L shapes from top left to top right then down to bottom right
lShaped :: [[a]] -> [[a]]
lShaped = lShaped' . map reverse

-- L shapes from top right backwards to top left then down to bottom left
lShaped' :: [[a]] -> [[a]]
lShaped' [] = []
lShaped' ([]:_) = []
lShaped' (xs:xss) = (reverse xs ++ map head xss) : lShaped' (map tail xss)

We need the two base cases to deal with rectangles taller than they are
wide as well as wider than they are tall - your code is missing one
of these.

Alternatively we could try to use library functions rather than doing
manual recursion.

This function slices a rectangle into two parts along an upward-sloping line. n is
the length of the first row of the upper/left part, or if n is greater
than the width of the rectangle you have to imagine it as a coordinate
outside the rectangle defining the top-right point of the cutting
line, so that some full rows will appear in the upper/left part before
we get down to the cut.

slice :: Int -> [[a]] -> ([[a]], [[a]])
slice n xss = unzip (zipWith splitAt [n,n-1 ..] xss)

Using slice splits up the elements nicely for the horizontal and
vertical parts of the Ls, but the vertical parts aren't arranged in a
useful way. Rather than try to rearrange them we can use slice again
on the transpose of the matrix to get them in the right lists.
Finally we put the horizontal and vertical parts together with
zipWith (++).

lShaped'' :: [[a]] -> [[a]]
lShaped'' [] = []
lShaped'' xss = zipWith (++) rowParts (reverse colParts)
  where
    (rowParts, _) = slice width xss
    (_, colParts) = slice width (transpose xss)
    width = length (head xss)

I don't know if I like this solution better than the manual recursion
but there it is. It's always a bit of a shame to introduce lengths
and numbers into a list algorithm but I don't see a cleaner way at the
moment.

无声情话 2025-01-24 11:02:23

由于表示输入矩阵有几种可能性,因此我们可以尝试将“导航”(即元素选择)与实际矩阵表示形式区分开。

为了实现这一目标,我们可以轻松地编写一个递归功能,该功能产生2D列表,从输入矩阵中提取的笛卡尔坐标列表:


{-#  LANGUAGE  TupleSections        #-}

-- returns 2D list of Cartesian coordinates for entries of L-shaped matrix:
coordList :: Int -> [[(Int,Int)]]
coordList n = go n 0 n  where   -- rl: Row Length   sr: Starting Row
    go n sr rl = ((map (sr,) [0..(rl-1)]) ++ (map (,rl-1) [(sr+1)..(n-1)]) )  :
                  if (rl > 1)  then  go n (sr+1) (rl-1)  else  []

ghci解释下检查下:

 λ> 
 λ> coordList 3
 [[(0,0),(0,1),(0,2),(1,2),(2,2)],[(1,0),(1,1),(2,1)],[(2,0)]]
 λ> 

接下来,我们测试我们的新coordList 通过幼稚使用效率低下的功能!列表提取操作员:

 λ> printAsLines xs = mapM_  (putStrLn . show)  xs
 λ> 
 λ> xss = [[1,2,3], [4,5,6], [7,8,9]]
 λ> 
 λ> printAsLines $ map (map (\(i,j) -> ((xss !! i) !! j))) $ (coordList 3)
 [1,2,3,6,9]
 [4,5,8]
 [7]
 λ> 

这可能是低效的,但这是正确的。因此,我们可以通过用向量和列表替换列表来获得更有效的版本!!等效向量的运营商!操作员:

import qualified  Data.Vector as  V

-- vector-based version:
lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse xss = 
    let
         rank   = length (head xss)  -- matrix rank
         pairs  = coordList rank     -- 2D list of Cartesian coordinates
         matrix = V.fromList (map  V.fromList  xss)  -- 2D vector
    in
         map  (map (\(i,j) -> ((matrix V.! i) V.! j)))  $  pairs

测试程序:

printAsLines :: Show α => [α] -> IO ()
printAsLines xs = mapM_  (putStrLn . show)  xs


main :: IO ()
main = do
    let  xss   = [[1,2,3], [4,5,6], [7,8,9]]
         lMat1 = lShapedTraverse  xss

    putStrLn $ "res1 = "
    printAsLines lMat1

程序输出:

res1 = 
[1,2,3,6,9]
[4,5,8]
[7]

As there are several possibilities to represent the input matrix, we can try to separate the “navigation”, i.e. choice of elements, from the actual matrix representation.

In order to achieve this, we can easily write a recursive function that produces the 2D list of Cartesian coordinates to be extracted from the input matrix:


{-#  LANGUAGE  TupleSections        #-}

-- returns 2D list of Cartesian coordinates for entries of L-shaped matrix:
coordList :: Int -> [[(Int,Int)]]
coordList n = go n 0 n  where   -- rl: Row Length   sr: Starting Row
    go n sr rl = ((map (sr,) [0..(rl-1)]) ++ (map (,rl-1) [(sr+1)..(n-1)]) )  :
                  if (rl > 1)  then  go n (sr+1) (rl-1)  else  []

Checking under the ghci interpreter:

 λ> 
 λ> coordList 3
 [[(0,0),(0,1),(0,2),(1,2),(2,2)],[(1,0),(1,1),(2,1)],[(2,0)]]
 λ> 

Next, we test our new coordList function by naïvely using the inefficient !! list extraction operator:

 λ> printAsLines xs = mapM_  (putStrLn . show)  xs
 λ> 
 λ> xss = [[1,2,3], [4,5,6], [7,8,9]]
 λ> 
 λ> printAsLines $ map (map (\(i,j) -> ((xss !! i) !! j))) $ (coordList 3)
 [1,2,3,6,9]
 [4,5,8]
 [7]
 λ> 

This might be inefficient, but it is correct. And so we can have a more efficient version of this by replacing lists by vectors and the list !! operator by the equivalent vector ! operator:

import qualified  Data.Vector as  V

-- vector-based version:
lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse xss = 
    let
         rank   = length (head xss)  -- matrix rank
         pairs  = coordList rank     -- 2D list of Cartesian coordinates
         matrix = V.fromList (map  V.fromList  xss)  -- 2D vector
    in
         map  (map (\(i,j) -> ((matrix V.! i) V.! j)))  $  pairs

Test program:

printAsLines :: Show α => [α] -> IO ()
printAsLines xs = mapM_  (putStrLn . show)  xs


main :: IO ()
main = do
    let  xss   = [[1,2,3], [4,5,6], [7,8,9]]
         lMat1 = lShapedTraverse  xss

    putStrLn $ "res1 = "
    printAsLines lMat1

Program output:

res1 = 
[1,2,3,6,9]
[4,5,8]
[7]

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文