3 ms·
def hash(str): len(str) O(1), baby!
by Sharlin 6mo ago
def hash(str):
len(str)
O(1), baby!
- zimpenfish 6mo agoO(1) only if you're working in a language with length-stored strings (like Pascal[0]), right? In something like C with its generic strings[1], it would surely have to be O(n) since you have to scan the entire string to calculate its length? (I have always been terrible at big-O, mind.) [0] There's probably more of them by now. [1] ie. not a specific length-stored string type.
- Sharlin 6mo agoYes. But that's a known misfeature of C and no other language does it like that. Plus I kind of meant arbitrary byte strings where you can have embedded zeroes and thus have to know the length.
- eru 6mo agoYou'd probably want 'return len(str)', if this is Python? In any case, for some applications this is indeed a great hash function. Programs like rmlint use it as part of their checks for duplicate files: if files have different lengths, they can't have the same content after all.
- andai 6mo agoRe: missing return keyword Actually, in Python, None is a valid key... (I'm so sorry. JavaScript has ruined me.)
- Sharlin 6mo agoYes, too much Rust :D Eliding the `return` becomes so intuitive after a while that you sort of forget that most other languages require it.
- eru 6mo agoHaskell and the Lisps also work like this.
- Sharlin 6mo agoYes, I know, it's the natural way to do it in functional programming. Honestly I doubt there are any FP languages that don't do it like that.
- eru 6mo agoI like that Rust, just like Lisp and Haskell et al also allow any block to return a value, not just functions. So if-then-else and loops etc can do that. It be nice if Python could do that. Perhaps I should hack up Python to allow that. Would be an interesting little project.
- nkrisc 6mo agoIf you use the identity function as your hashing function then is it O(0) because you are done before you start?
- Sharlin 6mo agoFor an arbitrarily long input, you still have to compress it to constant size somehow.