Today I stumbled over yet another minor trick which could speed up the execution of the Dijkstra algorithm. Let me shortly introduce this shortest path algorithm: If you need the path (and not only the shortest path tree) you will give the method an additional toNode parameter and compare this to distEntry.node to break the … Continue reading »
Running Shortest-Path Algorithms on the German Road Network within a 1.5GB JVM
Update: With changes introduced in January 2013 you only need 1GB – live demo! In one of my last blog posts I wrote about memory efficient ways of coding Java. My conclusion was not a bright one for Java: “This time the simplicity of C++ easily beats Java, because in Java you need to operate … Continue reading »
Failed Experiment: Memory Efficient Spatial Hashtable
The Background of my Idea The idea is to use a hash table for points (aka HashMap in Java) and try to implement neighbor searches. First of all you’ll need to understand what a spatial key is. Here you can read the details, but in short it is a binary Geohash where you avoid the memory … Continue reading »
How I found the Googloson and why it has negative Energy
I have finally found the Googloson with my self-made Small Googtron Collidor (SGC) – I even had the time to make a photo of it to show you that it is not a fake (see below). Everyone will say I’ve gimped that, but no, I didn’t. Really. I have developed a theoretical proof of the existence of … Continue reading »
Tricks to Speed up Neighbor Searches of Quadtrees. #geo #spatial #java
In Java land there are at least two quadtree implementations which are not yet optimal, so I though I’ll post some possibilities to tune them. Some of those possibilities are already implemented in my GraphHopper project. Quadtree What is a quadtree? Wikipedia says: “A quadtree is a tree data structure in which each internal node … Continue reading »
Spatial Keys – Memory Efficient Geohashes
When you are operating on geographical data you’ll use latitude and longitude to specify a location somewhere on earth. To look up some associated information or if you want to do neighborhood searches you could create R-trees, quad-trees or similar spatial data structures to make them efficient. Some people are using Geohashes instead because then … Continue reading »
Memory Efficient Java – Mission Impossible?
First, the normal usage in Java leads to massive memory waste as its pointed out in several articles or here in a nice IBM article. Some examples for the 32 bit JVM: Using 3 * 4 bytes for an object with no member variables. Using 4 * 4 bytes for an empty int[] array! Using … Continue reading »
Free Online Graph Theory Books and Resources
A link compilation of some Hackernews and Stackoverflow posts and a longish personal investigation. The DaMN book and its companion book Graph Theory with Applications, J.A. Bondy and U.S.R. Murty Graph Theory, Reinhard Diestel Graph Theory Tutorials Digraphs: Theory, Algorithms and Applications, 1st Edition Wikipedia – Graph Algorithms Algorithms and Complexity, Herbert S. Wilf Lecture … Continue reading »
Rage Against the Android – Nearly solved! #eclipse #netbeans
After ranting against Android in my previous post I have mainly solved now the untestable situation Android is producing. Thanks to Robolectric all my tests are finally fast and do not unpredictable hang or similar! The tests execute nearly as fast as in a normal Maven project – plus additional 2 seconds to bootstrap (dex?). Robolectric … Continue reading »
Rage Against the Android #eclipse
Developing Android applications on Linux with Eclipse sometimes can get really ugly. Sadly neither NetBeans which has a really nice Android plugin, but cannot execute a single test nor IDEA can rescue me or make me switching but probably they wouldn’t rescue me due to problems of Android development kit itself – I’m not sure. … Continue reading »
