People‎ > ‎John Stavrakakis‎ > ‎John's blog‎ > ‎

Day of programming

posted 26 Oct 2011, 00:38 by John Stavrakakis   [ updated 26 Oct 2011, 01:17 ]
Today is more server side coding for algorithms straight from my thesis. There are some tweaks to the order of the algorithm for improved performance. I really want to get away with single data pass, but I need two steps: 
1) accumulate geometry in projection space.
2) iterated over projection space, presented in order.

This is a similar problem of finding the index of an item in a sorted list. 
< "forest", "sign", "deer", "road" >

A fast approach to finding the index for quick lookup time O(log n) requires sorting the list first. A lexicographical sort gives:
< "deer", "forest", "road", "sign" >

The index of the word "forest" is 1

To achieve this without sorting requires knowing all the preceding lower values. This is linear in search time, since a traversal through the entire list is needed to find out that there is one element less than "forest". Now to complicate the problem, what if it were a stream of data. It would be impossible to determine how many following items had value less than "forest" until they are seen. Halting problem.

For anyone curious about Object Oriented programming with C, here is a useful online book from Axel Schreiner:

EDIT: forgot to mention Xcode crashed only once today!
Comments