algorithm - 有哪些快速的熵计算算法

Question

private double log(double num, int base){
   return Math.log(num)/Math.log(base);
}

public double entropy(List<String> data){

    double entropy = 0.0;
    double prob = 0.0;

    if(this.iFrequency.getKeys().length==0){
        this.setInterestedFrequency(data);
    }


    String[] keys = iFrequency.getKeys();

    for(int i=0;i<keys.length;i++){

        prob = iFrequency.getPct(keys[i]);
        entropy = entropy - prob * log(prob,2);
    }

    iFrequency.clear();
    return entropy;
}

我编写了一个函数来计算数据集的熵。该功能运行良好，数学计算正确。如果我处理的是小型数据集，一切都会好起来的，但问题是我正在使用此函数来计算具有数千或数万个成员的集合的熵，并且我的算法运行缓慢。

除了我正在使用的算法之外，是否还有其他算法可用于计算集合的熵？如果没有，是否可以向我的代码添加任何优化以使其运行得更快？

我找到了 this问题，但他们并没有真正深入细节。

Answer 1

首先，您似乎构建了一个复杂度为 O(N^2) 的算法，因为您在每次调用 getPct 时重新计算计数总和。我推荐两个操作:(1) 对计数求和一次 并存储值。手动计算 prob 作为 value[i]/sum。(2) 如果将熵计算为总和 prob * Math.log(prob)，将会节省少量时间。当你全部完成后，将 一次 除以 Math.log(2)。