Самый быстрый способ скопировать почти пустой массив

Question

Мне нужно оптимизировать действительно дрянной код на C ++. Парень, который сделал это, не умеет кодировать: у него есть память, индексы используются, начиная с 1 вместо 0, спагетти-код, вы называете плохую практику, и вот она.

Итак, 40% в то время как этот алгоритм копирует большие массивы, которые почти пусты. Я пытаюсь внести минимальные изменения, потому что это, вероятно, означало бы изменение тысяч и тысяч строк кода, и любая ошибка означала бы получение совершенно разных результатов.

Итак, вместо объявления этих больших, почти пустых массивов, таких как: HLLE [dimcl]; // определение dimcl 600

Я делаю что-то вроде этого

    ArrayTimes HLLE;
    
/////
// Stores the occupied positions in another array, when copying, instead of copying all, empty the occupied ones
// then fill with the other occupied ones
    class ArrayTimes
    {
    public:
        ArrayTimes(int numTasks);
        ArrayTimes(const ArrayTimes& _other);
        virtual ~ArrayTimes();
        inline short& operator[](int _index)
        {
            auto &result = (*m_times)[_index];
            if (result == 0) //if there was already a value doesn't count as occupied again
            {
                (*m_occupied)[m_numOccupied] = _index;
                ++m_numOccupied;
            }
            return result;
        }
    
        inline const short& operator[](int _index) const
        {
            return (*m_times)[_index];
        }
    
        inline ArrayTimes& operator= (const ArrayTimes &_other)
        {
            //vaciamos
            for (int i = 0; i < m_numOccupied; ++i)
            {
                auto occIndex = m_occupied->operator[](i);
                m_times->operator[](occIndex) = 0;
            }
    
            *m_occupied = *(_other.m_occupied);
            m_numOccupied = _other.m_numOccupied;
    
            for (int i = 0; i < _other.m_numOccupied; ++i)
            {
                auto occIndex = _other.m_occupied->operator[](i);
                m_times->operator[](occIndex) = _other.m_times->operator[](occIndex);
            }
            return *this;
        }

    ArrayTimes::ArrayTimes(int numTasks) :
        m_numOccupied(0)
    {
        m_occupied = new std::vector<int>();
        m_times = new std::vector<short>();
    
        m_times->resize(numTasks);
        m_occupied->resize(numTasks / 4);
    }
    
    ArrayTimes::ArrayTimes(const ArrayTimes& _other)
    {
        m_occupied = new std::vector<int>();
        m_times = new std::vector<short>();
    
    
        auto datosGlobales = DatosGlobalesProblema::getInstance();
        auto numTareas = datosGlobales->GetNumTareas() + 1;
    
        m_occupied = new std::vector<int>();
        m_times = new std::vector<short>();
    
        m_times->resize(numTareas);
        m_occupied->resize(numTareas / 4);
    
        operator=(_other);
    }
    
    ArrayTimes::~ArrayTimes()
    {
        delete m_times;
        delete m_occupied;
    }
    
    
    int ArrayTimes::Size() const
    {
        return m_occupied->size();
    }

Я пробовал несколько контейнеров для хранения занятых позиций: список, набор, неупорядоченный набор, карта. Ни один из них не работает быстрее, чем копирование всех позиций массива.

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

Answer 1

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

Answer 2

Следующий код имеет это время от 300 до 600 копий. Вам не нужно ничего копировать вручную с помощью std::vector.

Я изменил оператор =, но вам нужно go через один из векторов, чтобы увидеть, что вам нужно скопировать.

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

Size: 300, 75
Element: 90

real    0m0,002s
user    0m0,002s
sys 0m0,000s

class ArrayTimes
{
    std::vector<int> m_occupied;
    std::vector<short> m_times;
    int m_numOccupied;
    
public:
    
    ArrayTimes(int numTasks) :
        m_numOccupied(0)
    {
        m_times.resize(numTasks);
        m_occupied.resize(numTasks / 4);
    }
    
    ArrayTimes(const ArrayTimes& _other)
    {
        auto numTareas = 600;

        m_times.resize(numTareas);
        m_occupied.resize(numTareas / 4);
    
        operator=(_other);
    }
    
    ~ArrayTimes()
    {
    }
    
    inline short& operator[](int _index)
    {
        auto &result = m_times[_index];
        if (result == 0) //if there was already a value doesn't count as occupied again
        {
            m_occupied[m_numOccupied] = _index;
            ++m_numOccupied;
        }
        return result;
    }
    
    inline const short& operator[](int _index) const
    {
        return m_times[_index];
    }
    
    inline ArrayTimes& operator= (const ArrayTimes &_other)
    {
        m_times.reserve (_other.m_times.size());
        for (auto e : _other.m_occupied) {
            m_times[e] = _other.m_times[e];
        }
        m_numOccupied = _other.m_numOccupied;
        return *this;
    }
    
    int OSize() const
    {
        return m_times.size();
    }

    int Size() const
    {
        return m_occupied.size();
    }
    
};

int main ()
{
    ArrayTimes a1(600);
    ArrayTimes a2(300);

    a2[3] = 9;

    a1 = a2;

    std::cout << "Size: " << a1.OSize() << ", " << a1.Size() << std::endl;
    std::cout << "Element: " << a1[3] << std::endl; // copied value from a2
    
    return 0;
}