July 2007 - Posts
From all fundamental data structure, hashtable is my favorite one. I know about this data structure not from college, in fact I never heard about it when I was studying in my college, my first time encounter with she is when I involved in a project that using the Beta version of .Net Framework as the tools.
The Application
After that first encounter, hashtable always come in handy whenever I need it. It was helped me when I was:
1. Developing an excel like pivot table program and print it using GDI+. As far as I can remember, in this project, I use a hashtable to group and summarize the data also to remember the cell boundaries when printing the displayed data in the grid. Well, thanks to hash table this program run faster than MS Excel and can load bigger data (millions of data) than the MS Excel version. This project is a proof that hashtable is good to handle big data.
2. Programming in JavaScript. I think the core point of JavaScript is hashtable. Because every array in javascript is also a hashtable. Every object is a hashtable.
3. Developing IrwanLang. I use hashtable to store list of variable and list of function declared so I can check if a variable/function is already defined or not by just passing the variable/function name to my hashtable friend.
3. Developing many more projects. I can't recall them again because I use hashtables unconsciously.
For me, a hashtable is just a love at the first sight, because I can use string or any kind of object as the index, more appropriately as the key, I don't have to do any calculation, just use it instantly.
In the beginning, I am courius how hashtable do his magic. Well, here is the fundamental theory of why people invented hashtable.
The Theory
Imagine that you have to build a software, a phonebook software, just like the one that you have on your cell phone. When there is someone calling, the software will display the name of the caller. So, the phone number is using as the key. Just forget about the persistent mechanism for now, let say the data is stored in volatile memory only. So the phone must always on, if it turned off, well the data will be gone :)
The requirements above, stated implicitly that the name retrieval function must be fast, so an algorithm with O(1) performance is preferred.
So with which data structure will you solve the problem?
Let's say there is four people that you'll have to add. We'll use Jakarta's phone number format for simplicity.
P1: 5357288
P2: 8849872
P3: 4358999
P4: 5697777
Those numbers are sparse, they are far away from each other. If you use array, then your data structure will look like this:
Figure 1. Phonebook data structure using an array
Well, what do you think with that? Is it a good solution? I don't think so, because it will consume a lot of memory just to store those four values.
Hmm...can we optimize it? Are there any alternatives?
Imagination is More Important Than Knowledge
What about linked list? Yeah, linked list can store those four numbers efficiently but what about its retrieval performance? Linked list is not adequate in terms of retrieval performance. Why?. (You can submit your answers by using the comments box below).
We need another kind of mechanism to achieve O(1) retrieval. Array is fast for retrieval, insertion too. OK, let's optimize our array.
After imagining for a while, I come up with this.
How about if we have this mechanism:
Figure 2. Optimizing the array by using the index calculator
We need to transform those numbers into the appropriate index of the cell in our array.
Hmm...Lets say I have an array with 10 cells. How do I transform those numbers to a valid array index? Think hard....!!!
OK, I think I've found the solution. We can use modulo.
10 mod 3 = 1
50 mod 3 = 2
90 mod 3 = 0
Well, modulo always yield result that is small number. But how can we makesure that the result will not give us index out of bounds error. Lets solve it heuristically. Let use our array size as the divisor.
5357288 mod 10 = 8
8849872 mod 10 = 2
4358999 mod 10 = 9
5697777 mod 10 = 7
Hey!!! I think we are quite sure that with modulo we won't have index out of bounds errors.
Those process is called hashing and the function we use, that is modulo by the array size, is called hash function. But can you help me to make sure our hash function is correct? (You can answer it mathematically or heuristically, I love to see both).
The Implementation
OK, lets implement our algorithm. Well, its your job to implement it :). Share it to the world ya! :)
Is it possible for two or more numbers to produce the same array index? If it yes, how can we solve it? Hmm...one problem solved comes another problem. That's why I love software development :-P
Can you give reason why the retrieval performance is O(1)? How about with its insertion and deletion?
Well, if you have reached to this section. Congratulations!!! You have build your own hashtable.
Conclusion
This is just an introduction to hashtable. Next time I will write more advance topic about hashtable. But from now on, use it. You don't have to write your own hashtable class, unless you really..really need it, because .Net already provided you with one. Especially in JavaScript :)
What if I have a language that run in a simple machine that consists of an array of 300 byte cells initialized to zero, a moveable pointer to the array (initialized to point to the lefmost byte of the array), and two streams of bytes for input and output using ASCII as the character encoding.
The language itself has eight commands:
> : increment the pointer (to point to the next cell to the right)
< : decrement the pointer (to point to the next cell to the left)
+ : increment (increase by one) the byte at the pointer
- : decrement (decrease by one) the byte at the pointer
. : output the value of the byte at the pointer
, : accept one byte of input, storing its value in the byte at the pointer
[ : jump forward to the command after the corresponding ] if the byte at the pointer is zero
] : jump back to the command after the corresponding [ if the byte at the pointer is nonzero
So, can you answer the question?
The requirements of my current projects states of changing business rules at runtime, well, actually I must build a feature like SAP validation and substition feature. First, I implemented it using Windows Workflow Foundation and then doing a stress test to it, but too bad the test results is not adequate, it slow.
I have to find another solution for it.
I need a way to add scripting to the application and the scripting mechanism must have feature to read my outside object. There are many ways to do it in .Net one of it is using CodeDomProvider to compile the code and generate assembly dynamically.
Because the person that has to modify the code is not a programmer so the language chosen must be the easiest one, so I pick VB language as the language. You can find the source program below.
Program.cs
using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
VBCompiler compiler = new VBCompiler();
StringBuilder sb = new StringBuilder();
sb.AppendLine("Imports System");
sb.AppendLine("Imports System.Windows.Forms");
sb.AppendLine("Imports DomainModel");
sb.AppendLine("Public Class Test");
sb.AppendLine("Public Shared Sub Main()");
sb.AppendLine("DomainModel.Class1.Test()");
sb.AppendLine("End Sub");
sb.AppendLine("End Class");
System.Reflection.Assembly asm = compiler.Compile(sb.ToString());
ExecuteEntryPoint(asm, "Main");
Console.ReadLine();
}
private static int ExecuteEntryPoint(System.Reflection.Assembly assembly, string entryPoint)
{
try
{
if (assembly != null)
{
Module[] mods = assembly.GetModules(false);
Type[] types = mods[0].GetTypes();
foreach (Type type in types)
{
MethodInfo mi = type.GetMethod(entryPoint, BindingFlags.Public
| BindingFlags.Static);
if (mi != null)
mi.Invoke(null, null);
}
}
}
catch (Exception ex)
{
Console.WriteLine(ex.ToString());
}
}
VBCompiler.cs
using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.CodeDom;
using System.CodeDom.Compiler;
using Microsoft.VisualBasic;
namespace ConsoleApplication2
{
public class VBCompiler
{
private CodeDomProvider _codeProvider = new VBCodeProvider();
public CompilerErrorCollection Errors = new CompilerErrorCollection();
public Assembly Compile(string SourceCode)
{
ICodeCompiler compiler = _codeProvider.CreateCompiler();
CompilerParameters compilerParams = new CompilerParameters();
compilerParams.CompilerOptions = "/target:library /optimize"
compilerParams.GenerateExecutable = false;
compilerParams.GenerateInMemory = true;
compilerParams.IncludeDebugInformation = false;
compilerParams.ReferencedAssemblies.Add("mscorlib.dll");
compilerParams.ReferencedAssemblies.Add("System.dll");
compilerParams.ReferencedAssemblies.Add
("System.Windows.Forms.dll");
//Uncomment this code if you need to reference outside assembly.
//The assembly must reside in the same folder as the application folder
//compilerParams.ReferencedAssemblies.Add(@"DomainModel.dll");
CompilerResults results = compiler.CompileAssemblyFromSource
(compilerParams, SourceCode);
if (results.Errors.Count > 0)
{
foreach (CompilerError error in results.Errors)
Errors.Add(new CompilerError(error.FileName, error.Line,
error.Column, error.ErrorNumber, error.ErrorText));
return null;
}
Assembly generatedAssembly = results.CompiledAssembly;
return generatedAssembly;
}
}
}
>++++++++++++++[<+++++>-]<+++.>++++++++++[<++++>-]<+.+++++.>++++++++++[<-->-]<--.+++++++++++++.
Can you guess what is it?
I have two numbers:
a. 138091830918309183190839018390182309183901890381290389103810239012839083091809381902830912839012830912839018230918290381092389103
b. 138091830918309183190839018390182309183901890381290389103810239012839083091809381902830912839012830912839018230918290381092389103
What is the result of their multiplication?
Well, finding the solution using javascript is easy:
<html>
<body>
<script language="javascript">
var o = 138091830918309183190839018390182309183901890381290389103810239012839083091809381902830912839012830912839018230918290381092389103;
var c = 138091830918309183190839018390182309183901890381290389103810239012839083091809381902830912839012830912839018230918290381092389103;
alert(c*o);
</script>
</body>
</html>
Try that with your language! :P
The ILP problem can be solved in IrwanLang just using this code:
ILP[1,1000];
I think IrwanLang has beat Mathematica :).
This is for those of you who thinks JavaScript only lives on browsers also don't forget to read all the comments there.
This is one example of desktop application using JavaScript.
JavaScript is sweet isn't she?
Three head hunters have sent me a message of job opportunities on Singapore. One sent directly to my office email address the other two through Friendster private message.
They are all introducing as an employee of Asia Select Indonesia.
They are look suspicious to me. Why? Because, the first one, send an email without a subject and ask me to send my CV to her yahoo email. The other two are using a newly created Friendster account. One of them has a photo the other one is not. You can read below the messages sent to me on Friendster.
What do you think?
Their message:
From:
Jelyn
Date:
Friday, 6 July, 2007 4:58 PM
Subject:
IT Professionals
Message:
Hello ,
I am working on behalf of Asia Select Indonesia as an independent consultant. Right now I am looking out for IT Professionals for permanent IT positions for our client in Singapore.
Our client is a large investment bank providing large corporate,
government and institutional clients with solutions to their financing and
risk management needs. It has offices in more than 20 countries, employing
over 10,000 people and has the global reach and distribution power to meet
the needs of issuers and investors worldwide.
To support the continued growth of its business, our client is now looking
for at least 100 highly talented IT professionals from all over the region
to join its global software development and application maintenance
services and production infrastructure support centre in Singapore.
Information Technology Professionals (Singapore)
Requirements:
• University degree-holder.
• Has at least 3 years total work experience, mostly IT-related.
• Has 1 year relevant experience in any of the following areas:
• Project Management / QA Management
Project management of software development/maintenance engagements; QA
management and software engineering process improvement; testing management.
• Business Analysis
Define, analyse, communicate and validate requirements for changes to
business processes and information systems.
• Software Development and Maintenance
Application development and maintenance across various software
development platforms (e.g. Java, C++, C#/.NET, VB/VBA, PL/SQL, SAP,Oracle, Unix/Windows).
• Software Testing
Planning and manual or automated execution of various tests: functional,assembly, regression, stress, load, product testing, etc.
• Technical Architecture
Definition of strategic direction of technology platforms and development of strategies for technical infrastructure products & services.
• Production Support
Deployment and support of various technology platforms (hardware/OS,storage, email, network/voice, etc)
A competitive salary will be offered commensurate with proven track record
and experience. For confidentiality and priority attention on your application, we invite you to submit your resume with your recent photograph within 10 days from date of ad release to resume@asiaselect.co.id. Please keep the CV under 500kb.
Or please send it to my email add : jelyn_job@yahoo.com
You can also check our job postings, just go to google and type asia select indonesia.
Thank you.
Regards,
Jelyn
From:
Chuck
Date:
Thursday, 5 July, 2007 6:21 PM
Subject:
Job Opportunity in Singapore
Message:
Hi,
I am an Associate on behalf of the Technology Practice Group of Asia
Select Indonesia, the largest executive search firm in the country.
The team is currently handling the largest accounts in the industry,
both local and regional.
They currently have an urgent requirement for several topnotch IT
Professionals for one of our clients, a major financial institution.
It is one of the largest investment banks based in Singapore. This
post is for permanent employment and they offer good compensation
packages.
If you are interested, please send your resume asap for screening and we will contact you immediately should your qualification match our job description.
Thank you so much.
Here are the Job Descriptions
*C# Developers
At least 3 years experience in IT
2003 or earlier Graduate
Graduate of a Degree Course
Average English Communication Skills
* Summit Developers
Skill Set and Experience Needed (Proficient in at least 2)
API (2yrs)
UNIX (1 yr)
PERL (1 yr)
Shell Scripting (1 Yr)
Sybase (2 years)
C ++ ( 1 Yr)
Average English Communication Skills
* SQL Developer
Data Base Design Development and Optimization using MS SQL Server 2000
MSCSD Certified
Average English Communication Skills
* Java / J2EE developers
At least 3 years experience in IT
2003 or earlier Graduate
Graduate of a Degree Course
Average English Communication Skills
Warm Regards,
Chuck Ochava