Как мне оптимизировать этот код? - PullRequest
0 голосов
/ 07 ноября 2018

Я пишу функцию, чтобы найти среднее значение массива, в котором массив состоит в основном из чисел, которые переполнились бы, если бы были добавлены все сразу.

Он работает путем создания подмассива (b в моем коде), который равен половине размера входного (a в моем коде) массива (ar_size в моем коде), а затем помещает среднее значение из 2 значений из входной массив a[i+0] and a[i+1] без наложения на b[j].

Как только он выполняет итерацию по всему входному массиву, он перезапускает функцию с возвратом подмассива и размера входного массива до тех пор, пока размер не станет равным 2, а затем завершает рекурсию, возвращая среднее из двух значений b[2].

Прошу прощения за повторное использование j.

Также размер массива равен некоторой степени двух.

uint64_t* array_average(uint64_t* a, const int ar_size)
{
    uint64_t* b = new uint64_t[ar_size / 2];

    uint64_t* j = new uint64_t;

    if (ar_size == 2)
    {
     *j = (a[0] / 2) + (a[1] / 2) + ((a[0] % 2 + a[1] % 2) / 2);

     return j;
    }

    for (int i = 0; i < ar_size; i += 2)
    {
        b[*j] = (a[i + 0] / 2) + (a[i + 1] / 2) + ((a[i + 0] % 2 + a[i + 1] % 2) / 2);

        ++*j;
    }
    delete j;
    return array_average(b, ar_size / 2);
}

Также у кого-нибудь есть лучший способ усреднения при работе с числами, которые могут вызвать переполнение?

Вот пересмотренная версия:

uint64_t* tools::array_average(uint64_t* a, const int ar_size)
{
    uint64_t* b = new uint64_t[ar_size];
    uint64_t* c = new uint64_t[ar_size / 2];

    int j;
    j = 0;

    for (int i = 0; i < ar_size; ++i)
    {
        b[i] = a[i];
    }

    if (runs > 0) //This is so i do not delete the original input array I.E not done with it
    {
        delete[] a;
    }

    if (ar_size == 2)
    {
        uint64_t* y = new uint64_t;

        runs = 0;

        *y = (b[0] / 2) + (b[1] / 2) + ((b[0] % 2 + b[1] % 2) / 2); 

        delete[] b;

        return y;
    }

    for (int i = 0; i < ar_size; i += 2)
    {
        c[j] = (b[i + 0] / 2) + (b[i + 1] / 2) + ((b[i + 0] % 2 + b[i + 1] % 2) / 2);

        ++j;
    }

    delete[] b;

    ++runs;

    return array_average(c, ar_size / 2);

Ответы [ 3 ]

0 голосов
/ 07 ноября 2018

Вы можете использовать:

constexpr bool is_power_of_2(uint64_t n)
{
    return n && !(n & (n - 1));
}

uint64_t array_average(std::vector<uint64_t> v)
{
    if (!is_power_of_2(v.size())) {
        throw std::runtime_error("invalid size");
    }
    uint64_t remainder = 0;
    while (v.size() != 1) {
        for (int i = 0; i != v.size(); i += 2) {
            remainder += (a[i] % 2 + a[i + 1] % 2);
            b[i / 2] = a[i] / 2 + a[i + 1] / 2;
            if (remainder >= 2 && b[i / 2] < -(remainder / 2)) {
                b[i / 2] += remainder / 2;
                remainder %= 2;
            }
        }
        v.resize(v.size() / 2);
    }
    return v[0] + remainder / 2;
}
0 голосов
/ 07 ноября 2018

На самом деле не так уж много нужно конвертировать, так как в stl уже есть контейнеры, функции и алгоритмы, которые сделают это за вас. Без какой-либо функции изучите эту короткую программу:

#include <vector>
#include <numeric>
#include <iostream>
#include <exception>

int main() {
    try {

        std::vector<uint64_t> values{ 1,2,3,4,5,6,7,8,9,10,11,12 };
        int total = std::accumulate( values.begin(), values.end(), 0 );
        uint64_t average = static_cast<uint64_t>( total ) / values.size();
        std::cout << average << '\n';

    } catch( const std::runtime_error& e ) {
        std::cerr << e.what() << '\n';
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

На моем компьютере windows 7 ultimate 64bit работает visual studio 2017 CE скомпилировано с языковой версией, установленной на самую последнюю версию c++17 или выше. Это дает мне предупреждение компилятора! Warning: C4244 генерируется из-за конвертации и возможной потери данных. Однако нет ошибок компилятора, и он работает и дает ожидаемый результат. Выходные данные здесь 6, как и ожидалось, поскольку integer division усекается. Если я изменю эти строки кода выше на это:

double total = std::accumulate( values.begin(), values.end(),
                            static_cast<double>( 0 ) );
double average = total / values.size();

Он исправляет предупреждения компилятора выше, добавляя static_cast, и он достаточно точно выводит 6.5, который является фактическим значением.

Это все хорошо, так как вектор уже инициализирован значениями; однако, это не всегда так, поэтому давайте переместим это в функцию, которая будет принимать произвольный массив. Это будет выглядеть примерно так:

uint64_t array_average( std::vector<uint64_t>& values ) {
    // Prevent Division by 0 and early return 
    // as to not call `std::accumulate`
    if ( !values.empty() ) {
        // check if only 1 entry if so just return it
        if ( values.size() == 1 ) {
            return values[0];
        } else { // otherwise do the calculation.
            return std::accumulate( values.begin(), values.end(),
                                    static_cast<uint64_t>( 0 ) ) / values.size();
        } 
    } 
    // Empty Container 
    throw std::runtime_error( "Can not take average of an empty container" );
}

Эта функция хороша, и все, мы можем добиться большего, улучшив ее, сделав ее немного более универсальной, которая будет работать с любым arithmetic type!

template<typename T>
T array_average( std::vector<T>& values ) {
    if( std::is_arithmetic<T>::value ) {
        if( !values.empty() ) {
            if( values.size() == 1 ) {
                return values[0];
            } else { 
                return std::accumulate( values.begin(), values.end(), static_cast<T>( 0 ) ) / values.size();
            }
        } else {
            throw std::runtime_error( "Can not take average of an empty container" ); 
        }
    } else {
        throw std::runtime_error( "T is not of an arithmetic type" );
    }
}

На первый взгляд все в порядке. Он будет скомпилирован и запущен, если вы используете его с типами arithmetic. Однако, если мы используем его с типом, который не является, это не сможет скомпилироваться. Например:

#include <vector>
#include <numeric>
#include <iostream>
#include <exception>
#include <type_traits>

class Fruit {
protected:
     std::string name_;
public:
    std::string operator()() const {
        return name_;
    }
    std::string name() const { return name_; }

    Fruit operator+( const Fruit& other ) {
        this->name_ += " " + other.name();
        return *this;
    }
};

class Apple : public Fruit {
public:
    Apple() { this->name_ = "Apple"; }

};

class Banana : public Fruit {
public:
    Banana() { this->name_ = "Banana"; }
};

class Pear : public Fruit {
public:
    Pear() { this->name_ = "Pear"; }
};

std::ostream& operator<<( std::ostream& os, const Fruit& fruit ) {
    os << fruit.name() << " ";
    return os;
}

template<typename T>
T array_average( std::vector<T>& values ); // Using the definition above

int main() {
    try {
        std::vector<uint64_t> values { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
        std::vector<double> values2 { 2.0, 3.5, 4.5, 6.7, 8.9 };
        std::vector<Fruit> fruits { Apple(), Banana(), Pear() };

        std::cout << array_average( values ) << '\n';  // compiles runs and prints 6
        std::cout << array_average( values2 ) << '\n'; // compiles runs and prints 5.12
        std::cout << array_average( fruits ) << '\n'; // fails to compile.

    } catch( const std::runtime_error& e ) {
        std::cerr << e.what() << '\n';
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

Не удается скомпилировать, поскольку static_cast не может преобразовать int в T с T = Fruit MSVC ошибка компилятора C2440

Мы можем исправить это, изменив одну строку кода в нашем шаблоне функции, если ваш компилятор поддерживает это:

Мы можем изменить if( std::is_arithmetic<T>::value ) на if constexpr( std::is_arithmetic<T>::value ), и теперь наша функция будет выглядеть так:

template<typename T>
T array_average( const std::vector<T>& values ) {
    if constexpr( std::is_arithmetic<T>::value ) {
        if( !values.empty() ) {
            if( values.size() == 1 ) {
                return values[0];
            } else {
                return std::accumulate( values.begin(), values.end(), static_cast<T>( 0 ) ) / values.size();
            }
        } else {
            throw std::runtime_error( "Can not take average of an empty container" );
        }
    } else {
        throw std::runtime_error( "T is not of an arithmetic type" );
    }
}

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

int main() {
    //....
    std::cout << array_average( fruits ) << '\n'; // Now compiles
    //...
}

Однако, когда вы запустите этот код, он сгенерирует ошибку времени выполнения, и в зависимости от того, как настроены ваша IDE и отладчик, вам может понадобиться поставить точку останова в операторе catch, где return EXIT_FAILURE должен видеть напечатанное сообщение. на экран, в противном случае приложение может просто выйти без какого-либо уведомления.

Если вы не хотите ошибок времени выполнения, вы можете заменить и произвести ошибки времени компиляции, используя static_assert вместо выдачи ошибки времени выполнения. Это может быть удобной маленькой функцией, но она не на 100% без каких-либо незначительных ограничений и ошибок, но чтобы узнать больше информации об этой функции, вы можете проверить Вопрос, который я задавал, когда писал реализацию этой функции, которая можно найти здесь , и вы можете прочитать там комментарии, которые помогут вам лучше понять некоторые ограничения, которые предоставляет эта функция.

Одним из текущих ограничений для этой функции было бы следующее: допустим, у нас есть контейнер, содержащий несколько комплексных чисел (3i + 2), (4i - 6), (7i + 3) и вы можете взять их среднее, так как это допустимая вещь, но вышеприведенная функция не будет считать это арифметическим в своем текущем состоянии.

Чтобы решить эту проблему, можно сделать следующее: вместо использования std::is_arithmetic<t> вы можете написать свои собственные policy и traits, которые должна принимать эта функция. Я оставлю эту часть в качестве упражнения для вас.

Как видите, большая часть работы уже выполняется для нас со стандартной библиотекой. Мы использовали accumulate и поделили на размер контейнеров, и мы закончили, все оставшееся время мы были уверены, что он принимает правильные типы, если он должен быть потокобезопасным и / или исключительным и т. Д.

Наконец, нам не пришлось беспокоиться о громоздких циклах for в массивах и о том, чтобы циклы не превышали размер массива. Нам не нужно было звонить new и беспокоиться о том, когда и куда звонить delete, чтобы не было утечек памяти. АСФАИК Я не думаю, что std::accumulate переполнится на поддерживающих контейнерах, но не указывайте меня на этом. Это может зависеть от types, которые находятся в контейнере, и от того, что static_cast задействовано. Даже с некоторыми из этих предостережений во многих случаях все же лучше использовать контейнеры, чем управлять собственной необработанной памятью, и использовать алгоритмы и функции, предназначенные для работы с ними. Они делают вещи намного проще, проще в управлении и даже отладке.

0 голосов
/ 07 ноября 2018

Прежде всего, помните, что ваше среднее значение не является фактическим средним, так как вы выбрасываете половину. Результат вашего алгоритма для массива, который чередуется между 0 и 1, будет 0, так как 0/2 + 1/2 + (0% 2 + 1% 2) / 2 = 0. Хотелось бы начать с этого, потому что это серьезная слабость вашего алгоритма.

Также обратите внимание, что если исходный размер не является степенью 2, некоторые данные получат больший вес.

Кроме того, рассмотрите этот алгоритм: Скопируйте данные. До тех пор, пока в данных не останется только одна запись, поместите среднее значение ячеек 0 и 1 в ячейку 0, 2 и 3 в ячейку 1, 4 и 5 в 2 и т. Д. Сжатие данных после каждого такого шага.

Как код:

uint64_t average(std::vector<uint64_t> data)
{
    while(data.size() != 1)
    {
        for(size_t i=0; i<data.size()/2; i++)
        {
            data[i] = data[2*i]/2 + data[2*i+1]/2 + /* modular stuff */;
        }
        data.resize(data.size()/2 + data.size()%2); //last part is required if the size is not an even number
    }
    return data[0];
}

Кстати, использование подходящего контейнера также избавляет от утечки памяти.

Обратите внимание, что этот код все еще имеет слабость, о которой я говорил. Вы можете расширить его, собрав половинки, то есть если ваша модульная часть равна 1, вы увеличиваете переменную, а когда переменная равна двум, вы добавляете единицу в некоторую ячейку.

Редактировать: Если вход должен быть необработанным массивом (потому что вы получаете его из какого-то внешнего источника, например), используйте это:

uint64_t average(uint64_t* array, const int array_size)
{
    std::vector<uint64_t> data(array, array + array_size);

    (rest of the code is identical)

Редактировать: код выше со сбором половинок:

inline uint64_t average(const uint64_t& a, const uint64_t& b, uint8_t& left_halves)
{
    uint64_t value = a/2 + b/2 + (a%2 + b%2)/2;
    if((a%2 + b%2)%2 == 1)
    {
        left_halves += 1;
    }
    if(left_halves == 2)
    {
        value += 1;
        left_halves = 0;
    }
    return value;
}

uint64_t average(std::vector<uint64_t> data)
{
    if(data.size() == 0) return 0;

    uint8_t left_halves = 0;
    while(data.size() != 1)
    {
        for(size_t i=0; i<data.size()/2; i++)
        {
            data[i] = average(data[2*i], data[2*i+1], left_halves);
        }
        data.resize(data.size()/2 + data.size()%2); //last part is required if the size is not an even number
    }
    return data[0];
}

По-прежнему имеет слабость увеличенного веса клетки, если размер не является степенью двойки.

...