DAU 统计

今日头条2017实习生招聘418在线笔试编程
时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 32768KB；其他语言 557056KB
题目描述：
日活跃用户数 (DAU) 是衡量一个产品表现的重要指标。
需要编写程序，根据给定的某一天的 n 条访问记录，对当天的用户总数 m 进行统计。
每个用户可能访问多次。

输入
每一行包含一个 uid，遇到 0 时认为输入结束。
输入共包含 n+1 行，可认为是无序的。
输出
一个数字：去重后 uid 的数量 m。
样例输入
12933
111111
59220
69433
59220
111111
0
样例输出
4
Hint
数据范围
0 < uid < 2^63
对于 30% 的数据，0 < n < 100,000, 0 < m < 100,000
对于 100% 的数据，0 < n < 1,000,000, 0 < m < 800,000

解决方案

1 使用set就可以了。

2 如果数据量大而稠密，而且最大值为2^32次方，则可以使用bitmap算法来做更好，并使用位算法来统计1的个数。

3 使用Hyperloglog算法

好像是一个近似的概率算法

[Damn Cool Algorithms: Cardinality Estimation]

4 还有直接上代码的另一种hash算法

def trailing_zeroes(num):
  """Counts the number of trailing 0 bits in num."""
  if num == 0:
    return 32 # Assumes 32 bit integer inputs!
  p = 0
  while (num 
>
>
 p) 
&
 1 == 0:
    p += 1
  return p

def estimate_cardinality(values, k):
  """Estimates the number of unique elements in the input set values.

  Arguments:
    values: An iterator of hashable elements to estimate the cardinality of.
    k: The number of bits of hash to use as a bucket number; there will be 2**k buckets.
  """
  num_buckets = 2 ** k
  max_zeroes = [0] * num_buckets
  for value in values:
    h = hash(value)
    bucket = h 
&
 (num_buckets - 1) # Mask out the k least significant bits as bucket ID
    bucket_hash = h 
>
>
 k
    max_zeroes[bucket] = max(max_zeroes[bucket], trailing_zeroes(bucket_hash))
  return 2 ** (float(sum(max_zeroes)) / num_buckets) * num_buckets * 0.79402

类似的问题

查找数组中重复的数

从0到n-1的n个数的数组中查找有重复的数：Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

For example, let n be 7 and array be {1, 2, 3, 1, 3, 6, 6}, the answer should be 1, 3 and 6.

一种解决方法是

traverse the list for i= 0 to n-1 elements
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}

但是如果有k>3次以上重复就会输出k-1次相同的数，当然也可以改进好。

[Find duplicates in O(n) time and O(1) extra space | Set 1]

所以lz觉得还不如使用bitmap算法，更省内存，速度也快，重复多少次也可以。具体可参考[BitMap算法]示例。