Изучение многомерного массива, переданного функции в GDB - PullRequest
Новая
       6

Изучение многомерного массива, переданного функции в GDB

1 голос
/ 08 октября 2019

Я написал код для динамического программирования, алгоритм умножения цепочки матриц. На этот вопрос меня не интересуют детали реализации алгоритма.

Я пытаюсь отладить его, используя gdb . Тем не менее, мне трудно исследовать массив cost_table 2-D внутри функции matrix_chain_order.

Внутри функции matrix_chain_order, я устанавливаю точку останова и проверяю массив cost_table 2-D. Я также использовал printf заявления там. Операторы printf выводят правильное значение ячейки в cost_table.

Я нашел некоторую полезную информацию в этом SO QA: как вывести значения 2d arry в gdb .

Я не понял, что на самом деле объяснил ответ. Но это дало мне направление, поэтому я попытался напечатать cost_table и значения его ячеек в gdb . (Сессия ниже)

Код: 

/* MATRIX-CHAIN-MULTIPLICATION - CLRS 3rd Edition, Chapter 15 */

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>


#define array_length(arr) (sizeof(arr) == 0 ? 0 : sizeof(arr) / sizeof((arr)[0]));

/* define input sequence to matrix_chain_order function */
const int INPUT_SEQUENCE[] = {4, 10, 3, 12, 20};

/* DEFINE m[i, j]:
 * Let m[i, j] be the minimum number of scalar multiplications needed to compute
 * matrix A_suffix_i..j; for the full problem, the lowest cost way to compute A_suffix_1..n
 * would thus be m[1, n].
 */
/* The function computes the rows from bottom to top and from left to right within
 * each row.
 * It computes each entry m[i, j] using products p_suffix_i-1 * p_suffix_k * p_suffix_j
 * for k = i, i + 1, ...., j - 1 and all entries southwest and southeast from m[i, j].
 *
 * This prodedure assumes that matrix A_suffix_i has dimensions p_suffix_i-1 * p_suffix_i
 * for i = 1, 2, ...., n.
 * Its input is a sequence p = <p_suffix_0, p_suffix_1, ...., p_suffix_n>, where
 * p.length = n + 1.
 *
 * The procedure uses an auxiliary table m[1 ..n, 1 ..n] for storing the m[i, j] costs,
 * and another auxiliary table s[1 ..n - 1, 2 ..] that records which index of k achieved
 * the optimal cost in computing m[i, j].
 */
void matrix_chain_order (int ct_rows, int ct_cols, int cost_table[ct_rows][ct_cols], int kit_rows, int kit_cols, int k_idx_table[kit_rows][kit_cols]);

int main ()
{
  int sequence_len = array_length(INPUT_SEQUENCE);

  /* initialize table (2-D array), m[1 ..n, 1..n] */
  int m = 0, n = 0;
  int cost_table[sequence_len][sequence_len];
  for (m = 0; m < sequence_len; m++) {
    for (n = 0; n < sequence_len; n++) {
      /* m[i, i] = 0, for i = 1, 2, ...., n (the minimum costs for chains of length 1) */
      if (n == m) {
        cost_table[m][n] = 0;
      } else {
        cost_table[m][n] = INT_MAX;
      }
    }
  }

  /* initialize table (2-D array), s[1 ..n - 1, 2..n] */
  int o = 0, p = 0;
  int k_idx_table[sequence_len - 1][sequence_len - 1];
  for (o = 0; o < sequence_len - 1; o++) {
    for (p = 0; p < sequence_len - 1; p++) {
      k_idx_table[o][p] = -1;
    }
  }

  matrix_chain_order(sequence_len, sequence_len, cost_table, sequence_len, sequence_len - 1, k_idx_table);

  return 0;
}

/* NOTE on array passed to the function. */
/* When you pass an array to a function, it decays into a pointer to the first element,
 * at which point knowledge of its size is lost. You need to work it out before decay 
 * and pass that information with the array.
 */
void matrix_chain_order(int ct_rows, int ct_cols, int cost_table[ct_rows][ct_cols], int kit_rows, int kit_cols, int k_idx_table[kit_rows][kit_cols])
{
  int sequence_len = array_length(INPUT_SEQUENCE);

  /* use recurrence,
   *
   * min[i, j] = 0 , if  i = j
   * min[i, j] = min {m[i, k] + m[k + 1, j] + p_suffix_i-1 * p_suffix_k * p_suffix_j , if i < j
   *
   * to compute m[i, i + 1] for i = 1, 2, ...., n - 1 (the minimum costs of chains of length l = 2)
   * during the first execution of the for loop.
   * The second time through the loop, it computes m[i, i + 2] for i = 1, 2, ...., n - 2
   * (the minimum costs for chains of length l = 3), and so forth.
   */
  int chain_len = 0, i = 1, j = 0, k = 0, cost = INT_MAX;
  for (chain_len = 2; chain_len <= sequence_len; chain_len++) {
    for (i = 1; i <= sequence_len - chain_len + 1; i++) {
      j = i + chain_len - 1;

      for (k = i; k <= j - 1; k++) {
        /* at each step, the m[i, j] cost computed depends only on table entries m[i, k] and m[k + 1, j]
         * already computed
         */
        printf("Printed cost_table[%d][%d] : %d\n", i, k, cost_table[i][k]);
        printf("Printed cost_table[%d][%d] : %d\n", (k+1), j, cost_table[k+1][j]);
        cost = cost_table[i][k] + cost_table[k + 1][j] + INPUT_SEQUENCE[i - 1] * INPUT_SEQUENCE[k] * INPUT_SEQUENCE[j];

        if (cost < cost_table[i][j]) {
          cost_table[i][j] = cost;
          k_idx_table[i][j] = k;
        }
      }
    }
  }
}

Сессия GDB: 

(gdb) p ((int (*) [5][5]) cost_table)[1][1]
$3 = {0, 0, 65280, 0, -8944}
(gdb) p (int [][5]) *cost_table 
$4 = 0x7fffffffdca0
(gdb) p (int [5][5]) *cost_table 
Invalid cast.
(gdb) p (int [][5]) **cost_table 
warning: array element type size does not divide object size in cast
$5 = 0x7fffffffdca0
(gdb) p (int [][5]) *cost_table 
$6 = 0x7fffffffdca0
(gdb) p (int [][5]) cost_table 
warning: array element type size does not divide object size in cast
$7 = 0x7fffffffdbe0
(gdb) p cost_table@5@5
$16 = {{0x7fffffffdca0, 0x500000005, 0x26, 0x100000002, 0x500000001}, {0x7fffffff00000002, 0x4, 0x3, 0x1f7ffe728, 0x7fffffffdca0}, {0x0, 0x5, 0x7fffffffddf0, 0x400952 <main+892>, 0xffffffffffffffff}, {
    0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff}, {0xffffffffffffffff, 0xffffffffffffffff, 0x0, 0x7fffffffde10, 0x7fffffff00000000}}
(gdb) p *cost_table@5@5
$17 = {{{0, 2147483647, 2147483647, 2147483647, 2147483647}, {2147483647, 0, 2147483647, 2147483647, 2147483647}, {2147483647, 2147483647, 0, 2147483647, 2147483647}, {2147483647, 2147483647, 
      2147483647, 0, 2147483647}, {2147483647, 2147483647, 2147483647, 2147483647, 0}}, {{0, -140389360, 32767, 4, 0}, {0, 0, 65280, 0, -8944}, {32767, 4, 0, 0, 0}, {4, 0, 0, 0, 4}, {0, 0, 0, 4, 0}}, {{
      0, 0, 0, 5, 5}, {4, 4, 5, 4, 0}, {4, 0, -9056, 32767, 3}, {0, 3, 0, -9136, 32767}, {1781326592, 1051810453, 0, 0, 0}}, {{0, 4195552, 0, -8496, 32767}, {0, 0, 0, 0, 4197632}, {0, -140322768, 32767, 
      0, 0}, {-8488, 32767, 0, 1, 4195798}, {0, 0, 0, 1661416990, 1731120}}, {{4195552, 0, -8496, 32767, 0}, {0, 0, 0, -989383138, -1731249}, {-690538978, -1735179, 0, 0, 0}, {0, 0, 0, 1, 0}, {4195798, 
      0, 4197744, 0, 0}}}
(gdb) p **cost_table@5@5
$18 = {{0, 2147483647, 2147483647, 2147483647, 2147483647}, {2147483647, 0, 2147483647, 2147483647, 2147483647}, {2147483647, 2147483647, 0, 2147483647, 2147483647}, {2147483647, 2147483647, 2147483647, 
    0, 2147483647}, {2147483647, 2147483647, 2147483647, 2147483647, 0}}
(gdb) p cost_table[i][k] 
Cannot perform pointer math on incomplete types, try casting to a known type, or void *.

Я не понимаю, как команды, которые я использовал в сеансе GDB, приводят к их соответствующим выводам.

  • Почему я не могу использовать p cost_table[i][k] непосредственно в GDB , тогда как операторы printf выводят результат выполнения кода?

  • p ((int (*) [5][5]) cost_table)[1][1]: Что произойдет, если я изменю значение чисел в этой команде или сделаю что-то вродеp ((int(*) [][5]) cost_table)[1][1]?

  • Почему выходные данные p *cost_table@5@5 и p **cost_table@5@5 такие разные?

Мое требование состоит в том, чтобыбыть в состоянии изучить cost_table и его ячейки в GDB.

Любые другие предложения приветствуются.

1 Ответ

1 голос
/ 08 октября 2019

Просто спросите об этом у gbd:) 

Breakpoint 2, matrix_chain_order (ct_rows=5, ct_cols=5, cost_table=0x7fffffffdac0, kit_rows=5, kit_cols=4, k_idx_table=0x7fffffffda80) at delme.c:96
96              printf("Printed cost_table[%d][%d] : %d\n", (k+1), j, cost_table[k+1][j]);
(gdb) ptype cost_table
type = int (*)[5]
(gdb) p ((int (*) [5])cost_table)[i][j]
$12 = 2147483647

Вы также можете подняться на один кадр («вверх» в gdb) и напечатать непосредственно cost_table[idx1][idx2], но, вероятно, менее удобно для отладки вloop ...

тип, который gdb дает (int (*) [5]), обозначает указатель на массив 5 из int (см. https://cdecl.org/?q=int+%28*t%29%5B5%5D, если вы хотите использовать синтаксис.)

Тип массива уменьшается, поэтому остается только указатель;Вы можете взглянуть на Управление многомерным массивом в функции для более подробного объяснения в C.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...