Acodemics

Page 4 of 6

Unit Testing C# With Data in Visual Studio 2012

When writing unit tests it is likely you will need to include some additional input files containing data or settings etc. If you’re trying to include some data for a C# unit test and are using Visual Studio 2012 follow this guide –

Add a separate folder for data to the project then ‘add an existing item’ and select your files.
In the Solution Explorer, navigate to your newly added file, right click and go to properties.
Set ‘Copy to Output Directory’ to an appropriate option.
When you want to use this data in a unit test add the following before the function – [DeploymentItem(“Data”, “Data”)]

The line in the last step will copy all data from Data in your build directory to the a new folder in the test directory.

I presume that these instructions will apply to older versions of Visual Studio.

Optimising C++ The STL Way

May 16, 2013 / Jack Concanon / 0 Comments

A co worker emailed out an interesting question, how would we optimise the following piece of code –

// Returns the average of k smallest values from the array arr of size n.
// The original order of elements in arr is not guaranteed to be preserved.
float average_of_k_smallest(float* arr, int n, int k)
{
    assert(k > 0 && k <= n);

    std::sort(arr, arr + n);
    float s = 0.0f;
    for (int i = 0; i < k; i++) s += arr[i];
    return s/k;
}

// Returns the average of k smallest values from the array arr of size n.

// The original order of elements in arr is not guaranteed to be preserved.

float average_of_k_smallest(float* arr, int n, int k)

{

assert(k > 0 && k <= n);

std::sort(arr, arr + n);

float s = 0.0f;

for (int i = 0; i < k; i++) s += arr[i];

return s/k;

}

The code looks fast, light and up to the job right? Sure, it will work fine and it will be reasonably fast, but it can always be faster. The first obvious waste of time is with the sort; sorts are lengthy beasts and as much as possible should be done to minimise their impact. The aim of this function is to get the average of the k smallest values in the array, imagine if the array is ten thousand elements big and you only need the average of the two smallest? Sorting that entire array just to get two values is a waste of time.

So, how do we optimise this? My lecturer at university always used to tell us how good the STL is and that it was nearly always better and faster than anything we can write. The obvious solution is to move away from the primitive programming shown in the above function and see what the STL can do for us; luckily enough there are several great functions that do exactly what we want. The first great time saver is the partial sort which simply sorts the array in such a way that the range we specify contains the sorted elements but anything above that middle point is left unsorted. Simply using this method would save a large amount of time over the original method of doing a full sort.

The only requirement of these improvements is to change the function parameters to accept a vector rather than a float array, luckily there were no rules set in the original question!

In order to show that these changes would be faster I wrote some code to prove it. It runs the old function and the new function ten thousand times with the same data and calculates the time taken based on clock cycles. The quicker the better. Take note that the time also includes creating a copy of the input array. If we just pass in the array it will be sorted in place so in reality we are testing how quick it is on already sorted data.

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <cassert>

using namespace std;

const int ARRAY_SIZE = 10000;
const int FIND_SMALLEST = 300;
const int RUN_N_TIMES = 10000;

float average_of_k_smallest(float* arr, int n, int k);
float average_of_k_smallest_partial_sort(vector<float> arr, int n);

int main(int argc, char* argv[]) {

    clock_t begin, end;
    float res;

    srand(time(NULL));
    float array[ARRAY_SIZE];
    vector<float> array_v(ARRAY_SIZE);
    // load the array with random data
    for(int i = 0; i < ARRAY_SIZE; ++i) {
        array[i] = (float)rand()/(float)RAND_MAX; // random numbers from 0..1
        array_v[i] = array[i];
    }

    begin = clock();
    for(int i = 0; i < RUN_N_TIMES; ++i) {
        // Make a copy of the array due to array being passed by reference.
        float array_copy[ARRAY_SIZE];
        copy(&array[0], &array[ARRAY_SIZE], &array_copy[0]);
        res = average_of_k_smallest(array_copy, ARRAY_SIZE, FIND_SMALLEST);
    }
    end = clock();
    cout << "Original function: (" << res << ") " << (float)(end - begin)/CLOCKS_PER_SEC << " sec" << endl;

    begin = clock();
    for(int i = 0; i < RUN_N_TIMES; ++i) {
        // Make a copy of the array
        vector<float> array_copy(array_v);
        res =average_of_k_smallest_partial_sort(array_copy, FIND_SMALLEST);
    }
    end = clock();

    cout << "STL function: (" << res << ") " << (float)(end - begin)/CLOCKS_PER_SEC << " sec" << endl;

    return 0;
}

// Returns the average of k smallest values from the array arr of size n.
// The original order of elements in arr is not guaranteed to be preserved.
float average_of_k_smallest(float *arr, int n, int k) {
    assert(k > 0 && k <= n);
    std::sort(arr, arr + n);
    float s = 0.0f;
    for (int i = 0; i < k; i++) s += arr[i];
    return s/k;
}

float average_of_k_smallest_partial_sort(vector<float> arr_v, int k) {
    partial_sort(arr_v.begin(), arr_v.begin()+k, arr_v.end());
    float sum = accumulate(arr_v.begin(), arr_v.begin()+k, 0.0);
    return sum/k;
}

#include <iostream>

#include <ctime>

#include <vector>

#include <algorithm>

#include <iterator>

#include <numeric>

#include <cassert>

using namespace std;

const int ARRAY_SIZE = 10000;

const int FIND_SMALLEST = 300;

const int RUN_N_TIMES = 10000;

float average_of_k_smallest(float* arr, int n, int k);

float average_of_k_smallest_partial_sort(vector<float> arr, int n);

int main(int argc, char* argv[]) {

clock_t begin, end;

float res;

srand(time(NULL));

float array[ARRAY_SIZE];

vector<float> array_v(ARRAY_SIZE);

// load the array with random data

for(int i = 0; i < ARRAY_SIZE; ++i) {

array[i] = (float)rand()/(float)RAND_MAX; // random numbers from 0..1

array_v[i] = array[i];

}

begin = clock();

for(int i = 0; i < RUN_N_TIMES; ++i) {

// Make a copy of the array due to array being passed by reference.

float array_copy[ARRAY_SIZE];

copy(&array[0], &array[ARRAY_SIZE], &array_copy[0]);

res = average_of_k_smallest(array_copy, ARRAY_SIZE, FIND_SMALLEST);

}

end = clock();

cout << "Original function: (" << res << ") " << (float)(end - begin)/CLOCKS_PER_SEC << " sec" << endl;

begin = clock();

for(int i = 0; i < RUN_N_TIMES; ++i) {

// Make a copy of the array

vector<float> array_copy(array_v);

res =average_of_k_smallest_partial_sort(array_copy, FIND_SMALLEST);

}

end = clock();

cout << "STL function: (" << res << ") " << (float)(end - begin)/CLOCKS_PER_SEC << " sec" << endl;

return 0;

}

// Returns the average of k smallest values from the array arr of size n.

// The original order of elements in arr is not guaranteed to be preserved.

float average_of_k_smallest(float *arr, int n, int k) {

assert(k > 0 && k <= n);

std::sort(arr, arr + n);

float s = 0.0f;

for (int i = 0; i < k; i++) s += arr[i];

return s/k;

}

float average_of_k_smallest_partial_sort(vector<float> arr_v, int k) {

partial_sort(arr_v.begin(), arr_v.begin()+k, arr_v.end());

float sum = accumulate(arr_v.begin(), arr_v.begin()+k, 0.0);

return sum/k;

}

And the results speak for themselves, across ten thousand iterations of each function the STL function is generally twice as fast.

Original function: (0.0157705) 20.56 sec
STL function: (0.0157705) 7.75 sec

May 15, 2013

I think I should finally commit to using this site for something. Anytime I find out something useful or create something that has a remote chance of being reused I will stick it on here.

Maybe it could actually live up to the Acodemic name.

Vinaigrette Sort

May 15, 2013 / Jack Concanon / 0 Comments

When programming in C for embedded systems where memory, disk usage and CPU usage are all very strict there are several ‘rules’ in place such as not use dynamically allocated arrays; this ensures that you can retain more control over memory management.

In a recent experience I had a fixed size array which was always populated below capacity, this array needed to be sorted which would normally leave my zero initialised elements at the start of my array and mess up my loop logic further on in the program.

I had an idea that I could use my sort comparison function to do two things – the first is the original sort purpose of ordering my elements, the second would be to move all unused elements to the end of the array.

Guess what, it’s very simple! I present the vinaigrette sort (so called because the oil and vinegar separate into layers in a vinaigrette).

/* Vinaigrette sort example.
   Author: Jack Concanon
   Date:   14/05/2013
   Website: www.acodemics.co.uk
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

const int BUF_SIZE = 14;
const int NUM_SENSORS = 7;

typedef struct {
    unsigned int id;
    float value;
} Data;

void printBuffer(Data *buf, unsigned size);
int compare(const void *elem1, const void *elem2);

int main(int argc, char* argv[]) {

    Data d[BUF_SIZE];
    memset(d, 0, sizeof(Data)*BUF_SIZE); // Important to zero the array.
    srand(time(NULL));

    unsigned i;
    for(i = 0; i < NUM_SENSORS; ++i) {
        d[i].id = rand(); // random ID number.
        d[i].value = rand(); // random sample value.
    }

    printf("-------- Unsorted array --------\n");
    printBuffer(d, BUF_SIZE);

    // The Magic
    // Sort the d array by ID but at the same time
    //   bubble empty elements to the end.
    qsort(d, BUF_SIZE, sizeof(Data), compare);

    printf("\n\n-------- Sorted By ID --------\n");
    printBuffer(d, BUF_SIZE); 

    return 0;
}

int compare(const void *elem1, const void *elem2) {
    const Data *da = elem1;
    const Data *db = elem2;
    if(db->id == 0) { return -1; }  // Move empty elements to the end
    //if(da->id == 0) { return 1; } // Force empty structs to bubble to beginning.

    if(da->id > db->id) { return 1; }
    if(da->id < db->id) { return -1; }
    return 0;
}

void printBuffer(Data *buf, unsigned size) {
    // loop 'size' times over buf and print.
    unsigned i = 0;
    for(i = 0; i < size; ++i) {
        printf("%d %f\n", buf[i].id, buf[i].value);
    }
}

/* Vinaigrette sort example.

Author: Jack Concanon

Date: 14/05/2013

Website: www.acodemics.co.uk

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

const int BUF_SIZE = 14;

const int NUM_SENSORS = 7;

typedef struct {

unsigned int id;

float value;

} Data;

void printBuffer(Data *buf, unsigned size);

int compare(const void *elem1, const void *elem2);

int main(int argc, char* argv[]) {

Data d[BUF_SIZE];

memset(d, 0, sizeof(Data)*BUF_SIZE); // Important to zero the array.

srand(time(NULL));

unsigned i;

for(i = 0; i < NUM_SENSORS; ++i) {

d[i].id = rand(); // random ID number.

d[i].value = rand(); // random sample value.

}

printf("-------- Unsorted array --------\n");

printBuffer(d, BUF_SIZE);

// The Magic

// Sort the d array by ID but at the same time

// bubble empty elements to the end.

qsort(d, BUF_SIZE, sizeof(Data), compare);

printf("\n\n-------- Sorted By ID --------\n");

printBuffer(d, BUF_SIZE);

return 0;

}

int compare(const void *elem1, const void *elem2) {

const Data *da = elem1;

const Data *db = elem2;

if(db->id == 0) { return -1; } // Move empty elements to the end

//if(da->id == 0) { return 1; } // Force empty structs to bubble to beginning.

if(da->id > db->id) { return 1; }

if(da->id < db->id) { return -1; }

return 0;

}

void printBuffer(Data *buf, unsigned size) {

// loop 'size' times over buf and print.

unsigned i = 0;

for(i = 0; i < size; ++i) {

printf("%d %f\n", buf[i].id, buf[i].value);

}

It is as simple as modifying the compare function required by the qsort function. Check if a field in your struct (or your data) is zero and therefore unused and then declare it as ‘greater’ than any comparison. I did find that an older GCC version (3.7) required the line as described in the above source code, GCC 4.7 compiled and ran as required with just the one comparison.

Note the memset line, if you leave the array uninitialised then the compare won’t have anything defined to search for that would signify an unused element.

Python Socketed Receiver

March 14, 2013 / Jack Concanon / 0 Comments

This is a quite cool little class I wrote for receiving log messages over sockets. It is launched as a thread and uses a python Queue to store messages for retrieval by consumers in your main program. It also means I can have multiple sockets for different log sources.

#!/bin/python2.6

import threading
from Queue import Queue
import socket

class LoggingReceiver(threading.Thread):

    def __init__(self, host, port):
        threading.Thread.__init__(self)
        self.host = host
        self.port = port
        self.msg_queue = Queue()
        self.running = True
        self.max_waiting_connections = 10
        self.daemon = True
        self.debug = True

    def run(self):
        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        s.bind((self.host, self.port))
        s.listen(self.max_waiting_connections)
        while self.running:
            accepted_socket, address = s.accept()
            self.debug_msg('Received connection from {0}'.format(address))
            msg = ""
            while self.running:
                data = accepted_socket.recv(1024)
                if not data: 
                    break
                msg += data
            self.add_message(msg, address)
        s.close()

    def debug_msg(self, msg):
        if self.debug:
            print msg

    def add_message(self, msg, source):
        self.debug_msg('{0} sent message - {1}'.format(source, msg))
        self.msg_queue.put(msg)

    def get_message(self):
        if not self.msg_queue.empty():
            msg = self.msg_queue.get()
            self.msg_queue.task_done()
            return msg

    def flush_queue(self):
        while not self.queue.empty():
            self.msg_queue.get(block=True)
            self.msg_queue.task_done()

    def stop(self):
        self.debug_msg('Stopping main loop.')
        self.running = False

#!/bin/python2.6

import threading

from Queue import Queue

import socket

class LoggingReceiver(threading.Thread):

def __init__(self, host, port):

threading.Thread.__init__(self)

self.host = host

self.port = port

self.msg_queue = Queue()

self.running = True

self.max_waiting_connections = 10

self.daemon = True

self.debug = True

def run(self):

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

s.bind((self.host, self.port))

s.listen(self.max_waiting_connections)

while self.running:

accepted_socket, address = s.accept()

self.debug_msg('Received connection from {0}'.format(address))

msg = ""

while self.running:

data = accepted_socket.recv(1024)

if not data:

break

msg += data

self.add_message(msg, address)

s.close()

def debug_msg(self, msg):

if self.debug:

print msg

def add_message(self, msg, source):

self.debug_msg('{0} sent message - {1}'.format(source, msg))

self.msg_queue.put(msg)

def get_message(self):

if not self.msg_queue.empty():

msg = self.msg_queue.get()

self.msg_queue.task_done()

return msg

def flush_queue(self):

while not self.queue.empty():

self.msg_queue.get(block=True)

self.msg_queue.task_done()

def stop(self):

self.debug_msg('Stopping main loop.')

self.running = False

Linux Mint on VirtualBox – Enable 3D Acceleration

March 5, 2013 / Jack Concanon / 1 Comment

Just spent a bit of time installing the latest Linux Mint (14.1) on VirtualBox and struggling to get the VirtualBox 3D acceleration to work correctly. This causes the window manager to fall back to software rendering (yuk); to see if your machine is currently using software rendering run inxi -G and check for Gallium 0.4 on llvmpipe (LLVM 0x300).

To get the full 3D acceleration from VirtualBox ensure that 3D acceleration has been enabled from the settings menu and a decent amount of video RAM is available, I have it running quite well with 56MB of RAM. Load up Linux Mint and install the VirtualBox additions from the devices menu. Ignore the warnings about it already being installed and carry on. Reboot the virtual box and run inxi -G again, it should now show something similar to this –

Graphics: Card: InnoTek Systemberatung VirtualBox Graphics Adapter
X.Org: 1.13.0 drivers: ati,vboxvideo (unloaded: fbdev,vesa) Resolution: 1920×1200@60.0hz
GLX Renderer: Chromium GLX Version: 2.1 Chromium 1.9

I only get this problem on a fresh install of Linux Mint. It’s supposed to be bundled with the VirtualBox guest additions but I guess they don’t always work as they should.

WTF Is UPlay?

January 4, 2013 / Jack Concanon / 1 Comment

Wanted to play Far Cry 3, turns out I have to use yet another pointless game ‘service’. Seriously, for single player I have to register an account and be logged on and all sorts of other rubbish. Really getting tired of this all because of piracy. Next time I’m getting it from the Pirate Bay.

New Gmail Compose Screen

November 5, 2012 / Jack Concanon / 0 Comments

Just been prompted by Gmail to use a new email composing screen. Not a massive change as you’d expect from Google but it does make the web client a bit more seamless. Basically instead of being directed to a new screen when composing an email, a composition window similar to a Google chat window will appear in the lower right hand of your screen.

It is a nice change and will no doubt be rolling out to everyone shortly.

Project Eternity

October 29, 2012 / Jack Concanon / 0 Comments

I have backed my first Kickstarter campaign, and what a place to start! Project Eternity is the idea from a group of clearly very talented developers with titles such as Baldur’s Gate, Fallout and Planescape Torment under their belts. TAKE MY MONEY PLEASE. Cannot wait to see how this game turns out.

Been very impressed with their attitude about the whole thing, very frequent updates and lots of chances to communicate with the developers. I just really hope they preserve the feel of the original Baldur’s Gate which seems to be it’s closest spiritual predecessor.

The Kickstarter process is very easy and clear to use, I will definitely be on the lookout for more good ideas to get behind.

Some more info – http://www.kickstarter.com/projects/obsidian/project-eternity

September 13, 2012

Today I learnt that it is programmer’s day, apparently we’re all supposed to get beer and pizza? I for one shall be celebrating by porting various tools from Linux to Solaris.

Correct Setup of Python Easy-Install

August 11, 2012 / Jack Concanon / 1 Comment

Starting work on some python driver development today for the ant+ system (more on this later) and had to install a bunch of Python modules that didn’t appear on the standard Ubuntu repos.

Python has a very easy package manager of it’s own called easy tools which is found in the python-setuptools package. But this isn’t everything you need, you’ll receive a lot of errors when trying to use easy tools such as –

msgpack/_msgpack.c:4:20: fatal error: Python.h: No such file or directory
compilation terminated.
error: Setup script exited with error: command ‘gcc’ failed with exit status 1

In order to resolve these errors you’ll need to ensure you have g++ installed as well as the python header and static library files. These two packages are called g++ and python2.7-dev. Change the python version depending on your preference or download the python-all-dev package.

HTC One X – One Hot Potato

August 11, 2012 / Jack Concanon / 0 Comments

I bought the HTC One X after my trusty Desire HD ended it’s life inside my washing machine. A fantastic phone and quite the looker but woah does this thing get hot when it’s doing something!

The other day I was using the Google video chat and the notification LED started flashing orange and green at me, seems to mean that it’s overheating and you should probably stop doing what you’re doing.

There’s a new update doing the rounds at the moment, V2.05 I think, hopefully it will sort some of these problems out.

Theme by Anders Norén — Up ↑

Categories

Meta

Page 4 of 6

Unit Testing C# With Data in Visual Studio 2012

Optimising C++ The STL Way

Vinaigrette Sort

Python Socketed Receiver

Linux Mint on VirtualBox – Enable 3D Acceleration

WTF Is UPlay?

New Gmail Compose Screen

Project Eternity

Correct Setup of Python Easy-Install

HTC One X – One Hot Potato

Recent Comments