在保留原始索引的同時對價值進行排序的更快方法

我希望得到一些幫助，以便在保留原始訂單上的關鍵字的同時實現排序值的更快速的方式。我寧願避免使用boost，也不需要進行穩定的排序。這是我提出的代碼，它可以工作，但速度很慢並且不夠靈活。排序完成後，我無需保留地圖。在保留原始索引的同時對價值進行排序的更快方法

struct column_record 
{ 
    int index; 
    float value; 
}; 

// sort each column on value while retaining index 
column_record *preprocess_matrix(float *value, int m, int n) 
{ 
    std::multimap<float,int> column_map; 
    column_record *matrix = new column_record[m*n]; 

    for (int i=0; i<n; i++) 
    { 
     for (int j=0; j<m; j++) 
     { 
      column_map.insert(std::pair<float,int>(value[m*i+j],j)); 
     } 

     int j = 0; 

     for (std::multimap<float,int>::iterator it=column_map.begin(); it!=column_map.end(); it++) 
     { 
      matrix[m*i+j].index = (*it).second; 
      matrix[m*i+j].value = (*it).first; 
      j++; 
     } 

     column_map.clear(); 
    } 

    return matrix; 
}

來源

2011-08-26 darckeen

也許我有壞眼睛，但我沒有看到'分配後的矩陣'，也沒有看到'列'聲明在哪裏可能他們的意思是一樣的，你混合起來？ – Nobody

假設它的罰款返回column_record對象的數組，我不認爲你的解決方案是特別低效。你可以把它也許更清潔，並使用STL算法消除std::multimap的需要：

bool compare_column_records(const column_record& lhs, const column_record& rhs) 
{ 
    return lhs.value < rhs.value; 
} 

column_record* preprocess_matrix(float* value, int m, int n) 
{ 
    const int num_elements = m * n; 
    column_record* matrix = new column_record[num_elements]; 

    for (int i = 0; i < num_elements; ++i) 
    { 
     // not sure what you mean by index; it looks like you want column index only? 
     matrix[i].index = i; 
     matrix[i].value = value[i]; 
    } 

    std::sort(matrix, matrix + num_elements, compare_column_records); 
    return matrix; 
}

來源

2011-08-26 08:14:46 Dawson

謝謝。我認爲地圖速度很慢，因爲你無法預先分配 – darckeen

首先，我看你使用一維數組來模擬你的矩陣。第一步，我想創建索引的新數組：

int count = m*n; 
int *indices = new int[count]; 
for (i=0;i<count;i++) indices[i] = i;

（我沒有用C++編寫的一段時間，所以我不知道如果你能做到在運行初始化）。

然後，您可以改變排序方法來接受原始矩陣和新創建的索引數組並對其進行排序。爲了使事情更容易，我將轉置矩陣來排序行（連續索引），而不是列。

來源

2011-08-26 08:19:26

在保留原始索引的同時對價值進行排序的更快方法

回答

相關問題