3 ms·
The two most common operations on lists in typical functional programs are consing and deconsing, which are O(1). The most analogous operations on trellises are
by rntz 16y ago
The two most common operations on lists in typical functional programs are consing and deconsing, which are O(1). The most analogous operations on trellises are appending and removing the tail element, which are O(log n). So it seems inappropriate to propose trellises as general replacements for lists.
Indeed, I'm not sure in what situations this tradeoff of cons/decons- for lookup-speed is helpful. If I just need fast lookup, I'll use a mapping structure (hashtable, balanced binary tree, patricia trie, etc). If I need reasonable lookup speed and also standard sequence manipulations, finger trees or ropes seem like a better choice. They're more complex, but if performance is an issue, then it's probably worth it.
Also, a bug/design flaw: You can't store NILs in the terminal position:
> (trellis 1 2)
(1 (2))
> (trellis 1 2 nil)
(1 (2))
- daniel-cussen 16y agoAbout the bug, I talk about this at the end of trellis2.lisp. I didn't want to weird people out by adding a second sentinel to the list. I realize these aren't the best at any one thing, but in situations where you'd normally use lists (exploratory programming, say) you can swap to this for a performance boost.
- jules 16y agoThat's just broken, and will lead to horrible bugs. There is a reason why normal Lisp lists end with NIL instead of storing the last element in the last cdr.
- daniel-cussen 16y ago> That's just broken, and will lead to horrible bugs. You mean you think people will use this? Thanks :) Here's how I was thinking of fixing it: (setf nol 'nol) ; make nol evaluate to itself (defun my-null (x) ;redefine null (if (or (null x) (eql nol x)) t null)) Then, change add so that if it's adding a nil, it changes the sentinel at the end of the linked list part of the list to nol. So (trellis 1 2) returns (1 . ((2 . NIL) . NIL)) And (add nil (trellis 1 2)) returns (1 . ((2 . NIL) . NOL)) As soon as someone adds something other than a nil to a cdr of a cons in a tree, add changes nol back to nil.