원래 색인을 유지하면서 값을 정렬하는 더 빠른 방법

Question

원래의 순서대로 키를 유지하면서 값을 정렬하는 더 빠른 방법을 찾고자합니다. 나는 부스트를 사용하는 것을 피하고 안정된 정렬 일 필요는 없다. 이것은 내가 생각해 낸 코드입니다. 작동하지만 느리고 비효율적입니다. 정렬이 완료된 후지도를 유지할 필요가 없습니다.

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; 
} 

Answer 1

이 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; 
} 

Answer 2

첫째, 당신이 당신의 매트릭스를 에뮬레이트하는 1 차원 배열을 사용하는 것을 알 수있다. 첫 번째 단계, 나는 인덱스를 새로운 배열을 만들 것입니다 :

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

(당신이 즉시 초기화를 할 수 있을지 모르겠다 그래서 한 동안 C++로 프로그래밍하지 않은 경우).

그런 다음 정렬 방법을 변경하여 원본 매트릭스와 새로 생성 된 인덱스 배열을 모두 받아들이고 정렬 할 수 있습니다.

작업을 쉽게하기 위해 행 대신 행을 정렬하기 위해 행렬을 조 변경했습니다 (연속 색인).