Category Archives: C/C++

sort list via selection sort

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *insertionSortList(ListNode *head){
      if (head == NULL || head->next == NULL) return head;

      ListNode *cur = head->next;
      head->next = NULL; // set up the termination condition
      while (cur){
          ListNode *nxt = cur->next;
          ListNode * brk = head;

          if (cur->val < brk->val) {
              cur->next = brk;
              head = cur;
          }
          else {
               while (brk && brk->next && brk->next->val <= cur->val){
                         brk = brk->next;
               }
               cur->next = brk->next; // propagate the NULL, a smart move!
               brk->next = cur;
          }
          cur = nxt;
     }
      return head;
    }
};

 

 

[OJ report] binary tree right side view

https://leetcode.com/problems/binary-tree-right-side-view/

The solution is at solution @ github .

The idea is to use DFS to do pre-order traversal of the mirror tree. At the same time, use an array to mark current level, so that we can keep from putting wrong element into the result vector.

class Solution {
public:
   void Helper( TreeNode * root, vector<int> & result,
                    int cur, vector<int> & marked ){
     if(root == NULL) return;
    // pre-order of the mirror binary tree
    // (DFS & just by swapping the traversal order)
    if( result.size() == cur ){
      // maintain a marked vector to keep from putting
      // wrong element into the result vector
      result.push_back(root->val);
    }
    Helper(root->right, result , cur+1, marked);
    Helper(root->left , result , cur+1, marked);
   }
  vector<int> rightSideView(TreeNode * root){
    vector<int> result, marked;
    if(root == NULL) return result;
    Helper(root, result, 0, marked);
    return result;
  }
};

The runtime complexity is O(n), where n is the node number.

The worst-case memory complexity is O(n) = O(n) .

Eigen for exponential matrix

Useful link
http://eigen.tuxfamily.org/dox/unsupported/group__MatrixFunctions__Module.html

Reference:
(Implementation and theoretical details) Nicholas J. Higham, “The scaling and squaring method for the matrix exponential revisited,”SIAM J. Matrix Anal. Applic., 26:1179–1193, 2005.

g++ a.cpp -o a -I$(EIGENPackage), where EIGENPackage = where your eigen source code

#include <unsupported/Eigen/MatrixFunctions>
#include <iostream>
using namespace Eigen;
int main()
{
  const double pi = std::acos(-1.0);
  MatrixXd A(3,3);
  A << 0,    -pi/4, 0,
       pi/4, 0,     0,
       0,    0,     0;
  std::cout << "The matrix A is:\n" << A << "\n\n";
  std::cout << "The matrix exponential of A is:\n" << A.exp() << "\n\n";
}

strcpy traps me

Be aware of strcpy function has requirement for different char *, which is strcpy(char *, const char *). If you do something like strcpy(p,p+1) is dangerous, why not just use p++. Otherwise, some of compiler will have the issue shown at this link https://community.oracle.com/thread/2330498?start=0&tstart=0 .

Implementation mistake causes memory leakage when build Sparse Matrix in mex C/C++ to interact with MATLAB

Let’s first take a look at 6 Lessons From Dropbox – One Million Files Saved Every 15 Minutes, we know, when the product scales, engineers tend to use more computational efficient (C/C++) languages to compensate the side effect of rapid prototyping/development (Python) language.

Similar thing happens in academic prototyping, MATLAB is convenient, and more worthwhile to be used to explore novel idea and save time. However, some important parts are required to implemented in more efficient way to make the idea more solid. Therefore, programming and interacting programming languages is a handy skill set to computer science students.  When we deal with those situation, memory management and transferring is always pain.

In this article, I program in C with MEX to talk to MATLAB. I mistakenly transfer the sparse matrix format with redundant allocations so it blows up the memory (PS: I deal with large scale computing problem).

Do not use this memory Blow-Up version code:

plhs[0] = mxCreateSparse( c_stamp->M, c_stamp->N, c_stamp->NNZ, mxREAL);
cPr = (double *)mxMalloc(sizeof(double) * (c_stamp->NNZ));
cIr = (mwIndex *)mxMalloc(sizeof(mwIndex) * (c_stamp->NNZ));
cJc = (mwIndex *)mxMalloc(sizeof(mwIndex) * (c_stamp->N + 1));

//copy memory
memcpy( cPr, c_stamp->Pr, sizeof(double) * (c_stamp->NNZ));
memcpy( cIr, (mwIndex *)(c_stamp->Ir), sizeof(mwIndex) * (c_stamp->NNZ));
memcpy( cJc, (mwIndex *)(c_stamp->Jc), sizeof(mwIndex) * (c_stamp->N + 1));

mxSetPr(plhs[0], cPr);
mxSetIr(plhs[0], cIr);
mxSetJc(plhs[0], cJc);

Instead, this version is right

plhs[0] = mxCreateSparse( c_stamp->M, c_stamp->N, c_stamp->NNZ, mxREAL);
cPr = (double *) mxGetPr(plhs[0]);
memcpy(cPr, c_stamp->Pr, sizeof(double)*(c_stamp->NNZ));
cIr = (mwIndex *) mxGetIr(plhs[0]);
memcpy( cIr, (mwIndex *)(c_stamp->Ir), sizeof(mwIndex) * (c_stamp->NNZ));
cJc = (mwIndex *) mxGetJc(plhs[0]);
memcpy( cJc, (mwIndex *)(c_stamp->Jc), sizeof(mwIndex) * (c_stamp->N + 1));

where cPr, cIr, cJc are defined before. c_stamp is a sparse matrix I want to wrap from C/C++ to MATLAB via mex.

References: