This is G o o g l e's cache of http://sixteenvolts.blogspot.com/2006/01/time-to-sow-time-to-reap.html as retrieved on 13 Sep 2006 02:45:35 GMT.
G o o g l e's cache is the snapshot that we took of the page as we crawled the web.
The page may have changed since that time. Click here for the current page without highlighting.
This cached page may reference images which are no longer available. Click here for the cached text only.
To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:-DiFkhcYSO8J:sixteenvolts.blogspot.com/2006/01/time-to-sow-time-to-reap.html+site:sixteenvolts.blogspot.com&hl=en&ct=clnk&cd=434


Google is neither affiliated with the authors of this page nor responsible for its content.

Send As SMS

« Home | A few linguistic thoughts for the Saturday evening » | Rage against the machine » | Unions and intersections » | So what if polygamy? » | I can walk to Turkmenistan » | Take me to your leader » | Full of black goodness » | But it doesn't always correlate » | Silver screen magic » | A few ponderings of a religious nature »

Time to sow, time to reap

In computer science, the term "data structure" refers to any technique of organizing data in a way that allows certain operations on that data to be faster compared to what they would be if the data was just kept in a single unorganized pile. For a real-world example, the names in a phone book are kept in alphabetical order instead of just any order to facilitate fast lookup based on the name. Since sorting the names needs to be done only once, the total time saved is greater compared to not sorting the names and spending more time in each lookup.

Sorted arrays and lists are perhaps the simplest nontrivial data structures, but there are many different data structures available, consisting of a more complex network of objects and the relationships between them than just a single linear array of elements. These structures differ in what operations the efficiently support. Some other operations may be inefficient (for example, looking up a number in an ordinary phone book instead of a name), but the idea is to always use a data structure that makes those operations efficient that you actually need in your program, and the operations that you don't need at all or need only rarely don't have to be fast.

Of course, there is always the cost of organizing and maintaining the structure with each operation, which you don't need to do if you don't care how your data is organized. But it usually pays off to do this extra work to save (a lot) more time elsewhere in the future. This is especially true if the organization work needs to be done just once in the beginning, as is the case with a simple printed phone book.

Dynamic sets are data structures that represent a collection of elements. As the program runs, it can add more elements to the set, remove existing elements and check whether the set currently contains a given element. Some well-known dynamic set data structures are binary trees and hash tables. There are countless variants available tuned for specific purposes, but in a very interesting fashion they all seem to have one thing in common: at least for all dynamic set data structures that I can think of right now, inserting a new element to the structure is both computationally cheaper and conceptually less complex (or at least, not more expensive or more complex) than removing an existing element from the structure, when all the reorganization work to make a structure to be legal after each operation is taken into consideration.

This asymmetry is quite astonishing when I think about it, and I kinda suspect that there is some interesting and fundamental information-theoretic aspect of the very reality itself behind it. The physical universe of course constantly erases massive quantities of information (which, as a side note, is one reason why your computer will generate heat as it computes stuff, unless we could achieve sufficiently reversible computation that doesn't erase information), but then again, the physical reality is not a data structure whose purpose is to allow efficient access to and operations on the data that it contains.

Comments

Links to this post

Create a Link

Contact

ilkka.kokkarinen@gmail.com

Buttons

Site Meter
Subscribe to this blog's feed
[What is this?]