問題

我正在開發一個需要操作巨大矩陣的專案,特別是copula計算的金字塔總和.

簡而言之,我需要在矩陣(多維陣列)中零的海域中跟蹤相對較少的數值(通常值為1,在罕見情況下超過1).

稀疏陣列允許使用者儲存少量值,並假設所有未定義的記錄都是預設值.由於物理上不可能儲存記憶體中的所有值,我需要只儲存少量非零元素.這可能是幾百萬條目.

速度是一個巨大的優先順序,我也想在執行時動態選擇類中的變數數.

我目前正在研究一個使用二進位制搜尋樹(b-tree)來儲存條目的系統.有誰知道更好的系統嗎?

  最佳答案

對於C,地圖執行良好.數百萬個物件不會成為問題.1000萬個專案花費了大約4.4秒,大約57meg在我的計算機上.

我的測試應用程式如下:

 #include <stdio.h>
#include <stdlib.h>
#include <map>

class triple {
public:
    int x;
    int y;
    int z;
    bool operator<(const triple &other) const {
        if (x < other.x) return true;
        if (other.x < x) return false;
        if (y < other.y) return true;
        if (other.y < y) return false;
        return z < other.z;
    }
};

int main(int, char**)
{
    std::map<triple,int> data;
    triple point;
    int i;

    for (i = 0; i < 10000000; ++i) {
        point.x = rand();
        point.y = rand();
        point.z = rand();
        //printf("%d %d %d %d
", i, point.x, point.y, point.z);
        data[point] = i;
    }
    return 0;
}
 

現在動態選擇變數數,最簡單的解決方案是將索引表示為字串,然後使用字串作為對映的鍵.例如,位於[23][55]的專案可以透過“23,55”字串表示.我們還可以將這個解決方案擴充套件到更高的維度;例如,對於三個維度,任意索引將看起來像“34,45,56”.此技術的簡單實現如下:

 std::map data<string,int> data;
char ix[100];

sprintf(ix, "%d,%d", x, y); // 2 vars
data[ix] = i;

sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars
data[ix] = i;
 

  相同標籤的其他問題

c++oopdata-structureshashmaps