Recent Changes - Search:

TreeVsDict

(:toc:)

Tree Vs Dict

This page compares Tree with Dict using a simple example.

A tree Example

Here is an example that loads a table of data into a tree and then performs some updates.

variable Users {
     tom  { Name "Tom Brown"  Sex M Age 19  Class {4 5} Rate {A 1 B 2}}
     mary { Name "Mary Brown" Sex F Age 16  Class {5}   Rate {A 2}  }
     sam  { Name "Sam Spade"  Sex M Age 19  Class {3 4} Rate {B 3}  }
 }

 set t [tree create]
 foreach {i d} $Users {
    $t insert 0 -label $i -data $d -tags $i
 }

 $t update   tom       Sex F   Name "Tomi Brown"   Age 20
 $t append   sam       Name " Jr"
 $t lappend  sam       Class 5
 $t update   tom       Rate(A) 2
 $t set      tom       Sax F
 $t set      sam       Rate(C) 0
 $t incr     mary      Age
 $t incr     0->mary   Age;   # Address via label instead of tag.

 # Display it.
 pack [treeview .t -tree $t] -fill both -expand y
 eval .t column insert end [$t keys all]

Note the use of -tags to eliminate prefixing with 0->.

A dict Example

Let's repeat the above example using the Tcl dict command (with the tree equivalent included in comments).

 variable Users {
     tom  { Name "Tom Brown"  Sex M Age 19  Class {4 5} Rate {A 1 B 2}}
     mary { Name "Mary Brown" Sex F Age 16  Class {5}   Rate {A 2}}
     sam  { Name "Sam Spade"  Sex M Age 19  Class {3 4} Rate {B 3}}
 }


 # $t update tom  Sex F  Name "Tomi Brown"  Age 20
 dict set Users tom Sex F
 dict set Users tom Name "Tomi Brown"
 dict set Users tom Age 20

 # $t incr mary Age
 dict set Users mary Age [expr {[dict get $Users mary Age]+1}]

 # $t append sam Name " Jr"
 dict set Users sam Name [concat [dict get $Users sam Name] " Jr"]

 # $t lappend sam Class 5
 dict set Users sam Class [concat [dict get $Users sam Class] 5]

 # $t update tom Rate(A) 2
 dict set Users tom Rate A 2

 # $t set tom Sax F
 dict set Users tom Sax F

 # $t set sam Rate(C) 0
 dict set Users sam Rate C 0

 foreach {i j} $Users { puts [list $i $j] }

Issues

The following discusses issues with dict in comparison with tree.

Incr Issues

Dicts incr returns the entire updated dict as its result. Thus to get the result of an incr requires 2 statements:

  # DICT
  dict incr Users tom Age 2
  set n [dict get Users tom Age]

  # TREE
  set n [$t incr 0->Users->tom Age 2]

Also dict incr is limited to integers which means incrementing a double requires use of expr. Trees incr sub-command, on the other hand, supports both integers and doubles.

  # DICT
  dict set Users tom Age [set n [expr {[dict get $Users tom Age]+9.1}]]

  # TREE
  set n [$Users incr tom Age 9.1]

Another problem with incr (and other dict commands) is they don't take sub-keys. So you can't do:

 #WRONG
 dict incr Users tom Age 2

Finally, it is too easy to do the wrong thing, eg:

  set V [dict create name Bob age 9]
  dict incr $V age
  # Oops, created new dict var called ${name Bob age 9}.

with Issues

Dict provides a with command to try simplifying things:

  dict with Users mary { incr Age }

Unfortunately dict with has a very serious side effect: keys can overwrite variables.

For example:

   variable Users {
      mary { Age 9 Users {}}
   }
   dict with Users mary { incr Age }
   # Oops, deleted the whole dict 

As the key "Users" occurs in a key, the dictionary gets unintentionally deleted!

with has no option to limit the creation of unneeded local variables.

(See tree with)

update Issues

Dict provides an alternative to with: the update command. This lets you choose your variable names. Unfortunately, dict update does not support lists of (nested) keys. Thus a nested update would use:

 set mary [dict get $Users mary]
 dict update mary Age mage {
    incr mage
 }
 dict set Users mary $mary

This seems more convoluted than necessary.

Modifying

Dict has no command to just update, without creation. This means that dict set silently creates new key/values if they don't already exist.

Tree on the other hand, has commands like modify and incr that only modify existing keys. These helps reduce the amount of user check code while making it easier to avoid programming errors (eg. from typos).

Fragility

Dict makes it easy to accidentally do the wrong thing, usually without warning. Above we showed that a with statement can liquidate the dict. But it is also easy to corrupt data within a dict.

Say for example we mean to do:

  dict set Users tom Sex F

but instead typo and omit an argument:

  # DICT:
  dict set Users Sex F; # Forgot 'tom'; created new dict 'Sex' key
  dict set Users tom F; # Forgot 'Sex'; overwrote the 'tom' key.

  # TREE:
  $t update Sex F;  # error: can't find tag or id "Sex".
  $t update tom F;  # error: odd # of key/values.

Finally, we accidently use a dict value instead of the variable:

  set V [dict create name Bob age 10]
  dict incr $V age 2
  # Oops: created new variable ${name Bob age 10}

Variable Traces

Dict doesn't support variable traces. Tree does, for nodes, keys and tags. This can be used for example to provide:

  • integrity constraints on updates.
  • read-only nodes (or fields).
  • disallow adding new fields.
  • sync writes to an sqlite database.
  • debugging!

This lets tree be used to compose new data structures. See Trees for an example.

Proc Calls

Although dict values can be passed in proc calls, you will still need to pass the variable name in order to do updates. This largely nullifies one of the original motivations for dict over array.

Complexity

Some dict commands operate on variables and some on values. Some take multiple keys, while others take one or none. This makes dict difficult to learn and use.

Dict is clearly powerful, but it's usage rules are quite complex, and it's use cases are at best un-intuitive.

Bulk Updates

Dict does not support group updates. But in tree commands like set and incri accept multi-node tags or node lists. This allows a single command to perform multiple changes.

Performance

Speed-wise, tree can actually be faster than Tcl variables, particularly when using tagged updates.

Memory

Memory-wise, dict (like lists) can be hampered by multiple copies of text representations for nested structures.

Dict + Array

If we change Users to be an array of dicts in the example above, dict fares better for many operations. But there are still limitations, eg:

 # $t incr    mary    Age 1.5
 dict set Users(mary) Age [expr {[dict get $Users(mary) Age]+1.5}]

 # $t incr  tom     Rate(A) 2
 dict set Users(sam) Rate B [expr {[dict get $Users(sam) Rate B]+2}]

Internal Storage Differences

Unlike dict, tree stores only the key value (but not the name) as an object. Key string names are stored in a hash table (see tree manpage).

Dict also (now) perserves order of insertion. In tree, this is setable (See Tree#keyhash).

dict Advantages

There are of course many advantages to dict, eg.

  • Works with standard Tcl 8.5+.
  • Works on standard Tcl lists.
  • More generalized to handle arbitrary nested data.
Edit - History - Print - Recent Changes - Search
Page last modified on August 28, 2010, at 09:08 AM