标签: bitarray

我需要在GetHashCode中为BitArray生成快速哈希码.我有一个字典,其中键是BitArrays,所有BitArrays长度相同.

有没有人知道从可变位数生成良好哈希的快速方法,如在这种情况下？

更新:

我最初采用的方法是直接通过反射访问内部int数组(速度比这种情况下的封装更重要),然后对这些值进行异或.XOR方法似乎运行良好,即在"字典"中搜索时,我的"等于"方法不会过度调用:

    public int GetHashCode(BitArray array)
    {
        int hash = 0;
        foreach (int value in array.GetInternalValues())
        {
            hash ^= value;
        }
        return hash;
    }

但是,Mark Byers建议并在StackOverflow其他地方看到的方法稍好一些(对于我的测试数据,XOR为16570等于呼叫,而对于XOR为16608).请注意,此方法修复了前一个错误,其中超出位数组末尾的位可能会影响散列值.如果位数组的长度减少,则可能发生这种情况.

    public int GetHashCode(BitArray array)
    {
        UInt32 hash = 17;
        int bitsRemaining = array.Length;
        foreach (int value in array.GetInternalValues())
        {
            UInt32 cleanValue = (UInt32)value;
            if (bitsRemaining < 32)
            {
                //clear any bits that are beyond the end of the array
                int bitsToWipe = 32 - bitsRemaining;
                cleanValue <<= bitsToWipe;
                cleanValue >>= bitsToWipe;
            } …

如何取消设置一个字的最重要的设置位(例如0x00556844 - > 0x00156844)？__builtin_clzgcc中有一个,但它只计算零,这对我来说是不必要的.另外,我应该如何为msvc或intel c编译器替换__builtin_clz？

目前我的代码是

 int msb = 1<< ((sizeof(int)*8)-__builtin_clz(input)-1);
 int result = input & ~msb;

更新:好的,如果你说这段代码相当快,我会问你,我应该如何为这段代码添加一个可移植性？这个版本适用于GCC,但是MSVC和ICC？

我刚刚开始在 python 中使用 bitarray 包，并尝试从整数创建 bitarray 给了我非常令人困惑的结果：

>>> import bitarray
>>> bitarray.bitarray(5)
bitarray('01000')
>>> bitarray.bitarray(5)
bitarray('00010')
>>> bitarray.bitarray(5)
bitarray('00100')
>>> bitarray.bitarray(5)
bitarray('00110')

有谁知道为什么会发生这种情况？

另外：从 int 生成位数组的更好方法是什么？这是可行的，但是字符串转换似乎是一种奇怪的方法......

>>> bitarray.bitarray(bin(5)[2:])
bitarray('101')

编辑：我最终切换到bitstring，它确实有一个从整数获取位串的简单方法：

>>> bitstring.BitArray(uint=5,length=6)
BitArray('0b000101')

我需要将BitArray(从std.bitmanip)分成两半.到目前为止,我已经发现切片没有实现,迭代它并且追加或分配产生超出范围的异常.我试图将它转换为其他类型(它适合long/ulong)但这似乎太麻烦了,当我尝试初始化新的BitArrays时它也会给我一个超出范围的异常,如下所示:

BitArray[] C, D;
long lg = toLong(bitArr);
C[0].init(cast(void[])((lg >> 28) & 0x0fff_ffff), 28);

对我的问题有一个更简单的解决方案吗？如果没有,我做错了什么？

我有以下字符串，需要霍夫曼编码并将其有效地存储到位数组中：

>>> print sequence
GTCAGGACAAGAAAGACAANTCCAATTNACATTATG|

中的符号频率为sequence：

>>> print freqTuples
[(0.40540540540540543, 'A'), (0.1891891891891892, 'T'), (0.16216216216216217, 'C'), (0.16216216216216217, 'G'), (0.05405405405405406, 'N'), (0.02702702702702703, '|')]`

我将其翻译成霍夫曼代码字典：

>>> print codeDict
{'A': '1', 'C': '010', 'G': '001', 'N': '0110', 'T': '000', '|': '0111'}

然后，我使用Python bitstring包将字符串逐个字符地转换为BitArray该类的实例，我称之为bitArray，该实例包含每个用其各自的霍夫曼代码编码的字符的位：

>>> print bitArray.bin
0b001000010100100110101100111100110101101100000100101100000001101010100000010000010111

这是位数组，以字节为单位：

>>> print bitArray.tobytes()
!I\254\363[^D\260^Z\240Ap

我必须使用tobytes()而不是bytes，因为我生成的位数组不能平均分为8位段。

当我计算表示的存储效率BitArray（位数组和输入字符串的大小之比）时，与未对输入字符串进行未编码的情况相比，我得到的性能更差：

>>> sys.getsizeof(bitArray.tobytes()) / float(len(sequence))
1.2972972973

我是否正确测量存储效率？（如果我对更长的输入字符串进行编码，则该比率会提高，但似乎接近0.28的渐近极限。我想确认这是否是正确的度量方法。）

编辑

以下两种方法得出不同的答案：

>>> print len(bitArray.tobytes()) / float(len(mergedSequence))
0.297297297297

>>> print bitArray.len …

另一个合成基准:Eratosthenes筛选

C++

#include <vector>
#include <cmath>

void find_primes(int n, std::vector<int>& out)
{
   std::vector<bool> is_prime(n + 1, true);
   int last = sqrt(n);
   for (int i = 2; i <= last; ++i)
   {
      if (is_prime[i])
      {
         for (int j = i * i; j <= n; j += i)
         {
            is_prime[j] = false;
         }
      }
   }

   for (unsigned i = 2; i < is_prime.size(); ++i)
   {
      if (is_prime[i])
      {
         out.push_back(i);
      }
   }
}

OCaml(使用Jane Street的Core和Res库)

open Core.Std …

我试图减少python dict的内存消耗,在我的情况下,它作为word-->document_id"倒排索引".每个word都作为整数进行哈希处理,占用24个字节.

我想知道我是否可以将每个元素dict的值和每个键转换dict为一个bitarray.我注意到任何遇到的最大值int都小于2^22,所以我可以只分配一个"22号"的位数组.

如何才能做到这一点？到目前为止,我已经看过gmpy2和bitarray库,以及std::bitsetC++ stdlib,我可以使用Cython.我从这篇文章中读到的bitarray并不是那么快gmpy.在gmpy,我不知道如何设置大小.最后,我想知道Python中的内存开销gmpy或bitarray对象是否值得,当我可以使用时std::bitset,它可能使用最少的内存.

我有一个很大的char*str,其中前8个字符(如果我没有错,则等于64位)代表一个位图.有没有办法迭代这8个字符,看看哪些位是0？我在理解位的概念方面遇到了很多麻烦,因为你无法在代码中"看到"它们,所以我想不出任何方法来做到这一点.

我的C代码中有几个uint8_t数组，我想将任意一个序列位与另一个序列进行比较。例如，我有bitarray_1和bitarray_2，我想将bitarray_1的13-47位与bitarray_2的5-39位进行比较。最有效的方法是什么？

当前，这是我程序中的一个巨大瓶颈，因为我只有一个幼稚的实现，可以将这些位复制到新的临时数组的开头，然后对它们使用memcmp。

好吧,所以我有一个字节[],我得到使用 File.ReadAllBytes(filename); 我的问题是我的程序需要将文件中的数据视为一个bool数组.我搜索过,但我没有找到一种方法来获得正确有效的转换.一个例子是:

{ 00101011, 10111010 } ->
            { false, false, true, false, true, false, false, true, true,
              false, true, true, true, false, true, false }

我还需要改变程序.

我遇到的大多数解决方案涉及从每个字节中获取一个布尔值.即,得到的数组与数组的bool[]长度相同byte[],我似乎不明白这是怎么可能的,8位如何只产生一个布尔值？在我的情况下,我需要一个结果数组:bool[bytes.Length * 8].

非常感谢,任何帮助都非常感谢.

实现其中一个解决方案我试图让它工作但它有点错误,因为生成的文件,我读取的文件的副本被损坏:

public static bool[] boolsFromFile(string filename)
    {
        List<bool> b = new List<bool>();
        using (FileStream fileStream = new FileStream(filename, FileMode.Open))
        using (BinaryReader read = new BinaryReader(fileStream))
        {
            while (fileStream.Position != fileStream.Length)
                b.Add(read.ReadBoolean());
        }
        return b.ToArray();
    }

    public static void boolsToFile(string filename, bool[] bools)
    {
        using …