-3

我有一个字符串列表列表，以便将字符串与'1'的数量进行分组，例如 string = "00000" 属于第一组，而 string = "00001" 属于第二组。所有字符串的长度相等。现在我将第一组与第二组进行比较，将第二组与第三组进行比较，很快……就像在图像中一样。将第一组中的第一个元素与第二组中的所有元素进行比较。直到比较每个字符串。有没有办法加快我的程序的性能？所以我可以实现 32000 长度为 15 的字符串。

编辑

对不起过去的帖子。读完后我意识到我这样问是愚蠢的。该计划的目标是简化。基于Quine-McCluskey 算法

考虑

000
001
010
011
100
101
110
111

我按 1 的数量对它们进行分组

000

001
010
100

011
101
110

111

然后我将组中的每个字符串与下一组进行比较

group 1
000

group 2
001
010
100

group 3
011
101
110

group1 -> group2
------------------
    000 -> 001 = 00-
    000 -> 010 = 0-0
    000 -> 100 = -00
------------------
group2 ->group3
--------------------  
    001 -> 011 = 0-1
    001 -> 101 = -01
    001 -> 110 = no output

    010 -> 011 = 01-
    010 -> 101 = no output
    010 -> 110 = -10

    100 -> 011 = no output
    100 -> 101 = 10-
    100 -> 110 = 1-0

---------------------
etc.

然后将输出再次按 1 的数量分组并再次比较它们，直到没有字符串可以比较。

我需要实现 15 个变量，但程序需要永远完成。任何想法如何加快它。我在线程上对其进行了测试，但只有一点改进。

字符串数：2048 变量长度：11 时间：10 分钟

需要实现

字符串数：32767 变量长度：15 时间：无法实现

 List<List<string>> ImplicantsByOneFinal = new List<List<string>>();
 List<List<string>> TermsByOne = new List<List<string>>();

有没有办法或算法来改进这段代码。它在 11 到 15 个变量上变得更慢。

bool CombineAndGroup(List<List<string>> ImplicantsByOne)
{ 
            TermsByOne = new List<List<string>>();
            int combined = 0; 
            for (int i = 0; i < ImplicantsByOne.Count - 1; i++)
            { 
                List<string> termsGrouped = new List<string>();
                for (int j = 0; j < ImplicantsByOne[i].Count; j++)
                { 
                    int combination = 0;
                    int num1 = Convert.ToInt32((ImplicantsByOne[i][j]).Replace('-','0'), 2); 
                        for (int k = 0; k < ImplicantsByOne[i + 1].Count; k++)
                        { 
                            int num2 = Convert.ToInt32((ImplicantsByOne[i + 1][k]).Replace('-', '0'), 2);
                            int num3 = num2 - num1;
                            double num4 = Math.Log((double)num3, (double)2); 
                            if (((num4 % 1) == 0) && (num3 > 0) && (Esum(ImplicantsByOne[i][j]) == Esum(ImplicantsByOne[i + 1][k])))
                            {  
                                string combinedMinterm = CompareString(ImplicantsByOne[i][j], ImplicantsByOne[i + 1][k]); 
                                if (!termsGrouped.Contains(combinedMinterm))
                                {
                                    termsGrouped.Add(combinedMinterm); 
                                }  

                            }
                        }   
                }
                if (termsGrouped.Count > 0)
                {
                    combined += termsGrouped.Count;
                } 
                TermsByOne.Add(termsGrouped);
            }

            return (combined > 0) ? true : false;
        } 

 private int Esum(String binCode)
        {
            binCode = binCode.Replace('1','0');
            binCode = binCode.Replace('-', '1');
            int esum = Convert.ToInt32(binCode, 2);
            return esum;
        }
//Purpose of CompareString is to compare two string and change the unique char to '-'
//like 000 and 001 = 00-
  private string CompareString(string str1, string str2)
        { 
            if (str1 == str2)
            { 
                CountCompareStringLoops++;
                return str1;
            }
            else 
            { 
                if (str1.Length == 1)
                { 
                    return "-";
                }
                int halflength = str1.Length / 2; 
                return CompareString(str1.Substring(0, halflength), str2.Substring(0, halflength)) + CompareString(str1.Substring(halflength), str2.Substring(halflength)); 
            }
        }

主程序

 MintermsByOne = Loaded with string 000 001 and so on

CombineAndGroup(MintermsByOne);
 ImplicantsByOneFinal = TermsByOne; 
 while (CombineAndGroup(TermsByOne))
 {
        ImplicantsByOneFinal = TermsByOne; 
 }

输出蕴涵ByOneFinal

4

2 回答 2

3

老实说，您要实现的目标并不是很清楚……您的描述与您的代码不匹配。（例如，您的代码从未提及字符 '1'。您从未使用调用结果的事实也CompareString很可疑。）LINQ 应该使您对“将字符串与 '1' 的数字分组”的描述变得容易并且高效的：

var grouped = strings.GroupBy(x => x.Count(c => c == '1'));

这只会计算每个字符串中的“1”字符数一次。您永远不需要将任何字符串与另一个字符串进行比较。

如果这不是你真正想要做的，你需要澄清你的实际目标是什么。

于 2013-05-10T10:39:59.973 回答
1

我不知道如何编写 C#，但我想提供帮助。所以我的代码是用Java给出的。

1.我认为==是一种O(n)手术，你的CompareString可能在O(nlgn)哪里n = str1.Length。使用更简单更快的O(n)方式，看看时间是否减少：

private String CompareString(String str1, String str2) {
    StringBuilder sb = new StringBuilder(str1.length());
    for (int i = 0; i < str1.length(); i++) {
        if (str1.charAt(i) == str2.charAt(i))
            sb.append(str1.charAt(i));
        else
            sb.append('-');
    }
    return sb.toString();
}

2.嗯，我发现有很多ToInt32。一次计算所有字符串的结果，ImplicantsByOne稍后使用。也是如此Esum。

3. 检查是否num3是 2 的幂：

private boolean isPowerOfTwo(int x) {
    return (x > 0 && (x & (x - 1)) == 0);
}
于 2013-05-10T11:41:33.093 回答