4 ms·
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
by joosters 7y ago
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)
- chalst 7y agoIf the list of chunks is represented as a deque, then concatenation and popping the first character can both be done in constant time.
- joosters 7y agoSure, 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
- chalst 7y agoIf 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 http://www.and.org/vstr/design - which is the examples page you had in mind?
- joosters 7y agoI 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.
- kevingadd 7y agoIf your strings are short that's basically O(1), which could be nice for some workloads - enums, json keys, etc.
- leetcrew 7y agoif all your strings are of size < c, you can do any string operation on a single string in constant time.
- saagarjha 7y agoThere are certain (randomized) operations that you can’t…
- jacwah 7y agoThat's not what O(1) means. If your strings are short, complexity doesn't matter either way.
- admax88q 7y agoThat's still misleading. If all my input is small then O(n^2) is basically O(1) as well.
- naniwaduni 7y agoEverything is O(1) when you have finite bounded input.