Python位掩码(可变长度)
发布时间:2020-12-20 11:17:01 所属栏目:Python 来源:网络整理
导读:为了解决一个研究问题,我们必须在 python中组织位掩码搜索. 作为输入,我们有一个原始数据(我们将其表示为一系列位).尺寸约为1,5Gb. 作为输出,我们必须得到特定位掩码的出现次数. 让我举一个例子来描述这种情况 input: sequence of bits,a bitmask to search(
为了解决一个研究问题,我们必须在
python中组织位掩码搜索.
作为输入,我们有一个原始数据(我们将其表示为一系列位).尺寸约为1,5Gb. 作为输出,我们必须得到特定位掩码的出现次数. 让我举一个例子来描述这种情况 input: sequence of bits,a bitmask to search(mask length: 12bits) 第一个想法(不是有效的)就是像这样使用XOR: 1step: from input we take 12 first bits(position 0 to 11) and make XOR with mask 2step: from input we take bits from 1 to 12 position and XOR with mask ... 让我们继续前进2步: input sequence 100100011110101010110110011010100101010110101010 mask to search: 100100011110 step 1: take first 12 bits from input: 100100011110 and XOR it with mask. step 2: teke bits from 1 to 12position: 001000111101 and XOR it with mask. ... 问题是:如何组织从输入中取位? 在我们使用python BitString包之前,我们花在搜索所有掩码上的时间都很高. 解决方法
你的算法是在数据中搜索“字符串”的天真方式,但幸运的是有更好的算法.
一个例子是 KMP algorithm,但还有其他一些可能更适合您的用例. 使用更好的算法,您可以从O(n * m)的复杂度到O(n m). (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |