[erlang-questions] strip end off of string

Kenji Rikitake kenji.rikitake@REDACTED
Sun May 9 04:35:31 CEST 2010


In the message <77A1754B-3894-4641-A0B8-9D5E0787D946@REDACTED>
dated Fri, May 07, 2010 at 05:30:31PM +1200,
Richard O'Keefe <ok@REDACTED> writes:
> The bottom line is that lists can *only* be traversed from front
> to back, because there are *only* forward pointers.

Indeed.
Searching a list: O(n) (where n is the number of the elements)
Searching a red-black tree: O(log(n))

An example of slowness of a list operation: assignment and matching of
multiple IPv4 or IPv6 addresses to a network interface on FreeBSD. Even
though the address list for each interface is a TAILQ (doubly-linked
list), the search time is still O(n).  I've had a problem when n > 1000
or even n > 100.

> One of the things I keep telling people is "STRINGS ARE WRONG".
> For many purposes, a list of tokens is superior to a string.
> (For most other purposes, some kind of tree is even better.
> I've had spectacular speedups in C from using trees of
> fragments instead of vectors of characters.)

Preparing a fast-searchable data structures is critical.

Just my JPY 2 thought,
Kenji Rikitake


More information about the erlang-questions mailing list