C++Guns – RoboBlog blogging the bot

Heute gefunden. Im Prinzip geht der pseudobug so:

void calc(int a, int b) {
  std::cout << "func " << a + b << "\n";
}

void add(int a, int b) {
  return calc(a, b);
}

int main() {
  add(2, 3);
  return 0;
}

Na, wer sieht das Problem? Wird calc aufgerufen?

(Ja, aber explicit void zurückgeben is braindamage ;) )

Update: Version with template instead of std::function C++ Guns: Passing function objects around (Update Example random generators)

Consider the following problem: One has a parallelly callable function which needs a random generator for every thread. One wants to call the function several times and every time we want another random sequence. How can we implement this?

Between every function call the random generator must keep its states. So the caller of the function must own the generator objects and pass them to the function. The caller is also in responsible the initialize the random generators. One can feed them with random seeds. But i think there exist a better solutions [1]

We create an array of n random generators, initialize them with a random seed and pass them per pointer to the function.

Inside this function we need a distribution. A simple rand() % maxrand is not good. It uses only the lower bits which may not be random. With c++11 we can bind the random generator and number distribution together. This allows us the create a nice dice() object which represent our rand(). Of course, this object can be simply pass around.

Output:

Thread 0 sum 5021
Thread 0 sum 4966
Thread 3 sum 4996
Thread 3 sum 5014
Thread 1 sum 5007
Thread 2 sum 4970
Thread 1 sum 5092
Thread 2 sum 5002
Info sizeof std::function 16

Code:

// can be passed by value
int function2(std::function dice) {
  int sum = 0;
  for(int i=0; i < 1000; i++) {
    sum += dice();
  }
  return sum;
}

// pass by reference. it has state
int function(std::minstd_rand& generator) {
  // we need random numbers from 0 to 10
  std::uniform_int_distribution distribution(0,10);

  // we bind the generator and distribution together to a new functor dice()
  // std::bind copy its arguments by value. To change the given generator state,
  // my must pass it by reference. This can be easly done with std:ref.
  // Yeah C++ can be strange.
  std::function dice = std::bind ( distribution, std::ref(generator) );

  return function2(dice);
}

int main() {
  omp_set_num_threads(4);

  // create 4 random generatores with random seed
  std::minstd_rand seedGen;
  std::minstd_rand generators[omp_get_num_threads()];
  for(int i=0; i < omp_get_num_threads(); i++) {
    generators[i].seed(seedGen());
  }

#pragma omp parallel for
  for(int i=0; i < 8; i++) {
    const int id = omp_get_thread_num();
    // pass one generator to our function
    int sum = function(generators[id]);

    std::cout << "Thread " << id << " sum " << sum << "\n";
  }

  std::cout << "Info sizeof std::function " << sizeof(std::function) << "\n";

  return 0;
}

[1] Tina’s Random Number Generator Library
Tina’s Random Number Generator Library

Standard random functions are not thread safe. Calling them in parallel may result in undefined behavior or the threads blocking each other. This is a little test to create the same random sequences in serial as in parallel too.

Setting the same seed on a random generator as a start point should produce the same random sequence. First we create one generator and print the first three numbers. Restart it with different seed numbers.
Then we create three random generators with the same seeds and call them parallel. They should create the same sequences even if they are called interleaved.

Program output:

seriell
seed 1
48271
182605794
1291394886

seed 2
96542
365211588
435306125

seed 3
144813
547817382
1726701011

parallel
Thread 0 seed 1: 48271
Thread 0 seed 1: 182605794
Thread 0 seed 1: 1291394886
Thread 1 seed 2: 96542
Thread 1 seed 2: 365211588
Thread 1 seed 2: 435306125
Thread 2 seed 3: 144813
Thread 2 seed 3: 547817382
Thread 2 seed 3: 1726701011

Yep, work as expected :D
The program looks not as simple as it might can be. But I think it is okay.

void waitlong() {
  long a = 0;
  for(int i=0; i < 1000000; i++) {
      a += i;
  }
}

int main() {
  // create some random number and store them in expectedResult
  int expectedResult[3][3] = { 0 };
  std::minstd_rand generator;

  std::cout << "seriell\n";

  for(int id=0; id < 3; id++) {
    generator.seed(id+1);
    std::cout << "seed " << id+1 << "\n";
    for(int i=0; i < 3; i++) {
      expectedResult[id][i] = generator();
      std::cout << expectedResult[id][i] << "\n";
    }
  }

  // create three generators with the same seed and call them parallel
  std::cout << "\nparallel\n";

  std::minstd_rand generators[3];
  generators[0].seed(1);
  generators[1].seed(2);
  generators[2].seed(3);

  int result[3][3] = { 0 };
  int count = 0;

  // create 3 threads and interleave them with schedule(static, 1) num_threads(3)
  // We can not call cout in a threaded enviroment. So we must store the random numbers
  // in a array and print them laster. count and result is for this.
#pragma omp parallel for firstprivate(count) shared(result) schedule(static, 1) num_threads(3)
  for(int i=0; i < 3*3; i++) {
    int id = omp_get_thread_num();
    int rand = generators[id]();

    // not error free even with omp critical
//     std::cout << "Thread " << id << " seed " << id+1 << ": " << rand << "\n";

    result[id][count++] = rand;

    // wait a litte bit to give the next thread a chance to start
    waitlong();
  }

  // now print and compre the results
  for(int id=0; id < 3; id++) {
    for(int i=0; i < 3; i++) {
      std::cout << "Thread " << id << " seed " << id+1 << ": " << result[id][i] << "\n";
      if(result[id][i] != expectedResult[id][i]) {
        std::cout << "but expected " << expectedResult[id][i] << "\n";
      }
    }
  }

  std::cout << "\nValues per seed must be equal\n";
  return 0;
}

Okay ich fasse mal zusammen. Ich sehe 3 Fälle, vom einfachsten zum schwersten.

1) Ganz normal Klassen ableiten.

class Base {
public:
  ~Base() {
    cout << "~TestClass\n";
  }
};

class Derived : public TestClass {
public:
  ~Derived() {
    cout << "~Derived\n";
  }
};

int main() {
  {
  cout << "a\n";
  Derived a;
  }
  cout << "b\n";
  Derived *b = new Derived();
  delete b;
}

Ausgabe:
a                                                                                                                
~Derived                                                                                                         
~Base
b
~Derived
~Base

Der Destructor wird immer aufgerufen.
2) Mit Polymorphie (Pointer ist vom Type Base)

class Base {
public:
  virtual ~Base() {
    cout << "~TestClass\n";
  }
};

class Derived : public TestClass {
public:
  virtual ~Derived() {
    cout << "~Derived\n";
  }
};

int main() {
  {
  cout << "a\n";
  Derived a;
  }
  cout << "b\n";
  Base *b = new Derived();
  delete b;
}

Ausgabe:
a                                                                                                                
~Derived                                                                                                         
~Base
b
~Derived
~Base

Der Destructor wird immer aufgerufen.

3) Mit Polymorphie und class Derived als abstracte Klasse

class Base {
public:
  virtual ~Base() = 0;
};

Base::~Base() {
    cout << "~Base\n";
}

class Derived : public Base {
public:
  virtual ~Derived() {
    cout << "~Derived\n";
  }
};

int main() {
  {
  cout << "a\n";
  Derived a;
  }
  cout << "b\n";
  Base *b = new Derived();
  delete b;
}

Ausgabe:
a                                                                                                                
~Derived                                                                                                         
~Base
b
~Derived
~Base

Der Destructor wird immer aufgerufen.
Der Destructor von Base ist zwar abstract, es gibt aber eine default Implementation, die im Zweifel garnichts macht. Es muss immer eine Implementation der Spezialfunktionen, wie dem Destructor, geben. Wird keine explicit angegeben, erstellt automatisch der Compiler eine. (Ausser man declariert ihn mit "=0" als abstract).

Wozu das ganze? Abstrace Klassen können nicht instanziiert werden, sie dienen wirklich nur als ein abstractes Interface. Sollte man es dennoch versuchen, bekommt man folgende Compilerfehler:

error: cannot declare variable ‘c’ to be of abstract type ‘Base’
 Base c;
 note:   because the following virtual functions are pure within ‘Base’:
 virtual ~Base() = 0;

PS: Wird das virtual keyword mal vergessen, wird der Base Destructor im ungünstigen Fall nicht aufgerufen ;)

Hf

Die Wikipedia Artikel zum Cocke-Younger-Kasami-Algorithmu kann man vergessen. Man kapiert nichts. Hab auf youtube ein 15min Video [1] von Benny Neugebauer dazu gefunden. Wunderbar, alles gleich verstanden :)
Hab ihn mal schnell in C++ implementiert. Hier die Hauptschleife:

    /*
    Für j = 2 ... n
      Für i = 1 ... n - j + 1
        Für k = 1 ... j - 1
          Setze V_{i,j} := V_{i,j} + { l | \exists B,C in N ((l -> BC) in P and B in V_{i,k} and C in V_{i + k, j - k}) \}

    Falls S \in V_{1,n}, stoppe und gib "w wird von G erzeugt" aus
    Stoppe und gib "w wird nicht von G erzeugt" aus
    */
    for(size_t row=1; row < n; row++) {
//        cout << "row " << row << "\n";
        for(size_t col=0; col < n-row; col++) {
//            cout << "col " << col << "\n";
            for(size_t k=0; k < row; k++) {
                const auto &e1 = V.at(k, col);
                const auto &e2 = V.at(row-k-1, col+k+1);

                for(size_t i=0; i < e1.size(); i++) {
                    for(size_t j=0; j < e2.size(); j++) {
//                        cout << "Check " << e1.at(i) << " " << e2.at(j) << "\n";
                        const Production::String toTest({e1.at(i), e2.at(j)});
                        for(const Production& p : P) {
                            if(p.right == toTest) {
                                // uniq append
                                if(contains(V.at(row, col), p.left) == false) {
                                    V.at(row, col).push_back(p.left);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Für jeden Matrixeintrag in der oberen linken Dreiecksmatrix:
Für jeden Eintrag oberhalt in der Spalte und Diagonal nach oben:
Schaue nach ob die Konkatenation der beiden Einträge in der rechten Seite der Produktionsregeln vorkommen:
Ja) Linke Seite der Produktion in die Matrix eintragen.

Steht am Ende in der letzten Zeile, erste Spalte das Startsymbol, dann kann das Wort erkannt werden.

CYK.zip

[1] https://www.youtube.com/watch?v=JugIgxUyA4Q