最大數組大小

Question

我有以下arduino代碼，執行遞歸合併排序。我們必須確定如何計算可以在此8192B SRAM中輸入的最大陣列元素數量。數組元素的數量在這個空間設置（）

int16_t Test_len = 64; 

我會一直愛來解決這個設定自己卻被小時後絕望，我錯過了這一個演講，因爲我有一個流感。

整個代碼的副本。

#include <Arduino.h> 
#include <mem_syms.h> 

// some formatting routines to indent our messages to make it easier 
// to trace the recursion. 

uint8_t indent_pos = 0; 
const uint8_t indent_amt = 2; 

void indent_in() { 
    if (indent_pos <= 32) { 
     indent_pos ++; 
     } 
    } 

void indent_out() { 
    if (indent_pos >= indent_amt) { 
     indent_pos --; 
     } 
    } 

void indent() { 
    for (uint8_t i=0; i < indent_pos * indent_amt; i++) { 
     Serial.print(" "); 
     } 
    } 

// print out memory use info, s is a simple descriptive string 
void mem_info(char *s) { 
    indent(); 
    Serial.print(s); 
    Serial.print(" Stack: "); 
    Serial.print(STACK_SIZE); 
    Serial.print(" Heap: "); 
    Serial.print(HEAP_SIZE); 
    Serial.print(" Avail: "); 
    Serial.print(AVAIL_MEM); 
    Serial.println(); 
    } 

// call this after a malloc to confirm that the malloc worked, and 
// if not, display the message s and enter a hard loop 

void assert_malloc_ok(void * mem_ptr, char *s) { 
    if (! mem_ptr) { 
     Serial.print("Malloc failed. "); 
     Serial.print(s); 
     Serial.println(); 
     while (1) { } 
     } 
    } 

// call this on entry to a procedure to assue that at least required amt of 
// memory is available in the free area between stack and heap if not, display 
// the message s and enter a hard loop 

void assert_free_mem_ok(uint16_t required_amt, char *s) { 

    if (AVAIL_MEM < required_amt) { 
     Serial.print("Insufficient Free Memory: "); 
     Serial.print(s); 
     Serial.print(" require "); 
     Serial.print(required_amt); 
     Serial.print(", have "); 
     Serial.print(AVAIL_MEM); 
     Serial.println(); 
     while (1) { } 
     } 
    } 

void merge(int16_t *Left, int16_t Left_len, int16_t *Right, int16_t Right_len, 
    int16_t *S) { 

    // position of next element to be processed 
    int Left_pos = 0; 
    int Right_pos = 0; 

    // position of next element of S to be specified 
    // note: S_pos = Left_pos+Right_pos 
    int S_pos = 0; 

    // false, take from right, true take from left 
    int pick_from_left = 0; 

    while (S_pos < Left_len + Right_len) { 

    // pick the smallest element at the head of the lists 
    // move smallest of Left[Left_pos] and Right[Right_pos] to S[S_pos] 
    if (Left_pos >= Left_len) { 
     pick_from_left = 0; 
     } 
    else if (Right_pos >= Right_len) { 
     pick_from_left = 1; 
     } 
    else if (Left[Left_pos] <= Right[Right_pos]) { 
     pick_from_left = 1; 
     } 
    else { 
     pick_from_left = 0; 
     } 

    if (pick_from_left) { 
     S[S_pos] = Left[Left_pos]; 
     Left_pos++; 
     S_pos++; 
     } 
    else { 
     S[S_pos] = Right[Right_pos]; 
     Right_pos++; 
     S_pos++; 
     } 

    } 
} 


// sort in place, i.e. A will be reordered 
void merge_sort(int16_t *A, int16_t A_len) { 
    indent_in(); 
    indent(); 
    Serial.print("Entering merge sort: array addr "); 
    Serial.print((int) A); 
    Serial.print(" len "); 
    Serial.println(A_len); 
    mem_info(""); 

    assert_free_mem_ok(128, "merge_sort"); 

    if (A_len < 2) { 
     indent_out(); 
     return; 
     } 

    if (A_len == 2) { 
     if (A[0] > A[1]) { 
      int temp = A[0]; 
      A[0] = A[1]; 
      A[1] = temp; 
      } 
     indent_out(); 
     return; 
     } 

    // split A in half, sort left, sort right, then merge 
    // left half is: A[0], ..., A[split_point-1] 
    // right half is: A[split_point], ..., A[A_len-1] 

    int split_point = A_len/2; 

    indent(); 
    Serial.println("Doing left sort"); 

    merge_sort(A, split_point); 

    mem_info("After left sort"); 

    indent(); 
    Serial.println("Doing right sort"); 

    merge_sort(A+split_point, A_len-split_point); 

    mem_info("After right sort"); 

    // don't need the merging array S until this point 
    int *S = (int *) malloc(A_len * sizeof(int));// source of 10 bytes accumulation in heap 

    assert_malloc_ok(S, "Cannot get merge buffer"); 

    mem_info("Doing merge"); 

    merge(A, split_point, A+split_point, A_len-split_point, S); 

    for (int i=0; i < A_len; i++) { 
     A[i] = S[i]; 
     } 

    // now we are done with it 
    free(S); 

    mem_info("After free"); 
    indent_out(); 
    } 

void setup() { 
    Serial.begin(9600); 

    // int *bad_news = (int *) malloc(4000); 

    mem_info("********* THIS IS THE BEGINNING *********"); 
    randomSeed(analogRead(0)); 

    int16_t Test_len = 64; 
    int16_t Test[Test_len]; 

    Serial.print("In: "); 
    for (int16_t i=0; i < Test_len; i++) { 
     Test[i] = random(0, 100); 
if (1) { 
     Serial.print(Test[i]); 
     Serial.print(" "); 
} 
     } 
    Serial.println(); 

    merge_sort(Test, Test_len); 

if (1) { 
    Serial.print("Out: "); 
    for (int16_t i=0; i < Test_len; i++) { 
     if (i < Test_len-1 && Test[i] > Test[i+1]) { 
      Serial.print("Out of order!!"); 
      } 

     Serial.print(Test[i]); 
     Serial.print(" "); 
     } 
    Serial.println(); 
} 
    } 

void loop() { 
    } 

Answer 1

遞歸幾乎紅鯡魚，最大輸入數組大小等於： -

（total_memory - memory_allocated_for_other_stuff）/（2個* number_of_elements *的sizeof array_element）

其中total_memory是系統有的內存量，memory_allocated_for_other_stuff是程序使用的內存（如果它使用相同的內存），堆棧和其他數據，number_of_elements是排列y長度和sizeof array_element是每個元素要排序的字節數。

其原因是2 * number_of_elements是您需要分配一個臨時緩衝區來將兩部分合併到您的代碼中的S。 S的上限等於要排序的數組的大小，因爲每個遞歸級別，所需的大小爲S的一半，臨時緩衝區僅在遞歸發生後分配。

我說遞歸性質幾乎是一個紅鯡魚，因爲S所需的空間減半，每個遞歸步驟如此，如果你有內存做最頂級的合併，那麼足夠做所有的遞歸合併作爲好。但是，每個遞歸步驟爲堆棧添加了一個固定數量（假設堆棧使用與數據相同的內存），所以memory_allocated_for_other_stuff隨着遞歸調用的數量線性增加，即堆棧的內存爲： -

stack_used = stack_frame_size *（日誌（元素的數量）+ 1）

其中stack_frame_size是創建一個堆棧幀（堆棧上的位來保存返回地址，局部變量所需的存儲器，等等...的功能）。問題是：stack_used可能超過S所需的最大空間。答案取決於堆棧幀的大小。使用電子表格，它看起來不是一個微不足道的問題 - 它依賴於排序數組的大小和堆棧幀的大小，儘管堆棧框架似乎需要相當大才能產生問題。

因此，事實證明，決定您可以排序的最大數組大小的因素之一是您正在排序的數組大小！

或者，你可以猜測一個值，看看它是否工作，使用二進制搜索縮小到一個特定的值。