Monday, December 8, 2014

Sample Usage of AVL, quick and dirty.

So, previous article ported FreeBSD AVL into Linux AVL. (AVL Tree in C )
Here is quick and dirty way of how to use it.
It will be straightforward, except one thing.

Your data struct must be divided into two pieces.  Data part and avl_node_t part.  The Data part size must be multiple of 8.  If not, there will be a puzzling assert((offset & 0x7) == 0).  Here is the usage.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <stdint.h>
#include "avl.h"

#define NAME_LEN 36
#define PHONE_LEN 10

// assuming dtype has a link member as node type (avl_node_t)
#define OFFSETOF(data) (sizeof((data)->name) + sizeof((data)->phone) )

typedef struct person {
 char name[ NAME_LEN + 1];
 char phone[ PHONE_LEN + 1];
 avl_node_t  my_link;
} Person;

int comparePerson(const void *a, const void *b) 
{
 Person *_a = (Person *)a;
 Person *_b = (Person *)b;
 if ( strncmp(_a->name, _b->name, NAME_LEN) < 0 )
  return -1;
 else if ( strncmp(_a->name, _b->name, NAME_LEN) > 0 )
  return 1;
 return 0;
}

Person* searchByName(avl_tree_t *tree, const char *name)
{
 Person *cur = AVL_NODE2DATA(tree->avl_root, tree->avl_offset);
 avl_node_t *p;
 while (cur) {
  if (strcmp(cur->name, name) == 0)
   return cur;
  else if (strcmp(name, cur->name) <0) {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[0];
  }
  else {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[1];
  }
  cur = p ? AVL_NODE2DATA( p, tree->avl_offset) : NULL;
 }
 return NULL;
}

void printTree(avl_tree_t *tree)
{
 int i = 0;
 Person *cur;

 printf("Total nodes in tree: %ld\n", avl_numnodes(tree));
 printf("Root: %s\n", ((Person *)(AVL_NODE2DATA( tree->avl_root, tree->avl_offset)))->name);

 cur = avl_first(tree);
 while (cur) {
  printf("%d : %s(%s)\n", i, cur->name, cur->phone);
  cur = AVL_NEXT(tree, cur);
  i++;
 }
 printf("---------------------------------------------------------------------\n");
}

int main(int argc, char **argv)
{
 avl_tree_t avl;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 avl_create(&avl, comparePerson, sizeof(Person), OFFSETOF(&a));
 avl_add(&avl, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 avl_add(&avl, &b);

 //traverse 
 printTree(&avl);

 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 avl_add(&avl, &c);

 //traverse!!  root must be Jack.
 printTree(&avl);

 // Searching.
 Person *search;
 search = searchByName(&avl, "Jack Stuart");
 if (search) 
  printf("Jack found: %s\n", search->name);
 else
  printf("Jack not found\n");

 search = searchByName(&avl, "lalalalala");
 if (search)
  printf("lala found:\n");
 else
  printf("lala not found\n");

 return 0;
}

AVL Tree in C

Code is here: github link

Practically speaking, we don't need AVL tree these days.  There are good alternatives in general.  In algorithm perspective, there is a Red Black Tree, the rival of AVL tree.  They mostly serve for the similar purpose.  RBTree is easier to implement, but size is factor of 2 vs. AVL is 1.4.  Linux uses RBTree internally, and FreeBSD had AVL.  (Linux RBTree article)

Well, in day to day life, modern languages provide their own version of "List".  In Python case, we just stuff data into the list, and later call it by index.  For efficient search, we use bisect module.  If we need sort, Python list takes very "Intelligent" approach to be efficient.  I will discuss this later, but listsort.txt in Python source can be referenced.

But, then, why bother AVL tree?
First, it's mentioned more in different algorithm books probably thanks to BST (Binary Search Tree).  And, AVL is a good subject to introduce concepts of algorithm, "let's cover the weakness of a given algorithm."  Second, it's personal.  I just like it with no reason.

When I searched AVL written in C, I found many pages.  First, GNU libavl is an overkill.  Other small projects are not mature enough.  Either it's "not generic", or data allocation logic is "malloc".  This will cost performance.  Modern days, C is chosen by performance in many cases.  So, too many or individual malloc is a bigger penalty.

Interestingly, FreeBSD has avl implementation and they still include it even today.  Probably, former SunOS used avl for kernel data.  This is small.  This only implements AVL algorithm, but comparator is a function pointer which I can attach.  AVL node does not bother the data, but my data suppose to embed avl_node_t.  And, AVL algorithm doesn't do high-level search.  So, I have to provide the high level search, like searchByName(const char *key).  I liked the design  because it is more flexible.  Unfortunately, it's not directly usable in Linux.  So, I tweaked and made it usable in Linux.  There are two files (avl.h and avl.c).  Enjoy.


Friday, December 27, 2013

Wednesday, October 30, 2013

Pushing scale practice doesn't help improvising.

I used to have this problem in my first year playing guitar.  My first ultimate goal was "Far beyond the sun" by Yngwie Malmsteen.  Pretty ambitious for a beginner.  Accomplishing song by song, picking speed went up, left finger maneuver became fluent.  However, Yngwie Malmsteen style is pretty challenging.  If I remember that time, I practiced different scales in metronome.  One day, I could play "far beyond the sun."  However, the speed I play for Yngwie Malmsteen didn't help other songs.  I was puzzled.

Big Question. "I could cover fastest genre of the music, but other than his music, I am still struggling with other pieces.  Why? "

Having 10 years of gap without playing guitar, I can't play Yngwie Malmsteen as I did.  But, I can enjoy more music than back then I used to play.  Here is my answer about the question.

Improvising has two modes.  "Controlled progression" and "Shredding".  Controlled progression relies on current musical context.  What is the key signature/main scale?  What is the beat signature/and main rhythm? More importantly, controlled progression much relies on the brain, the most important tool for music.  Muscle movement works together with the brain.  Do you see that the limiter is "the brain"?
On the other hand, shredding depends less on the brain.  It heavily relies on muscle memory.  Brain just sets up basic information like "what code/what sclae" and "what major beat", then finger works all.  In here, detail is less important, such as order of notes  as long as notes are in scale, and diatonically working.

When playing in band, these come out somewhat mixed.  For example, Yngwie Malmsteen, many phrases are roughly 20% controlled, 80% shredded.  So, brain tells "From now, 4 measures will be diminished rooted 20th fret C down."  Then, during 4 measures fingers improvise without help of brain.  In the meanwhile, brain accepts the next phase, "stop at 8th C vibration, for the 4 beats, and then the last half beat will Bm harmonic minor in pulling manner."  After executing 4 measure, this should end at C, and pulling Bm harmonic scale comes up.  Sure while this finger is working, Brain just thinks the next, not the one fingers are playing.

When in shredding mode, accidentals are not common.  Because accidental is a big brain work.  "We make irregular note X, which is not in scale, but produces effects of A,B,C, and some alpha of tention.  It will be resolved by in scale tonic Y or 5th of Y, etc. "  These need lots of controlled work.  Fingers can't just dance on their own.  They will pay attention to the brain.

Now the key point here.  Increasing maneuverability in controlled work is the foundation to play variety of music.  At the same time, brain should have more tools to provide good signals to the fingers.  I will explain this further.
Here is a simple test how fast I can maneuver in controlled.
Simply pentatonic through 6 strings.(Low A(5th fret 6th string) to high C(8th fret 1st string).  Try beginning with down picking. Change the same play with beginning with up picking.  This is one example of controlled picking.
There are different patterns of controls like 3rd down (C-A, B-G, A-F, G-E, F-D, .... ), alternate/3 string sweep, etc.
If these maneuver is fluent, many things will be easier.  Plus, shredding speed will also increase.

At the same time, don't forget to listen to more good musics.  And catch ideas from the music.  Eventually, collection of these ideas will make brain lucrative to utilize, and improvising will be cool and sound.




Monday, October 28, 2013

Guitarists...

So, my favorite instrument is the guitar.  Practically, I only can play the guitar.  Many great musicians inspires me, but due to my limited time, when I get a chance to play it, I have to concentrate for just one thing.

Anyway, my favorite guitarist is "Jason Becker."  He is the god and the most fluent guitarist.  At the same time, he had many brilliant ideas.  Considering all of his work, which ended at his age of 29, he didn't have his best time, unfortunately.

Then, my favorite "active" guitarist is "Guthrie Govan".  He is very special, to tell the truth.  Most of guitarists have own color, specializing handful of genre, Guthrie doesn't have specialty.  He is really all-rounder.  Rock, Blues, Jazz (Classic, Beebop, fusion, plus some brilliant covers with different colors), and Country.  Picking, finger style, slap, tapping, arpegio, ...  He also plays very good acoustic.  His theory is very strong.

I recommend his videos in youtube.  None have disappointed me, so far.

Wednesday, August 21, 2013

Tuesday, April 30, 2013

My youtube #10.

Time What is Time - Blind Guardian.