複製int數組與指針到bools

我正在研究一個程序，它需要將數組複製數千次/數百萬次。現在我有陣列中表示數據的方法有兩種：複製int數組與指針到bools

整數的數組：

int someArray[8][8];

其中someArray[a][b]可以具有0,1，或2的值，或

的指針數組布爾：

bool * someArray[8][8];

someArray[a][b]哪裏可以爲0（空指針），否則*someArray[a][b]可以是真（對應於1），或假（C或對應於2）。

哪個數組會被更快地複製（是的，如果我將指針指向布爾值數組，我每次複製數組時都必須聲明新的布爾值）？

來源

2010-12-03 wrongusername

掛上，什麼？在第二種情況下`someArray [a] [b]`的值肯定是一個指針，而不是一個整數。你在談論`* someArray [a] [b]`？ – 2010-12-03 21:34:01

@oli哦，你是對的，我會更新問題，謝謝！ – wrongusername 2010-12-03 21:37:18

這些陣列有多大？ – 2010-12-03 21:38:12

哪種方法可以更快地複製，這一點在旁邊，爲您的bool*方法分配和釋放條目以及取消引用指針以檢索每個值的開銷將大大降低複製成本。

如果您只有3個可能的值，請使用char的數組，這將比int快4倍。好吧，這不是一個科學證明的聲明，但陣列將小4倍。

來源

2010-12-03 21:39:10

您的問題的答案將與數據類型的大小相關聯。通常bool是一個字節，而int不是。指針的長度根據體系結構而不同，但現在通常是32位或64位。

不考慮緩存或其他處理器特定的優化考慮，較大的數據類型將需要較長時間的複製。

鑑於您有三種可能的狀態（0,1,2）和64個條目，您可以用128位來表示整個結構。使用一些實用程序例程和兩個無符號的64位整數，您可以非常快速地高效地複製陣列。

來源

2010-12-03 21:39:23 fbrereto

實際上，在複製方面它們看起來差不多 - 一個32位整數數組與32位指針數組的比較。如果你編譯爲64位，那麼指針可能會更大。

順便說一句，如果你存儲指針，你可能不希望爲該數組的每個字段都有一個「bool」的SEPARATE實例，對嗎？那肯定會慢得多。

如果你想快速複製，縮小體積儘可能，或者：的

使用char代替int，或
制定一個自定義類與此陣位操作。如果你將一個值表示爲兩位 - 一個「空」位和「如果不是空的值」位，那麼你需要128位= 4位整數的64位數值。這肯定會被複製得非常快！但是訪問任何單個位會更復雜一點 - 只需要幾個週期。

OK，你讓我很好奇:)我捲起這樣的：

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個字節，這是一個很好與使用char array[8][8]的解決方案和256字節的int array[8][8]的解決方案的64字節相比有所改進。

這可能就像一個人可以在這裏一樣低，不用鑽研更大的魔法。

來源

2010-12-03 21:40:52 Kos

我會說你需要重新設計你的程序。在int x[8][8]和bool *b[8][8]之間轉換「百萬次」不能是「正確」，但是您對「正確」的定義不嚴格。

來源

2010-12-03 21:42:11 zvrba

雖然我更喜歡使用堆棧分配（因爲動態分配可能需要一些時間來尋找一個可用空間），但我認爲他們大概需要大致相同的時間。

考慮使用short類型而不是int，因爲您不需要廣泛的數字。

我認爲使用一維數組可能會更好，因爲使用for循環的順序錯誤，編譯器用於存儲多維數組（原始主要或列主要）會導致性能損失！

來源

2010-12-03 21:42:51

不知道你是如何使用數組太多了，這是一個可能的解決方案：

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

這些陣列是隻有64字節，應該複製相當快的。您可以將數據類型更改爲int，但這意味着至少要複製256個字節。

來源

2010-12-03 22:23:37 Blastfurnace

用指針「複製」這個數組需要一個深度拷貝，否則改變拷貝會影響原始數據，這可能不是你想要的。由於內存分配的開銷，這將極大地降低速度。

您可以通過使用boost::optional來表示「可選」數量 - 這是您在此處添加間接級別的唯一原因。現代C++中的情況很少，其中原始指針真的是最好的東西:)但是，因爲無論如何，只需要一個char來存儲值{0,1,2}，這可能會更好一些的空間。我很確定sizeof(boost::optional<bool>) > 1，雖然我沒有測試過它。我會留下深刻的印象，如果他們專門爲此:)

你甚至可以位打包一個2位數組的數組，或使用兩個位打包布爾數組（一個「掩碼」，然後另一組實際的真實 - 假值） - 例如使用std::bitset。這肯定會節省空間並縮短複製時間，但這可能會延長訪問時間（假設您確實需要一次訪問一個值）。

來源

2010-12-03 22:31:02

複製int數組與指針到bools

回答

相關問題