I have written code for dynamic programming, matrix chain multiplication algorithm. For this question, I am not concerned with the implementation details of algorithm.
I am trying to debug it using gdb. However, I am having a hard time examining cost_table 2-D array inside matrix_chain_order function.
Inside matrix_chain_order function, I set a breakpoint and examine the cost_table 2-D array. I have also used printf statements there.
The printf statements print the correct value of a cell in cost_table.
I found some revelant information in this SO QA: how to print 2d arry values in gdb.
I did not understand what the answer really explained. But it gave me a direction, so I tried printing cost_table and its cell values in gdb. (Session below)
Code:
/* 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 session:
(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 *.
I don't get how the commands that I have used in gdb session result in their respective outputs.
Why am I unable to use
p cost_table[i][k]directly in gdb, whereas theprintfstatements print the result in execution of code?p ((int (*) [5][5]) cost_table)[1][1]: What happens if I change value of numbers in this command or if I do something likep ((int(*) [][5]) cost_table)[1][1]?Why is the output of
p *cost_table@5@5andp **cost_table@5@5so different?
My requirement is to be able to examine the cost_table and its cells in gdb.
Any other suggestions is welcomed.
