如何使用最少的请求实现两列相关数据的一一对应？

Question

具体问题是这样的：

某个网站，uid和注册时间是正相关且单调，比如
uid[1001-1100] 是 2016年6月6日注册的，
uid[1101-1200] 是 2016年6月7日注册的。

示例

如果已知uid 1000对应2016.6.5，uid 1001和1100对应2016.6.6，uid 1101对应2016.6.7，那么可以判定uid 1001到1100都对应2016.6.6

想要获取某个uid的注册时间，只能爬取一次https://domain.com/user/:uid

我现在想获取每个uid对应的注册时间，那么要怎样设计uid生成策略，才能使得爬取的次数尽量少呢？假设总共经过了1000天，每天平均有100个新用户注册（具体数量完全随机），爬取次数大概能减少到哪个数量级？

Answer 1

粗想一下. 用二分法进行数据查找, 并判mid的前一天或后天的data数据不同来确定uid对应的时间间隔
先建立一个dict, key为uid value为data.
举个栗子
start = for i in dict.key()[0]
end = for i in dict.key()[-1]
start_data = for i in dict.value()[0]
end_data = for i in dict.value()[-1]
mid = (start+end)/2
然后访问domain../:mid 获取data 设为mid_data = data
判断mid_data的值, 与start_data,end_data比较
mid_data == start_data:取mid+1(mid_1)再抓取data.与mid_data作比较

if mid_1_data > mid_data:  
    for i in range(start+1,mid):
        dict[i]=data

如果mid_1_data和mid_data 相同, 那start=mid_1 , 继续2分法 查找日期

随便写的伪代码, 有点长仓促, 考虑不周请见谅.希望有帮助

Answer 2

我理解你是要通过尽量少的爬取，获取某个uid对应所属的注册时间段？（把1000天的分段？如果是这样，可能还需要不同的策略）
这个其实是搜索问题的变形

这个因为你有平均100用户这个信息，则可以把起始点上下各50步长去看是否还和当前是一个，然后用折半查找类似的策略进行逐次逼近。

如果是要分段1000天的，从0开始依次搜索，则确定一个靠近分段点后，加100，依据情况向上或者向下搜索靠近的分段点。