Wednesday, August 22, 2012

Nested Looping

Nested looping is something of an art. There are many times when I was starting out where I thought a jump statement like a GOTO would make things easier. As I've developed my programming skills, I have learned that GOTO is a waste of time that will create spaghetti code, unreadable and hard to follow. Instead, many solutions can be created with looping. Although sometimes nested looping is needed. Nested looping can be complicated to grasp, but it is actually very simple.

Nested looping can process multi-dimensional arrays, create simple user interfaces, and are commonly used for graphics for staying alive and checking events.

The flow of nested looping is very sequential. For every time to outer loop executes, the inner loop will execute however many times it is set to loop. So say you have two nested loops to populate a 2 dimensional array where it is an array of 10 arrays of 10 integers, the inner loop will run 100 times.

int val = 0
for(int i = 0; i < 10; i++) {
    for(int z = 0; z < 10; z++) {
        array[i][z] = val++;
    }
}

This will populate the array sequentially, starting with the first array. It will go through that then move on to the next array, so on and so fourth. Nested looping does not always have to include just loops and does not always need to be iterative. Here is some psuedocode showing a very basic user interface.

while(keepGoing) {
    refresh();
    events[] = event.get();
    for(event in events) {
        if(event = QUIT) keepGoing = 0;
        else ;// Some event handlers
    }
}

It is crude, but I didn't feel like mocking up a full featured one. On top of the extra code, you can also nest multiple loops on the same level or nest on even more levels. Perhaps it would make a nice way to mark up the flow for something to solve a sudoku puzzle or something like that.

However, sometimes there is no clear and linear way to process information. Or perhaps there is but it is messy. You may want to use a GOTO. Before you do, consider recursion. By using multiple functions to achieve a task, your code will be more scalable, compartmentalized, cleaner and shorter for these dire situations. If the recursion will be very deep, I suggest looking into lazy evaluation and if you can use it.

Just some simple recursion and branching can allow you to jump to any point in the code without complicated looping and tracking of variables. The idea is that when you enter a function, you then branch out to other functions selectively, allowing you do go in a non-linear flow. One important caveat, make sure a limit is in place so the recursion will actually end. If it does not, you will either get an error or it will run forever depending on how you implement it and in what language.

Sunday, August 19, 2012

Multidimensional Arrays

Multidimensional arrays are hard to comprehend at first, but they are actually very simple. The problem arises in people using multidimensional lists and similar data structures that can make things awkward as they do not function the same.

In my previous post on arrays, I mention that an array will contain all the same datatype. The reason for this that I was trying to get across is because since an array would be contiguous memory, to find any element you simply multiply what element by the size of the datatype (since all are the same datatype), which will result in how many bytes to add to the memory address to get the address of the element you wish to access. It would be like arranging items an equidistant apart and telling someone to find an item where instead of counting, you use a ruler and measure out where the start of the index is to get the item.

Since an array requires all datatypes to be the same to easily find the item, multidimensional arrays work the same. A multidimensional array is just an array of arrays, and as such all arrays inside the array must be the exact same length, meaning also they are the exact same datatype. If the items are not the same length, a couple things can happen. The first thing is the memory will still be allocated, but the unused elements will be empty. This will preserve the speed to access the information and in some instances is called "padding". Padding is filling up unused space with empty information so that it will reach a certain size. It is used in some database designs and will be used for an array. Another thing to consider is an array of strings. Strings are arrays themselves, more specifically character arrays. In the case of an array of strings, all strings will be padded to the longest string in the array. The end of a string is determined by the null character, denoted as \0, which is character zero (0x00). This also means a string is one character longer than what you normally see, as programming environments like compilers and interpreters deal with that for you.

So the math to access an element in a multidimensional array pretty much the same as a single dimensional array, except you also tack on the length of any preceding arrays. Like if you have an array char[10][10], the first index is 10 characters in length for each index, then you add on the last part normally.

(sizeof array) * i1 + (sizeof type) * i2

This is the basics of a two dimensional array and can be expanded for nth dimensional arrays.

Friday, August 10, 2012

Looping

After polling for an idea for a post, one on looping was asked for, so hopefully I can shed some light on looping. First thing to note is that not every language loops the same. The two most common loops I have seen are for and while. There are also foreach, do...while, and various syntaxes that are similar to or emulate these ideas. You can also "loop" with recursion, which is something more for functional programming. So for now we sill stick to the common loops and I will cover the syntaxes I know for certain languages.

First off, there are two kinds of looping. Iterative and conditional, the first being what most people think of when looping. Iterative looping requires going for a fixed amount of times and commonly used for processing data iteratively, or one element at a time. Conditional looping will most often, though not always, use an infinite loop and some condition to break out of the loop. This is what you would use for a network application or anything where it is unknown how many times you will loop. To start, let us look at iterative looping.

Iterative looping will often use a for or foreach style syntax. Since foreach is not very common, I will stick to the C style for for now. This type of for loop uses 3 optional statements for the condition, variable for tracking, condition, and an update. The common layout is

for(int i = 0; i < dataSetLength; i++)

In this, i is usually the index of the loop, dataSetLength is the amount of times to loop, either the length of a set of data like an array or just an arbitrary number to preform a task and i++ will increment the index for each time it loops. The main use of this is for a linear style processing, like so

int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for(int i = 0; i < 10; i++) x[i] += 2;

Now foreach style looping is much easier to use than all this extra variable manipulation, however each language seems to have its own syntax for this, so I will breeze through these. C does not have one, so you would either need to make a macro for it or use the standard for loop.

Python, one of my favorites, uses for variable in iterable, where iterable is something like a list or dictionary. Simply it looks like

x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for y in range(len(x)): x[y]+=1
This for variable in dataset style syntax is also in Ruby and Javascript, but with parenthesis around the condition part in Javascript, (variable in dataset).

Java has its own syntax which was borrowed by C++, which is simply
for(type variable: dataset)

The last one I'll look at is php's foreach loop, which looks a lot like Perl's.

foreach ($iterable as $item)

All of these can be made with a standard for loop, save for in the languages that do not use a standard for loop, like Python, a while loop or generator expression can be used for a standard for loop flow, as the for is a foreach. To use a while loop like a for, in C syntax it is

int i = 0;
while(i < dataSetLength) {
    // Do stuff
    i++;
}

I'll leave converting it to other languages as while loops to yourself since it is pretty standard throughout many languages. Now we turn our heads to conditional looping. Conditional looping, as previously stated, will take an infinite loop (not always) and loop until a condition terminates it. This can use while and do...while loops or for loops in some languages, however a while loop is generally preferred for clarity. There are two C style infinite loops.

while(1)

and

for(;;)

Infinite loops while use a break statement in a conditional to terminate the loop. This would be used for something like a user interface that collects data indefinitely or a network app that needs to keep getting and sending information until some arbitrary point or anything else where you are unsure of how long it should loop for. if a single condition exists that terminates the loop, one could use a variable and do something like

while(condition)

or

for(;condition;)

For this, a while loops would generally be used. Instead of checking a condition, you would even simply use just a variable name assuming the variable can be tested as either true or false, which is also easy and in some cases clearer. I suppose the easiest way to understand this is to show an example. So we shall make a simple cli.

#include <stdio.h>
#include <curses.h>

int main(void) {
    initscr(); // Initalise the ncurses library
    cbreak(); // option to disable buffering etc.
    char x;
    while (1) {
        printw("0 to exit;> ");
        refresh(); // update the screen, so the text is displayed
        x = getch();
        if(x == '0') break;
        printw("\nBlah blah blah\n");
        refresh();
    }
    getch();
    endwin(); // close ncurses library
}

While this program doesn't do anything really, it gives an example of how to use an infinite loop. As you should notice, the break happens in the middle of the loop, so if the condition is met it will break out before it executes everything in the loop. If we moved the condition in the if statement to the while itself, it will not check the condition until everything in the loop executes. This is why jump statements are necessary. Here is a more complex example using another jump statement.

#include <stdio.h>
#include <curses.h>

int main(void) {
    initscr(); // Initalise the ncurses library
    cbreak(); // option to disable buffering etc.
    char x;
    while (x != '2') {
        printw("0 break; 1 continue; 2 end> ");
        refresh(); // update the screen, so the text is displayed
        x = getch();
        if(x == '0') break;
        else if (x == '1') continue;
        printw("\nBlah blah blah\n");
        refresh();
    }
    getch();
    endwin(); // close ncurses library
}

In this case, 0 will exit the loop, 1 will skip sending text and 2 will show the text then end. Now there is one more alternative, a do...while loop. These loops are the same as a while loop, however guaranteed to run the code in the loop at least once (excluding if a jump statement is met). With some minor tweaking, we could utilize it in a useful way.

#include <stdio.h>
#include <curses.h>

int main(void) {
    initscr(); // Initalise the ncurses library
    cbreak(); // option to disable buffering etc.
    char x;
    do {
        printw("0 break; 1 continue; 2 loop again> ");
        x = getch();
        if(x == '0') break;
        else if (x == '1') continue;
        printw("Blah blah blah");
    } while (x == '2');
    getch();
    endwin(); // close ncurses library
}

This will make it so that 2 will keep the program looping. The reason we need the do...while instead of a normal while is because without that, the program would not execute.

This is just a brief overview of how to use some loops. Sometime later I may cover nested looping. The summary is looping will repeat code until a condition is met. That condition can either be a set amount of time or indefinite, it all depends what you need to do. Something to always keep in mind is how many times a program will loop and how fast. Looping with some blocking statement, usually i/o, will prevent it from using too much cpu by running code as fast as possible, even if not doing anything. As such, if using something that is not blocking, meaning it will not stop and wait for something else to happen, a frame rate of some kind is suggested. I will cover timing in another post, probably with nested looping.

Wednesday, August 8, 2012

Understanding Arrays

I was out of state for a bit and a friend I wanted to asked me for some help with his programming work for school. Now being as I'm used to Python, I did not understand fully what the goal was but I feel arrays are something people need to understand. So I am going to explain the basic concept of an array in C terms and hopefully that may clear up some confusion. Keep in mind my explanation is not 100% true and I will explain the catches when I get there.

An array is a piece of contiguous memory allocated to store n number of elements of the same data type. In essence, it is a variable. However technically it is a pointer. A pointer is a variable that contains an address to a particular memory address. For example, if you have

int arr[10];

Here we have an array of 10 integers. The variable arr is not the array, but it points to the memory location at the start of the array. Thus arr is not the same as arr[0], as this accesses the first value. In a more diagram-like example you have

arr => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        ^
        arr[0]

Now say we want to get the second element (arr[1]). To do this we then need to start at where arr points to, then move along that memory point to the next int. To get to this we need the memory address arr then to add the size of an int to it to get the next value. Thus to get this we can do

((sizeof int) * n) + arr

Where n is the array index arr[n], in this case 1, so we end up with

((sizeof int) * 1) + arr

This will give us the memory location of the second element, 0 being the first because arr points to the start of the array, but not the first element. That is the basic idea behind an array where the syntax given is more or less an alias that goes all the math automatically for you.

So now for some caveats. Higher level languages may use memory abstraction. This means the memory in reality is not contiguous, however to the program it appears as it is. The operating system further abstracts this with methods like paging, which allow for more efficient memory usage at the cost of some overhead for an abstraction process. To the program, the memory will appear contiguous to the program. Due to memory abstraction methods, you should not rely on contiguous memory and also use bounds checking where necessary as apposed to waiting for a segault or some other thing to hit the fan.

Uses for arrays include tracking sets of data and easy looping, accessing and assigning of data, for linear or non-linear processing, whereas lists are more suited for linear searching. With lists you can also create trees, which will allow different ways to access data. Arrays can also be used for sorting data and for a lot of things will be a good deal faster than lists and trees, but in some situation can be cumbersome.

Array manipulation is something I hate, like permutations and sorting. Easiest options are using an array manipulation class, as doing things manually is a pain and will need temporary variables, unless you can efficiently do recursion like with a lazy evaluation language (functional programming languages do this and are very clean with these methods because of it). So  before attempting something like that on your own, check for a library that can do it for you. If you absolutely need to do it yourself or just want to for knowledge seeking, good luck.

Tag Cloud

.NET (1) A+ (1) addon (6) Android (3) anonymous functions (5) application (9) arduino (1) artificial intelligence (2) bash (3) c (7) camera (1) certifications (1) cobol (1) comptia (2) computing (2) css (2) customize (15) encryption (2) error (15) exploit (13) ftp (2) gadget (2) games (2) Gtk (1) GUI (5) hardware (6) haskell (15) help (5) HTML (4) irc (1) java (5) javascript (20) Linux (18) Mac (4) malware (1) math (8) network (5) objects (2) OCaml (1) perl (4) php (8) plugin (6) programming (42) python (24) radio (1) regex (3) security (21) sound (1) speakers (1) ssh (1) telnet (1) tools (11) troubleshooting (1) Ubuntu (3) Unix (4) virtualization (1) web design (14) Windows (6) wx (2)