Browse thread
[Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
| Date: | -- (:) |
| From: | Oleg <oleg_inconnu@m...> |
| Subject: | Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive? |
On Wednesday 25 September 2002 11:33 am, Brian Hurt wrote: > I get that the cost of list concatenation is proportional to the length of > the first list. So (elem :: list) is O(1) no matter what the length of > list is. But (list :: elem) is O(n), with n being the length of the list. > > Why doesn't Ocaml keep a pointer to the last element of the list, as well > as the first element? This would make all list concatenation (in > situations where you don't have to duplicate a list) an O(1) operation. > At the cost of increasing the size of a list object. let a = [1; 2; 3; 4; 5; 6];; let b = 0 :: a;; the elements of "a" are _shared_. Now your suggestion regarding "efficient append" can not be used to append anything to one list, but not the other. HTH Oleg ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners