Alternatives to using lists? (lists are slow) 
Author Message
 Alternatives to using lists? (lists are slow)

I'm writing an application in Tk that does a lot of
operations on an ordered list.
This means I often insert items into the list, delete items
at a specific position, or get an item ay a position.
My problem is that most of the list operations in Tcl are
not very efficient for this.
They make a copy of the list every time I change it.
This uses much space and time; I'm mostly worried about the time.

For example, on a Sun Sparc I find that inserting 1000 elements
to the front of a list takes 1.5 seconds with the following code:

  set wilbert ""
  time {for {set i 1000} {$i >=0} {incr i -1} {
    set wilbert [linsert $wilbert 0 $i]}
  }

<yes I know I can use lappend but I don't always want to add to the
 front of the list>

Does anyone have a better way to do this?
I'm thinking of using arrays but then finding the nth element might
take a long time.

Cheers,

Rob Scott
---
Dept of Computer Science, City University, London, UK



Tue, 06 May 1997 21:18:49 GMT  
 Alternatives to using lists? (lists are slow)

   I'm writing an application in Tk that does a lot of
   operations on an ordered list.
   This means I often insert items into the list, delete items
   at a specific position, or get an item ay a position.
   My problem is that most of the list operations in Tcl are
   not very efficient for this.
   They make a copy of the list every time I change it.
   This uses much space and time; I'm mostly worried about the time.

 [code deleted]

   Does anyone have a better way to do this?
   I'm thinking of using arrays but then finding the nth element might
   take a long time.

Whenever speed becomes important, I write the operations in C.  You
might want to create a binary tree or linked list or simple array
package.  Hmmm... this sounds fun.  I think I'll do this.  Has anybody
else done this already?

 set ar [c_array create -size 10 -int] ; # or -double, or default -string
   # size can be variable, default initial size could be 0

 c_array $ar insert 3 $i
 c_array $ar delete 2
 c_array $ar set 7 $j
 set k [c_array $ar get 5]

Or maybe something like:
 list2 create -double -bintree|-llist|-array|-avltree|-skiplist
Where a common set of operation were defined, and different options
were more efficient on different list types.  Naw, the sematics of
linked lists would be too different from the rest.

So, guys would there be much demand for a set of commands like this?
I'm offering to write them (foolish me...).

--
Ed Karrels

What's the height of optimism?  A trombonist with a beeper.



Thu, 08 May 1997 21:53:46 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. List of lists using Ada

2. Using setf on a List of Lists

3. using list commands on lists with special chars

4. Intersection of multiple lists/list of lists

5. DXOracle / PyADO - convert lists of tuples to list of lists

6. PEP 308: Erik's alternatives list

7. As400 Slow when doing joins in browse list

8. List Directory is very slow

9. Are list objects slower than stem variables?

10. (set! erg (append erg (list x))) is slow

11. Computer Science question (python list is slow with my cruddy algorithm )

12. Python 2.0b1 List comprehensions are slow

 

 
Powered by phpBB® Forum Software