基本思想是首先计算出在删除一条记录之前需要经过多少条记录——这必须是一个浮点数。例如:
percentage = 37.0
lineCount = 912.0
deleteEveryN = 100.0 / percentage # ~2.702 lines
然后,您只需计算行数,删除每个相关的行。通过使用浮点,您可以避免只删除每一N
行的情况 - 有时它可能是N-1
或N+1
,具体取决于值。
countToNextDeletion = deleteEveryN / 2
foreach line:
countToNextDeletion = countToNextDeletion - 1.0
if countToNextDeletion <= 0.0:
delete line
countToNextDeletion = countToNextDeletion + deleteEveryN
我们将行数初始化countToNextDeletion
为一半的原因是尽可能平衡两端(使删除在中点周围对称)。这是我从画线算法中学到的一个技巧(来自 Bresenham,来自记忆)。否则,您可能不会像预期的那样删除,因为您在最终组中只有 97% 没有到达删除点。
您可以使用以下 Python 程序查看此算法的实际效果:
percentage = 37
lineCount = 97
deleteEveryN = 100.0 / percentage
print "Delete every %f" % deleteEveryN
delCount = 0
countToNextDeletion = deleteEveryN / 2
for n in range (lineCount):
countToNextDeletion = countToNextDeletion - 1.0
if countToNextDeletion <= 0.0:
print "Deleting %d" % n
delCount = delCount + 1
countToNextDeletion = countToNextDeletion + deleteEveryN
print "Deleted %d/%d (%f%%)" % (delCount, lineCount, delCount*100.0/lineCount)
其输出是(稍微修改输出以节省垂直空间):
pax> python testprog.py
Delete every 2.702703
Deleting 1
Deleting 4
Deleting 6
Deleting 9
Deleting 12
Deleting 14
Deleting 17
Deleting 20
Deleting 22
Deleting 25, 28, 31, 33, 36, 39, 41, 44, 47, 49, 52, 55, 58
Deleting 60, 63, 66, 68, 71, 74, 77, 79, 82, 85, 87, 90, 93
Deleting 95
Deleted 36/97 (37.113402%)
everyN
您可以在那里看到,它有时会每隔两行删除一次,有时每隔三行删除一次,具体取决于阈值(因为值为 ,所以三行多于二行2.7ish
)。
最后一行还表明这是给定数据的最佳匹配:
linesDeleted/lineCount percentage deltaPercentage (from 37)
====================== ========== =========================
35/97 36.0824742 0.9175258
36/97 37.1134021 0.1134021 <== closest
37/97 38.1443299 1.1443299
只是为了展示它在前几次迭代中countToNextDeletion
是如何工作的,最初设置为2.7027027 / 2
or 1.3513514
。对于第一行0
,我们添加1
到 get2.3513514
但不超过阈值。
第二行1
,我们添加1
得到高于阈值3.3513514
的值,因此我们删除该行并减去得到的阈值。0.6486487
然后需要另外三行将我们推到阈值以上3.6486487
,此时我们删除该行4
并减去阈值得到0.945946
。
从那里只需要另外两条线即可到达2.945946
阈值以上,因此我们删除6
并减去阈值即可获得0.2432433
。
所以基本上,你会非常详细地记住(浮点)你在列表中的位置,但只在整数边界上删除。