嵌套迴路加速性能

Question

我有一個字符串列表的列表，以便將字符串編號爲'1'，如字符串=「00000」屬於第一組，字符串=「00001」屬於到第二組。 ALl字符串長度相等。現在我比較第一組和第二組以及第二組到第三組，並且很快...就像在圖像中一樣。第一組中的第一個元素與第二組中的所有元素進行比較。直到每個字符串進行比較。有沒有辦法加快我的程序的性能？所以我可以達到32000個長度爲15的字符串。

編輯

對不起過去post.After讀它，我知道我是啞巴問這樣。該計劃的目標是一個簡化。基於該奎因 - 麥克拉斯基算法

考慮

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

輸出ImplicantsByOneFinal

Answer 1

這不是真的清楚你要實現的，說實話的...你的描述沒有按」不符合你的代碼。 （例如，您的代碼從未提及過字符'1'，而您從不使用調用CompareString的結果的事實也是可疑的。）LINQ應該實現你的描述「組字符串的數字‘1’」簡單而有效：

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

這將只能算「1」的字符數在每串一次。你永遠不需要比較任何字符串與另一個。

如果這不是你實際想要做的，你需要澄清你的實際目標是什麼。

Answer 2

我不知道如何編寫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(); 
} 

好吧，我發現有很多的ToInt32。立即計算ImplicantsByOne中所有字符串的結果並稍後使用。 Esum也是如此。

3.要檢查是否num3是二的冪：

private boolean isPowerOfTwo(int x) { 
    return (x > 0 && (x & (x - 1)) == 0); 
}