1
\$\begingroup\$

I have a running program. That accepts 1 to 15 variables The goal of the program was a simplifier. Based on the Quine–McCluskey algorithm

Consider 3 variables

000
001
010
011
100
101
110
111

I group them by number of 1

000

001
010
100

011
101
110

111

Then I compare each string from the group to the next group

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.

then group the output again by number of 1 and compare them again until no strings can be compared.

I need to achieve a 15 variable but it take for ever for the program to finish.Any Idea how to speed it up. I was testing it on threading but just a little improvement.

Number of Strings: 2048 Length of variable: 11 Time: 10 minutes

Need to Achieved

Number of Strings: 32767 Length of variable: 15 Time: cannot be achieved

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

is there a way or algorithm to improve this code. it becomes slower on 11 to 15 variables.

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

Main Program

 MintermsByOne = Loaded with string 000 001 and so on

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

Output ImplicantsByOneFinal

\$\endgroup\$
1
  • \$\begingroup\$ It's good to see you here. \$\endgroup\$ May 10, 2013 at 12:39

1 Answer 1

1
\$\begingroup\$

I don't know how to write C#, but I want to help. So my code is given in Java.

  1. I think == is an O(n) operation, your CompareString is O(nlgn) (n = str1.Length). Use a simpler and faster O(n) way and see if the time decreases:

    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. Well, I found that there are a lot of ToInt32. Calculate the result of all strings in ImplicantsByOne at once and use it later. Do the same thing to Esum.

  3. To check if num3 is a power of two:

    private boolean isPowerOfTwo(int x) {
        return (x > 0 && (x & (x - 1)) == 0);
    }
    
\$\endgroup\$
1
  • \$\begingroup\$ Thanks .I will try to get the time of CompareString if its faster.Also thanks for the Power of two method :). \$\endgroup\$
    – Snippet
    May 11, 2013 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.