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.
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")
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:
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”.