你如何在只知道第一个和最后一个项目而不知道项目数的情况下估计你在一个集合中迭代的进度？
AAAAAAA
....
....
....?
....
....
ZZZZZZZZZZZZ第一项和最后一项保证是整个集合的字典最小值和最大值。可以假设项目值的分布接近均匀。您接收项目的顺序未知，可能无法预测，也可能是有序的。项目保证是唯一的。
只要估计值随着时间的推移逐渐接近99.999%，就可以波动。
这让我想起了德国坦克的问题，只是（据我所知）没有一种方法可以按字典顺序减去或得到项目之间的距离。例如，我想把收到的最大项目和最后一个项目进行比较，但我不知道如何获得任意项目之间的“距离”。
上下文：我让mapreduce作业中的Map程序使用这些键，在无法报告进度百分比的情况下，tasktracker假设任务被卡住，并开始在相同的数据上生成推测性的冗余Map。
2条答案
按热度按时间wlzqhblo1#
利用排列秩求距离：http://www.geeksforgeeks.org/lexicographic-rank-of-a-string/
你要做的是计算每个字符串的秩并减去距离。
qnyhuwrf2#
可以将字符串“s1s2…sn”视为等于s1/n+s2/n^2+…+的数字sn/n^n，其中n是字母表的大小。换句话说，字符串的字符是该数字的n元表示形式的逗号后的数字。
然后你可以用这些数字之间的差值作为字符串之间的距离，因为它相对于字典顺序是单调的。