{"id":119263,"date":"2019-05-22T12:38:11","date_gmt":"2019-05-22T04:38:11","guid":{"rendered":"http:\/\/www.fagao.me\/?p=119263"},"modified":"2019-05-22T12:38:11","modified_gmt":"2019-05-22T04:38:11","slug":"%e7%94%a8-python-%e5%ae%9e%e7%8e%b0%e4%b8%80%e4%b8%aa%e5%a4%a7%e6%95%b0%e6%8d%ae%e6%90%9c%e7%b4%a2%e5%bc%95%e6%93%8e-6","status":"publish","type":"post","link":"https:\/\/www.fagao.me\/p\/119263.htm","title":{"rendered":"\u7528 Python \u5b9e\u73b0\u4e00\u4e2a\u5927\u6570\u636e\u641c\u7d22\u5f15\u64ce"},"content":{"rendered":"

\"\"<\/p>\n

<\/div>\n

\u641c\u7d22\u662f\u5927\u6570\u636e\u9886\u57df\u91cc\u5e38\u89c1\u7684\u9700\u6c42\u3002Splunk\u548cELK\u5206\u522b\u662f\u8be5\u9886\u57df\u5728\u975e\u5f00\u6e90\u548c\u5f00\u6e90\u9886\u57df\u91cc\u7684\u9886\u5bfc\u8005\u3002\u672c\u6587\u5229\u7528\u5f88\u5c11\u7684Python\u4ee3\u7801\u5b9e\u73b0\u4e86\u4e00\u4e2a\u57fa\u672c\u7684\u6570\u636e\u641c\u7d22\u529f\u80fd\uff0c\u8bd5\u56fe\u8ba9\u5927\u5bb6\u7406\u89e3\u5927\u6570\u636e\u641c\u7d22\u7684\u57fa\u672c\u539f\u7406\u3002<\/span><\/p>\n

\u5e03\u9686\u8fc7\u6ee4\u5668 \uff08Bloom Filter\uff09<\/span><\/p>\n

\u7b2c\u4e00\u6b65\u6211\u4eec\u5148\u8981\u5b9e\u73b0\u4e00\u4e2a\u5e03\u9686\u8fc7\u6ee4\u5668\u3002<\/span><\/p>\n

\u5e03\u9686\u8fc7\u6ee4\u5668\u662f\u5927\u6570\u636e\u9886\u57df\u7684\u4e00\u4e2a\u5e38\u89c1\u7b97\u6cd5\uff0c\u5b83\u7684\u76ee\u7684\u662f\u8fc7\u6ee4\u6389\u90a3\u4e9b\u4e0d\u662f\u76ee\u6807\u7684\u5143\u7d20\u3002\u4e5f\u5c31\u662f\u8bf4\u5982\u679c\u4e00\u4e2a\u8981\u641c\u7d22\u7684\u8bcd\u5e76\u4e0d\u5b58\u5728\u4e0e\u6211\u7684\u6570\u636e\u4e2d\uff0c\u90a3\u4e48\u5b83\u53ef\u4ee5\u4ee5\u5f88\u5feb\u7684\u901f\u5ea6\u8fd4\u56de\u76ee\u6807\u4e0d\u5b58\u5728\u3002<\/span><\/p>\n

\u8ba9\u6211\u4eec\u770b\u770b\u4ee5\u4e0b\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u4ee3\u7801\uff1a<\/span><\/p>\n

\n

class<\/span><\/span>Bloomfilter<\/span>(<\/span>object<\/span>)<\/span>:<\/span><\/span><\/p>\n

<\/span>“””<\/span><\/span><\/p>\n

A Bloom filter is a probabilistic data-structure that trades space for accuracy<\/span><\/p>\n

when determining if a value is in a set. It can tell you if a value was possibly<\/span><\/p>\n

added, or if it was definitely not added, but it can’t tell you for certain that<\/span><\/p>\n

it was added.<\/span><\/p>\n

“””<\/span><\/p>\n

<\/span>def __init__<\/span>(<\/span>self<\/span>,<\/span><\/span>size<\/span>)<\/span>:<\/span><\/span><\/p>\n

<\/span>“””Setup the BF with the appropriate size”””<\/span><\/span><\/p>\n

<\/span>self<\/span>.<\/span>values<\/span>= <\/span>[<\/span>False<\/span>]<\/span>* <\/span>size<\/span><\/span><\/p>\n

<\/span>self<\/span>.<\/span>size<\/span>= <\/span>size<\/span><\/span><\/p>\n

def hash_value<\/span>(<\/span>self<\/span>,<\/span><\/span>value<\/span>)<\/span>:<\/span><\/span><\/p>\n

<\/span>“””Hash the value provided and scale it to fit the BF size”””<\/span><\/span><\/p>\n

<\/span>return<\/span><\/span>hash<\/span>(<\/span>value<\/span>)<\/span>% <\/span>self<\/span>.<\/span>size<\/span><\/span><\/p>\n

def add_value<\/span>(<\/span>self<\/span>,<\/span><\/span>value<\/span>)<\/span>:<\/span><\/span><\/p>\n

<\/span>“””Add a value to the BF”””<\/span><\/span><\/p>\n

<\/span>h<\/span>= <\/span>self<\/span>.<\/span>hash_value<\/span>(<\/span>value<\/span>)<\/span><\/span><\/p>\n

<\/span>self<\/span>.<\/span>values<\/span>[<\/span>h<\/span>]<\/span>= <\/span>True<\/span><\/span><\/p>\n

<\/span>def might_contain<\/span>(<\/span>self<\/span>,<\/span><\/span>value<\/span>)<\/span>:<\/span><\/span><\/p>\n

<\/span>“””Check if the value might be in the BF”””<\/span><\/span><\/p>\n

<\/span>h<\/span>= <\/span>self<\/span>.<\/span>hash_value<\/span>(<\/span>value<\/span>)<\/span><\/span><\/p>\n

<\/span>return<\/span><\/span>self<\/span>.<\/span>values<\/span>[<\/span>h<\/span>]<\/span><\/span><\/p>\n

<\/span>def print_contents<\/span>(<\/span>self<\/span>)<\/span>:<\/span><\/span><\/p>\n

<\/span>“””Dump the contents of the BF for debugging purposes”””<\/span><\/span><\/p>\n

<\/span>print <\/span>self<\/span>.<\/span>values<\/span><\/span><\/p>\n<\/blockquote>\n