c# - 繁重的计算分析/优化

Question

首先，我没有乘法、除法运算，所以我可以使用移位/加法、溢出乘法、预计算等。我只是将一个 n 位二进制数与另一个进行比较，但根据算法此类操作的数量似乎很大。在这里:

1. 给定一个由 0 和 1 组成的序列，这些序列被分成 block 。令序列的长度为 S， block 的长度为 N，它是 2 的某个幂(4、8、16、32 等)。 block 的数量是 n=S/N，这里没有火箭科学。
2. 根据选择的 N，我正在构建一组所有可能的 N 位二进制数，它是 2^N-1 个对象的集合。
3. 在此之后，我需要将每个二进制数与源序列中的每个 block 进行比较，并计算每个二进制数匹配的次数，例如:
   S : 0000000011111111100000000111111110000000011111111...(0000000011111111 重复 6 次，总共 16 位 x 6 = 96 位)
   人数:8
   block :{00000000, 11111111, 00000000, 1111111,...}
   计算:

.

// _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 很小，我似乎也有 (2^N-1)(S/N) 次迭代，当 N=64 时，数字增长到 2^64=(max value of type long) 所以这不是很漂亮.我确定需要优化循环，并且可能从根本上改变方法(N=32 的 c# 实现需要 2h @ dual-core pc w/Parallel.For)。有什么想法可以减少上述方案的时间和资源消耗？似乎我必须预先计算二进制数并通过从文件中读取“i”并使用“即时” block 对其进行评估来摆脱第一个循环，但文件大小将为 (2^N)*N 字节(( 2^N-1)+1)*N) 这在某种程度上也是 Not Acceptable 。

Answer 1

您似乎想要计算每个特定 block 在您的序列中出现的次数；如果是这样的话，将每个 block 与所有可能的 block 进行比较，然后进行计数是一种可怕的处理方法。最好制作一本将 block 映射到计数的字典；像这样:

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; 
    }
}

在此之后，任何特定 block 的计数 q 将在 dict[the_block] 中，如果该键不存在，则计数为 0。