Data.STM.LinkedList实现

问题描述 投票：1回答：1

我正在寻找Data.STM.LinkedList实现以获取高性能的链接列表。查看文档，长度函数在O（n）中运行-为什么？在O（1）中实现它是否有任何实际问题？

这里是源代码https://hackage.haskell.org/package/stm-linkedlist-0.1.0.0/docs/src/Data-STM-LinkedList-Internal.html#length

是否可以在O（1）中实现它？我是Haskell的新手，所以我不确定保存有关该列表的某些元数据是否有问题。

谢谢！

haskell doubly-linked-list
1个回答
0
投票

近似起见，Haskell是一种充分表达的语言，以另一种通用语言实现的算法也可以在Haskell中实现，同时保留渐近性能特征。 （这是一个非常低的标准。大多数通用语言都具有这种表现力。）

特别是，尽管Haskell最自然地支持不可变数据结构，但它对可变数据具有足够的支持，因此可变数据结构及其算法通常可以相当直接地转换为Haskell代码。可能会有一些开销（通常是相当大的开销），并且可变数据结构使用起来要比它们的不可变表亲笨拙得多，但仍然可能。

不过，实际上，要匹配不可变数据结构的C ++实现的actual（相对于渐近）性能，即使不是不可能，也可能会极其困难。达到C ++性能的2-3倍之内是合理的，而达到5-10倍的性能则很容易（见下文）。但是，如果您需要匹配C ++性能，则最好用C ++编写高性能的变异代码，并使用FFI（外部函数接口）与该代码进行接口。

无论如何，带有O（1）length的“中等性能”双链表肯定是可能的，并且维护可变的全表元数据没有根本的困难。 stm-linkedlist不提供O（1）length的原因可能与C ++仅保证O（n）std::list<>::size性能before C++11的原因相同。即，双链表的许多实际用途都不需要调用length / size，并且提供O（1）性能会带来额外的簿记成本。

作为概念证明，以下数据类型足以实现具有O（1）长度函数的完全可变的双向链表。在此，以下划线结尾的类型和标识符仅供内部使用。该列表的指针严格（因此没有无限列表！），但其值却是惰性的。

data List a = List
  { headNode_ :: !(IORef (Node_ a))
  , length_ :: !(IORef Int) }
data Node_ a = Node_
  { prev_ :: !(IORef (Node_ a))
  , next_ :: !(IORef (Node_ a))
  , value_ :: a }

List类型包含指向不完整IORef的指针（即headNode），该指针指向列表的开头和结尾（或指向空列表本身），但具有未定义的值字段。这使其成为不安全的节点值，因此最终用户绝对不能直接访问它。 List还包含一个指向列表长度值的指针。

附加类型Node（无下划线）用于用其对应的列表装饰节点指针（如注释中的“迭代器”，以使列表元数据可用于需要它的函数：

data Node a = Node
  { node_ :: !(IORef (Node_ a))
  , list_ :: !(List a) }

请注意，List和Node是用于使用列表的面向用户的数据类型。

您像这样创建empty列表：

empty :: IO (List a)
empty = mdo
  n <- newIORef (Node_ n n undefined)
  List n <$> newIORef 0

在给定节点之前和之后的插入操作如下。这是不安全的头节点表示的回报，因为该算法可以将列表开头和结尾处的插入视为头节点与实际列表节点之间插入的特殊情况。

insertBefore :: a -> Node a -> IO (Node a)
insertBefore x Node{node_=rnode2, list_} = do
  Node_{prev_=rnode1} <- readIORef rnode2
  insertBetween_ x list_ rnode1 rnode2

insertAfter :: a -> Node a -> IO (Node a)
insertAfter x Node{node_=rnode1, list_} = do
  Node_{next_=rnode2} <- readIORef rnode1
  insertBetween_ x list_ rnode1 rnode2

insertBetween_ :: a -> List a -> IORef (Node_ a) -> IORef (Node_ a) -> IO (Node a)
insertBetween_ x l rnode1 rnode2 = do
  modifyIORef' (length_ l) succ
  newnode <- newIORef (Node_ rnode1 rnode2 x)
  modifyIORef' rnode1 (\n -> n{next_=newnode})
  modifyIORef' rnode2 (\n -> n{prev_=newnode})
  return $ Node newnode l

由于不允许用户“拥有”头节点，因此我们需要在列表的开头和结尾处插入其他面向用户的功能：

prepend :: a -> List a -> IO (Node a)
prepend x l = insertAfter x (Node (headNode_ l) l)

append :: a -> List a -> IO (Node a)
append x l = insertBefore x (Node (headNode_ l) l)

观察到所有插入都通过insertBetween_，这会增加长度值。

删除既简单又统一，无论是内部节点还是开始或结束节点。所有删除都通过此delete函数，该函数负责减小长度值。

delete :: Node a -> IO ()
delete Node{node_,list_} = do
  modifyIORef' (length_ list_) pred
  Node_{next_, prev_} <- readIORef node_
  modifyIORef' prev_ (\n -> n{next_=next_})
  modifyIORef' next_ (\n -> n{prev_=prev_})

删除头节点将是一场灾难，但是不允许用户使用这样的Node，所以我们很安全。

如果用户有Node，则可以在列表中来回移动：

prev :: Node a -> IO (Maybe (Node a))
prev Node{node_, list_} = do
  Node_{prev_} <- readIORef node_
  return $ maybeNode_ prev_ list_

next :: Node a -> IO (Maybe (Node a))
next Node{node_, list_} = do
  Node_{next_} <- readIORef node_
  return $ maybeNode_ next_ list_

maybeNode_ :: IORef (Node_ a) -> List a -> Maybe (Node a)
maybeNode_ n l =
  if n == headNode_ l
  then Nothing
  else Just (Node n l)

请注意，我们绝对不要给用户头节点，因此maybeNode_在此进行检查并返回Nothing。

[开始，用户可以使用以下功能（在禁止的头节点上使用List或prev）获得next的开头或结尾：

start :: List a -> IO (Maybe (Node a))
start l = next $ Node (headNode_ l) l

end :: List a -> IO (Maybe (Node a))
end l = prev $ Node (headNode_ l) l

缺少的只是一些其他查询功能：

value :: Node a -> IO a
value = fmap value_ . readIORef . node_

null :: List a -> IO Bool
null l = (==0) <$> length l

length :: List a -> IO Int
length = readIORef . length_

一些可转换为纯列表的实用程序：

toList :: List a -> IO [a]
toList = toList_ next_

toListRev :: List a -> IO [a]
toListRev = toList_ prev_

toList_ :: (Node_ a -> IORef (Node_ a)) -> List a -> IO [a]
toList_ dir l = go =<< readIORef h
  where h = headNode_ l
        go n = do
          if dir n == h then return []
            else do
            n' <- readIORef (dir n)
            (value_ n':) <$> go n'

和用于调试的Show实例：

instance (Show a) => Show (List a) where
  showsPrec d lst = showParen (d > 10) $ showString "fromList " . showsPrec 11 (unsafePerformIO $ toList lst)

而且，由于我们可以删除和重新插入，虽​​然不是严格必需的，但是如果没有就地修改元素，就不会有任何自重的可变结构：

modify :: (a -> a) -> Node a -> IO ()
modify f Node{node_} = modifyIORef' node_ (\n -> n { value_ = f (value_ n) })

这是完整的代码。 （有关用法的示例，请参见定义ex1。）欢迎您将其用作自己的实现的起点。它未经测试且没有基准测试，除了一些快速测试表明它可能比C ++实现慢大约5-10倍。

{-# LANGUAGE NamedFieldPuns, RecursiveDo #-}

module LinkedList
  ( List, Node
  , value, null, length
  , empty, prepend, append, insertBefore, insertAfter, delete, modify
  , prev, next, start, end
  , toList, toListRev
  ) where

import System.IO.Unsafe
import Control.Monad
import Prelude hiding (null, length)

import Data.IORef

data List a = List
  { headNode_ :: !(IORef (Node_ a))
  , length_ :: !(IORef Int) }
data Node a = Node
  { node_ :: !(IORef (Node_ a))
  , list_ :: !(List a) }
data Node_ a = Node_
  { prev_ :: !(IORef (Node_ a))
  , next_ :: !(IORef (Node_ a))
  , value_ :: a }

instance (Show a) => Show (List a) where
  showsPrec d lst = showParen (d > 10) $ showString "fromList " . showsPrec 11 (unsafePerformIO $ toList lst)

value :: Node a -> IO a
value = fmap value_ . readIORef . node_

null :: List a -> IO Bool
null l = (==0) <$> length l

length :: List a -> IO Int
length = readIORef . length_

empty :: IO (List a)
empty = mdo
  n <- newIORef (Node_ n n undefined)
  List n <$> newIORef 0

prepend :: a -> List a -> IO (Node a)
prepend x l = insertAfter x (Node (headNode_ l) l)

append :: a -> List a -> IO (Node a)
append x l = insertBefore x (Node (headNode_ l) l)

insertBefore :: a -> Node a -> IO (Node a)
insertBefore x Node{node_=rnode2, list_} = do
  Node_{prev_=rnode1} <- readIORef rnode2
  insertBetween_ x list_ rnode1 rnode2

insertAfter :: a -> Node a -> IO (Node a)
insertAfter x Node{node_=rnode1, list_} = do
  Node_{next_=rnode2} <- readIORef rnode1
  insertBetween_ x list_ rnode1 rnode2

insertBetween_ :: a -> List a -> IORef (Node_ a) -> IORef (Node_ a) -> IO (Node a)
insertBetween_ x l rnode1 rnode2 = do
  modifyIORef' (length_ l) succ
  newnode <- newIORef (Node_ rnode1 rnode2 x)
  modifyIORef' rnode1 (\n -> n{next_=newnode})
  modifyIORef' rnode2 (\n -> n{prev_=newnode})
  return $ Node newnode l

delete :: Node a -> IO ()
delete Node{node_,list_} = do
  modifyIORef' (length_ list_) pred
  Node_{next_, prev_} <- readIORef node_
  modifyIORef' prev_ (\n -> n{next_=next_})
  modifyIORef' next_ (\n -> n{prev_=prev_})

modify :: (a -> a) -> Node a -> IO ()
modify f Node{node_} = modifyIORef' node_ (\n -> n { value_ = f (value_ n) })

prev :: Node a -> IO (Maybe (Node a))
prev Node{node_, list_} = do
  Node_{prev_} <- readIORef node_
  return $ maybeNode_ prev_ list_

next :: Node a -> IO (Maybe (Node a))
next Node{node_, list_} = do
  Node_{next_} <- readIORef node_
  return $ maybeNode_ next_ list_

maybeNode_ :: IORef (Node_ a) -> List a -> Maybe (Node a)
maybeNode_ n l =
  if n == headNode_ l
  then Nothing
  else Just (Node n l)

start :: List a -> IO (Maybe (Node a))
start l = next $ Node (headNode_ l) l

end :: List a -> IO (Maybe (Node a))
end l = prev $ Node (headNode_ l) l

toList :: List a -> IO [a]
toList = toList_ next_

toListRev :: List a -> IO [a]
toListRev = toList_ prev_

toList_ :: (Node_ a -> IORef (Node_ a)) -> List a -> IO [a]
toList_ dir l = go =<< readIORef h
  where h = headNode_ l
        go n = do
          if dir n == h then return []
            else do
            n' <- readIORef (dir n)
            (value_ n':) <$> go n'

ex1 :: IO (List Int)
ex1 = do
  t <- empty
  mapM_ (flip prepend t) [10,9..1]
  mapM_ (flip append t) [11..20]
  return t
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.