Where do I find the complexity of an operation?

Question

In this answer it is mentioned that for a string doing s.chars().count() to get the number of characters is an O(n) operation. For simple ASCII strings getting the number of bytes using s.len() works as well. When using a check to make sure that all those bytes are actually ASCII this is probably safe.

I want to know what the complexity of that operation is. It might still have to find the end of the string like in C and be O(n).

I tried to look it up and found the documentation of the std::string::String, which applies for appropriate s. However it doesn't state its complexity. Looking at the source it just does this self.vec.len(). So we go to look at the vector docs and find that this simply returns a stored length self.len meaning that this is indeed an O(1) operation.

That was a lot of work though. Now what about the case that s is a std::str? I tried to do the same but got stuck in this mess.

Is there a more easily accessible ressource for operation complexities in Rust?

Something like this list for Python would be great.

Note that checking that all characters are ascii is O(n) just like `s.chars().count()`, so unless you need the check for another reason, you might as well use `s.chars().count()`. — Jmb, Dec 15 '17 at 13:14
Complexities should be documented for all datatypes. Where they are missing, feel free to send a PR or file an issue. I don't think a centralized list with all complexities is the right place for this; this only makes sense for collections, where you need an overview to decide which collection to use. — Sven Marnach, Dec 15 '17 at 15:56

score 7 · Accepted Answer · answered Dec 15 '17 at 12:10

7

Other than the performance section on collections I don't think there currently is a common list like the Python one you referenced.

As for str, determining its length is an O(1) operation, because a string slice consists of a pointer and length:

// We can re-build a str out of ptr and len. This is all unsafe because
// we are responsible for making sure the two components are valid:
let s = unsafe {
    // First, we build a &[u8]...
    let slice = slice::from_raw_parts(ptr, len);

    // ... and then convert that slice into a string slice
    str::from_utf8(slice)
};

answered Dec 15 '17 at 12:10

ljedrz

20,316
4
69
97

1

To be precise, `str::len` determines the length in code units (just like `String::len`). To get the length in code points, you need to call `str::chars::count` which is O(1) (same as for a `String`). – Jmb Dec 15 '17 at 13:22
3

@Jmb I know you mean O(n), but just figured I'd mention it in case somebody else came along and was confused :) – trent Dec 15 '17 at 14:53

score 3 · Answer 2 · answered Dec 15 '17 at 13:26

String and str offer the same complexity guarantees for all actions. In fact, most operations on String (including chars()) are actually operations on str that use the implicit conversion from String to str (that conversion is free since they share the same low-level representation).

Where do I find the complexity of an operation?

2 Answers2