[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

Some observations about "data structure complexity"

joshipura

7/27/2015 2:54:00 PM

[I self-taught Computer Science curriculum - so I may be terribly off in my observations.]

All,
I have three observations (2.1, 2.2 and 2.3) to solicit your comments for my learning. For the below discussion, "data structure" means "data structures as described in normal undergraduate text books".

I have read a lot of discussions on the web loosely calling one data structure (say, a list) being less complex than the other (say, a tree). That kind of confuses me.

I know a bit about complexity of a particular algorithm regarding a data structure but what is the complexity of a data structure? It is easy to discard the notion of "data structure A being less complex than data structure B" as loose talk - but intuitively we "feel" that a graph is considerably more complex than anything linear. What is the measure of inherent "complexity" of a data structure?

Now assume that the text book order of introducing data structures (lists/arrays, stack, queue, tree, graph) indicates complexity somehow. In linear structures the relation between two connected links is one-to-one, in trees it is one-to-many and in graphs it is many-to-many. That way, a graph should be the most complex data structure because there isn't a more complex relation than many-to-many.

However, when I tried to imagine chemicals as nodes of a graph, and an arch as a chemical reaction, an arch needing more than two sources will terminate on one chemical.
For example, a branch originating from H2 and O2 will end up in H2O.
In case of Carbon burning, it may get even worse because edges starting from C and O2 may end up at two places - CO and CO2.

Question 1: What is this data structure with multi-source, multi-destination arch called in the literature? It appears to be "more complex" than a graph.

I could imagine more complex a data structure - the one with catalysts. A multi-source, multi-destination arch would require something that isn't even a source or a destination - a catalyst!

Question 2: Then, such "triangular arch" graph would be even "more complex" than Question 1. What is such data structure called in the literature?

Another interesting point of view can be gained if we try to see when we try to store the data of data structures as relations. List and Tree can be stored with one key reference (of previous node) as a field. (An irreducible) Graph will need another edge table indicating nodes with a composite keys as the primary key.

In that sense, Question 1 and 2 will require multiple-composite-primary-keys of nodes to indicate an edge in that edge table [for fixed number of chemicals reacting with each other, of course. Or we need third table of reaction participants.]

Question 3. Is this what we mean when we say "data structure A is more complex than data structure B"?
3 Answers

Dmitry A. Kazakov

7/27/2015 5:24:00 PM

0

On Mon, 27 Jul 2015 07:54:17 -0700 (PDT), joshipura@gmail.com wrote:

[...]
> Question 3. Is this what we mean when we say "data structure A is more
> complex than data structure B"?

Depends on who is we.

In my view the complexity of a data structure depends on:

1. The number of independent states it may have.

2. Density of valid states in relation to all possible memory patterns,
i.e. the type invariant. If the invariant is always true the structure is
less complex. For example, the invariant of an 2-complement integer is
true, the invariant of a prime number is computationally far more complex.
Thus integers are simpler than prime numbers.

3. Connectivity of memory representation (e.g. contiguous or not) Thus the
computational complexity of maintaining the representation of.

4. Computational complexity of the operations. Data structure is a
meaningless construct. Programmers deal with data types. Type values are
data structures. Operations are defined on these values, e.g. the operation
"insert".

5. From the client POV, the computational complexity of the preconditions
of the operations. E.g. when division requires non-zero divisor, such
numbers are more complex than numbers with any divisor and zero-divide
exception as an outcome. Of course if the postcondition includes
propagation of exceptions it is more complex than when it does not.

6. Complexity of non-computational/non-functional constraints imposed. I.e.
concurrency aspects. A lock-free, a mutually exclusive data structure is
far more complex than a structure without such constraints. Other examples
of constraints: real-time constraints, bounded upper execution time of
operations. Memory constraints, bounded memory footprint, bounded stack
usage of the operations etc.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-...

Ben Bacarisse

7/27/2015 11:53:00 PM

0

joshipura@gmail.com writes:
<snip>
> Question 3. Is this what we mean when we say "data structure A is more
> complex than data structure B"?

If there is a subset of instances of A that are isomorphic to all the
instances of B, then it is reasonable to say that A is more complex than
B. This is not a full answer (there many be other factors that people
consider important to "complexity") but it does answer your initial
question about why trees are considered more complex that lists: a
subset of trees is isomorphic to the set of lists.

--
Ben.

Dmitry A. Kazakov

7/28/2015 7:54:00 AM

0

On Tue, 28 Jul 2015 00:53:00 +0100, Ben Bacarisse wrote:

> joshipura@gmail.com writes:
> <snip>
>> Question 3. Is this what we mean when we say "data structure A is more
>> complex than data structure B"?
>
> If there is a subset of instances of A that are isomorphic to all the
> instances of B, then it is reasonable to say that A is more complex than
> B. This is not a full answer (there many be other factors that people
> consider important to "complexity") but it does answer your initial
> question about why trees are considered more complex that lists: a
> subset of trees is isomorphic to the set of lists.

Yes, but mapping values of A onto B need to constrained. Computers are
finite, all instances are countable, and we can map anything onto
everything. Not all mappings are relevant, but only ones conformant with
the operations defined on the instances. This is why "data structure" as
such is a meaningless concept.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-...