Nick's blog - Comments

Debbie Payne: Response from Gohop

nospam@example.com (Debbie Payne) — Fri, 21 Nov 2008 10:34:14 +0000

I read your note on Gohop and I can commserate with you on the experience especially given the circumstances and the very special occassion. Congrats by the way. We have used Gohop since 2003 and have always found them very helpful and responsive, and I think they deserve credit for offering a good website that has a backup service staffed by people in Ireland who give a timely response as has always been my experience.

qath: Transforming ATOM 1.0 into HTML using XSLT

nospam@example.com (qath) — Wed, 12 Nov 2008 10:39:26 +0000

thanks!!

Nick Johnson: Getting O2 Ireland's "Mobile Broadband" working in OSX 10.5

nospam@example.com (Nick Johnson) — Tue, 28 Oct 2008 07:00:39 +0000

Afraid not, sorry.

Teresita: Getting O2 Ireland's "Mobile Broadband" working in OSX 10.5

nospam@example.com (Teresita) — Tue, 28 Oct 2008 02:10:09 +0000

A computer-literate person in the UK named Nick who talks about a "metric space" can only be my long lost friend Nick Ray. I hope.

legrand: Damn Cool Algorithms, Part 3: Anagram Trees

nospam@example.com (legrand) — Thu, 23 Oct 2008 18:16:00 +0100

Pour un algorithme de resolution d'anagrammes : tri des mots du dictionnaire dans l'ORDRE ALPHABETIQUE puis recherche textuelle .

paul: Cryptographically secure IOUs without a trusted third-party

nospam@example.com (paul) — Thu, 16 Oct 2008 19:10:45 +0100

OOPS. i meant to say that anonymity is NOT the most imortant feature ... leave anonymity for 2.0 or later...

paul: Cryptographically secure IOUs without a trusted third-party

nospam@example.com (paul) — Thu, 16 Oct 2008 19:09:27 +0100

surprised you aren't getting more comments on this one. Anonymity is the most important feature of the protocol...especially for the 1.0 ... i say we alpha this thing asap...

Adam: LOLCode.net - Now your LOLCats can use the CLR!

nospam@example.com (Adam) — Sun, 14 Sep 2008 17:11:03 +0100

Wen teh awesumness is dun, can we has "Wut j00 cz iz wut j00 getz" vershun?

Arjun Pakrashi: Damn Cool Algorithms, Part 3: Anagram Trees

nospam@example.com (Arjun Pakrashi) — Sat, 05 Jul 2008 19:04:10 +0100

It is unbelievable, i thought almost the same concept and similar tree structure, but never tried to implement because it takes a huge memory, but it is fast.

I rejected this idea, and thought about another structure, that i like to share. Please read carefully to fully understand.Please comment also and tell if it is good.
I subdivided a terr in several segments, in which i loaded a full dictionary
I took two types of self referential structures.
[1]alpha
[2]len

alpha has one character field, which contains an alphabet.the alphabet denotes the starting alphabet of the words which are under that node.
Simmilar nodes are linked together with a "next" field
Now again i have subdivided the words which have same starting alphabets, and same string length and those are grouped in another tree, under a perticular alpha node.
The alpha node has an array of pointers which points to len type data.There is a char array which denote which pointer array index contains a perticular length of string.
Example:
A main node contains only the words starting with 'a'
under that node one of the len pointer array points to a linear list which contains only 4 string length words starting with 'a' another pointer points to a list who points 6 string length words starting with 'a' etc.
now which pointer index points to which length (4 or 6) is stored inside the main node, in a char array (to reduce memory, 'sted of int, and is matched when searching)
Now the sublists of same string length are not just a linked list, they are linked chunks, or segments, the len nodes.
Each len node contains a 2-d char array each node is capable to store 50 words. When the 50 words are exceeded, a new simmilar len is allocated and then added, and new words are inserted in the new list.
This saves memory space which is taken by the pointer in 1-word per node type list, and also overcomes the problem of allocating large 2d arrays.
Like if there are 1200 words which starts with 'b' and is 6 char in length.then first the 'b' alpha node will be entered. and the 6-string-length node will be visited with the help of the array of pointers(will be created if it does not exist)
Then a len node will be allocated, and 50 words will be stored, after which another len type node will be allocated and more 50 words will be stored.
Like this we can save a lot memory consumed by pointers to indicate the next node.
And small sized arrays are available sparsely in the memory which we link.

Once this is loaded the searching is lightning fast.
like
'stop'
First it visits the node alpha, 's' Then it directly goes into the 4-string-length-word-list with the indexed pointer.
And then performs a linear search.

Then it visits the 't' alpha node and repets the same
And the 'o' and then 'p'
When a match is found, the base address of the string of the string in the node is stored in a pointer to pointer variable.
And at the end passed in the calling function.

I took care of some pitfalls. like in 'eye'
It prints 'eye' two times. As it gets the first 'eye' with the first 'e' and when it enters the 'e' node with the last 'e' it again finds 'eye'

I have kept a flag variable in the main alpha nodes.
Once a main alpha node is visited once the flag if set TRUE
When it is attempted to visit again and see the flag set to TRUE it will at once quit the search.

Like 'madam' (or mmaad whatever you say) it searches with 'm' and gets 'madam'. when visiting the 'm' alpha node it sets the flag variable to TRUE. simmilarly it scans with 'a' and 'd'.
When it comes to the next 'a' it quits the search at once as it finds the flag is set in the 'a' node. Similarly when the last 'm' comes it also finds the flag variable is set in the 'm' node and quits.
So the search cost is saved 33.33%
But for each new set of jumbled word, the flag variables has to be reset. as there is limited and fixed number or alpha nodes 'a' to 'z' (lower case only) so only 26 or such traversal is need with the "next" pointer.
the "down" pointer is used to indicate the len node subtrees (segmented lists)

The loading function is pretty complex, but it loads in lightning speed. And it loads instantly, (not almost, it is instant)And ofcource the search is fast.

But as the words are limited, and very few searches for a computer for nowadays, so i need to calculate the complexity.

The algorithm is under construction. I have thought to just load the len structure nodes with integers, which points to the particular file position, avoiding , loading of the words, which will save memory.

Or this tree can be stored in the file(in a easy decodable manner) and the required segment can be loaded only when it is needed.

I have written a program in C, it works really fine.
Still i have to do a lot of tuning, and reduce the comparisons and arithmetic operations.

Now how is that concept?

raptor_87: Read this: Little Brother by Cory Doctorow

nospam@example.com (raptor_87) — Mon, 02 Jun 2008 23:47:08 +0100

"sincerely hope that my (thus-far hypothetical) children someday read this book and scoff at how ridiculous it is."

Given that 1984 remains highly relevant 60 years after its publication (and despite it's focus on the USSR on Stalin), I wouldn't be that optimistic...

Anonymous: Damn Cool Algorithms, Part 1: BK-Trees

nospam@example.com () — Wed, 14 May 2008 18:17:25 +0100

C# implementation:

http://www.smartcorner.eu/post/2008/05/BK-Trees-implementation.aspx

Anonymous: Damn Cool Algorithms, Part 1: BK-Trees

nospam@example.com () — Wed, 14 May 2008 18:15:51 +0100

C# implementation:
http://www.smartcorner.eu/post/2008/05/BK-Trees-implementation.aspx

vytah: LOLCode.net - Now your LOLCats can use the CLR!

nospam@example.com (vytah) — Mon, 07 Apr 2008 22:35:49 +0100

"I still can't believe I'm looking at LOLCode and its x86 disassembly in Visual Studio."

Coz u r not. Iz x64 not x86. Im in ur commentz disproovin ur assumpshunz.

I haz x86 dissassembleh. Oh noez thay be steeling my dissassembleh!!

But howevah... LOLCode haz a flavr!
I can haz Windoze surses in LOLCode? Kthxbye

Anonymous: Damn Cool Algorithms, Part 1: BK-Trees

nospam@example.com () — Wed, 02 Apr 2008 06:24:55 +0100

Holy WTF.

Rodrigo: LOLCode.net - Now your LOLCats can use the CLR!

nospam@example.com (Rodrigo) — Wed, 19 Mar 2008 14:36:52 +0000

This programming age is lost...
Let's just sit and wait for new Einsteins to come.