最大数组大小

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所需的最大空间。答案取决于堆栈帧的大小。使用电子表格，它看起来不是一个微不足道的问题 - 它依赖于排序数组的大小和堆栈帧的大小，尽管堆栈框架似乎需要相当大才能产生问题。

因此，事实证明，决定您可以排序的最大数组大小的因素之一是您正在排序的数组大小！

或者，你可以猜测一个值，看看它是否工作，使用二进制搜索缩小到一个特定的值。