Representing an Upper-Triangular Matrix as an Array

Hello Avid Readers,

Today, I want to discuss a efficient and fast data structure that represents a Upper-Triangular matrix. An upper triangular matrix consists of 1+2+…n=n(n+1)/2 elements, which is less then n^2 of a matrix. The question is how should we represent this as an primitive array? Or more specifically, what should the hash function be that maps and index of this data structure to a 1d-array. I stumbled upon this blog post, which suggests the following approach. First define a hash function:

i=(n * r) + c – (r * (r + 1))/2

So now we can iterate:

string[] array = new string[(n*(n+1))/2]; //allocate
for (int r=0; r<matrix.GetLength(0); ++r) //each row
{
  for (int c=0; c<matrix.GetLength(1); ++c)
  {
    int i = (n * r) + c – ((r * (r+1)) / 2);
    array[i] = matrix[r,c];
  }
}

And it works beautifully.

 

Advertisements

Simple C++ debugging in Mac OS X

If you are familiar with C\C++ debugging in Linux, you probably use GDB. However, GDB is not readily available on Mac OSX. First of all, Mac OS X uses Clang instead of the GCC compiler. GDB is configured to work with GCC. Fortunately, Clang has a different debugger available that is natively installed on your Mac machine  — LLDB. LLDB is the default debugger on  Mac OS X.

LLDB works almost exactly like GDB. For a good introduction see here. For more details on GDB and debugging, see my UCLA CS 35L slides. Most importantly, to debug your need to add the “-g” parameter when compiling. If you are using CMake, that translates to:

set (DEBUG_FLAG "-g")
add_definitions(${DEBUG_FLAG})

Happy Debugging!

Making animation GIFs with Blender and Mac OS X

Today I wanted to put a GIF of some recent result of my animation. First of all, I need a screen capture of the animation. For that I used Quicktime. More specifically, open Quicktime, and then click File –> New Screen Recording. After recording your animation, import it Blender. Blender has an awesome video editing tool, and but that is a topic for a different blog post. After editing the animation, for example corping the edges of the screen, and picking your preferred  GIF resolution, we choose to render it as a PNG file for each frame. Finally, select a folder to save the animation and animate the video.

After the creating PNG files, we want to combine them to a GIF. I followed this post:
1. Install imagemagick with this command on linux (sudo port install for Mac OSX):

sudo apt-get install imagemagick

2. Go to the default render directory (this will be /tmp in linux) where you should find a lot of png files.
3. Type this command to create your gif from the PNG files:

convert -delay 4 -loop 0 *.png animated.gif

4. Enjoy your new animated gif.

Note – the delay setting refers to 1/100ths of a second. so in the example above 4/100th = 25fps. So for 60 FPS, we do “-delay 1.67”.