繁重的计算分析/优化

Question

首先,我没有乘法,除法运算,所以我可以使用移位/加法,溢出乘法,预先计算等.我只是比较一个n位二进制数到另一个,但根据算法的数量运营似乎是巨大的.这里是 :

1. 给出了0和1的序列,它被分成块.假设序列的长度为S,则块的长度为N,其为2的幂(4,8,16,32等).块数量是n = S/N,这里没有火箭科学.
2. 根据所选择的N i构建一组所有可能的N位二进制数,它是2 ^ N-1个对象的集合.
3. 在此之后,我需要将每个二进制数与源序列中的每个块进行比较,并计算每个二进制数匹配的次数,例如:
   S:000000001111111100000000111111110000000011111111 ...(0000000011111111重复6次,16位x 6 = 96位 总计)
   N:8
   个街区:{00000000,111111111,00000000,111111,...}
   计算:

.

// _n = S/N;
// _N2 = Math.Pow(2,N)-1
// S=96, N=8, n=12, 2^N-1=255 for this specific case
// sourceEpsilons = list of blocks from input, List<string>[_n]
var X = new int[_n]; // result array of frequencies
for (var i = 0; i < X.Length; i++) X[i] = 0; // setting up
for (ulong l = 0; l <= _N2; l++) // loop from 0 to max N-bit binary number
var currentl = l.ToBinaryNumberString(_N/8); // converting counter to string, getting "current binary number as string"
var sum = 0; // quantity of currentl numbers in blocks array
for (long i = 0; i < sourceEpsilons.LongLength; i++)
{
   if (currentl == sourceEpsilons[i]) sum++; // evaluations of strings, evaluation of numbers (longs) takes the same time
}
// sum is different each time, != blocks quantity                    
for (var j = 0; j < X.Length; j++) 
if (sum - 1 == j) X[j]++; // further processing
// result : 00000000 was matched 6 times, 11111111 6 times, X[6]=2. Don't ask me why do i need this >_<

即使很小的S i似乎也有(2 ^ N-1)(S/N)次迭代,其中N = 64,数量增长到2 ^ 64 =(类型为long的最大值),因此这并不漂亮.我确信需要优化循环并且可能更改基本方法(N = 32的c#实现需要2h @双核pc/Parallel.For).任何想法如何使上述方案更少的时间和资源消耗？看起来我必须预先计算二进制数并通过从文件中读取"i"来摆脱第一个循环并使用块"即时"评估它,但文件大小将是(2 ^ N)*N个字节(( 2 ^ N-1)+1)*N)这在某种程度上是不可接受的.

Answer 1

看起来你想要的是计算序列中每个特定块发生了多少次; 如果是这种情况,将每个块与所有可能的块进行比较然后计算是一种可怕的方法.制作一个将块映射到计数的字典要好得多; 这样的事情:

var dict = Dictionary<int, int>();
for (int j=0; j<blocks_count; j++)
{
    int count;
    if (dict.TryGetValue(block[j], out count)) // block seen before, so increment
    {
        dict[block[j]] = count + 1;
    }
    else // first time seeing this block, so set count to 1
    {
        dict[block[j]] = 1; 
    }
}

在此之后,q任何特定块的计数将在dict[the_block],并且如果该键不存在,则计数为0.