c#中的算法实现似乎是灾难性的

本文关键字：似乎是 灾难性 实现 算法 | 更新日期: 2023-09-27 18:03:50

我正在尝试实现这篇研究论文中指定的算法:[这里-请忽略数学，因为它与问题无关][2]。这个算法是形式化概念分析中非常基础的。输入是一个矩阵NXM，以。txt文件的形式存储为X和.。根据论文中嵌入的伪代码，输入也必须表示为矩阵

c#中的算法实现似乎是灾难性的

没有能够看到源到c++实现,你是比较反对它是不可能确定的原因是如此远远超过你的c#代码,但是由于你的每个值是0或1那么你可以做一个优化的成本(让你的代码更复杂)是存储的值的位掩码数据结构,或者就像挤一点int数组中的值并使用位操作操作来操纵它们。有可能c++实现正在这样做，但为了便于解释，在发布的伪代码中没有显示。

例如，由于CT_WIDTH为126，您可以将单行存储为4个32位整数(128位)，而不是126个整数。

然后像这样操作:

match = true;
for (int j = 0; j < CT_WIDTH; j++)
{
    if (B[j] == 1 && FCAContext[rows[y][i] * CT_WIDTH + j] == 0)
    {
        match = false;
        break;
    }
}

可以这样重写，一次有效地处理32个值:

// CT_WIDTH_SHIFTED = (CT_WIDTH + 31) / 32
match = true;
int index = rows[y][i] * CT_WIDTH_SHIFTED;
for (int j = 0; j < CT_WIDTH_SHIFTED; j++)
{
    if (B[j] & FCAContext[index + j] != B[j])
    {
        match = false;
        break;
    }
}

同样,:

for (int j = 0; j < CT_WIDTH; j++)
    if (FCAContext[rows[y][i] * CT_WIDTH + j] == 0)
         D[j] = 0;

可以重写为

for (int j = 0; j < CT_WIDTH_SHIFTED; j++)
    D[j] &= FCAContext[index + j];

FCAContext、D和B中的值需要以打包位的形式存储。

例如，在数组中设置一个位，而不是使用下面的代码来设置int数组的第j个元素:

B[j] = 1;

首先通过j除以32向左移动5来计算索引(j>> 5)然后计算元素内部的位，就像这样1 <<(j和;31)，即右移1，即j除以32的余数，然后使用按位或操作设置它:

B[j >> 5] |= 1 << (j & 31)

这是一个关于位屏蔽的在线教程。谷歌"位操纵"、"位移位"、"位掩码"、"位黑客"answers"位操作"/"按位操作"了解更多信息。然而，位操作可能会变得非常繁琐，使您的代码难以阅读。

还可以考虑使用。net BitArray类

相关文章：