0

再帰マージソートを行う次の arduino コードがあります。この 8192B SRAM に入力できる配列要素の最大量を計算する方法を決定する必要があります。配列要素の数は、この void setup() で設定されます

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() {
    }
4

1 に答える 1

0

再帰はほとんど赤ずきんです。最大入力配列サイズは次のようになります。

(total_memory - memory_allocated_for_other_stuff) / (2 * number_of_elements * sizeof array_element)

ここtotal_memoryで、 はシステムが持つメモリの量、memory_allocated_for_other_stuffはプログラムが使用するメモリ (同じメモリを使用している場合)、スタックとその他のデータ、number_of_elementsは配列の長さ、sizeof array_elementはソートする要素あたりのバイト数です。

その理由2 * number_of_elementsは、コードで、2 つの半分をマージする一時バッファーを割り当てる必要があるためSです。各再帰レベル、半分に必要なサイズ、一時バッファは再帰が発生した後にのみ割り当てられるSため、ソートする配列のサイズに等しい上限があります。S

再帰的な性質はほとんど厄介者だと言いました。S各再帰ステップで必要なスペースが半分になるため、最上位のマージを実行するメモリがあれば、すべての再帰マージも実行するのに十分です。ただし、各再帰ステップはスタックに固定量を追加するため (スタックがデータと同じメモリを使用すると仮定)、memory_allocated_for_other_stuff再帰呼び出しの数に比例して増加します。つまり、スタックのメモリは次のようになります。

stack_used = stack_frame_size * (log 2 (要素数) + 1)

ここstack_frame_sizeで、スタック フレームを作成するために必要なメモリ (関数のリターン アドレス、ローカル変数などを保持するためのスタック上のビット) です。問題はstack_used、 に必要な最大スペースを超える可能性があることですS。答えは、スタック フレームのサイズによって異なります。スプレッドシートを使用すると、答えるのが簡単な質問ではないように見えます-ソートする配列のサイズとスタックフレームのサイズに依存しますが、スタックフレームが問題を引き起こすにはかなり大きくする必要があるようです.

したがって、ソートできる配列の最大サイズを決定する要因の 1 つは、ソートする配列のサイズであることがわかります。

または、バイナリ検索を使用して特定の値に絞り込んで、値を推測し、それが機能するかどうかを確認することもできます。

于 2012-11-14T10:03:07.500 に答える