Hacker News Reader

Comment by joosters | Hacker News Reader

Are these claims of O(1) behavior accurate? They might not be O(n), where n is the length of the string, but they sound likely to be O(v), where v is the number of 'iovec chunks' that the string is using (which could get large, depending upon how you are building up your strings)

View on HN

If the list of chunks is represented as a deque, then concatenation and popping the first character can both be done in constant time.

Sure, but the page O(1) examples are:

1) Getting the data for a writev() call: Sure, it’s just returning a pointer to an array of iovecs, but someone is going to have to linearly scan that array.

2) Substituting or moving data anywhere in the string: As you say, you can do stuff with the start or end of a (v)string with O(1) but anywhere else will require a linear walk of the data chunks

If the claim is random access, then I agree that O(1) is imposssible. Rope would allow these tasks to be carried out in logarithmic time.

The tasks I chose were the first two API desiderata from http://www.and.org/vstr/design - which is the examples page you had in mind?

I was quoting from the ‘about’ section of the linked page. I’m not deliberately trying to pick on or criticise this data structure, it’s certainly a good way of manipulating some forms of text (I’ve used similar data structures for efficient HTTP processing/mangling). It’s just that there can be hidden costs and the O(1) claims appeared misleading.

If your strings are short that's basically O(1), which could be nice for some workloads - enums, json keys, etc.

That's not what O(1) means. If your strings are short, complexity doesn't matter either way.

That's still misleading.

If all my input is small then O(n^2) is basically O(1) as well.

if all your strings are of size < c, you can do any string operation on a single string in constant time.

There are certain (randomized) operations that you can’t…

Everything is O(1) when you have finite bounded input.

Reply on news.ycombinator.com