Haskell中的熵计算函数

Question

我用Haskell编写了一个函数来计算集合的熵。我想了解如何重写该函数，使其更加灵活/可重用，以及如何对该函数进行分析，以及如何对其进行调优和/或修改，以获得更好的性能。

import Data.List (foldl1')

entropy :: [Int] -> Int -> Int -> Double
entropy itemFrequencies totalElements logarithmicBase =
  -(foldl1' (+) $ map (\p -> p * (logBase b p)) probabilities)
    where
      is = map fromIntegral itemFrequencies
      l  = fromIntegral totalElements
      b  = fromIntegral logarithmicBase
      probabilities = map (\i -> i / l) $ is

在某些背景下，熵计算是构建决策树的核心函数。对于更复杂的数据集和决策树，该函数将经常被调用。我正在研究ID3算法的顺序实现，这个熵函数是该算法的一部分，稍后我将并行/并发作为一个单独的练习，然后我还将编写ID3's后代的实现: C4.5和C5.0。

请尊重我自己在重写代码的并发性/并行性方面所做的斗争的愿望，我只对我可以为性能所做的任何顺序改进和任何可以使代码更易于维护和重用的重构感兴趣。

Answer 1

通用代码评审

首先，您的功能与我建议的更改(entropy')并排进行.

import Data.List (foldl1', foldl')

entropy :: [Int] -> Int -> Int -> Double
entropy itemFrequencies totalElements logarithmicBase =
  -(foldl1' (+) $ map (\p -> p * (logBase b p)) probabilities)
    where
      is = map fromIntegral itemFrequencies
      l  = fromIntegral totalElements
      b  = fromIntegral logarithmicBase
      probabilities = map (\i -> i / l) $ is

entropy' :: (Foldable f, Integral a, Floating b) => a -> a -> f a -> b
entropy' totalElems base =
  negate . foldl' (\ent f2 -> ent + freqEntropy f2) 0
  where
    freqEntropy f = let p = (fromIntegral f) / l
                    in  p * logBase b p
    l             = fromIntegral totalElems
    b             = fromIntegral base

我的评论是武断的：

1. 你为什么要使用foldl1'？从性能角度使用foldl'是有意义的，但我不清楚为什么需要一个非空列表。也许使用Maybe来封装这种失败的可能性，或者概述为什么您希望在注释中出现一个非空列表。最好保持对部分函数所在位置的跟踪，以避免在运行时出现意外。我的函数只对空Foldable返回0。
2. 如果您希望Int和Double更灵活/更可重用，您的类型可以被更广泛地概括。为了找到这些类型，我所做的就是跟踪您正在使用的函数，并找出它们的类型(这些函数比Int、Double或[]更通用)。然后，我将整个函数分解为它最一般的类型。这是必要的还是有用的取决于您的应用程序。我认为这里最有用的概括是Foldable，如果您想要计算不是列表的事物的熵。
3. 当我改为泛化为Foldable时，我将所有的maps都卷到了foldl'中。如果编译器不结合maps，这可能会更有表现力，但理解起来也有点复杂。
4. 我将itemFrequencies移到最后一个参数，这样我就可以编写这个函数了。Pointfree有点可爱，但如果您认为它更易读，您可以更改顺序和/或将显式itemFrequencies放回。
5. 我向negate添加了一个显式调用(我最初不了解-(foldl1' ...)是怎么回事)。
6. 我把名字缩短了，这样事情就不会太长或太冗长了。这只是我个人的品味。我认为，如果要使用描述性较长的变量名，就不应该省略对临时变量的描述。我认为b是可以的，因为它是一个基本变量，但是我建议使用类似len而不是l和itemFreqs'来代替is。

性能和分析

在这方面我真的帮不了你。GHC确实有一个轮廓仪，如果您想要进行一些严肃的分析，这可能很有用。