8

我需要一个函数，它接受一个列表，如果存在则返回唯一元素，如果不存在则返回 []。如果存在许多独特的元素，它应该返回第一个（不要浪费时间去寻找其他元素）。此外，我知道列表中的所有元素都来自（小且已知的）集合 A。例如，此函数为 Ints 完成工作：

unique :: Ord a => [a] -> [a]
unique li = first $ filter ((==1).length) ((group.sort) li)
    where first [] = []
          first (x:xs) = x

ghci> unique [3,5,6,8,3,9,3,5,6,9,3,5,6,9,1,5,6,8,9,5,6,8,9]
ghci> [1]

然而，这还不够好，因为它涉及排序（n log n），而它可以在线性时间内完成（因为 A 很小）。此外，它要求列表元素的类型是 Ord，而所有应该需要的是 Eq。如果比较的数量越少越好（即，如果我们遍历一个列表并遇到元素 el 两次，我们不会测试后续元素是否与 el 相等）

这就是为什么例如：计算列表中的唯一元素并不能解决问题 - 所有答案都涉及排序或遍历整个列表以查找所有元素的计数。

问题是：如何在 Haskell 中正确有效地做到这一点？

4

6 回答 6

12

好的，线性时间，来自有限域。运行时间将为O((m + d) log d)，其中m是列表的大小，d是域的大小，当d固定时，它是线性的。我的计划是使用集合的元素作为trie的键，计数作为值，然后在 trie 中查找计数为 1 的元素。

import qualified Data.IntTrie as IntTrie
import Data.List (foldl')
import Control.Applicative

计算每个元素。这将遍历列表一次，使用结果（ O(m log d) ）构建一个 trie ，然后返回一个在 trie 中查找结果的函数（运行时间为O(log d)）。

counts :: (Enum a) => [a] -> (a -> Int)
counts xs = IntTrie.apply (foldl' insert (pure 0) xs) . fromEnum
    where
    insert t x = IntTrie.modify' (fromEnum x) (+1) t

我们使用Enum约束将类型的值转换a为整数，以便在 trie 中对它们进行索引。一个Enum实例是您假设的见证的一部分，它a是一个小的有限集（Bounded将是另一部分，但见下文）。

然后寻找那些独一无二的。 

uniques :: (Eq a, Enum a) => [a] -> [a] -> [a]
uniques dom xs = filter (\x -> cts x == 1) dom
    where
    cts = counts xs

该函数将整个域的枚举作为其第一个参数。我们本可以需要一个Bounded a约束并[minBound..maxBound]改为使用它，这在语义上对我很有吸引力，因为有限本质上是Enum+ Bounded，但是非常不灵活，因为现在需要在编译时知道域。所以我会选择这个稍微难看但更灵活的变体。

uniques遍历域一次（懒惰，所以head . uniques dom只会遍历它需要找到第一个唯一元素 - 不是在列表中，而是在 中dom），对于运行我们建立的查找函数的每个元素是O(log d )，所以过滤器需要O(d log d)，构建计数表需要O(m log d)。所以uniques在O((m + d) log d)中运行，当d固定时它是线性的。至少需要Ω(m log d)才能从中获取任何信息，因为它必须遍历整个列表才能构建表格（您必须一直到列表末尾才能查看元素是否为重复，所以你不能做得比这更好）。

于 2013-04-18T08:37:31.587 回答
6

真的没有任何方法可以有效地做到这一点Eq。您需要使用一些效率低得多的方法来构建相等元素的组，并且如果不扫描整个列表，您将无法知道仅存在一个特定元素。

另外，请注意，为了避免无用的比较，您需要一种方法来检查之前是否遇到过某个元素，而唯一的方法是拥有一个已知多次出现的元素列表，并且唯一的检查当前元素是否在该列表中的方法是...将其与每个元素进行比较。

如果您希望它比 O（非常可怕的东西）更快地工作，您需要该Ord约束。

好的，根据评论中的澄清，这是我认为您正在寻找的一个快速而肮脏的示例：

unique [] _ _ = Nothing
unique _ [] [] = Nothing
unique _ (r:_) [] = Just r
unique candidates results (x:xs)
    | x `notElem` candidates = unique candidates results xs
    | x `elem` results       = unique (delete x candidates) (delete x results) xs
    | otherwise              = unique candidates (x:results) xs

第一个参数是候选列表，最初应该是所有可能的元素。第二个参数是可能的结果列表，最初应该是空的。第三个参数是要检查的列表。

如果它用完了候选者，或者到达列表末尾但没有结果，则返回Nothing. 如果它到达结果列表的末尾，则返回结果列表前面的那个。

否则，它会检查下一个输入元素：如果它不是候选元素，则忽略它并继续。如果它在结果列表中我们已经看到了两次，那么将其从结果和候选列表中删除并继续。否则，将其添加到结果中并继续。

不幸的是，这仍然必须扫描整个列表以获取单个结果，因为这是确保它实际上是唯一的唯一方法。

于 2013-04-17T22:42:30.780 回答
2

首先，如果您的函数旨在最多返回一个元素，则几乎可以肯定使用Maybe a而不是[a]返回结果。

其次，至少，您别无选择，只能遍历整个列表：在查看所有其他元素之前，您无法确定任何给定元素是否真的是唯一的。

如果您的元素没有Ord经过验证，但只能进行质量测试Eq，那么您确实没有比以下更好的选择：

firstUnique (x:xs)
  | elem x xs = firstUnique (filter (/= x) xs)
  | otherwise = Just x
firstUnique [] = Nothing

请注意，如果您不想，则不需要过滤掉重复的元素——最坏的情况是二次的。

编辑：

由于上述小/已知的一组可能元素，上述内容错过了提前退出的可能性。但是，请注意，最坏​​的情况仍然需要遍历整个列表：所需要的只是使这些可能元素中的至少一个从列表中丢失......

但是，在集合耗尽的情况下提供早期退出的实现：

firstUnique = f [] [<small/known set of possible elements>] where
  f [] [] _ = Nothing  -- early out
  f uniques noshows (x:xs)
    | elem x uniques = f (delete x uniques) noshows xs
    | elem x noshows = f (x:uniques) (delete x noshows) xs
    | otherwise      = f uniques noshows xs
  f []    _ [] = Nothing
  f (u:_) _ [] = Just u

请注意，如果您的列表包含不应该存在的元素（因为它们不在小/已知集合中），它们将被上面的代码明确忽略......

于 2013-04-17T22:58:37.317 回答
2

正如其他人所说，没有任何额外的约束，你不能在小于二次的时间内做到这一点，因为如果不了解元素，你就无法将它们保存在某种合理的数据结构中。

如果我们能够比较元素，一个明显的O(n log n)解决方案首先计算元素的计数，然后找到第一个计数等于 1 的元素：

import Data.List (foldl', find)
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Maybe (fromMaybe)

count :: (Ord a) => Map a Int -> a -> Int
count m x = fromMaybe 0 $ Map.lookup x m

add :: (Ord a) => Map a Int -> a -> Map a Int
add m x = Map.insertWith (+) x 1 m

uniq :: (Ord a) => [a] -> Maybe a
uniq xs = find (\x -> count cs x == 1) xs
  where
    cs = foldl' add Map.empty xs

请注意，log n因子来自我们需要对Map大小为n的 a 进行操作的事实。如果列表只有k个唯一元素，那么我们的地图大小最多为k，因此整体复杂度仅为O(n log k)。

但是，我们可以做得更好——我们可以使用哈希表而不是映射来获得O(n)解决方案。为此，我们需要STmonad 在哈希映射上执行可变操作，并且我们的元素必须是Hashable。ST解决方案与以前基本相同，只是由于在monad中工作而稍微复杂一点：

import Control.Monad
import Control.Monad.ST
import Data.Hashable
import qualified Data.HashTable.ST.Basic as HT
import Data.Maybe (fromMaybe)

count :: (Eq a, Hashable a) => HT.HashTable s a Int -> a -> ST s Int
count ht x = liftM (fromMaybe 0) (HT.lookup ht x)

add :: (Eq a, Hashable a) => HT.HashTable s a Int -> a -> ST s ()
add ht x = count ht x >>= HT.insert ht x . (+ 1)

uniq :: (Eq a, Hashable a) => [a] -> Maybe a
uniq xs = runST $ do
    -- Count all elements into a hash table:
    ht <- HT.newSized (length xs)
    forM_ xs (add ht)
    -- Find the first one with count 1
    first (\x -> liftM (== 1) (count ht x)) xs


-- Monadic variant of find which exists once an element is found.
first :: (Monad m) => (a -> m Bool) -> [a] -> m (Maybe a)
first p = f
  where
    f []        = return Nothing
    f (x:xs')   = do
        b <- p x
        if b then return (Just x)
             else f xs'

笔记：

  • 如果您知道列表中只有少量不同的元素，您可以使用HT.new代替HT.newSized (length xs). 这将为您节省一些内存和一次通过，xs但在许多不同元素的情况下，哈希表将不得不调整几次。
于 2013-04-18T07:52:02.260 回答
1

这是一个可以解决问题的版本：

unique :: Eq a => [a] -> [a]
unique =  select . collect []
  where
    collect acc []              = acc
    collect acc (x : xs)        = collect (insert x acc) xs

    insert x []                 = [[x]]
    insert x (ys@(y : _) : yss) 
      | x == y                  = (x : ys) : yss
      | otherwise               = ys : insert x yss

    select []                   = []
    select ([x] : _)            = [x]
    select ((_ : _) : xss)      = select xss

因此，首先我们遍历输入列表 ( collect)，同时维护我们更新的相等元素的桶列表insert。然后我们只需选择出现在单例桶 ( select) 中的第一个元素。

坏消息是这需要二次时间：对于每个访问过collect的元素，我们需要遍历桶列表。恐怕这是您必须为只能将元素类型限制为 in 所付出的代价Eq。

于 2013-04-18T03:10:21.150 回答
0

像这样的东西看起来很不错。 

unique = fst . foldl' (\(a, b) c -> if (c `elem` b) 
                                    then (a, b) 
                                    else if (c `elem` a) 
                                         then (delete c a, c:b) 
                                         else (c:a, b)) ([],[])

折叠的结果元组的第一个元素包含您所期望的，一个包含唯一元素的列表。元组的第二个元素是一个元素是否已经被丢弃时所记住的进程的内存。

关于空间表现。
由于您的问题是设计，因此在显示结果之前，应至少遍历列表的所有元素一次。并且内部算法除了对好的值外，还必须对丢弃的值进行跟踪，但丢弃的值只会出现一次。那么在最坏的情况下，所需的内存量等于输入列表的大小。正如你所说的这种声音商品预期的投入很小。

关于时间表现。
由于预期输入很小且默认未排序，因此尝试将列表排序到算法中是无用的，或者在应用之前是无用的。事实上，我们几乎可以静态地说，将元素放置在其有序位置（放入子列表a和b元组中(a,b)）的额外操作将花费与检查该元素是否出现在列表中相同的时间。

下面是一个更好、更明确的 foldl' 版本。 

import Data.List (foldl', delete, elem)

unique :: Eq a => [a] -> [a]
unique = fst . foldl' algorithm ([], []) 
  where 
    algorithm (result0, memory0) current = 
         if (current `elem` memory0)
         then (result0, memory0)
         else if (current`elem` result0)
              then (delete current result0, memory) 
              else (result, memory0) 
            where
                result = current : result0
                memory = current : memory0

在嵌套if ... then ... else ...指令中，列表result在最坏的情况下被遍历两次，这可以避免使用以下辅助函数。

unique' :: Eq a => [a] -> [a]
unique' = fst . foldl' algorithm ([], []) 
  where 
    algorithm (result, memory) current = 
         if (current `elem` memory)
         then (result, memory)
         else helper current result memory []
            where
               helper current [] [] acc = ([current], [])
               helper current [] memory acc = (acc, memory)
               helper current (r:rs) memory acc 
                   | current == r    = (acc ++ rs, current:memory) 
                   | otherwise = helper current rs memory (r:acc)

但是可以使用 fold 重写助手，如下所示，这绝对更好。 

helper current [] _ = ([current],[])
helper current memory result = 
    foldl' (\(r, m) x -> if x==current 
                         then (r, current:m) 
                         else (current:r, m)) ([], memory) $ result
于 2013-04-17T22:58:04.983 回答