Programming


A nice article, I like his point of view of programming: Why I Program In Ruby (And Maybe Why You Shouldn’t)

Today, while playing with Java code and Eclipse, I falled to the following code:

package test;

/**
 * @author Hong Nam NGUYEN -- Created: 18 oct. 07 - 15:23:41
 */
public class Recursion
{
	private int x;
	private Recursion obj;
	
	public void init(int x)
	{
		this.x = x - 1;
		System.out.println("x = " + this.x);
		
		while (this.x > 7)
		{
			obj = new Recursion();
			obj.init(this.x);
		}
	}
	
	public static void main(String[] args)
	{
		Recursion obj = new Recursion();
		obj.init(10);
		System.out.println("Finish");
	}
}


I thought that the program will print out
x = 9
x = 8
x = 7
Finish
and stop!
But not, the real result is
x = 9
x = 8
x = 7
x = 7
x = 7
x = 7
….
and infinite loop ??

By reinspecting the code, I found that I have made an error. The variable x is an instance variable, so it belongs to each instance of the class Recursion, but not to the class at a whole. When a new instance is created (Recursion obj = new Recursion();) and the init method called, the following instruction is executed: this.x = x – 1;, but not the same x each time. In fact, the x of the very first instance has the value 9 (= 10 – 1), and then, it never change any more ! That’s why I get the infinite loop.
To correct this problem, there are (at least) two solutions:
– make x a static variable (static private int x;)
– or add code that changes x in the while loop

		while (this.x > 7)
		{
			obj = new Recursion();
			obj.init(this.x);
			this.x--;
		}


!!! The results of the two solutions are not the same, but the loop finite.

Recently, I worked on a problem which can be resumed as following:

I have a function that take an input, do some calcul and give me a output value. Now I have a output value and I want to know the input that produce the output.

Example: y = x*x + sqrt(x) – 7/x + (15/(2*x) – 4.5*x)*(sqrt(6*x) – x*sqrt(x/2));
If I have x, I can calculate y.
Now I have y and I want calculate x.

Of course, my function is a thousand of time more complex than in the example. The calculation formula is about a dozen of pages long.

I had tried to inverse the formula to obtain something like x = func(y) so I could calculate x when I know y, but I had failed because it was really difficult for me. Fortunately, a friend tell me about the dichotomy algorithm.

Dichotomy algorithm:
The idea is
I have y = func(x), I know y and want to calculate x, so
I take a value x, calculate func(x), compare the result with y,
    if result == y, so x is what I need,
    if not, I take another x, and recalculate func(x), recompare the result with y, …
repeat it until I find x.

Does it sound stupid ? Yes, if I don’t have a computer, but I have a power computer who does the calculation for me, so this is a wonderful idea.

However, I was skeptical at first, because I don’t know how many loops I have to repeat to obtain the result and the simplest way to implement this algorithm is to use recursion. But when I started to implement the algorithm, I recognize that with some simple optimizations and some heuristic knowledge, the number of loops (and so the performance) is really acceptable. (about 50 to 100 loops to get the result).

Here is the first code I used:

package test;

/**
 * @author Hong Nam NGUYEN -- Created: 15 oct. 07 - 16:26:27
 */
public class Dichotomie
{
	public static void main(String[] args)
	{
		double x = 2.55;
		double y = func(x);
		System.out.println("x = " + x);
		System.out.println("y = func(x) = " + y);

		System.out.println("=========================");

		double result = 5105.4;
		double variable = getX(result);
		System.out.println("result = " + result);
		System.out.println("variable = " + variable);
	}

	private static double func(double x)
	{
		return 2000000 * x + 7 - Math.sqrt(x);
	}

	public static double getX(double y)
	{
		double x = y * 2000000;

		double max = 0;
		double min = 0;

		double tmp = func(x);
		double diff = tmp - y;

		// TODO: On peut améliorer les méthodes getMin/Max
		if (diff > 0.0)
		{
			max = x;
			min = getMin(x / 2, y);
		}
		else if (diff < 0.0)
		{
			min = x;
			max = getMax(x * 2, y);
		}
		else
		{
			return x;
		}

		return dichotomie(min, max, y);
	}

	private static double dichotomie(double min, double max, double y)
	{
		double x = (min + max) / 2;
		double tmp = func(x);
		double diff = tmp - y;
		if (diff > 0)
		{
			return dichotomie(min, x, y);
		}
		else if (diff < 0)
		{
			return dichotomie(x, max, y);
		}
		else
		{
			return x;
		}
	}

	private static double getMax(double x, double y)
	{
		double tmp = func(x);
		double diff = tmp - y;
		if (diff > 0)
		{
			return x;
		}
		return getMax(x * 2, y);
	}

	private static double getMin(double x, double y)
	{
		double tmp = func(x);
		double diff = tmp - y;
		if (diff < 0)
		{
			return x;
		}
		return getMin(x / 2, y);
	}
}

This code works well, but the functions getMin and getMax could be done better, so here is the second version. The difference between the two versions of code is showed when I have made a really bad choice for the first try – heuristic plays its role in this choice (here is double x = y * 2000000;)

package test;

/**
 * @author Hong Nam NGUYEN -- Created: 15 oct. 07 - 16:26:27
 */
public class Dichotomie2
{
	static int	loopFunc		= 0;

	public static void main(String[] args)
	{
		double x = 2.55;
		double y = func(x);
		System.out.println("x = " + x);
		System.out.println("y = func(x) = " + y);

		System.out.println("=========================");

		double result = 5105.4;
		double variable = getX(result);
		System.out.println("result = " + result);
		System.out.println("variable = " + variable);
	}

	private static double func(double x)
	{
		System.out.println("func: " + (++loopFunc));
		return 2000000 * x + 7 - Math.sqrt(x);
	}

	public static double getX(double y)
	{
		double x = y * 2000000;

		double max = 0;
		double min = 0;
		double[] minmax = new double[2];

		double tmp = func(x);
		double diff = tmp - y;

		if (diff > 0.0)
		{
			max = x;
			minmax = getMin(x / 2, x, y);
		}
		else if (diff < 0.0)
		{
			min = x;
			minmax = getMax(x, x * 2, y);
		}
		else
		{
			return x;
		}
		min = minmax[0];
		max = minmax[1];

		return dichotomie(min, max, y);
	}

	private static double dichotomie(double min, double max, double y)
	{
		double x = (min + max) / 2;
		double tmp = func(x);
		double diff = tmp - y;
		if (diff > 0)
		{
			return dichotomie(min, x, y);
		}
		else if (diff < 0)
		{
			return dichotomie(x, max, y);
		}
		else
		{
			return x;
		}
	}

	private static double[] getMax(double min, double x, double y)
	{
		double tmp = func(x);
		double diff = tmp - y;
		if (diff > 0)
		{
			return new double[] {min, x};
		}
		return getMax(x, x * 2, y);
	}

	private static double[] getMin(double x, double max, double y)
	{
		double tmp = func(x);
		double diff = tmp - y;
		if (diff < 0)
		{
			return new double[] {x, max};
		}
		return getMin(x / 2, x, y);
	}
}

The strength of this algorithm is that I even don’t need to know the detail of func(x), I can treat it like a black-box.
enjoy;

I read this article this morning : Becoming a Better Programmer: A Conversation With Java Champion Heinz Kabutz.
It’s good to see others points of view. It helps open my mind.
Here’s some points that I find interesting:

When I asked Sun’s Brian Goetz the key to writing fast Java code, he said developers should write “dumb code,” by which he meant straightforward, clean code that follows the most obvious object-oriented principles in order to get the best compiler optimization. Compilers are big pattern-matching engines, written by humans who have schedules and time budgets, so they focus their efforts on the most common code patterns, in order to get the most leverage. Goetz argues that clever, hacked-up, bit-banging code will get poorer results.

JSC: What are some of the big mistakes that even experienced Java developers make?

Kabutz: Not unit testing.

To really learn, you need to choose the technology that you want to experiment in and take the time to study and read, which will require sacrificing your personal time. If you follow this advice, you’ll grow more valuable over time and won’t become a computer dinosaur.

If you are currently a Java programmer, you owe it to yourself to experiment in other technologies. Try out Squeak, JRuby, and other languages. Install and use a different IDE. Never stop learning. The moment you stop, you can lose the wave, and it will require a lot of paddling to catch up with it again.

This discussion is very interesting:
Why do people insist on doing EVERYTHING in Java?

Pour toutes les applications Web, interaction entre la BDD et l’interface utilisateur est un élément de base.
L’utilisateur consulte/modifie/supprime/crée les informations via son interface d’utilisation, ces actions sont prises en compte par l’application et il y a forcément la récupération/la modification/la suppression/la création des données dans la BDD de l’application.
Mais qu’est-ce qui se passe au milieu de la BDD et l’interface utilisateur, où se trouve souvent les codes (les objets Java) de la couche Métier ?
Examinons les choses dans l’ordre, commencer par la BDD
La BDD contient des données de l’application, avec les valeurs connues mais souvent n’ont pas de sens (pour comprendre ces valeurs, généralement, on a besoin au moins d’un dictionnaire de données – un type de méta-données). Ces données sont souvent stockées dans un ordre indéfini (mais on peut toujours récupérer les données dans certains ordres avec les requêtes SQL)
La couche métier stocke les données (récupérées de la BDD) souvent dans un ordre controllable (un List, par exemple). Les valeurs de données ici sont connues et ont un sens (le sens métier – que le développeur de la couche métier doit maitriser).

Une question se pose: l’ordre et les valeurs de données de la BDD et ceux de données de la couche métier sont-il les mêmes ?
La réponse est souvent NON. Parce que la logique relationnelle utilisée par les BDD pour stocker les données est différente de la logique objet utilisée par le langage de programmation orienté-objet pour traiter ces données. En plus, pour stocker les données, le DBA pense à minimiser les redondants, optimiser le temps de requête, … (on trouve souvent les ‘code’ dans la BDD, d’où la nécessité d’un dictionnaire de données). Mais pour traiter les données dans le sens métier, le développeur pense à encapsuler les objets par des classes, représenter la logique métier de manière le plus claire et le plus facile à traiter possible (on peut trouver les classes qui ‘ressemblent’ les objets dans la vie – contrat, dossier, formule, … et les méthodes qui font les actions métiers)
Résultat: il faut souvent une couche de mapping entre la BDD et la couche métier. On a entendu parlé de la couche DAO (Data Access Object) ou plus récent, il y a les frameworks de mapping R-O (Relationnel – Objet) comme par exemple Hibernate.
Bref, il faut toujours penser à une solution de mapping entre la BDD et la couche métier pour les application un peu compliqué et si l’on veut avoir maximum de souplesse dans la structure de l’application.

La couche l’interface utilisateur, quant à elle, représente les données sous forme de l’information, dans un ordre fixé, avec les valeurs affichés qui ne sont pas obligées d’être la même chose qu’on trouve dans la couche métier et la BDD. Il y a souvent aussi les valeurs cachées qui sont aussi différentes des valeurs affichées et les valeurs de la couche métier.
Là, on a la même problème, c’est-à-dire, il faut une couche de mapping entre la couche métier et l’interface utilisateur. Mais à ma connaissance, cette couche n’est pas prise en compte suffisamment sérieusement par les développeurs. Preuve, on trouve souvent les règles d’affichage de la page JSP dans le bean modèle, ou bien, à l’inverse, les valeurs métiers exposées dans les codes JSP ou pire encore, dans les codes JavaScript.
(… à suivre)

Yes, the most effective way is Invest in yourself

Next Page »