Optimized lists

Luke Gorrie luke@REDACTED
Fri Mar 11 13:22:57 CET 2005

Zoltan Peter Toth <zoltan.peter.toth@REDACTED> writes:

> Currently there's no length information stored in the list elements, so
> length/1 is an O(n) operation.

You might want to look in jungerl/lib/ermacs/src/cord.erl. This is an
efficient string data structure built on a balanced tree (with ~2KB
binaries for leaves). Length check is O(1), space is about one byte
per character, and I've loaded 100MB log files with it.

Boehm's idea. He used them for efficient immutable strings in C.

Of course cords aren't IO-lists.

More information about the erlang-questions mailing list