Long ago, when I was a naive schoolboy, I suddenly felt curious. What is a magical way that data takes up less space in an archive? I started surfing the Internet in order to find an answer. So I found many interesting articles with fairly detailed information on this topic. But all of them did not seem to me easy, the code listings were very difficult to understand.
Let us consider a situation when you need to handle collisions between some objects. What do you do in this case? Probably, the easiest solution would be to check interaction between these objects. This is the right decision, and everything will be fine until you get a lot of objects. As soon as their number gets up to a few thousand, you will notice that everything works much slower. What if you get thousands of the particles? Then everything stops. Here things get much more interesting. What tricks and optimizations would you use to solve this problem?
Let us consider 2D case to make it simple, the particles are round, and the radius of the particles is the same for all of them.
Table of contents
1. Overview of algorithms
1.1. Exhaustive search
1.2. Sweep & Prune
1.3. Regular grid
2. Some optimizations
2.1. Sweep & Prune
2.2. Regular grid
3. Speed comparison
4. Application (software and source code)
Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python, OpenJDK 7 and Android JDK 1.5. Here is a table in order to understand that better from Wikipedia.
There are only 7 of adequate algorithms among a huge selection in the table (with complexity O(n logn)), but only two of them have stability and complexity of O(n) at best. One of the two is long well known to everyone "Tree sort that builds a binary search tree", and the second one is Timsort.
This article discusses the algorithms’ sieves for finding prime numbers. We consider in detail the classic Sieve of Eratosthenes, particularly its implementation in the popular programming languages, parallelization and optimization, and then we will describe a modern and fast Sieve of Atkin.
Here is a picture of the Sieve of Eratosthenes sculpture that was created by abstract expressionist Mark Di Suvero, constructed on the campus at Stanford University.
Basilio Noris PhD from the Federal Polytechnic School of Lausanne created a remarkable program that is perfect for the demo of some tasks that solve the machine learning algorithms (classification, clustering, and regression using the various methods). In one program are captured the libraries, algorithms and code patches that could be found. Unlike Matlab, here GUI runs fast in the interactive mode, thus it comes out very well.
MLDemos 0.3.2 for Windows (minimum requirements: XP SP3)
MLDemos 0.3.2 for Mac (minimum requirements: Snow Leopard)
MLDemos 0.1.3 for Linux 32bit (deb) (build for: Ubuntu 10.04)