Return the approximated cardinality of the set based on the harmonic * mean of the registers values. 'hdr' points to the start of the SDS * representing the String object holding the HLL representation. * * If the sparse representation of the HLL object is not valid, the integer * pointed by 'invalid' is set to non-zero, otherwise it is left untouched. * * hllCount() supports a special inte
| 1011 | * This is useful in order to speedup PFCOUNT when called against multiple |
| 1012 | * keys (no need to work with 6-bit integers encoding). */ |
| 1013 | uint64_t hllCount(struct hllhdr *hdr, int *invalid) { |
| 1014 | double m = HLL_REGISTERS; |
| 1015 | double E; |
| 1016 | int j; |
| 1017 | /* Note that reghisto size could be just HLL_Q+2, because HLL_Q+1 is |
| 1018 | * the maximum frequency of the "000...1" sequence the hash function is |
| 1019 | * able to return. However it is slow to check for sanity of the |
| 1020 | * input: instead we history array at a safe size: overflows will |
| 1021 | * just write data to wrong, but correctly allocated, places. */ |
| 1022 | int reghisto[64] = {0}; |
| 1023 | |
| 1024 | /* Compute register histogram */ |
| 1025 | if (hdr->encoding == HLL_DENSE) { |
| 1026 | hllDenseRegHisto(hdr->registers,reghisto); |
| 1027 | } else if (hdr->encoding == HLL_SPARSE) { |
| 1028 | hllSparseRegHisto(hdr->registers, |
| 1029 | sdslen((sds)hdr)-HLL_HDR_SIZE,invalid,reghisto); |
| 1030 | } else if (hdr->encoding == HLL_RAW) { |
| 1031 | hllRawRegHisto(hdr->registers,reghisto); |
| 1032 | } else { |
| 1033 | serverPanic("Unknown HyperLogLog encoding in hllCount()"); |
| 1034 | } |
| 1035 | |
| 1036 | /* Estimate cardinality form register histogram. See: |
| 1037 | * "New cardinality estimation algorithms for HyperLogLog sketches" |
| 1038 | * Otmar Ertl, arXiv:1702.01284 */ |
| 1039 | double z = m * hllTau((m-reghisto[HLL_Q+1])/(double)m); |
| 1040 | for (j = HLL_Q; j >= 1; --j) { |
| 1041 | z += reghisto[j]; |
| 1042 | z *= 0.5; |
| 1043 | } |
| 1044 | z += m * hllSigma(reghisto[0]/(double)m); |
| 1045 | E = llroundl(HLL_ALPHA_INF*m*m/z); |
| 1046 | |
| 1047 | return (uint64_t) E; |
| 1048 | } |
| 1049 | |
| 1050 | /* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */ |
| 1051 | int hllAdd(robj *o, unsigned char *ele, size_t elesize) { |
no test coverage detected