一种计数算法

前言

常见的一个问题: 给定一个整形数组, 统计其中有多少唯一的元素.

常见的思路有哪些呢?

1. 元素去重并统计, 利用哈希表进行去重计数.
2. 数组排序后统计

以上空间复杂度均与元素数量关联, 如果允许损失精度, 是否可以使用较低的空间占用来统计呢?

• 利用布隆过滤器是一种的一种

但是, 我在这篇文章看到了一种全新的思路. 尽管并不建议在生产环境中使用, 但仍不失为一种思路.

统计思路

这种思路简单说就是: “采样”. 就像是统计一个湖泊中鱼的数量, 并不会一次性将所有的鱼都捞上来. 而是先钓n 条鱼上来, 给他们都做上记号. 几天后再钓 n 条鱼上来, 看其中有多少个有记号的鱼. 从而来估算整个湖泊中鱼的总数.

这个思路是否也可以在这个问题上借鉴呢?

通常的统计方式如下:

func count(arr []int) int {
	m := make(map[int]bool)
	for _, i := range arr {
		m[i] = true
	}
	return len(m服务器托管网)
}

好, 现在开始利用”采样”的思路, 丢失精确度, 降低空间复杂度.

我们将一半的元素放到hash表中保存:

func count(arr []int) int {
	m := make(map[int]bool)
	f服务器托管网or _, i := range arr {
		if rand.Intn(2) == 0 {
			m[i] = true
		}
	}
	return len(m) * 2
}

但, 如此有个问题, 元素在数组中出下的次数, 会影响其最终放入hash的概率. 次数越多, 概率越大. 这显然会影响计算的公平性.

一个非常简单的解决思路: 在随机之前, 我们将该元素从hash中先删除. 这样, 影响此元素是否在hash中出现的, 就只是其最后一次随机的结果了.

func count(arr []int) int {
	m := make(map[int]bool)
	for _, i := range arr {
		delete(m, i)
		if rand.Intn(2) == 0 {
			m[i] = true
		}
	}
	return len(m) * 2
}

当然, 现在的内存使用应该是数组长度的一半. 我们可以增加随机率来进一步降低内存占用.

func count(arr []int, p int) int {
	m := make(map[int]bool)
	for _, i := range arr {
		delete(m, i)
		if rand.Intn(p) == 0 {
			m[i] = true
		}
	}
	return len(m) * p
}

至此, 基本思路已经介绍完了, 但实际的内存占用仍然与数组大小关联. 可以看到, 随机率越高, hash中保存的元素就会越少. 我们是否可以动态的来调整呢? 让随机率随着数组长度的增加而增加.

func count(arr []int, maxSize int) int {
	p := 2
	m := make(map[int]bool)
	for _, i := range arr {
		delete(m, i)
		if rand.Intn(p) == 0 {
			m[i] = true
		}
		if len(m) >= maxSize {
			p *= 2
			// 因为随机率增大了一倍
			// 之前的元素也需要再次进行随机, 使得其满足现有的随机率
			for k, _ := range m {
				if rand.Intn(2) == 0 {
					delete(m, k)
				}
			}
		}
	}
	return len(m) * p
}

以上, 就是整个算法的全部内容了. 这是一个实现简单, 思路也简单的算法. 它给我打开了新的视野

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 面试官：Redis如何保证高可用？

Redis 高可用（High Availability，HA）是指 Redis 通过一系列技术手段确保在面临故障的情况下也能持续提供服务的能力。 Redis 作为一个内存数据库，其数据通常存储在内存中，一旦发生故障，可能导致数据丢失或服务中断，所以，为了保证 …