circular traversing list

Hi Blaz,

That's likely to be as close to the most efficient (without thinking about it too much). tconc structures are quite efficient because they maintain a pointer to the last cell in the list, and so any time you need to get to the end of the list quickly, they are a good bet.

Only requirement in your case is that the list is non-nil, but apart from that the efficiency is going to be good - probably I'd have to understand precisely how it's going to be used to know if there's any more optimal way of doing this. One approach (if the list of values is fixed) would be to use listToVector to convert the original list to an array and then have an index which cycled through (incrementing and taking the modulus with the length):

defclass(CCFqueue ()
  (
    (vector @initarg list)
    (index @initform 0)
    (length)
  )
)

defmethod(initializeInstance @after ((obj CCFqueue) @rest _initArgs)
  obj->vector=listToVector(obj->vector)
  obj->length=length(obj->vector)
  t
)

defmethod(CCFnext ((obj CCFqueue))
  prog1(
    obj->vector[obj->index]
    obj->index=mod(obj->index+1 obj->length)
  )
)

You'd then use this:

queue=CCFqueue(?list '(1 2 3 4 5 6 7 8 9)
CCFnext(queue) => 1
CCFnext(queue) => 2
...
CCFnext(queue) => 9
CCFnext(queue) => 1

Without profiling it in the situation you specifically need it, I probably can't comment on whether this would be any better (it probably generates less garbage for garbage collection, but it does require the list to be fixed).

Regards,

Andrew.

Hi Blaz,

That's likely to be as close to the most efficient (without thinking about it too much). tconc structures are quite efficient because they maintain a pointer to the last cell in the list, and so any time you need to get to the end of the list quickly, they are a good bet.

Only requirement in your case is that the list is non-nil, but apart from that the efficiency is going to be good - probably I'd have to understand precisely how it's going to be used to know if there's any more optimal way of doing this. One approach (if the list of values is fixed) would be to use listToVector to convert the original list to an array and then have an index which cycled through (incrementing and taking the modulus with the length):

defclass(CCFqueue ()
  (
    (vector @initarg list)
    (index @initform 0)
    (length)
  )
)

defmethod(initializeInstance @after ((obj CCFqueue) @rest _initArgs)
  obj->vector=listToVector(obj->vector)
  obj->length=length(obj->vector)
  t
)

defmethod(CCFnext ((obj CCFqueue))
  prog1(
    obj->vector[obj->index]
    obj->index=mod(obj->index+1 obj->length)
  )
)

You'd then use this:

queue=CCFqueue(?list '(1 2 3 4 5 6 7 8 9)
CCFnext(queue) => 1
CCFnext(queue) => 2
...
CCFnext(queue) => 9
CCFnext(queue) => 1

Without profiling it in the situation you specifically need it, I probably can't comment on whether this would be any better (it probably generates less garbage for garbage collection, but it does require the list to be fixed).

Regards,

Andrew.

Hi Andrew, 

Thanks for super fast answer.

I need to implement search forward/backward mechanism in treeTable (GUI).

At the moment I create the list of treeTable elements (hiGetTreeItems, once) and then traverse through elements forward/backwards applying match check on every description (hiGetTreeItemDescription(eval(item))

Working with indexes would be possible as well (increasing/decreasing the index). What is more efficient?

Side notice: this is one example, but I was generally interested, how to efficiently implement push/pop mechanism, could use it elsewhere..

Thanks and best regards

Blaz

Hi Blaz,

This is one of those things that I would probably have more than one attempt at implementing, and experiment with the profiler to determine which was the fastest. For example, it sounds as if you might be able to use a hash table, but maybe you only ever want to find a certain range of tree table items - so maybe that wouldn't be appropriate.

Your push/pop isn't a traditional push/pop - which can easily be achieved with adding/removing elements from the beginning of a list. In your case you are not really pushing or popping - you're just cycling around the list. There's no doubly-linked list in SKILL (without creating one yourself) which sounds as if it might be one way. Creating a vector (array) on the fly might be an efficient way of doing this though - that really depends on whether the data keeps changing or is (reasonably) fixed - i.e. creating the vectors is a relatively infrequent operation.

Regards,

Andrew.