SetOps, Create

Purpose: Definition and discussion of set functionality, especially the function to create a set from a number of elements.

Back to the Chart of proposed set functionality.


::setops::create element...

Arguments:

  • Any number of arguments, each a possible element in the set.

Result:

  • A list containing a new set.

Implementation:

Several variants are possible:

  1. Use an array to unify the given elements. Predicted performance: O(n), n the number of arguments to the procedure. Variant A.
  2. Sort the elements, then scan the resulting list to remove the duplicates. Predicted performance: O(n+nlogn), n as above. Variant B.
  3. Use the namespace of local variables as an implicit array. Predicted performance: O(n), n as above. Variant C.
  4. Same as (3), but with a different way of creating the variables. Variant D.

Shortcuts to use in the code:

  • No argument => Result is empty.
  • One argument => Result is a list containing that argument.

Timing:

Summary:

  • Variant D is much faster than all others.

Variant A.

 proc ::setops::create {args} {
    if {[llength $args] == 0} {
        return {}
    }
    if {[llength $args] == 1} {
        return $args
    }

    foreach e $args {
        set aa($e) .
    }

    array names aa
 }

Variant B.

 proc ::setops::create {args} {
    if {[llength $args] == 0} {
        return {}
    }
    if {[llength $args] == 1} {
        return $args
    }

    set args [lsort  $args]
    set last [lindex $args 0]
    set args [lrange $args 1 end]
    set res  $last

    foreach e $args {
        if {[string compare $e $last] != 0} {
            lappend res $e
            set last    $e
        }
    }

    return $res
 }

Variant C.

 proc ::setops::create {args} {
    if {[llength $args] == 0} {
        return {}
    }

    foreach e $args {
        set $e .
    }

    info locals
 }

Variant D

 proc ::setops::create {list} {
    if {[llength $list] == 0} {
        return {}
    }

    foreach $list {.} {break}
    unset list

    info locals
 }

-- AK