James : Rants

Dearest colleagues,

(Further to Pietro’s blog post)

I do hope you are getting on well with your C++ assignment, which from the sounds of it is going down like a lubed anvil. Couple of things id like to get off my chest, if I may be so bold.

1. Hash Maps

A hash map is none of the following:

1. A linked list
2. A “big” array
3. A binary tree
4. A balanced tree
5. A “happy” atlas

If we store our records in a linked list, we can access them by scanning along and comparing the key until we find the right one. If the list is unsorted and of an unknown length this will take at worse N comparisons (and increments) where N is the length of the list. If the list is sorted and of a known length then it will take Log(N) comparisons (binary cut), but to get to each node one must still traverse the list in that direction, so it in fact takes (I believe… john?) xLog(x) (i.e the order of the integral of log(x)). So sorting a linked list and binary chopping is therefore futile unless you can access elements without scanning. Don’t iterate over list.at(i)!

Enter: the hash map. Let us say we are storing students with a cid and a name. The key will be the id. We know that these are evenly distributed between odd/even so we could construct two linked lists, one with the evens and one the odds. This would cut the average search time in half. Thus the hash function (which decides which list to enter) would be cid%2. Obviously this generalises quite nicely, so if we have 10,000,000 students we could have 100 lists from our table and use cid%100 as the hash function.

However, when running on a computer that has even a marginally faster clock rate than a wall clock, there is no fucking difference – just search the damn list and get on with something more useful.

Here is the only code you need to look for records:

class Record {
int cid;
string name;
};

class Node {
Record* record;
Node* next;
};

class JamesList
{
Node *head;

string lookupNameByCid(int cid) {
Node* runner = head;
while (head != null) {
if (runner->record->cid == cid) return runner->record->name;
runner = runner->next;
}
return null;
}

};

I thank you.

2. Simulating Circuits

Here is a circuit:

(circuit)

The aim is simulate its behaviour using an event queue. There are two different types of entities here, nodes (blob) and gates. Both share common functionality, they have an output value (Vo) and a set (see above) of outward connections. This makes traversing the network in the same direction as the input changes propagate easy.

So:

class Device {
int Vo;
int delay;
JamesList drivenDevices;
};

class Node : public Device {};

class Gate : public Device {};

Good. Some good stuff there. So when the user presses the button for node a to change its voltage to 1, we create an event in the event queue (an ordered list of some kind). Then start the simulation by making the first event happen. The output of a device only changes when the event is actually executed, not when we realise that a change must happen. The time difference between these is the propagation delay of the device (for a node this = 0).

I think the event execution should go something like this:

void simulate(int until)
{
EventListNode *runner;
runner = events->head;

/* FOR EACH EVENT */
for (int i=0; isize; i++)
{
//Check we arent about to overstep the mark
if (runner->event->time > until && until > 0)
{
break;
}

//This event's node
Device *changedDevice;
changedDevice = runner->event->node;

//Actually change the output voltage
changedDevice->setVo(runner->event->Vnew);

//The gate immediately to the right of this node
Set *affectedGates;

affectedGates = changedDevice->drivenDevices;

if (affectedGates != NULL)
{
set::iterator itr;
itr = affectedGates->begin();

Device *thisDevice; //Gate for which to update output

//Foreach Device which this Device affects, recalculate its output
int vnew;
while( itr != affectedGates->end() )
{
thisDevice = ((*itr)->device);

vnew = thisDevice->Vnew;

//If the voltage has changed make an event
if (thisDevice->Vo != vnew)
{
events->addEvent(thisDevice,
thisDevice->Vo,
vnew,
runner->event->time + thisDevice->delay);
}

itr++;
}

}

runner = runner->next;
}

//We're done, so delete the events.
events->clear();
}

I do hope that makes some sense, since I have personally given up caring.
Its also important that the ordered event list puts new events with the same time as existing events after the current ones, else they will be missed.

Love and cuddles,
James

:: james at jgubby.com

This entry was posted on Tuesday, April 17th, 2007 at 3:52 pm and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.