Копирование массива целых и указателей в bools

Question

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

Массив целых чисел:

int someArray[8][8];

, где someArray[a][b] может иметь значение 0, 1 или 2,или

Массив указателей на логические значения:

bool * someArray[8][8];

, где someArray[a][b] может быть 0 (нулевой указатель), в противном случае *someArray[a][b] может быть истинным (соответствует 1) или ложным(соответствует 2).

Какой массив будет копироваться быстрее (и да, если бы я делал указатели на логический массив, мне пришлось бы объявлять новые bools каждый раз, когда я копировал массив)?

Answer 1

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

Если у вас есть только 3 возможных значения, используйте массив char, и он будет копироваться в 4 раза быстрее, чем int. Хорошо, это не научно доказанное утверждение, но массив будет в 4 раза меньше.

Answer 2

На самом деле, оба выглядят более или менее одинаково с точки зрения копирования - массив 32-битных целых по сравнению с массивом 32-битных указателей.Если вы скомпилируете как 64-битный, то указатель, вероятно, будет больше.

Кстати, если вы храните указатели, вы, вероятно, не хотите иметь экземпляр SEPARATE "bool" для каждого поля этого массива, вы?Это, конечно, будет намного медленнее.

Если вы хотите быстрое копирование, максимально уменьшите размер. Либо:

• используйте char вместо int, либо
• разработать пользовательский класс с битовыми манипуляциями для этого массива.Если вы представляете одно значение как два бита - бит «null» и бит «value-if-not-null», то вам потребуется 128 бит = 4 дюйма для всего этого массива из 64 значений.Это, безусловно, будет скопировано очень быстро!Но доступ к любому отдельному биту будет немного сложнее - всего на несколько циклов больше.

---

Хорошо, вы меня заинтересовали :) Я свернул что-то вроде этого:

struct BitArray {
public:
    static const int DIMENSION = 8;

    enum BitValue {
        BitNull = -1,
        BitTrue = 1,
        BitFalse = 0
    };
    BitArray() {for (int i=0; i<DIMENSION; ++i) data[i] = 0;}
    BitValue get(int x, int y) {
        int k = x+y*DIMENSION; // [0 .. 64)
        int n = k/16;          // [0 .. 4)
        unsigned bit1 = 1 << ((k%16)*2);
        unsigned bit2 = 1 << ((k%16)*2+1);

        int isnull = data[n] & bit1;
        int value = data[n] & bit2;
        return static_cast<BitValue>( (!!isnull)*-1 + (!isnull)*!!value );
    }
    void set(int x, int y, BitValue value) {
        int k = x+y*DIMENSION; // [0 .. 64)
        int n = k/16;          // [0 .. 4)
        unsigned bit1 = 1 << ((k%16)*2);
        unsigned bit2 = 1 << ((k%16)*2+1);
        char v = static_cast<char>(value);

        // set nullbit to 1 if v== -1, else 0
        if (v == -1) {
            data[n] |= bit1;
        } else {
            data[n] &= ~bit1;
        }

        // set valuebit to 1 if v== 1, else 0
        if (v == 1) {
            data[n] |= bit2;
        } else {
            data[n] &= ~bit2;
        }
    }
private:
    unsigned data[DIMENSION*DIMENSION/16];
};

Размер этого объекта для массива 8x8 составляет 16 байтов , что является хорошим улучшением по сравнению с 64 байтами с решением char array[8][8] и 256 байтами int array[8][8].

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

Answer 3

Я бы сказал, что вам нужно изменить дизайн вашей программы. Преобразование между int x[8][8] и bool *b[8][8] «миллионами» раз не может быть «правильным», однако ваше определение «правильного» является слабым.

Answer 4

«Копирование» этого массива с указателями потребует глубокого копирования, так как в противном случае изменение копии повлияет на оригинал, что, вероятно, не то, что вам нужно.Это значительно замедлит процесс из-за перерасхода памяти.

Вы можете обойти это, используя boost::optional для представления «необязательных» величин - единственная причина, по которой вы добавляете уровенькосвенность здесь.В современном C ++ очень мало ситуаций, когда лучше использовать необработанный указатель :) Однако, так как вам нужно всего лишь char для хранения значений {0, 1, 2} в любом случае, это, вероятно, будет лучшес точки зрения пространства.Я почти уверен, что sizeof(boost::optional<bool>) > 1, хотя я не проверял это.Я был бы впечатлен, если бы они специализировались на этом:)

Вы могли бы даже упаковать битовый массив из 2-битных величин или использовать два битовых массива (один «маска», а затем другой набор фактических данных).значения true-false) - например, используя std::bitset.Это, безусловно, сэкономит место и сократит время копирования, хотя, вероятно, увеличит время доступа (при условии, что вам действительно нужен доступ к одному значению за раз).

Answer 5

Не зная слишком много о том, как вы используете массивы, это возможное решение:

typedef char Array[8][8];
Array someArray, otherArray;
memcpy(someArray, otherArray, sizeof(Array));

Эти массивы занимают всего 64 байта и должны копироваться довольно быстро.Вы можете изменить тип данных на int, но это означает копирование не менее 256 байтов.

Answer 6

Я не уверен на 100%, но я думаю, что они займут примерно одинаковое время, хотя я предпочитаю использовать выделение стека (поскольку для динамического выделения может потребоваться некоторое время при поиске свободного места).

Рассмотрите возможность использования типа short вместо int, поскольку вам не нужен широкий диапазон чисел.

Я думаю, что было бы лучше использовать один размерный массив, если вы действительно хотите максимальную скорость, поскольку использование циклов for в неправильном порядке, который компилятор использует для хранения многомерных массивов (необработанных основных или главных столбцов), может привести к снижению производительности !

Answer 7

Ответ на ваш вопрос будет связан с размером типов данных. Обычно bool - это один байт, а int - нет. Длина указателя варьируется в зависимости от архитектуры, но в наши дни обычно это 32- или 64-разрядные.

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

Учитывая, что у вас есть три возможных состояния (0, 1, 2) и 64 записи, вы можете представить всю свою структуру в 128 битах. Используя некоторые служебные программы и два 64-разрядных целых числа без знака, вы можете очень быстро эффективно скопировать ваш массив.