排序插入到一個固定大小的陣列與複製

-1

我想找到最有效的C程序來存儲N個最大值從傳入數據流。例如。假設傳入的數據是每個32bytes，並且是來自傳感器的連續流，我需要存儲流中N個最大值（允許的副本）。簡單的方法是迭代並找到位置，然後將所有元素移動1（可能丟棄當前最小值）。有沒有更好的方法來做到這一點？排序插入到一個固定大小的陣列與複製

Source

//MAX_KEEP 32 


typedef struct accel_sys 
{ 
    FILE *infile; 

    /* Data for largest and last */ 
    u32 largest[MAX_KEEP]; /* largest in highest index, smallest in lowest index */ 
    u32 last[MAX_KEEP]; /* circular buffer */ 
    u8 last_start; /* points to the oldest value */ 

    /* Data for reading and processing the file */ 
    u8 last_byte; 
    Bool even; 
    int num_read; 

} accel_t; 

typedef accel_t * accel_h; 
static void store_max(accel_h accel, u32 cur_value) 
{ 
    int i = MAX_KEEP-1; 
    int j = 0; 

    while(i >= 0) 
    { 
     if(cur_value > accel->largest[i]) 
     { 
      /* found it */ 

      break; 
     } 
     i--; 
    } 

    /* i < 0 if the value doesn't belong in the array, do nothing in that case */ 
    if(i >= 0) 
    { 
     /* Move everything lower than cur_value down, losing the last value, 
     * then store our new value in our found spot */ 
     j = 0; 
     while(j < i) 
     { 
      accel->largest[j] = accel->largest[j+1]; 
      j++; 
     } 
     accel->largest[i] = cur_value; 
    } 


}

來源

2015-05-02 vjtron

你的算法是合理的。還有其他的數據結構可能更適合您的需求，但是如果您嚴格考慮使用數組，您可以放棄自己需要重複移位並改爲使用memmove。 'memmove（accel，accel + 1，i）;' – bentank

如果傳入的數據是每個32字節，將它存儲在'u16'中可能不是最好的想法... – abarnert

值是否符合可以被分類的範圍'如{小，中，大}或類似的小範圍？這樣的分佈是否相當均衡，還是會偏向一側？如果分佈相當平衡，一個簡單的優化就是使用散列來存儲表示這個較小範圍的K數組（例如：3個桶）。這有點類似於基數排序。您的基本插入排序算法仍然適用，但只適用於每個存儲桶。 –

第一種優化是更換您的明確循環的陣列與memmove轉移。當然，無論哪種方式都是線性時間，但在大多數平臺上，memmove與更快的恆定乘數成線性關係。

接下來，N有多大？因爲你顯然已經按照排序順序保存了值，所以，爲什麼不做一個二分搜索而不是線性搜索？這意味着您的平均分配時間變爲O（log N）而不是O（N）。 ^*

左右（未經檢驗，我保證至少一個差一錯誤的地方...）：

static void store_max(accel_h accel, uint16_t cur_value) { 
    size_t first = 0, last = N, middle; 
    while (first < last) { 
     middle = (first + last)/2; 
     if (accel->largest[middle] < cur_value) 
      first = middle + 1; 
     else if (accel->largest[middle] == cur_value) 
      break; 
     else 
      last = middle - 1; 
    } 
    if (middle > 0) { 
     memmove(accel->largest, accel->largest+1, middle); 
     accel->largest[middle] = cur_value; 
    } 
}

如果你想提高最壞情況的時候，你想堆，因爲你可以在對數時間推動彈出。 ^**您可以將堆存儲在一個普通的N值數組中，就像您的排序數組一樣，並以線性時間的排序順序讀出值。但是這增加了更多的複雜性，我不想嘗試在手機上編寫代碼。 :)

_{*您最壞的情況下仍然是O（N）;設想一個病態的情況下，價值只是不斷增加。但即使在這種情況下，一個非常快的O（N）+一個緩慢的O（log N）也許是一個非常快速的O（N）+一個緩慢的O（N）的有價值的改進。}

_{**雖然在實踐中，爲O（log N）掉期可能比memmove爲N你可能關心的值慢...}

來源

2015-05-02 04:30:12 abarnert

排序插入到一個固定大小的陣列與複製

回答

相關問題