Friday, December 14, 2012

Notes on memset

1. memset

  void * memset ( void *pMemoryBlock, int byte, size_t numOfByte );

2. Typical using senarios
  • Bytewise memory initialization
  • Zero a block of memory
  • Zero a POD struct

3. Test

#include<vector>
#include<string>
#include<algorithm>
#include<cstring>

using namespace std;

struct C {
 char a;
 short *b;
 int c[10];
};

struct CPP {
 string a;
 CPP& operator=(const CPP &r);
};

CPP& CPP::operator=(const CPP &r) {
 if (this != &r) {
  (*this).a = r.a;
 }
 return *this;
}

char achar[3];
int aint[3];

C s;
C as[3];

CPP c;
CPP ac[3];

int main (){
 // 1. Initialize a block of memory using a given byte
 memset(achar, 'a', 3);
 
 // 2. Quickly zero a block of memory
 memset(achar, 0, 3);
 memset(achar, 0, sizeof achar);
 
 memset(aint, 0, 3 * sizeof(int));
 memset(aint, 0, sizeof aint);
 
 memset(as, 0, 3 * sizeof as[0]); 
 memset(as, 0, 3 * sizeof (struct C));
 
 // 3. Reset POD struct
 memset(&s, 0, sizeof(struct C));
 
 // Caution 1. memset works byte by byte only
 memset(aint, 1, 3 * sizeof(int)); // aint : 16843009, 16843009, 16843009
 
 // Caution 2. Be careful with pointer in struct
 s.b = new short;
 memset(&s, 0, sizeof s); // address of b : 0
 
 // Caution 3. POD only
 //memset(&c, 0, sizeof(CPP)); // crash!!!
 
 // Either define a reseting member function, or
 // use fill() and '=' overriding
 c.a = "N/A";
 fill(ac, ac+3, c);  // ac : "N/A", "N/A", "N/A"
 
 return 0;
}

 (code test on g++ 4.6.2)

Tuesday, September 11, 2012

Netbeans "Cannot locate java installation in specified jdkhome..."

If you change the jdk's dir path after Netbeans installation, the Netbeans will complains it cannot find the original jdk's path and ask if you'd like to use "default" jdk in a message box each time you start the program.

To disable the warning message box, just change the default jdk path to the new one Netbeans at "<netbeans_dir>/etc/netbeans.conf":

netbeans_jdkhome="E:\Java\jdk1.6"



Wednesday, August 15, 2012

Flashing Screen followed by Windows Hang or Crash


I switched to Windows 7 from XP two years ago and have never experienced one system crashing since then, but until recently I began to be haunted by a Windows 7 system crash, or precisely, a crash caused by the NVidia video card driver.

My Dell T3500 had its original video card replaced with NVidia Quadro NVS 295 not too long ago. Unluckily, I have never got a change to enjoy the performance that would have come with this video card. What I have experienced on the contrary has been continuous system hanging, then crashing, or even (at times) BOSD since the replacement!

Symptom: Initially, the screen suddenly becomes flashing (glowing colorful dots and lines) with blurring resolution for no reason (for 3~60 seconds); then the whole screen goes frozen (for 20 ~ 60 seconds); finally it is blacked out forever, but the CPU and power indicators are still on.

Attempt: 1. I have checked the event viewer each time it crashes but found no clue. And I also attempted to reinstall the video card driver using Windows device manager which still did not help at all;

2. Installed the Windows Debugger (link) and examined the system dump file at C:\Windows\MEMORY.DMP, which said:

Defaulted to export symbols for nvlddmkm.sys -
Probably caused by : nvlddmkm.sys ( nvlddmkm+7b73bc )


So the Windows kernel mode driver nvlddmkm.sys file may be the culprit.

The interim solution I have so far is to disable the nView and dual monitor to use a single screen. I have two DPI ports on the video card, and I guess the overhead when using both of the ports of the video card at the same time may cause the issue...

Same with other users experiecing this issue. No official solution found so far...

a. http://en.kioskea.net/faq/6210-handling-nvlddmkm-sys-crash
b. http://voices.yahoo.com/techtips-nvidia-blue-screen-death-nvlddmkmsys-5316783.html
c. http://en.community.dell.com/support-forums/desktop/f/3515/t/19436822.aspx
Ref.: 1. Handling "nvlddmkm.sys" Crash, http://en.kioskea.net/faq/6210-handling-nvlddmkm-sys-crash;
2. How to solve Windows 7 crashes in minutes, http://www.networkworld.com/supp/2011/041811-windows-7-crashes.html?page=1;

Tuesday, August 14, 2012

Using `awk` to Convert CSV Format Data

The awk utility provides a handy way to extract and transform data.

In many application scenarios, we wish to quickly convert a form of tabular data to another tabular form that 1) is separated using a different character, 2) contains a subset of all the fields, or 3) contains a reordered set of fields. The awk utility can be very helpful in these situations by calling only its print command.

1.       To CSV

For example, the table1.txt contains data in tabular form of:

1    a1   b1
2    a2   b2
3    a3   b3
4    a4   b4

And the command below:

$ awk '{print $3","$1;}' table1.txt

will extract the 3rd and the 1st fields of table1.txt which are separated by tabs (or spaces), and generate the results in the comma separated format:

b1,1
b2,2
b3,3
b4,4

2.       From CSV

Or you can also specify the separator in the file by the `-F` argument. For example, the table2.txt contains comma separated data of:

1,a1,b1
2,a2,b2
3,a3,b3
4,a4,b4

And the command of:

$ awk -F, '{print $NF"\t"$2"\t"$1;}' table2.txt

states that the separator of the fields will be `,`. And it will convert the fields in table2.txt into the tab separated form (NF means the number of last field):
b1 a1 1
b2 a2 2
b3 a3 3
b4 a4 4



Thursday, April 26, 2012

Notes on Gson (when converting a Json string to a Java Object)


Google's Gson library provides a handy way to convert Java Class from/to Json strings using fromJson() and toJson() function.

When converting a Json string to Java object, it is important that the fields' names in the Java Class must be exactly the same as the keys' names in the Json String. The visibility of the fields' name does not matter. E.g.:

  String json = "{'key1':'1', 'key2':2}";
  class Object {
   public String key1;
   private int key2;
  }
  Object objs = new Gson().fromJson(json, Object.class);


Otherwise, the null values will returned for each field.

Tuesday, April 17, 2012

Identify Functions Definition within a C Source File

1. Use the ctags tools, on a console, typing in "ctags -x --c-kinds=f " with the file name(s) (e.g. "flex.c"):

ctags -x --c-kinds=f flex.c

will generate the list of C functions defined in "flex.c" file:

FlexParser       function   2228 flex.c           extern parserDefinition* FlexParser (void)
addContext       function    786 flex.c           static void addContext (tokenInfo* const parent, const tokenInfo* const child)
addToScope       function    796 flex.c           static void addToScope (tokenInfo* const token, vString* const extra)
buildFlexKeywordHash function    207 flex.c           static void buildFlexKeywordHash (void)
copyToken        function    705 flex.c           static void copyToken (tokenInfo *const dest, tokenInfo *const src)

...

Ref.: http://ctags.sourceforge.net/ctags.html

Tuesday, March 20, 2012

MinGW Simple Installation Guide

MinGW is a minimal GNU development environment for MS Windows (http://www.mingw.org/Welcome_to_MinGW_org). On MinGW, MSYS provides a collection of GNU tools, which provides some of the GNU utilities and enables the use of autotools build system (http://www.mingw.org/wiki/MSYS).

Installation:

1. Main program: Install the MinGW from: http://sourceforge.net/projects/mingw/files/
2. Set system variable PATH to include the X:\MinGW\bin; where X is the root drive
3. mingw-get: Install the mingw-get-inst from
http://sourceforge.net/projects/mingw/files/Installer/mingw-get-inst/mingw-get-inst-20111118/
4. Open a CMD console on Windows:
  1) gmake, gcc, g++, gdb: Install the make, compiler and debuger
  2) msys: Install the GNU utilities collection tool - msys.bat
 
 > mingw-get install gcc g++ gmake gdb msys
 > cd X:\MinGW\msys\1.0\postinstall
 > pi.bat
 > X:\MinGW\msys\1.0\msys.bat


Done!

Sunday, March 4, 2012

Simulating a Queue using two Stacks

// Simulating a queue by two stacks, one for enqueue, another for dequeue
#include <iostream>
#include <stack>
#include <queue>

using std::stack;
using std::queue;
using std::cin;
using std::cout;
using std::endl;
using std::boolalpha;

template<class T>
class squeue {
public:
 T& back()
 {
  assert (!empty());
  while (!_s2.empty())
  {
   _s1.push(_s2.top());
   _s2.pop();
  }
  return _s1.top();
 }
 
 T& front()
 {
  assert (!empty());
  while (!_s1.empty())
  {
   _s2.push(_s1.top());
   _s1.pop();
  }
  return _s2.top();
 }

 void push(const T& e) //enqueue
 {
  while (!_s2.empty())
  {
   _s1.push(_s2.top());
   _s2.pop();
  }
  _s1.push(e);
 }

 void pop() //dequeue
 {
  assert (!empty());
  while (!_s1.empty())
  {
   _s2.push(_s1.top());
   _s1.pop();
  }
  _s2.pop();
 }

 size_t size() const
 {
  return _s1.size() + _s2.size();
 }
 
 bool empty() const
 {
  return size() == 0;
 }
private:
 stack<T> _s1, _s2;
};

int main()
{ 
 squeue<int> sq;
 queue<int> q; // the control
 
 // push, back
 for (size_t i=0; i<5; i++)
 {
  sq.push(i); q.push(i);
  cout << sq.back() << " " << q.back() << "\n";
 }
 
 // size
 cout << "\n" << sq.size() << " " << q.size() << "\n\n";
 
 // front, pop
 for (size_t i=0; i<5; i++)
 {
  cout << sq.front() << " " << q.front() << "\n";
  sq.pop(); q.pop();
 }
 
 // empty
 cout << boolalpha << "\n" << sq.empty() << " " << q.empty() << endl;
 
 return 0;
}

Sunday, February 19, 2012

How to Find Common Characters among two Strings

There are several ways to find the common characters among two strings. Speaking of the worst-case time complexity, different algorithms perform differently from quadratic to linear, such as O(n2), O(nlogn) and O(n)

The average run time of naive method can be O(n2), which is straightforward to design. So here are the other two possible methods whose time complexity are O(nlogn) and O(n).

Let's assume the strings to be compared are a and b, and the functions are:
    string comchr(string&, string&)
and
    string comchr2(string&, string&)
in C++ respectively.

1. comchr(): Sort the strings first and then find the common characters - O(nlogn)

If we use merge sort to sort the two strings and then do the comparison, the average and worst time complexity of the problem will be of order O(nlogn), where n is the max(a.length(), b.length()). So here are the C++ implementation of the algorithm:


string comchr(string &a, string &b)
{
    string r;
    string::size_type i, j, k;
    if (a.length()+b.length()<=1)    return "";
    if (a.compare(b)==0)    return a;
    merge_sort(a, 0, a.length()-1);
    merge_sort(b, 0, b.length()-1);
    i=j=k=0;
    while (i<a.length() && j<b.length())
    {
        if (a[i]==b[j])
        {
            if (k==0 || r[k-1]!=a[i])     
            {
                r.push_back(a[i]);           
                k++;
            }
            i++; j++;
        }        
        else
  
        (a[i]<b[j]) ? i++ : j++;

    return r;
}
The merge_sort() is the merge sort routine that sorts the string and contributes O(nlogn) to the complexity.

2. comchr2(): Map the characters in string a into a set and then compare each of the characters in this set with string b - O(n) 
A simple way to improve the running time is to use a direct-address access table (here called t) for insertion (O(1)) of each character of one string and for table look up (O(1)). The implementation could be:

string comchr2(string &a, string &b)
{
    string r;
    set<char> s;    //s to remove duplicate chars
    bitset<256> t;    // All ASCII char
    if (a.length()+b.length()<=1)    return "";
    if (a.compare(b)==0)    return a;
    for (string::size_type i=0; i<a.length(); i++)
        if (!t.test(a[i]))
            t.set(a[i]);
    for (string::size_type i=0; i<b.length(); i++)
        if (t.test(b[i]))
            s.insert(b[i]);
    for (set<char>::iterator it=s.begin(); it!=s.end(); it++)
        r.push_back(char(*it));
    return r;
}

Note that the function uses a bitset t for direct-address access. Of course, the comchr2() is easier to design
3. Short experiment

A simple experiment to compare the performance of the two functions is done using test set:
                a            b
Test 1    abcdefghi     jklmnopqr
Test 2    abcdefghi     abcdefghi
Test 3    abcdefghi     aaabbbccc

The same function will be called 1000000 times to scale up the time to run the problem. The average running time (in second) of each function on different strings is shown below:
   


The comchr2() function runs faster than the comchr() when the test strings are not 'too' similar. And both functions perform similarly on the test case 2 because the test strings are same in both cases.

4. Conclusion

In programming practice, sometimes the simplest approach may also be the 'best'! Given the scale of the problem, the computing resource or the performance requirement, we may tune the program in different ways or even have different solutions.

For example, what if the strings we compare use wide character set (e.g. Unicode)?

What if the strings are stored in separate files on disk?