Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   I'd say it's the exact opposite: When you start having more than 2^16
> > nodes, that's when you need to star worrying about the amount of space the
> > data structure is taking. With less than 2^16 nodes the size of an individual
> > node is rather irrelevant.

> My thought was that if you have that much data, you're probably running on a 
> machine where the memory limits aren't very tight (i.e., a desktop system, 
> say).

  Well, I may be biased because of my programming history background, but
usually an app crunching tons of data requires space-efficient data containers
(so that it can crunch as much data as possible with a given amount of RAM).
You usually want your app to be able to handle as much data as possible.

  Also my recent programming history can also have some effect on how I view
these things, namely programming for handheld systems. For example, games
which require a full (eg. English) dictionary are an extremely typical case
where you need a very fast data container which should take as little space
as possible (because a handheld system won't have a multi-GHz CPU nor
gigabytes of RAM). A typical English dictionary is excruciatingly annoying
in this regard because they usually go just a bit over the magical limit
of 65536 words, especially if the game requires plurals and other inflected
forms. (And even if the dictionary did have under 65536 words, the total
amount of character data would still be well beyond that limit, and since
words are of differing lengths you really need byte-pointers/indices.)

>  Of course, the killer is the ratio of the number of nodes to the 
> amount of memory, so sure, when you start getting up in the 2^25 number of 
> nodes range the size of the nodes is going to be prohibitive on a 32-bit 
> machine again.

  Hmm, I'm not so sure. 2^25 nodes, each node taking eg. 16 bytes, would
require "only" 512 MB of RAM, which is well below the capacity of any
modern desktop system.

-- 
                                                          - Warp

Post a reply to this message