3. Hilfe bei Optimierung

Hilfe bei Optimierung

  • O

    Vielleicht kann mir hier jemand helfen um mein Programm zu optimieren.
    Nur in Bezug auf die Schnelligkeit.
    Es geht größtenteils um die do while Schleife in der unteren Häflte des main Programm's.
    Ohne die ganzen Rechnungen braucht die komplette Permutation (im 10er System) ca. 10 Sekunden.
    Mit dem ganzen Zeug braucht sie eine knappe Minute. Vielleicht sieht ja jemand noch wie ich irgendwas optimieren kann.
    Bitte überseht meine Englisch Kenntnisse! *g*
    Hoffe das Programm ist nicht zu groß!

    #define max_digits 6         //define the maximum value for the input
#define version "1.0"        
#define date "17.10.2003"

#include <iostream>
#include <string>
using namespace std;

void input_string(string &s,string** vgl,int base,int &a,int i);

void init_vgl(string s,string** vgl, int base, int &a,bool &err2);
void init_vgl_num(string** vgl,int base);

inline int s_num(string s,string** vgl,int base);
inline int op(int num1, int num2, int op);
inline void new_num(string** vgl,int base);
inline void swap(string &number, int first, int second);

string output(string s,string** vgl,int a);

/*
Main Program, for the input_string and output
*/

int main()
{
  int base; //Number base for the riddle!
  int a=0;

  cout << "Version:     " << version << "\n";
  cout << "Create Date: " << date << "\n";

  cout << "\nCreate and Solve a riddle from the following structure:\n";
  cout << "\n     s1        op1        s2   =   s3\n";
  cout << "\n     op4                  op5  =   op6\n";
  cout << "\n     s4        op2        s5   =   s6\n";
  cout << "   ------------------------------------\n";
  cout << "     s7        op3        s8   =   s9\n";
  cout << "\ns1-9 = Number up to n digits!\nop1-6 = + , - , * , /";

  cout << "\n\nOk now its up to you please choose!";
  cout << "\nFirst choose please the number base: ";
  cin >> base;
  cout << "\nPlease enter the encoded strings from the riddle (max is " << max_digits << " digits):";
  cout << "\nPlease enter only " << base << " different symbols for your encoded strings!";

  /*Variables for the input_string of the program*/
  string s1,s2,s3,s4,s5,s6,s7,s8,s9;
  int op1,op2,op3,op4,op5,op6;

  /*vgl is a n,2 matrix, n=number base
    on the first column are the encoded symbols
    on the second column is the actual init string*/
  string** vgl;
  int i;

  vgl=new string *[base];
  for (i=0;i<base;i++)
  {
    vgl[i]=new string[2];
  }

  cout << "\n\n";

  input_string(s1,vgl,base,a,1);
  input_string(s2,vgl,base,a,2);
  input_string(s3,vgl,base,a,3);
  input_string(s4,vgl,base,a,4);
  input_string(s5,vgl,base,a,5);
  input_string(s6,vgl,base,a,6);
  input_string(s7,vgl,base,a,7);
  input_string(s8,vgl,base,a,8);
  input_string(s9,vgl,base,a,9);

  init_vgl_num(vgl,base);

  cout << "\nNow enter please the Operator's you want to have in your riddle!\n(1) for +\n(2) for -\n(3) for *\n(4) for /";

  cout << "\n\nOperator 1: ";
  cin >> op1;

  cout << "Operator 2: ";
  cin >> op2;

  cout << "Operator 3: ";
  cin >> op3;

  cout << "Operator 4: ";
  cin >> op4;

  cout << "Operator 5: ";
  cin >> op5;

  cout << "Operator 6: ";
  cin >> op6;

  /*Variables for the calculating, for the loop
    and for the text decoration!*/
  int s1_n,s2_n,s3_n,s4_n,s5_n,s6_n,s7_n,s8_n,s9_n;
  string s1_o,s2_o,s3_o,s4_o,s5_o,s6_o,s7_o,s8_o,s9_o;
  int s3_erg,s6_erg,s7_erg,s8_erg,s9_erg_hori,s9_erg_verti;
  bool erfolg=false;
  char op_s[4+1]={'+','-','*','/','\0'};
  double cal=0;
  double exit=0;
  double fak1=1,fak2;

  for (i=1;i<base;i++)
  {
    fak1*=i;
  }
  fak2=fak1*base;

  cout << "\nCalculating\n." << flush;
  do
  {

    //One new point is one new digit at the beginning of the number!
    if (cal==fak1)
    {
      cout << "." << flush;
      cal=0;
    }
    cal++;

    s1_n=s_num(s1,vgl,base);
    s2_n=s_num(s2,vgl,base);
    s3_n=s_num(s3,vgl,base);

    s3_erg=op(s1_n,s2_n,op1);

    if (s3_n==s3_erg)
    {
      s4_n=s_num(s4,vgl,base);
      s5_n=s_num(s5,vgl,base);
      s6_n=s_num(s6,vgl,base);

      s6_erg=op(s4_n,s5_n,op2);

      if (s6_n==s6_erg)
      {
        s7_n=s_num(s7,vgl,base);

        s7_erg=op(s1_n,s4_n,op4);

        if (s7_n==s7_erg)
        {
          s8_n=s_num(s8,vgl,base);

          s8_erg=op(s2_n,s5_n,op5);

          if (s8_n==s8_erg)
          {
            s9_n=s_num(s9,vgl,base);

            s9_erg_hori=op(s7_n,s8_n,op3);
            s9_erg_verti=op(s3_n,s6_n,op6);

            if (s9_n==s9_erg_hori && s9_n==s9_erg_verti)
            {
              s1_o=output(s1,vgl,a);
              s2_o=output(s2,vgl,a);
              s3_o=output(s3,vgl,a);
              s4_o=output(s4,vgl,a);
              s5_o=output(s5,vgl,a);
              s6_o=output(s6,vgl,a);
              s7_o=output(s7,vgl,a);
              s8_o=output(s8,vgl,a);
              s9_o=output(s9,vgl,a);
              cout << "\n\t\t" << s1_o << "\t" << op_s[op1-1] << "\t" << s2_o << "\t=\t" << s3_o << "\n";
              cout << "\t\t"<< op_s[op4-1] << "\t\t" << op_s[op5-1] << "\t\t" << op_s[op6-1] << "\n";
              cout << "\t\t" << s4_o << "\t" << op_s[op2-1] <<"\t" << s5_o << "\t=\t" << s6_o << "\n";
              cout << "\t\t=\t\t=\t\t=\n";
              cout << "\t\t" << s7_o << "\t" << op_s[op3-1] << "\t" << s8_o << "\t=\t" << s9_o << "\n";

              cout << "\n\n";

              for (i=0;i<base;i++)
              {
                cout << vgl[i][0] << " = " << vgl[i][1] << "\n";
              }

              erfolg=1;
            }
          }
        }
      }
    }

    exit++;

    new_num(vgl,base);

  }while (erfolg!=true && exit<fak2);

  if (erfolg==0) cout << "\n\nNo Solution found!";

  cout << "\n\n\t\t\tEND";
}

/*
Methode for the string input.
With an error control for wrong input!
*/

void input_string(string &s,string** vgl,int base,int &a,int i)
{
  bool err1,err2;

  do
  {
  err1=false;
  err2=false;

  cout << "Enter the string for s" << i << ": ";
  cin >> s;

  if (s.size()>max_digits)
  {
    err1=true;
    cout << "\nYou've entered to much digits for the number, please stay within the Parameters and enter only 6 Digits for every string!\n\n";
  }
  else
  {
    init_vgl(s,vgl,base,a,err2);
  }

  if (err2==true)
  {
    cout << "\nYou've already entered to much different symbols for the base you've entered above. Please use only " << base << " different symbols!\n\n";
  }

  }while(err1!=false || err2!=false);

}

/*
The First Column of the Matrix will be initiated with the different symbols from the input_string!
*/

void init_vgl(string s,string** vgl, int base, int &a,bool &err2)
{
  string::size_type j;
  string temp;
  int i;
  bool vergl;

  for (j=0;j<s.size();j++)
  {
    temp=s[j];

    for (i=0;i<base;i++)
    {
      vergl = temp==vgl[i][0];

      if (vergl==true)
      {
        err2=false;
        break;
      }
      if (vergl==false && vgl[i][0].size()==0)
      {
        vgl[i][0]=temp;
        a++;
        err2=false;
        break;        
      }
      else
      {
        err2=true;
      }
    }
  }

}

/*
The second column of the Matrix will be initiated with the first number string that is possible!
*/

void init_vgl_num(string** vgl, int base)
{
  int i;
  int a=48;
  int b=65;

  for (i=0;i<base;i++)
  {
    if (i<=9)
    {
      vgl[i][1]=a;
      a++;
    }
    else
    {
      vgl[i][1]=b;
      b++;
    }
  }
}

/*
The string's will be transformed into int values, for the calculating!
*/

inline int s_num(string s,string** vgl,int base)
{
  string::size_type j;
  string temp;
  int num_temp,num=0,faktor=1;
  int i;
  bool vergl;

  for (j=s.size();j>0;j--)
  {
    temp=s[j-1];

    for (i=0;i<base;i++)
    {
      vergl = temp==vgl[i][0];

      if (vergl==true)
      {
        if (vgl[i][1]<="9")
        {
          num_temp=(vgl[i][1].at(0)-48);
        }
        else
        {
          num_temp=(vgl[i][1].at(0)-55);          
        }
        num_temp*=faktor;
        num+=num_temp;
        faktor*=base;
        break;
      }
    }
  }

  return num;

}

/*
The different operations will be performed in this Methode!
*/

inline int op(int num1, int num2, int op)
{
  int Ergebnis=0;

  switch (op)
  {
    case 1 :  Ergebnis=num1+num2;
              break;

    case 2 :  if (num1-num2>0)
              {
                Ergebnis=num1-num2;
              }
              break;

    case 3 :  Ergebnis=num1*num2;
              break;

    case 4 :  if (num2!=0)
              {
                if (num1%num2==0)
                {
                  Ergebnis=num1/num2;
                }
              }
              break;
  }

  return Ergebnis;
}

/*
In this Method the new number will be determinate, by the permutation of the number!
*/

inline void new_num(string** vgl,int base)
{
string number;
string::size_type i,j;
int a,b,c;

    for (i=0;i<base;i++)
    {
      number+=vgl[i][1];
    }

    for (i=number.size();i>0;i--)
    {
      if (number[i-2]<number[i-1])
      {
        a=i-2;
        b=i-1;
        break;
      }
    }

    for (i=b;i<number.size();i++)
    {
      if (number[i]>number[a])
      {
        c=i;
      }
    }

    swap(number,a,c);

    for (i=b;i<number.size();i++)
    {
      for (j=i;j<number.size();j++)
      {
        if (number[j]<number[i])
        {
          swap(number,j,i);
        }
      }
    }

    for (i=0;i<number.size();i++)
    {
      vgl[i][1]=number[i];
    }
}

/*
Swap is a Method for the Permutation. It swap's the digits to get a new number!
*/
inline void swap(string &number, int first, int second)
{
  char temp;

  temp=number[first];
  number[first]=number[second];
  number[second]=temp;

}

/*
Converted the input strings for a formatted output!
*/

string output(string s,string** vgl,int a)
{
int j;
string::size_type i;
string output="";

for (i=0;i<s.size();i++)
{
  for (j=0;j<a;j++)
  {
    if (s[i]==vgl[j][0].at(0))
    {
      output+=vgl[j][1];
    }
  }
}

return output;
}
    0
  • ?

    Das Problem ist, dass der Algorithmus recht unverständlich ist und überhaupt, was das Programm eigentlich machen soll (Ist das ein Lineares Gleichungssystem?). In den Kommentaren sollte nicht drin stehen, was das Programm macht (das sehe ich so auch), sondern wie es funktioniert.
    Und die Variablennamen tragen auch nicht so ungemein zum Verständniss bei ;((

    Und lass mal ein paar unnötige geschweifte Klammern weg, z.B.

    statement;

for (int a = 0; a < maxA; ++a)    // Wozu danach ne Klammer?
    for (int b = 0; b < maxB; ++b)
    {
        [bla]
    }

statement;

    schöner Code ist auch meistens schnell. Und ermöglicht es anderen besser, dir zu helfen 😃

    0
  • O

    Also das Programm soll Symbolrätsel lösen. (Besipiel)

    Und die Kommentare sind ja auch nur noch Platzhalter, bin noch nicht fertig mit dem kommentieren gewesen.

    Und die Methode new_num fürht einfach eine lexigrapische (oder wie das heißt) Permutation durch.

    Ich weiß ja auch das man die geschweiften Klammern weglassen kann, aber ich hab mir das irgendwie so angewöhnt.

    MfG
    Oliver

    0
  • P

    @Optimizer:

    schöner Code ist auch meistens schnell.

    Wenn du mit 'nem Compiler von 1975 arbeitest, dann ja...

    Und lass mal ein paar unnötige geschweifte Klammern weg, z.B.

    Wie schön das ist, ist Ansichtssache und hängt von den Umständen ab (also bei schlechter Beleuchtung und nem Glas Wein hat's ne gute Chance, aber generell?)

    Der Performance-Killer wird wohl s_num() sein, und an dem läßt sich ja noc heiniges machen..

    1. Kleinigkeiten:
      - den string als & rübergeben - sparst du dir ne Kopie. Kommt auf die STL-Implementation drauf an, aber etwas bringts auf jeden Fall.
      - die inline's vor ihrer Benutzung aufführen. Bringt wahrscheinlich fast nix, aber so könnten sie wenigstens

    2. Großheit
      - Deine Datenstruktur vgl ist völlig ungeeignet für das problem.

    Besser wäre ein Hilfsarray der Länge 256, wo am index [c] der "echte" Wert vom code c drinsteht. Außerdem lohnt es sich nicht mit einem string[1] zu arbeiten, wenn es auch ein char tut. Außerdem kann man auch vorwärts durchgehen (was für so ein kurzes Buffer nur selten was bringt, aber immerhin)

    Wenn ich's recht versteh, nimmt die Funktion eine codierten string (z.B. '

    int codemap[256];
    // So füllen, das codemap['x'] gibt dir die Ziffer gibt, die für 'x' steht. Natürlich nur einmal beim Einlesen der Daten und beim Permutieren. evtl. gleich in codemap statt in vgl permutieren). Und gleich als Integer, jedesmal in der schleife die Hex-Digit -> int - Umwandlung muß wirklich nicht sein

    int num = 0;
for(j=0; j<s.size(); ++j)
{
  num *= base;
  int digit = s[j];  
  num += digit;
}
    0
Anmelden zum Antworten