C ++: функция эксцентриситета на метрических пространствах

От: Из: Общие

Функция эксцентриситета с параметром $ r $ на метрическом пространстве $ X $ с участием $ N $ очков

begin {gather} f (y) = left ( sum_ {x in X} frac {d ^ r (x, y)} N right) ^ {1 / r}; ~~~ x, y in X end {gather}
(Примечание: для реализации $ X $ конечное метрическое пространство, поскольку $ N < infty $ для вычислимости)

Я попытался реализовать это для общего MetricSpace класс, с двумя примерами метрических пространств, а именно $ mathbb {R} ^ n $ и метрика на цепях ДНК. Однако, как это реализовано в настоящее время, я не могу объявить функцию эксцентриситета своим другом MetricSpace потому что MetricSpace это шаблон. Поэтому мне пришлось сделать две функции эксцентриситета, одну для $ mathbb {R} ^ n $ и один для ДНК. Этот подход работает, но не идеален.

Как я могу улучшить дизайн программы для удобства сопровождения, чтобы стало возможным определить только одну функцию эксцентриситета, которая принимает MetricSpace в качестве аргумента, который затем может быть Rn или DNA?

#include <iostream>
#include <stdio.h>
#include <stdexcept>
#include <vector>
#include <cmath>
#include <algorithm>
#include <time.h>
#include <random>

template<typename T>
class MetricSpace {
public:
    double d();

private:
    std::vector<T> points_;
};

class Rn : public MetricSpace<std::vector<double>> {
public:
    using MetricSpace::d; // So we can overload the distance function

    // Constructor
    Rn(std::vector<std::vector<double>> points, int n): dimension_{n} {
        points_ = points;

        bool invalidDimension = false;
        for (long i = 0; i < points_.size(); i++) {
            if (points_[i].size() != dimension_) {
                invalidDimension = true;
                break;
            }
        }

        if (invalidDimension) {
            throw std::invalid_argument("At least one point has the wrong dimension.");
        }
    }

    // Distance function
    double d(const std::vector<double>& point1, const std::vector<double>& point2) {
        double squaredDistance{0};

        for (int i = 0; i < dimension_; i++) {
            squaredDistance += (point1[i] - point2[i])*(point1[i] - point2[i]);
        }

        return sqrt(squaredDistance);
    }

private:
    std::vector<std::vector<double>> points_;
    int dimension_;
    friend double eccentric(Rn& space, long pointIndex, double r);
};

// Elements are sequences finite (x_1, ..., x_N) with x_i in {A, C, G, T}
// and the distance d(x, y) is the amount of i for which x_i != y_i.
class DNA: public MetricSpace<std::vector<char>> {
public:
    using MetricSpace::d;

    // Constructor
    DNA(std::vector<std::vector<char>> points, int length): length_{length} {
        points_ = points;

        bool invalidDimension = false;
        bool invalidCharacter = false;

        for (long i = 0; i < points_.size(); i++) {
            if (points_[i].size() != length_) {
                invalidDimension = true;
            }
            for (int j = 0; j < points_[i].size(); j++) {
                if ( points_[i][j] != 'A' && points_[i][j] != 'C' && points_[i][j] != 'G' && points_[i][j] != 'T' ) {
                    invalidCharacter = true;
                }
            }
        }

        if (invalidDimension) {
            throw std::invalid_argument("At least one DNA strand is too long or too short.");
        }

        if (invalidCharacter) {
            throw std::invalid_argument("At least one DNA strand contains a character not equal to A, C, G or T.");
        }

    }

    // Distance function
    double d(const std::vector<char>& point1, const std::vector<char>& point2) {
        int counter{0};
        for (int i = 0; i < point1.size(); i++) {
            if (point1[i] != point2[i]) {
                counter++;
            }
        }

        return counter;
    }

private:
    std::vector<std::vector<char>> points_;
    int length_;
    friend double eccentric2(DNA& space, long pointIndex, double r);
};


double eccentric(Rn& space, long pointIndex, double r) {
    double sum = 0;
    long N = space.points_.size();
    for (long i = 0; i < N; i++) {
        sum += pow(space.d(space.points_[pointIndex], space.points_[i]), r);
    }

    return pow(sum/N, 1/r);
}

double eccentric2(DNA& space, long pointIndex, double r) {
    double sum = 0;
    long N = space.points_.size();
    for (long i = 0; i < N; i++) {
        sum += pow(space.d(space.points_[pointIndex], space.points_[i]), r);
    }

    return pow(sum/N, 1/r);
}

Rn RnMaker(int dimension, long numberOfPoints) {

    std::vector<std::vector<double>> points;

    // Setting up the random machine
    double lowerBound = 0;
    double upperBound = 10;
    std::uniform_real_distribution<double> uniform(lowerBound, upperBound);
    std::default_random_engine randomEngine;

    // Creating the random points
    for (long i = 0; i < numberOfPoints; i++) {
        std::vector<double> point;
        for (int j = 0; j < dimension; j++) {
            point.push_back(uniform(randomEngine));
        }
        points.push_back(point);
    }

    return Rn(points, dimension);
}

DNA DNAMaker(int length, long numberOfPoints) {

    std::vector<std::vector<char>> points;

    // Random seed
    srand(time(NULL));

    char characters[4] = {'A', 'C', 'G', 'T'};

    // Creating the random points
    for (long i = 0; i < numberOfPoints; i++) {
        std::vector<char> point;
        for (int j = 0; j < length; j++) {
            point.push_back(characters[rand() % 4]);
        }
        points.push_back(point);
    }

    return DNA(points, length);
}

int main() {
    Rn space = RnMaker(3, 100);
    DNA space2 = DNAMaker(10, 100);

    std::cout << "Eccentricity of the 10'th point in R^n with r = 2.1: " << eccentric(space, 10, 2.1) << std::endl;
    std::cout << "Eccentricity of the 10'th point in a DNA metric space with r = 2.1: " << eccentric2(space2, 10, 2.1) << std::endl;
}

2 ответа
2

  • использовать шаблон для внутреннего типа
  • Сделайте основу абстрактной
  • Использовать const ссылки в соответствующих случаях
  • Переместите определение вашего списка персонажей в класс
  • Преобразуйте методы make в конструкторы
  • Использовать std::find вместо внутреннего цикла в вашем коде проверки
  • Использовать std::array чтобы заставить квадратную матрицу, а не перебирать
  • Напишите только одно определение eccentric
  • Не храните номер измерения как член

Предлагается:

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <random>
#include <vector>


template<
    size_t N,    // The point size
    typename T,  // The array sub-type
    typename D   // The distance type
>
class MetricSpace {
public:
    typedef std::array<T, N> Point;

    virtual D distance(
        const Point &point1,
        const Point &point2
    ) const = 0;

    // Note that this always returns a promoted double and not the distance type
    double eccentric(size_t pointIndex, double r) const {
        double sum = 0;
        for (size_t i = 0, e = points.size(); i != e; i++) {
            // Skip computation of the distance to "self" which should be 0
            if (i != pointIndex) {
                D dist = distance(points[pointIndex], points[i]);
                sum += pow(dist, r);
            }
        }

        return pow(sum/points.size(), 1/r);
    }

protected:
    MetricSpace() {}
    MetricSpace(const std::vector<Point> &_points) : points(_points) {}

    std::vector<Point> points;
};


template<
    size_t N,
    typename T = double,
    typename D = double
>
class Rn: public MetricSpace<N, T, D> {
public:
    typedef MetricSpace<N, T, D> Base;
    typedef typename Base::Point Point;

    Rn(const std::vector<Point> &_points): Base(_points) {}

    Rn(size_t n_points) {
        // Setting up the random machine
        T lowerBound = 0, upperBound = 10;
        std::uniform_real_distribution<T> uniform(lowerBound, upperBound);
        std::default_random_engine randomEngine;

        // Creating the random points
        for (size_t i = 0; i < n_points; i++) {
            Point point;
            for (size_t j = 0; j < N; j++) {
                point[j] = uniform(randomEngine);
            }
            Base::points.push_back(point);
        }
    }

    D distance(const Point &point1, const Point &point2) const {
        D squaredDistance = 0;

        for (size_t i = 0, e = point1.size(); i != e; i++) {
            T diff = point1[i] - point2[i];
            squaredDistance += diff*diff;
        }

        return sqrt(squaredDistance);
    }
};


// Elements are sequences finite (x_1, ..., x_N) with x_i in {A, C, G, T}
// and the distance d(x, y) is the amount of i for which x_i != y_i.
template<
    size_t N,
    typename T = char,
    typename D = int
>
class DNA: public MetricSpace<N, T, D> {
public:
    typedef MetricSpace<N, T, D> Base;
    typedef typename Base::Point Point;

    DNA(const std::vector<Point> &_points): Base(_points) {
        validate();
    }

    DNA(size_t n_points) {
        // Random seed
        srand(time(NULL));

        // Creating the random points
        for (size_t i = 0; i < n_points; i++) {
            Point point;
            for (size_t j = 0; j < N; j++) {
                point[j] = characters[rand() % 4];
            }
            Base::points.push_back(point);
        }

        validate();
    }

    void validate() const {
        const char *last = characters + sizeof(characters);
        for (const Point &p: Base::points) {
            for (T x: p) {
                if (std::find(characters, last, x) == last) {
                    throw std::invalid_argument(
                        std::string("At least one DNA strand contains bad character '")
                        + x + '''
                    );
                }
            }
        }
    }

    D distance(const Point &point1, const Point &point2) const {
        D counter = 0;
        for (size_t i = 0; i < point1.size(); i++) {
            if (point1[i] != point2[i]) {
                counter++;
            }
        }

        return counter;
    }

    static constexpr T characters[] = {'A', 'C', 'G', 'T'};
};


int main() {
    Rn<3> space = Rn<3>(100);
    DNA<10> space2 = DNA<10>(100);

    std::cout << "Eccentricity of the 10'th point in R^n with r = 2.1: "
              << space.eccentric(10, 2.1) << std::endl;
    std::cout << "Eccentricity of the 10'th point in a DNA metric space with r = 2.1: "
              << space2.eccentric(10, 2.1) << std::endl;
}

Предостережение: «кое-что» из этого — современный C ++, хотя я не эксперт. Это компилируется и работает с g++ -Wall -std=c++17.

    Быть последовательным

    В вашем коде много несоответствий:

    • Почему есть MetricSpace::d() что не требует параметров?
    • Зачем использовать правильные случайные функции C ++ в RnMaker(), но srand()/rand() в DNAMaker()?
    • Зачем использовать шаблонный базовый класс для MetricSpace, но потом специализировались eccentric() функция?

    Включите предупреждения компилятора и исправьте их

    Мой компилятор предупреждает об использовании вами long i в for-loops, где вы сравниваете это с size_t значение, например, points_.size(). Опять же, будьте последовательны и используйте size_t последовательно для всех размеров, размеров и индексов.

    удалять class MetricSpace

    Ничего в нем фактически не используется производными классами, все переопределяется. Вы можете удалить этот класс, и ваш код по-прежнему будет компилироваться и работать.

    Сделать eccentric() шаблон

    И то и другое eccentric() и eccentric2() сделайте то же самое, только тип первого параметра отличается. Это работа для шаблонов. Так:

    template<typename Space>
double eccentric(Space& space, size_t pointIndex, double r) {
    ...
}

    Вам также необходимо обновить свой friend объявления, соответствующие шаблону:

    class Rn {
    ...
    template<typename Space>
    friend double eccentric(Space& space, size_t pointIndex, double r);
};

    Рассмотрите возможность const доступ к points_

    Вместо того, чтобы делать points_ private и нужно добавить friend объявления для любой функции, которая должна получить доступ points_рассмотрите возможность добавления функции доступа, чтобы получить const ссылка на points_, вот так:

    class Rn {
public:
    ...
    const auto &get_points() const {
        return points_;
    }
    ...
};

    (Обратите внимание, что это зависит от C ++ 14, для более ранних версий вам нужно явно указать тип возвращаемого значения.) Затем в eccentric() ты можешь написать:

    template<typename Space>
double eccentric(Space& space, size_t pointIndex, double r) {
    auto &points = space.get_points();
    size_t N = points.size();
    ...
}

    Попробуйте сделать размер / длину точки параметром шаблона.

    Вектор векторов очень неэффективен. И для данного пространства все точки в этом пространстве имеют одинаковое измерение или длину. Поэтому имеет смысл сделать это параметром шаблона, а затем использовать std::array за каждую точку. Пока вы это делаете, используйте using-объявление для объявления типа точки для экономии ввода. Например:

    template<size_t Dimension>
class Rn {
public:
    using Point = std::array<double, Dimension>;
    
    Rn(const std::vector<Point> &points): points_(points) {}

    double d(const Point &point1, const Point &point2) {
        ...
    }        
    
private:
    std::vector<Point> points_;
};

    Вы также должны сделать RnMaker() шаблон, такой что в main() вы пишете что-то вроде:

    auto space = RnMaker<3>(100);

    Сделать Maker() функции статические функции-члены

    Это позволяет избежать всех проблем с созданием RnMaker() и DNAMaker() шаблоны и друзья. Сделав их статическими функциями-членами, они уже являются частью шаблона и могут без проблем обращаться к закрытым переменным-членам. Например:

    template <size_t Dimension>
class Rn {
public:
    using Point = std::array<double, Dimension>;

    Rn(const std::vector<Point> &points = {}): points_(points) {}

    double d(const Point& point1, const Point& point2) {
        ...
    }

    static Rn generate(size_t numberOfPoints) {
        Rn space;
        ...
        // Creating the random points
        for (size_t i = 0; i < numberOfPoints; i++) {
            Point point;
            for (size_t j = 0; j < Dimension; j++) {
                 point[j] = uniform(randomEngine);
             }
             space.points_.push_back(point);
         }

        return space;
    }

private:
    std::vector<Point> points_;
};

    А потом вы используете это так:

    auto space = Rn<3>::generate(100);

    Вы можете сделать что-то подобное для DNA конечно.

    Рассмотрите возможность использования алгоритмов STL

    Есть несколько алгоритмов STL, которые могут помочь вам заменить часть руководства. for-петли у вас есть, например std::generate_n() заполнять points_ со случайными точками, и std::inner_product() для вычисления суммы расстояний в степени.

    Использовать std::pow() и std::sqrt()

    Хотя в вашем коде это не проблема, вам следует предпочесть std:: вариант математических функций везде, где это возможно. Они будут иметь перегрузки для типов с плавающей запятой и, возможно, целочисленных типов, и поэтому будут более эффективными и / или правильными, чем математические функции C. pow() и sqrt() всегда предполагать double, и неявно приведёт.

    Именование вещей

    Я бы переименовал eccentric() к eccentricity() или возможно даже calculate_eccentricity(). Предпочитайте использовать глаголы для функций и существительные для большинства других вещей.

    Также рассмотрите возможность переименования d() к distance(). Я знаю, что первое — это обычное сокращение в математике, но в программировании оно встречается реже.

    • Статические функции «Maker» — это «нормально» — и фактически это единственный вариант в Python. В C ++ существует перегрузка конструкторов, поэтому нет причин не быть конструкторами.

      — Райндериен

    • 2

      @Reinderien: Верно, хотя я бы не стал делать конструктор, который заполняется случайными точками только для тестирования. В этом отношении исходная функция, возможно, была лучше, за исключением копирования вектора. Может быть, конструктор, который тогда принимает ссылку на r-значение на вектор точек, чтобы его можно было эффективно перемещать, а затем по-прежнему внешнюю функцию, которая генерирует случайные точки?

      — Г. Сон

    • Да, это было бы разумно. Честно говоря, я не понимаю научную подоплеку, поэтому, если использование random в технических целях, это безопасно в конструкторе, но если это просто для «демонстрации», тогда да, возможно, отдельно.

      — Райндериен

    • Большое спасибо за ваш отзыв. У меня вопрос о векторе векторов: точка в метрическом пространстве обычно не будет вектором некоторой фиксированной длины, как в этих примерах (так что, возможно, плохо выбранные примеры). Например, нити ДНК могут иметь разную длину или у нас может быть метрическое пространство функций. Если я сделаю MetricSpace абстрактным, с точками массива типа T с шаблоном, есть ли лучший выбор, чем еще один std :: array при реализации Rn и DNA?

      — шкура Пинды

    • 1

      Если точка действительно имеет переменную длину, то с помощью std::vector вместо std::array ибо это, конечно, нормально. Используйте лучший тип для точек в метрическом пространстве.

      — Г. Сон

    Похожие записи:

    1. Реализация функции шаблона recursive_replace_copy_if на C ++
    2. Программы C и C ++, позволяющие увеличить время доступа к файлам
    3. Симуляция биржи, торгующая между валютами
    4. Система оценок университетов (ООП)
    5. Калькулятор домашних расходов (OOP)

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *