Quelle bench-freeband.cpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021 James D. Mitchell
//                    Reinis Cirpons
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "bench-main.hpp"  // for LIBSEMIGROUPS_BENCHMARK
#include "catch.hpp"       // for REQUIRE, REQUIRE_NOTHROW, REQUIRE_THROWS_AS

#include "libsemigroups/freeband.hpp"  // for FreeBan`
#include "libsemigroups/types.hpp"     // for word_type

namespace libsemigroups {

  word_type random_word(size_t length, size_t nr_letters) {
    static std::random_device               rd;
    static std::mt19937                     gen(rd());
    std::uniform_int_distribution<uint64_t> dist(0, nr_letters);
    word_type                               out;
    for (size_t i = 0; i < length; ++i) {
      out.push_back(dist(gen));
    }
    return out;
  }

  void random_tree_word_helper(std::vector<size_t>& cont,
                               word_type&           out,
                               size_t               padding) {
    if (cont.size() == 1) {
      out.push_back(cont[0]);
      for (size_t i = 0; i < padding; i++)
        out.push_back(cont[0]);
    } else {
      // left half
      size_t l = cont.back();
      // left subtree
      cont.pop_back();
      random_tree_word_helper(cont, out, padding);
      // left letter
      out.push_back(l);
      cont.push_back(l);
      // padding
      if (padding > 0) {
        word_type pad = random_word(padding, cont.size() - 1);
        for (size_t i = 0; i < pad.size(); i++)
          pad[i] = cont[pad[i]];
        out.insert(out.end(), pad.begin(), pad.end());
      }
      // right half
      word_type           right;
      std::vector<size_t> right_cont(cont.size());
      std::copy(cont.begin(), cont.end(), right_cont.begin());
      std::random_shuffle(right_cont.begin(), right_cont.end());
      size_t r = right_cont.back();
      // right letter
      out.push_back(r);
      // right subtree
      right_cont.pop_back();
      random_tree_word_helper(right_cont, right, padding);
      out.insert(out.end(), right.rbegin(), right.rend());
    }
  }

  word_type random_tree_word(size_t nr_letters, size_t padding) {
    word_type           out;
    std::vector<size_t> cont;
    for (size_t i = 0; i < nr_letters; i++)
      cont.push_back(i);
    std::random_shuffle(cont.begin(), cont.end());
    random_tree_word_helper(cont, out, padding);
    return out;
  }

  TEST_CASE("random words (length)", "[quick][000]") {
    size_t              a = 50;
    std::vector<size_t> L = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000};
    for (auto const& l : L) {
      auto x = random_word(l, a), y = random_word(l, a);
      BENCHMARK("Random Word, Alphabet " + std::to_string(a) + " Length "
                + std::to_string(l)) {
        for (size_t i = 0; i < 100 / a; ++i) {
          freeband_equal_to(x, y);
        }
      };
    }
  }

  TEST_CASE("random words (alphabet)", "[quick][000]") {
    std::vector<size_t> A = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};
    size_t              l = 1000;
    for (auto const& a : A) {
      auto x = random_word(l, a), y = random_word(l, a);
      BENCHMARK("Random Word, Alphabet " + std::to_string(a) + " Length "
                + std::to_string(l)) {
        for (size_t i = 0; i < 100 / a; ++i) {
          freeband_equal_to(x, y);
        }
      };
    }
  }

  TEST_CASE("random words (alphabet and length)", "[standard][000]") {
    std::vector<size_t> A = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};
    std::vector<size_t> L = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000};
    for (auto const& a : A)
      for (auto const& l : L) {
        auto x = random_word(l, a), y = random_word(l, a);
        BENCHMARK("Random Word, Alphabet " + std::to_string(a) + " Length "
                  + std::to_string(l)) {
          for (size_t i = 0; i < 100 / a; ++i) {
            freeband_equal_to(x, y);
          }
        };
      }
  }

  TEST_CASE("unpadded random tree words", "[quick][001]") {
    std::vector<size_t> A = {5, 6, 7, 8, 9, 10};
    for (auto const& a : A) {
      auto x = random_tree_word(a, 0), y = random_tree_word(a, 0);
      BENCHMARK("Random Tree Word, Alphabet " + std::to_string(a)) {
        freeband_equal_to(x, y);
      };
    }
  }

  TEST_CASE("padded random tree words", "[quick][002]") {
    std::vector<size_t> A = {5, 6, 7, 8, 9, 10};
    std::vector<size_t> P = {0, 5, 10, 15};
    for (auto const& a : A)
      for (auto const& p : P) {
        auto x = random_tree_word(a, p), y = random_tree_word(a, p);
        BENCHMARK("Random Tree Word, Alphabet " + std::to_string(a) + " Length "
                  + std::to_string(x.size() + y.size())) {
          freeband_equal_to(x, y);
        };
      }
  }

}  // namespace libsemigroups

quality86%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.