在python中实现Flajolet和Martin's Algorithm

Question

以下是我编写的实现Flajolet and Martin’s Algorithm的代码。我使用Jenkins hash function生成了32 bit hash value数据。该程序似乎遵循算法，但偏离了大约 20%。我的数据集由超过 200,000 条唯一记录组成，而程序输出大约 160,000 条唯一记录。请帮助我理解我所犯的错误。哈希函数是根据鲍勃·杰金斯的网站实现的。

import numpy as np
from jenkinshash import jhash
class PCSA():
    def __init__(self, nmap, maxlength):
        self.nmap = nmap
        self.maxlength = maxlength
        self.bitmap = np.zeros((nmap, maxlength), dtype=np.int)
    def count(self, data):
        hashedValue = jhash(data)
        indexAlpha = hashedValue % self.nmap
        ix = hashedValue / self.nmap
        ix = bin(ix)[2:][::-1]       
        indexBeta = ix.find("1")    #find index of lsb
        if self.bitmap[indexAlpha, indexBeta] == 0:
            self.bitmap[indexAlpha, indexBeta] = 1

    def getCardinality(self):
        sumIx = 0
        for row in range(self.nmap):
            sumIx += np.where(self.bitmap[row, :] == 0)[0][0]
        A = sumIx / self.nmap
        cardinality = self.nmap * (2 ** A)/ MAGIC_CONST
        return cardinality

Answer 1

如果你在 Python2 中运行它，那么计算 A 的除法可能会导致 A 被更改为整数。

如果是这种情况，您可以尝试更改：

A = sumIx / self.nmap

自

A = float(sumIx) / self.nmap