2014-10-02 148 views
2

我想将包含0和1的字符串转换为位数组。
该字符串是长度〜30000的和是稀疏(主要是0,很少1S)
例如,给定的字符串
“00000000100000000010000100000000001000”
我想将其转换为位的阵列,其将存储
[00000000100000000010000100000000001000]将字符串转换为位数组

我正在考虑使用BitSetOpenBitSet 有没有更好的方法?用例是有效地执行逻辑或。

我沿着这些线路

final OpenBitSet logicalOrResult = new OpenBitSet(); 
for (final String line : lines) { 

    final OpenBitSet myBitArray = new OpenBitSet(); 
    int pos = 0; 
    for (final char c : str.toCharArray()) { 
     myBitArray.set(pos) = c; 
     pos++; 
    } 
    logicalOrResult.or(myBitArray); 
} 
+0

@ StevenA.Lowe它不是。 – Tad 2014-10-02 01:31:08

+0

@ StevenA.Lowe这不是一个好问题,就是一个坏问题。为什么你在乎作业是否功课? – 2014-10-02 01:31:17

+2

@AnubianNoob:如果它是作业,我告诉OP答案,那么他们什么都没学到。请参阅http://meta.stackexchange.com/questions/18242/what-is-the-policy-here-on-homework半官方政策 – 2014-10-02 01:33:14

回答

1

BitSet测距过030000之间的值需要一个long阵列大小小于500,所以可以假定BitSet.or(或各自的方法)将足够快,尽管稀疏。它看起来像OpenBitSetBitSet有更好的性能,但除此之外,它使用哪个并不重要,它们都将有效地执行or。但是,请确保将字符串的长度传递给(Open)BitSet构造函数,以避免在构造过程中重新分配内部的long数组!

如果你的字符串是更长的时间,你的稀疏性极端情况下,你也可以考虑将它们作为Integer秒的排序列表(或int S,如果你使用像特罗韦库),较其含有1指数。一个按位or可以以合并(排序)方式实现,这是非常有效的(时间O(n + m),其中n,m是每个字符串中的数字)。我怀疑在你的情况下,它会比BitSet的方法慢。

+0

我的BitSet的范围将超过值1和0 - 不是0和30000.这是你的意思吗? – Tad 2014-10-02 11:45:25

+1

不可以。您的'BitSet' *表示0到某个上限之间的一组整数。例如,位集01001101表示集合{0,2,3,6} - 索引集合被设置为1.这也构成了“BitSet”的'toString()'表示。由于您的字符串的长度为〜30000,因此相应的1-indices集合的范围介于0和30000之间。 – misberner 2014-10-02 18:40:08

0

您可以通过每个字符迭代想:

boolean[] bits = new boolean[str.length]; 

for (int i=0;i<str.length;i++) { 
    if (str.charAt(i).equals("1") 
     bits[i] = true; 
    else if (str.charAt(i).equals("0") 
     bits[i] = false; 
} 

如果你想成为高效存储,你可以尝试RLE (Run Length Encoding)

+0

我喜欢这种方法,但我已阅读http://stackoverflow.com/questions/383551 /使用BitSet的布尔变量大小是什么比使用布尔数组有更好的优化。我也在考虑RLE,这很好,因为我的数组很稀疏,但我不确定如何对压缩数组执行逻辑OR操作 - 我想我需要先解压它,除非我错过了某些东西。 – Tad 2014-10-02 01:55:07

2

BigInteger可以解析它并将其存储,并执行按位运算:

BigInteger x = new BigInteger(bitString, 2); 
BigInteger y = new BigInteger(otherBitString, 2); 
x = x.or(y); 
System.out.println(x.toString(2)); 
+0

您是否知道BigInteger和OpenBitSet以及BitSet(或任何其他库)之间是否有任何基准执行逻辑OR? – Tad 2014-10-02 01:46:26

+0

@Tad我不知道,但您可以通过在预期应用程序中执行基准来轻松比较它们。 – Boann 2014-10-02 01:51:13