back to c

re-visiting C so in a couple of nights during Ramadan while waiting for suhur. I played with the anti-prime seq problem. The problem: in a sequence of integers [n,m] where 1<=n,m<=1000, determine whether the sum of each sub-sequence of length k where 2<=k<=10 is a composite integer. I started recursively but it turned out a simple while loop will do.

/**
 12 Ramadan 1431
 08/22/2010
 ***/
#include 
#include 
#include 
#include 
int init_array(int array[],int n,int m,int d);
int find_anti_prime_sequence(int array[],int i,int candidate_to_not_use,int n,int m,int d,int length);
int find_next_solution(int array[],int index,int used,int n,int m,int d,int length);
int is_anti_prime(int array[],int from,int to,int d);
int is_prime(int n);
void dump_array(const char * arrayname,int * array, int length); 
//int * numbers_ptr = NULL;
int main (int argc, const char * argv[]) {
    int i = 0;
 int n = 1;
 int m = 1000;
 int d = 10;
 int length = m - n  + 1;
 int result = 0;
 int * array = NULL;
 int temp = 0;
 //printf("enter n, m and d (0 0 0 to quit:)");
 scanf("%d%d%d",&n, &m, &d);
 while (n>0) {
  length = m - n +1;
  result = 0;
  array = (int *) malloc(sizeof(int)*length);
  temp = n;
  for (i=0; i< length; i++) {
   array[i] = temp++;
  }
  for (i=0; i< length; i++) {
   array[i] = 0;
  }
  array[0] = n;
  result = find_anti_prime_sequence(array, 0, 0, n, m, d, length);
  if (result) {
   fprintf(stdout,"%d", array[0]);
   for (i=1; i< length; i++) {
     fprintf(stdout,",%d" , array[i]);
    }
    fprintf(stdout,"\n");
   }
  else{
   fprintf(stdout,"No anti-prime sequence exists.\n");
  }  
  fflush(stdout);
  fflush(stderr);  
  free(array);
  n = 0;m=0;d=0;
  //printf("enter n, m and d (0 0 0 to quit): ");
  scanf("%d%d%d",&n, &m, &d); 
 }
    return 0;
}
int init_array(int array[],int n,int m,int d)
{
 int i=0;
 int candidate = 0;
 array[0] = n;
 
 for (i=1; i 0) {
   array[i] = candidate;
  }
  else {
   return 1;/* break or return ? we probably should and try all values of n for the first case ?*/
  }
  
 }
 return 1;
}
/***
 * This is the recursive backtracking algorithm and the iterative one too.
 *
 *******/
int find_anti_prime_sequence(int array[],int i,int candidate_to_not_use,int n,int m,int d,int length)
{
 int candidate = 0;
 if (i<0) {
  return 0;
 }
 if (i>=length-1 /* && candidate_to_not_use == 0 */) {
  return 1;
 }
 //dump_array("main array", array, i);
 //candidate = find_next_solution(array, i, candidate_to_not_use, n, m, d,length);
 while(1)
 {
  if(i<0)
   return 0;
  if(i>= length - 1)
   return 1;
  candidate = find_next_solution(array, i, candidate_to_not_use, n, m, d,length);
  if(candidate >0)
  {
   array[++i] = candidate;
   candidate_to_not_use=0;
  }
  else
  {
   
   if(i==0 && array[i] < m)
   {
    array[i]++;
    candidate_to_not_use =0;    
   }
   else
   {
    candidate_to_not_use = array[i];
    i--;
   }
  }  
 }
 /*if (candidate > 0) {
  array[i+1]=candidate;
  return find_anti_prime_sequence(array,i+1,0,n,m,d,length);
  }
  else
  {
  if (i ==0 ) {
  if (array[i] < m) {
  array[i]++;
  return find_anti_prime_sequence(array,i,0,n,m,d,length);
  }
  }
  return find_anti_prime_sequence(array,i-1,array[i],n,m,d,length);
  }*/
}
int find_next_solution(int array[],int index,int used,int n,int m,int d,int length)
{
 int candidate = 0;
 int i =0; 
 int from = 0;
 int to = index + 1;
 if (index + 1 < d) {
  from = 0;
 }
 else {
  from = index - d + 2;
 }
 if (to >= length) {
  to = length -1;
 }
 if(used > 0){
  n=used+1;
 }
 while (n<=m) {
  for (i=0; i < = index; i++) {
   if (array[i]==n /* || n <= used */) {
    break;
   }
  } 
  if (i>index)
  {
   array[to]=n;
   // dump_array("array: ", array, length);
   // fprintf(stderr, " -- %d %d\n",from  , to); 
   if (is_anti_prime(array, from, to,d)) {
    candidate = n;
    break;
   }
  }
  n++;
 }
 return candidate;
}
int is_anti_prime(int array[],int from,int to,int d)
{
 int is_seq_prime = 0;
 int current_d= 2;
 int i = 0;
 int j = 0;
 int sum = 0;
 while (current_d < = d) {
  for (i=from; i < to; i++) {
   int limit = i+current_d-1;
   if (limit > to) {
    limit = to;
   }
   for (j=i; j < = limit; j++) {
    sum += array[j];
   }
   is_seq_prime =  is_prime(sum);
   if(is_seq_prime)
   {
    break;
   }
   sum = 0;
   
  }
  if (is_seq_prime) {
   break;
  }
  current_d++;
 }
 return !is_seq_prime;
}

int is_prime(int n)
{
 int i = 3;
 int square_root = 0;
 if (n%2 == 0) {
  return 0;
 }
 square_root = sqrt(n);
 i = 3;
 for (i; i < = square_root; i++) {
  if (n%i == 0) {
   return 0;
  }
 }
 return 1;
}
void dump_array(const char * arrayname , int * array,int length)
{
 int i =0;
 fprintf(stderr, "dum_array %s: ",arrayname);
 for (i=0; i < length; i++) {
  fprintf(stderr, "%d " , array[i]);
 }
 //fprintf(stderr, "\n");
}

XulRunner Firefox Add-on is not Mozilla XulRunner

Recently we found a firefox instance with a strange add-on XulRunner which hijacked firefox traffic when the user went to google. This is different from XulRunner Mozilla runtime program for more on the latter see https://developer.mozilla.org/en/XULRunner

The strange add-on would make http connection and exchange data with  google.ad.sgdoubleclick.net  as someone here https://support.mozilla.com/en-US/questions/749007 said. And I believe it was also responsible for exchanging data with a server here hosted-by.leaseweb.com

Here is a document from Mozilla on how to uninstall an add-on http://kb.mozillazine.org/Extensions_Uninstall 

Cheer up

This is one of the stories that cheer one up

http://money.cnn.com/2010/08/23/technology/sal_khan_academy.fortune/index.htm

Khan Academy is awesome http://www.khanacademy.org/  without tutorials on math, physics finance etc.

Back to Basics: C Basic Types and Their Representation in Memory

Great lectures Stanford put online http://www.youtube.com/watch?v=jTSvthW34GU 
The linked lecture explains very nicely two's complement are 15:00. Other great lectures in this series called Programming Paradigm.

Something I liked is that the lecturer explained why two's complement system is used to represent negative numbers. In short basically it makes basic operation like addition and subtraction really easy for hardware and thus fast. Examples are given in the lecture to illustrate.
see near the end of the lecture where representing floating-point numbers is discussed.

#include 
int main()
{
 int i = 37;
 float f = * (float *) &i;

 printf("%f\n",f);

 return 0;
}

You'll see why the code above does not print what one thinks it might print it first glance. By dereferencing a float point cast from the address of i, we're causing f to have the same pattern of 37 when interpreted as int but not the value 37.

Open . == Start .

If you're used to Windows command shell cmd.exe, you probably execute start . to start explorer with current directory; very nice saves a few seconds from the tedious navigation by hand.

In Mac OS X, the same thing can be done with open . or open /some/directory. Very handy.

Some variations of the open command

open . -g  : opens finder in the background

open -e filename : open filename with textedit { -t for default text editor and using -a you can specify application }

open filename : will open with default app

obviously the man pages have much more ...

Why my Cache´/ ODBC query is awfully slow?

It's not supposed to be this slow. The query is simple, optimized, performs great in different environment /severs or it just does not make it can be this slow. We're talking about an hour to hour.5 of execution time. It just does not make sense; it was working fine a while back. What's changed?

Suddenly you visit a tab in ODBC Data Source Administrator dialog box that you rarely (maybe) check. The tracing tab. Yes the tracing tab. Tracing was active. Some drivers like Cache odbc driver gives its own logging/tracing; that can slow queries. Because the query itself; its result and statistics about it and its transmission over the network are logged to file. Sometimes every row retrieved is analyzed and logged. This surly slows down your query. You use to debug issues. you if forgotten active, it can be a hidden cause of why queries take too long to come back with results.

Something happened to me a long time ago but wanted to record it here. Sometimes a problem seems daunting, sophisticated etc but the fix is awfully simple.

JavaScript Performance

Playing with client-side filtering. If we have a table with a number of rows, the goal is to allow a user type some text and if particular columns contain the typed text they will be left shown and the rest will be hidden (css display:none).

COL1	COL2	COL3
Value 1 to filter	Value2 to filter	Value3

First Attempt

We can have thousands of rows in a table. So iterate over all rows. for each row get its cells and then use indexOf on the cell innerText property to see if the string being searched for is in the table.

function FilterTable(tableName, text){
 var table = document.getElementById(tableName);
 var trs = table.getElementsByTagName('tr');
 var tds = [];
 if (text == '') {
 
  var tds = [];
  for (var i = 0; i < trs.length; i++) {
   trs[0].style.display = '';
  }
 }
 else {
  for (var i = 1; i < trs.length; i++) {
   trs[i].style.display = none;
   tds = trs[i].getElementsByTagName(td);
   index = tds[0].innerText.indexOf(text) + tds[1].innerText.indexOf(text);
   if (index > -1) {
    trs[i].style.display = '';
   }
  }
 }
}

I was only filtering by first and second column so I did not really iterate over every column.
The interesting thing is that this approach has a terrible terrible performance on large number of rows > 2500. The surprising thing is that even though performance is generally awful; it's even worse in Chrome than in IE8!!

Second Attempt

Playing with the above code, I noticed that the most expensive operation was actually not the indexOf call (although I didn't really use the chrome/ie8 profiler to verify this). The most expensive operation is accessing the DOM and changing properties. Namely this:

trs[i].style.display = 'none';

So in my second attempt I made some important changes:

• in the search loop I instead saved the indices of the table rows whose cells contain the text for which the code is filtering the table. I saved those indices to an array. Later in the code I iterated quickly over the rows and set them all to hidden and one more pass over of the RowsToBeShown array and set those rows only to be visible.
  
• 
  The second change: instead of calling indexOf on two cells, I concatenated (at the server side) the contents of both cells and put them in the title property of the first cell. Now I have to call indexOf just once.
  
• 
  Another change is that I use jquery this time to select the cells to be filtered. I set the class name of the those cell to "FilterTarget".
  

function NewFilterTable(tableName,text)
{
  text = trim(text.toUpperCase());
     var table = document.getElementById(tableName);
     var tds = [];
     var none = 'none';
     var showthese = [];

     var j = 0;
     var td = 'td';
     var index = -1;
     if (text == '') {
         var trs = table.getElementsByTagName('tr');
         for (var i = 1; i < trs.length; i++) {
             trs[i].style.display = '';
         }
     }
     else {
         tds = $(".FilterTarget");         
         for (var i = 0; i < tds.length ; i++) {
             if (
             tds[i].title.indexOf(text) > -1 ) {
                 showthese.push(i);
             }
         }
     }
     for (var i = 0; i < tds.length; i++) {
         tds[i].parentNode.parentNode.style.display = none;
     }
     for (var i = 0; i < showthese.length; i++) {
         tds[showthese[i]].parentNode.parentNode.style.display = '';
     }
     return true;
}

Although I am still iterating twice over the tds array, moving the DOM accessing code out of the search helped performance big time. Withe first approach, Chrome would choke when the filter function is called and give the user a choice to stop executing the JavaScript code. IE does take very long time relatively speaking to run through the filtering code. With the seconds approach and with the same number of rows in the table, both IE8 and Chrome take about 3-5 seconds to run the function.
I am sure that are better ways/well-tested libraries that will do the filter much better but it's rather interesting what moving things around can do to performance. I will see what jQuery API can do here and also jQrid plugin for jQuery is awesome by the way for showing tables and doing an amazing number of things http://www.trirand.com/blog/
here the trim function

function trim(text) {
     return text.replace(/^\s+|\s+$/, '');
 }

I changed some variable names and minor things while typing up this post, so there might some js errors