12 ms·

Big O, Little N

81 points by adamzerner 6y ago

pintxo 6y ago
"[...] premature optimization is the root of all evil [...]" D. Knuth
- deleted 6y ago
  [deleted]
jp3141 6y ago
Javas implementation of HashMap uses a tree on hash collision. [0] https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l156 https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/...
- quickthrower2 6y ago
  If the bin is big enough to warrant it, according to your link. Thanks for the link! I imagine they do this as the user space can define hash algorithms and someone is gonna just return zero every now and then out of laziness :-)
- deleted 6y ago
  [deleted]
- virgilp 6y ago
  You also need a comparable() key presumably - which you often have, but not always (a comparable() key is not strictly required by a hashtable).
CGamesPlay 6y ago
In addition to this, for many applications, programmer time is more valuable than the asymptotic savings of a faster algorithm. This isn't as "pure" of a discussion since it now starts to involve money, but when viewing programs through the lens of creating business value, it's important to consider.
- higerordermap 6y ago
  Even if this is true, don't say this loud. Because people have already taken it as license to write shitty code that is O(n²) where it can be O(n), or allocate in a frequently executed loop.
  - justincredible 6y ago
    premature simplification is the root of all evil?
tangus 6y ago
A heads up: if you use a dark theme in your phone, this webpage is recognizes it and changes its background to dark grey. This makes the grey words in the diagrams illegible.
- ziml77 6y ago
  Desktop too. At least on macOS, in both Firefox and Chrome.
3np 6y ago
> const isVowel = (char) => ["a", "e", "i", "o", "u"].includes(char); > [... ] it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char. This depends on how you define your `n`. Usually this would be defined as the input size. Unless you would like to be able to run this on arbitrary definitions of what a "vowel" is (and in this case, it's indeed both small and static), the only useful interpretation would be to consider this function O(1), regardless of iteration over this 5-element list. If the list of vowels would considered a parameter, it would indeed be O(n) or O(m).
- willvarfar 6y ago
  You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)! :)
  - virgilp 6y ago
    Depends. Are we talking about people who know what O(n) means? Parent comment explained it very well - "n" is typically your input size (or if it's not, you need to clearly define what it is). "n" is unlikely to ever be "number of vowels in the English alphabet" because that's a constant, that doesn't change at all when input changes. O(n) is meaningless if we don't say anything about "n", so no, 'iterating an array" is not necessarily O(n) - it's only so when the array has a size proportional with the input. Or, to put it differently: yes "array.includes" is not O(1) in common discussions, because typically we discuss the complexity of method `includes` as relative to the size of the array; but a program/algorithm that contains an invocation of `array.includes` does not automatically have complexity that is linear or worse - it can very well be logarithmic or constant. For example, looking up a value in a hashtable where the keys are strings is considered to be constant time, even though you need to iterate over the key in order to obtain its hashcode (i.e. the algorithm that takes a string and produces a hashcode is O(n) where n is the length of the string).
    - herbstein 6y ago
      This only makes sense if you consider a `contains` method to only take the arguments passed inside of the parenthesis. But in actuality there is an implicit `this` argument too. Armed with this knowledge it becomes trivial to see how the total input to the function is `N + 1` values. `N` being the length of the function, and the `1` representing the thing we're searching for. Since constant values in complexity theory are handily ignored we get an input of size `N`. And as to your second point, the choice of what is and isn't a constant-time operation is generally a practical concession. There's no reason to say "you can't say anything about any algorithm because it's an implementation detail" here. The conversation is specifically about element presence in an unsorted array. A very simple, easily understood, and unambiguous algorithm. Bringing up the runtime of the operation in a hashtable or in tree-structures is entirely nonsensical and just destroys any conversation there is to be had.
F-0X 6y ago
> And it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char. No, it's actually O(1). n refers to the _input_, which is always a single character. The iteration over an array (fixed at 5 elements) means a maximum of 5 comparisons. O(isVowel) = 5.
speakeron 6y ago
It's always worth remembering that O(n) describes the asymptotic limit where n is presumed to be very large (in fact, approaching infinity).
- MaxBarraclough 6y ago
  Related to this, there exist algorithms with impressive complexity-theoretic properties, but which are never useful in practice. They even have a cute name: https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
Tainnor 6y ago
No, the author didn't really understand how hash tables* work and what the big-O notation really means. If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance. But hash tables are probabilistic data structures, so we don't actually look at worst-case performance, but at the average case. It's important that for this analysis we need to make some assumptions about the hash function itself (e.g. what its collision probability is). Out of that, we can compute that hash table operations are on average constant. * There are actually multiple ways to deal with collisions in hash table, let's focus on open hashing/seperate chaining for now.
- jmalicki 6y ago
  You also misunderstand hash tables.. they are not merely expected constant time, they are amortized constant time.
  - Tainnor 6y ago
    as far as I understand, the amortization factor comes in because you occasionally might have to grow your table of buckets, in the same way that arbitrary-size array lookup is not actually constant, but only amortised constant. if we sidestep that issue for one moment, it's still true that you have worst case O(n) and average O(1), though.
    - josephg 6y ago
      > arbitrary-size array lookup is not actually constant, but only amortised constant. Array lookup operations are constant time. You don't need to grow an array while reading from it. Append operations in a vector are O(n) but amortized constant time. Hash tables work the same way - they have amortized constant time when inserting, but they should have constant time for reads when using a good hash function. That said, technically we still classify hash table reads and writes as O(n). Big-O notation defines an upper bound on time, not the average time. And the upper bound on hash table reads and writes is O(n) if you have a terrible hash function (or carefully crafted inputs). This is not useful knowledge though, because hash tables are usually fast in practice. If you're trying to figure out how something performs in practice (like the "isVowel" function in the blog post), the tool to reach for is a benchmark. Guess how a benchmark result will come out before you see the result, and over time you'll build an intuition for these things.
quickthrower2 6y ago
In languages with a BYO hash function you might write a crap one, so having the tree on collision might still be handy.
woadwarrior01 6y ago
I've seen binary trees used for collision resolution in hash buckets in quite a few production systems. A pathological case of O(log n) is vastly better than a pathological case of O(n), if you care about it. It might be instructive for programmers using higher level languages to learn about the cache hierarchy and the hardware prefetcher in modern systems. For those interested, I'd recommend reading Ulrich Drepper's classic: What Every Programmer Should Know About Memory[1]. [1]: https://www.akkadia.org/drepper/cpumemory.pdf https://www.akkadia.org/drepper/cpumemory.pdf
willvarfar 6y ago
Nice article. Easy to argue about the details, because the author is describing what they've discovered or bumped into, not what they've studied. But I still think its a nice intro that may make other programmers think. The article could explore open-addressing in hash-tables, and it could explore a switch statement for the vowels. Tangent: I've often wondered where the double-hashing tables are, and whether they could use the high and low bits of a single hash rather than the low bits of two hashes...?
siraben 6y ago
It's not uncommon in scientific computing for the algorithm used to be automatically adjusted based on the input. An example of this is if you want to multiply very large integers. Karatsuba is first used, then Toom-Cook, then Schönhage–Strassen. Karatsuba: θ(n^1.58) Toom-Cook: θ(n^1.46) Schönhage–Strassen: O(n log(n) log(log(n))) Benchmarking is really the only thing that can reveal this kind of thing, otherwise you'll end up with a theoretically fast but practically slow algorithm.
- BeetleB 6y ago
  Don't you need insanely high numbers before Karatsuba outperforms the simple O(n^2) algorithm? From Wikipedia: > As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits
  - moonchild 6y ago
    4096-bit keys are standard for RSA, for example.
- senderista 6y ago
  Another example is quicksort falling back to insertion sort as a recursive base case for some n=k (instead of recursing all the way to one element).
YesThatTom2 6y ago
This is why benchmarking is so important. It is the reality check you need. Also... it took me decades to appreciate that clear code is better than fast code. If it’s slow, I can rewrite the inner loop. I’d rather have clear code with one thing optimized out of clarity that an entire system of clever code that I can’t debug.
YesThatTom2 6y ago
Here’s another article about O(n): 10 optimizations on linear search: https://queue.acm.org/detail.cfm?id=2984631 https://queue.acm.org/detail.cfm?id=2984631
- bear8642 6y ago
  Thanks for this - very interesting small article
pritovido 6y ago
There is something that must be said about anything that increases complexity in order to get efficiency: 1. It increases developer time. 2. It increases the number of bugs of the system as it increases enormously the different possibilities. We have systems that actually meta program with Lisp our hash tables with different degrees of complexities. It is already programmed, the designs already debug. And even then for most of our hash tables we just use the minimum level of complexity, that is having a memory that is 10 to 20 times bigger than the elements on the hash and just have one or two collisions for the entire set. That way the code is way easier to understand, and the memory differences are just negligible(compared to the total amount of memory the program needs), if sets are well designed.
gfxgirl 6y ago
https://jsben.ch/WCjjG https://jsben.ch/WCjjG Well, seems like it does matter. Using an array is 50% slower than using an object and that's slower than using a Set in Chrome. Even worse in Safari. In Firefox array wins but you need to use a static array. I don't know all the rules of JS. Semantically declaring an array in the function itself creates a new array on every invocation. Of course the JS engine should be able to figure out it doesn't need to create a new array every call but apparently Firefox's JS engine doesn't do that. Note: I'm making the assumption we're talking about JavaScript since the code looked like JavaScript to me. I get that in another language the results might be vastly different.
- thomasahle 6y ago
  > Well, seems like it does matter. Using an array is 50% slower than using an object and that's slower than using a Set in Chrome. A 50% difference doesn't mean it matter. Unless this runs in some inner loop, just use the simplest solution.
  - gfxgirl 6y ago
    I agree that if the fast solution is 10x the code then maybe choose another solution. In this case all 6 solutions are basically the same amount of code. There's absolutely no reason to choose the slowest solution. 50% can easily be the difference between some VSCode extension making it sluggish vs not. Further, in my experience slow solutions will eventually come back to bite you. One I saw recenty. see if 2 arrays contain the same elements. The "simple" solution is sort copies of the arrays, concat them into strings, compare the strings. It looks simple but it's around 1000x slower than pretty much any normal but not 1 line solution. 1000x won't matter when you're testing your 5 element arrays in your unit test but it will matter then your users start using larger arrays.
    - thomasahle 6y ago
      At least in the blog post, the alternative solution has 10x the number of lines. Of course, if you benchmark and this turns out to be important, try to optimize it.
ComodoHacker 6y ago
>This works because the elements in the array are close to each other in the physical memory. But with a hash, my understanding is that they wouldn't be so close, and thus we wouldn't benefit from this spatial locality effect. By the same logic, when n is small, they will be close and benefit from cache locality as well.
gergelykalman 6y ago
> The real point of this post is that when you have a little n, Big-O doesn't matter. This is absolutely correct, however if this is done in a sufficiently generic programming language, there is a very good chance that falling back on a linked list on collision is a bad idea. This has been well-researched and most programming languages have chosen a hash algorithm that resists (blind) collision generation, precisely for this reason. I wrote some code recently to demonstrate this: https://github.com/gergelykalman/bigOH https://github.com/gergelykalman/bigOH
Radim 6y ago
My favourite: "You cannot sort floats faster than O(N logN)! It's been PROVEN!" True story – I've heard this claim even from a CS PhD (!!). This is what happens when you forget your assumptions and muddle your terminology. I politely directed him to radix sort [0]. [0] E.g. http://www.codercorner.com/RadixSortRevisited.htm http://www.codercorner.com/RadixSortRevisited.htm
ficklepickle 6y ago
Honest question: What would be the complexity of a function that took a string (or array of characters) and called this function on each character? Would it be O(5n) ? Is that a thing? For each additional character in the input, it must compare against 5 values. Or would it be O(n) because it scales linearly? Thanks in advance. I'm a front end engineer and this is my weakest area but I'm keen to learn. I've studied this before but I use it infrequently and it doesn't stick.
- Tainnor 6y ago
  O(5n) is the same thing as O(n), because we ignore constant factors in O notation. So, for a fixed size array of vowels, counting the vowels in a string is linear in the length of the string (it can't be sublinear, because we need to look at each character, and the straightforward algorithm is linear).
  - formerly_proven 6y ago
    > O(5n) is the same thing as O(n), because we ignore constant factors in O notation. Even better. f \in O(g) means there is some point and some factor after which f <= c*g. This means O(n²+21371232138091293n) and O(n²) are the same.
- tetha 6y ago
  You'll need to be careful what your N is and what you're counting. But lets assume the input is an array of n characters, n being an arbitrarily large but fixed positive number during a single invocation. And we're estimating the number of char compares. Then, each invocation of isVowel(c) will do 1 - 5 compares. 1 in the case that c is the first element of the array, 5 if c is the last element or no element. As a worst-case estimation, isVowel(c) will do 5 compares at worst. As such, if isVowel(c) is called for all elements of A, we will see between n compares (best case for all invocations) and 5*n compares (worst case for all compares). As such, your algorithm has a worst-case runtime of O(5n) for all arrays A, which is a subset of O(n). In practice and outside of academia, that's pretty much all you do: - Identify your input set, and estimate its size - Count how many loops are nested in the algorithm, call that L (1 in this case) - Your algorithm should be O(n^L). Once it gets into amortization and such... it becomes much harder.
GuB-42 6y ago
I see the "little N" argument often used to justify using high complexity (big O) algorithms. But don't declare "little N" too early. If N depends on user input for instance, there is a high chance it might turn out bigger than expected. There are even attacks that exploit worst case complexity of algorithms. For example, using a balanced tree as a way to deal with collisions in hash tables is not necessarily a stupid idea. If the table is overloaded or because of a poor or easily exploited hash function, your hash map will degenerate into O(log(n)) instead of O(n). Now if you know for sure that collisions are unlikely, for example because you control the data you put into it, that you know that it will never be larger than a certain size, and that your hash function is good, then you can assume N is small. That's why, when I doubt, I always consider N large. Using a O(log(n)) container may be a bit less efficient for low N, but it will not become catastrophic if N becomes big. If performance is needed and there is no guarantee about N, hybrid approaches are best, and that's how good libraries tend to work.
- adamzerner 6y ago
  Usually N has to be really, really big before it matters, right? If so, it seems easy enough to tell when it won't reach that point.
kyberias 6y ago
Why is there so much dark gray text on dark gray background? Impossible to read.
deleted 6y ago
[deleted]
ncmncm 6y ago
Of course if you are looking to see whether a lower-case letter is one of a set, you use a bitmap: bool isvowel(char c){ return (1<<c-'a')&0x104111; } Often O(1) is better than O(n) even for small n. Often O(1) is better than O(1). Modern compilers will turn bool isvowel(char c){ switch(c){ case'a':case'e':case'i':case'o':case'u': return true; } return false; } into sort-of the same code (after a range check). https://godbolt.org/z/aMcdY6 https://godbolt.org/z/aMcdY6 Looking at the code actually produced, the compiler has noticed that all the vowels are even-numbered characters (0,4,8,14,20), so combined the range check with a "rotate-right" so it can compress 0x104111 down to 0x495, and shift that right and check the low bit of the result instead of doing a "bt", or bit-test. It's anybody's guess why that is considered better; shifts are supposed to be constant-time; but checking the low bit is a byte-sized operation. So, maybe bool isvowel(char c){ return (0x104111>>c-'a')&1; } is better: https://godbolt.org/z/M784cK https://godbolt.org/z/M784cK
- fluffything 6y ago
  > So, maybe [...] is better You were one click away of using LLVM's Machine Code Analyzer (MCA) within godbolt to see why one of the two isvowel one-liners is objectively better than the other: https://godbolt.org/z/fGEv3c https://godbolt.org/z/fGEv3c This version: bool isvowel(char c){ return (0x104111>>c-'a')&1; } puts way more pressure on Port 2 on skylake, reducing the number of IPC that can be scheduled. The first version is therefore a bit better. ;)
  - ncmncm 6y ago
    Today I learned six new things: - Clang thinks compressing 0x104111 to 0x495 is a good idea - Clang thinks 0x495>>((c-'a')>>1)&1 is better than 1<<c-'a'&0x104111 - LLVM has a machine code analyzer - Godbolt has a button to apply it - Clang is wrong about that - Gcc-9 and newer prefers to index into a jump table, instead of bitmasking. (!) Yet another reason to set up a periodic contribution to Godbolt.
    - fluffything 6y ago
lxe 6y ago
Great read. It's dangerous to overlook the practical aspects of the real-world hardware on which the code runs and over-index on the theoretical optimization. Your convoluted O(1) implementation can be slower than a naive O(n) one if you're doing something practically time-consuming.
lolptdr 6y ago
Newbie question: why would a hash function ever result in hash collision? Why can't a hash function guarantee a unique output value?
- detaro 6y ago
  A hash function has a limited range of outputs (e.g. for a hashtable it might be a number only a few bits large), whereas the space of possible inputs is larger or even unrestricted - e.g. could be arbitrary text. If you have a space of possible inputs that isn't larger thant the outputs, then you can indeed design hash functions that do not collide.
- deleted 6y ago
  [deleted]
- Cribbin 6y ago
  Think what happens when the number of possible outputs is smaller than the number of possible inputs. If we have a hash function f(n) that outputs a number between 1-100, but n can be any number between 1-1000, then some inputs must result in collisions.
- andjd 6y ago
  Hash functions represent a chunk of data with fewer bits than the original data, hence there's always a _chance_ of a collision. With cryptographic hashes, the output of the hash function is relatively large in size, making the probability of an accidental hash collision vanishingly small. For example, sha-256 hash algorithm can result in over 115 quattuorvigintillion different values. The hashing functions used with hash tables typically reduce the hashed value to one of only tens or hundreds of values, making collisions unavoidable. Typically, a hash table will try and manage the number of available slots to be roughly equal to the number of items stored in the hash to achieve performance that is a good balance of lookup time and memory requirements. For an extreme example, In Ruby, hashes of less than a certain size (6, I believe) are just represented internally as a list because the overhead of using an actual hash table is greater than just iterating through every item in the list.
- Jtsummers 6y ago
senderista 6y ago
Related: linked lists are way overused in chaining hash tables when dynamic arrays could be used instead. One reason sometimes given is that linked lists are amenable to the "move-to-front" heuristic (move just-accessed element to the head of the list), but one can do the same thing in dynamic arrays by swapping the just-accessed element with the first element (a better heuristic though is to fix some k and swap with the kth element if the accessed element is outside the top k, or swap with the preceding element if it's in the top k).
senderista 6y ago
A good rule of thumb is "if it fits in a cache line, then computation is free", where "computation" could mean search, hashing, compression, etc. This means, e.g., that linear search generally beats binary search if the whole array fits in a single cache line (or half a cache line if it's unaligned).
c-smile 6y ago
For the value of "small-N" I am using 8 usually. Here is why: https://terrainformatica.com/2017/10/15/when-linear-search-is-faster-than-stdmapfind-and-stdunordered_mapfind/ https://terrainformatica.com/2017/10/15/when-linear-search-i... And in Sciter objects (key/value maps) are using adaptive approach - if number of properties is less than 8 then it is linked list, otherwise - hash table.
swiftcoder 6y ago
While this is correct about the theoretical effects of small N, an equally important factor in this day and age would be the cache. If that lovely little linked list causes O(N) cache misses through Java-style pointer-chasing... you are suddenly looking a a very slow hashmap. Cache effects tend to mean that open addressing works out faster/more predictable in real world conditions.
developer2 6y ago
Based on the specific example (hashing buckets for a hash map/table)… just use a hashing function that uses a random seed per map/table instance during hashing to prevent insertion attacks, eg. SipHash. This prevents an attacker from being able to purposely engineer the overloading of a single bucket with too many entries, allowing the implementer to use a standard linked list per bucket without worrying about external influences. Then, if you're still worried about the one in a trillion chance that a single bucket receives too many entries… yeah, you're over-engineering and wasting your own time, and the mental capacity of every developer who comes after you to try and understand your attempts to circumvent the problem in supposedly "smarter" ways.

Big O, Little N

81 points by adamzerner 6y ago

pintxo 6y ago

"[...] premature optimization is the root of all evil [...]" D. Knuth

deleted 6y ago
[deleted]

jp3141 6y ago

Javas implementation of HashMap uses a tree on hash collision. [0] https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l156 https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/...

quickthrower2 6y ago
If the bin is big enough to warrant it, according to your link. Thanks for the link! I imagine they do this as the user space can define hash algorithms and someone is gonna just return zero every now and then out of laziness :-)
deleted 6y ago
[deleted]
virgilp 6y ago
You also need a comparable() key presumably - which you often have, but not always (a comparable() key is not strictly required by a hashtable).

CGamesPlay 6y ago

In addition to this, for many applications, programmer time is more valuable than the asymptotic savings of a faster algorithm. This isn't as "pure" of a discussion since it now starts to involve money, but when viewing programs through the lens of creating business value, it's important to consider.

higerordermap 6y ago
Even if this is true, don't say this loud. Because people have already taken it as license to write shitty code that is O(n²) where it can be O(n), or allocate in a frequently executed loop.
- justincredible 6y ago
  premature simplification is the root of all evil?

tangus 6y ago

A heads up: if you use a dark theme in your phone, this webpage is recognizes it and changes its background to dark grey. This makes the grey words in the diagrams illegible.

ziml77 6y ago
Desktop too. At least on macOS, in both Firefox and Chrome.

3np 6y ago

> const isVowel = (char) => ["a", "e", "i", "o", "u"].includes(char); > [... ] it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char. This depends on how you define your `n`. Usually this would be defined as the input size. Unless you would like to be able to run this on arbitrary definitions of what a "vowel" is (and in this case, it's indeed both small and static), the only useful interpretation would be to consider this function O(1), regardless of iteration over this 5-element list. If the list of vowels would considered a parameter, it would indeed be O(n) or O(m).

willvarfar 6y ago
You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)! :)
- virgilp 6y ago
  Depends. Are we talking about people who know what O(n) means? Parent comment explained it very well - "n" is typically your input size (or if it's not, you need to clearly define what it is). "n" is unlikely to ever be "number of vowels in the English alphabet" because that's a constant, that doesn't change at all when input changes. O(n) is meaningless if we don't say anything about "n", so no, 'iterating an array" is not necessarily O(n) - it's only so when the array has a size proportional with the input. Or, to put it differently: yes "array.includes" is not O(1) in common discussions, because typically we discuss the complexity of method `includes` as relative to the size of the array; but a program/algorithm that contains an invocation of `array.includes` does not automatically have complexity that is linear or worse - it can very well be logarithmic or constant. For example, looking up a value in a hashtable where the keys are strings is considered to be constant time, even though you need to iterate over the key in order to obtain its hashcode (i.e. the algorithm that takes a string and produces a hashcode is O(n) where n is the length of the string).
  - herbstein 6y ago
    This only makes sense if you consider a `contains` method to only take the arguments passed inside of the parenthesis. But in actuality there is an implicit `this` argument too. Armed with this knowledge it becomes trivial to see how the total input to the function is `N + 1` values. `N` being the length of the function, and the `1` representing the thing we're searching for. Since constant values in complexity theory are handily ignored we get an input of size `N`. And as to your second point, the choice of what is and isn't a constant-time operation is generally a practical concession. There's no reason to say "you can't say anything about any algorithm because it's an implementation detail" here. The conversation is specifically about element presence in an unsorted array. A very simple, easily understood, and unambiguous algorithm. Bringing up the runtime of the operation in a hashtable or in tree-structures is entirely nonsensical and just destroys any conversation there is to be had.

F-0X 6y ago

> And it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char. No, it's actually O(1). n refers to the _input_, which is always a single character. The iteration over an array (fixed at 5 elements) means a maximum of 5 comparisons. O(isVowel) = 5.

speakeron 6y ago

It's always worth remembering that O(n) describes the asymptotic limit where n is presumed to be very large (in fact, approaching infinity).

MaxBarraclough 6y ago
Related to this, there exist algorithms with impressive complexity-theoretic properties, but which are never useful in practice. They even have a cute name: https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm

Tainnor 6y ago

No, the author didn't really understand how hash tables* work and what the big-O notation really means. If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance. But hash tables are probabilistic data structures, so we don't actually look at worst-case performance, but at the average case. It's important that for this analysis we need to make some assumptions about the hash function itself (e.g. what its collision probability is). Out of that, we can compute that hash table operations are on average constant. * There are actually multiple ways to deal with collisions in hash table, let's focus on open hashing/seperate chaining for now.

jmalicki 6y ago
You also misunderstand hash tables.. they are not merely expected constant time, they are amortized constant time.
- Tainnor 6y ago
  as far as I understand, the amortization factor comes in because you occasionally might have to grow your table of buckets, in the same way that arbitrary-size array lookup is not actually constant, but only amortised constant. if we sidestep that issue for one moment, it's still true that you have worst case O(n) and average O(1), though.
  - josephg 6y ago
    > arbitrary-size array lookup is not actually constant, but only amortised constant. Array lookup operations are constant time. You don't need to grow an array while reading from it. Append operations in a vector are O(n) but amortized constant time. Hash tables work the same way - they have amortized constant time when inserting, but they should have constant time for reads when using a good hash function. That said, technically we still classify hash table reads and writes as O(n). Big-O notation defines an upper bound on time, not the average time. And the upper bound on hash table reads and writes is O(n) if you have a terrible hash function (or carefully crafted inputs). This is not useful knowledge though, because hash tables are usually fast in practice. If you're trying to figure out how something performs in practice (like the "isVowel" function in the blog post), the tool to reach for is a benchmark. Guess how a benchmark result will come out before you see the result, and over time you'll build an intuition for these things.

quickthrower2 6y ago

In languages with a BYO hash function you might write a crap one, so having the tree on collision might still be handy.

woadwarrior01 6y ago

I've seen binary trees used for collision resolution in hash buckets in quite a few production systems. A pathological case of O(log n) is vastly better than a pathological case of O(n), if you care about it. It might be instructive for programmers using higher level languages to learn about the cache hierarchy and the hardware prefetcher in modern systems. For those interested, I'd recommend reading Ulrich Drepper's classic: What Every Programmer Should Know About Memory[1]. [1]: https://www.akkadia.org/drepper/cpumemory.pdf https://www.akkadia.org/drepper/cpumemory.pdf

willvarfar 6y ago

Nice article. Easy to argue about the details, because the author is describing what they've discovered or bumped into, not what they've studied. But I still think its a nice intro that may make other programmers think. The article could explore open-addressing in hash-tables, and it could explore a switch statement for the vowels. Tangent: I've often wondered where the double-hashing tables are, and whether they could use the high and low bits of a single hash rather than the low bits of two hashes...?

siraben 6y ago

It's not uncommon in scientific computing for the algorithm used to be automatically adjusted based on the input. An example of this is if you want to multiply very large integers. Karatsuba is first used, then Toom-Cook, then Schönhage–Strassen. Karatsuba: θ(n^1.58) Toom-Cook: θ(n^1.46) Schönhage–Strassen: O(n log(n) log(log(n))) Benchmarking is really the only thing that can reveal this kind of thing, otherwise you'll end up with a theoretically fast but practically slow algorithm.

BeetleB 6y ago
Don't you need insanely high numbers before Karatsuba outperforms the simple O(n^2) algorithm? From Wikipedia: > As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits
- moonchild 6y ago
  4096-bit keys are standard for RSA, for example.
senderista 6y ago
Another example is quicksort falling back to insertion sort as a recursive base case for some n=k (instead of recursing all the way to one element).

YesThatTom2 6y ago

This is why benchmarking is so important. It is the reality check you need. Also... it took me decades to appreciate that clear code is better than fast code. If it’s slow, I can rewrite the inner loop. I’d rather have clear code with one thing optimized out of clarity that an entire system of clever code that I can’t debug.

YesThatTom2 6y ago

Here’s another article about O(n): 10 optimizations on linear search: https://queue.acm.org/detail.cfm?id=2984631 https://queue.acm.org/detail.cfm?id=2984631

bear8642 6y ago
Thanks for this - very interesting small article

pritovido 6y ago

There is something that must be said about anything that increases complexity in order to get efficiency: 1. It increases developer time. 2. It increases the number of bugs of the system as it increases enormously the different possibilities. We have systems that actually meta program with Lisp our hash tables with different degrees of complexities. It is already programmed, the designs already debug. And even then for most of our hash tables we just use the minimum level of complexity, that is having a memory that is 10 to 20 times bigger than the elements on the hash and just have one or two collisions for the entire set. That way the code is way easier to understand, and the memory differences are just negligible(compared to the total amount of memory the program needs), if sets are well designed.

gfxgirl 6y ago

https://jsben.ch/WCjjG https://jsben.ch/WCjjG Well, seems like it does matter. Using an array is 50% slower than using an object and that's slower than using a Set in Chrome. Even worse in Safari. In Firefox array wins but you need to use a static array. I don't know all the rules of JS. Semantically declaring an array in the function itself creates a new array on every invocation. Of course the JS engine should be able to figure out it doesn't need to create a new array every call but apparently Firefox's JS engine doesn't do that. Note: I'm making the assumption we're talking about JavaScript since the code looked like JavaScript to me. I get that in another language the results might be vastly different.

thomasahle 6y ago
> Well, seems like it does matter. Using an array is 50% slower than using an object and that's slower than using a Set in Chrome. A 50% difference doesn't mean it matter. Unless this runs in some inner loop, just use the simplest solution.
- gfxgirl 6y ago
  I agree that if the fast solution is 10x the code then maybe choose another solution. In this case all 6 solutions are basically the same amount of code. There's absolutely no reason to choose the slowest solution. 50% can easily be the difference between some VSCode extension making it sluggish vs not. Further, in my experience slow solutions will eventually come back to bite you. One I saw recenty. see if 2 arrays contain the same elements. The "simple" solution is sort copies of the arrays, concat them into strings, compare the strings. It looks simple but it's around 1000x slower than pretty much any normal but not 1 line solution. 1000x won't matter when you're testing your 5 element arrays in your unit test but it will matter then your users start using larger arrays.
  - thomasahle 6y ago
    At least in the blog post, the alternative solution has 10x the number of lines. Of course, if you benchmark and this turns out to be important, try to optimize it.

ComodoHacker 6y ago

>This works because the elements in the array are close to each other in the physical memory. But with a hash, my understanding is that they wouldn't be so close, and thus we wouldn't benefit from this spatial locality effect. By the same logic, when n is small, they will be close and benefit from cache locality as well.

gergelykalman 6y ago

> The real point of this post is that when you have a little n, Big-O doesn't matter. This is absolutely correct, however if this is done in a sufficiently generic programming language, there is a very good chance that falling back on a linked list on collision is a bad idea. This has been well-researched and most programming languages have chosen a hash algorithm that resists (blind) collision generation, precisely for this reason. I wrote some code recently to demonstrate this: https://github.com/gergelykalman/bigOH https://github.com/gergelykalman/bigOH

Radim 6y ago

My favourite: "You cannot sort floats faster than O(N logN)! It's been PROVEN!" True story – I've heard this claim even from a CS PhD (!!). This is what happens when you forget your assumptions and muddle your terminology. I politely directed him to radix sort [0]. [0] E.g. http://www.codercorner.com/RadixSortRevisited.htm http://www.codercorner.com/RadixSortRevisited.htm

ficklepickle 6y ago

Honest question: What would be the complexity of a function that took a string (or array of characters) and called this function on each character? Would it be O(5n) ? Is that a thing? For each additional character in the input, it must compare against 5 values. Or would it be O(n) because it scales linearly? Thanks in advance. I'm a front end engineer and this is my weakest area but I'm keen to learn. I've studied this before but I use it infrequently and it doesn't stick.

Tainnor 6y ago
O(5n) is the same thing as O(n), because we ignore constant factors in O notation. So, for a fixed size array of vowels, counting the vowels in a string is linear in the length of the string (it can't be sublinear, because we need to look at each character, and the straightforward algorithm is linear).
- formerly_proven 6y ago
  > O(5n) is the same thing as O(n), because we ignore constant factors in O notation. Even better. f \in O(g) means there is some point and some factor after which f <= c*g. This means O(n²+21371232138091293n) and O(n²) are the same.
tetha 6y ago
You'll need to be careful what your N is and what you're counting. But lets assume the input is an array of n characters, n being an arbitrarily large but fixed positive number during a single invocation. And we're estimating the number of char compares. Then, each invocation of isVowel(c) will do 1 - 5 compares. 1 in the case that c is the first element of the array, 5 if c is the last element or no element. As a worst-case estimation, isVowel(c) will do 5 compares at worst. As such, if isVowel(c) is called for all elements of A, we will see between n compares (best case for all invocations) and 5*n compares (worst case for all compares). As such, your algorithm has a worst-case runtime of O(5n) for all arrays A, which is a subset of O(n). In practice and outside of academia, that's pretty much all you do: - Identify your input set, and estimate its size - Count how many loops are nested in the algorithm, call that L (1 in this case) - Your algorithm should be O(n^L). Once it gets into amortization and such... it becomes much harder.

GuB-42 6y ago

I see the "little N" argument often used to justify using high complexity (big O) algorithms. But don't declare "little N" too early. If N depends on user input for instance, there is a high chance it might turn out bigger than expected. There are even attacks that exploit worst case complexity of algorithms. For example, using a balanced tree as a way to deal with collisions in hash tables is not necessarily a stupid idea. If the table is overloaded or because of a poor or easily exploited hash function, your hash map will degenerate into O(log(n)) instead of O(n). Now if you know for sure that collisions are unlikely, for example because you control the data you put into it, that you know that it will never be larger than a certain size, and that your hash function is good, then you can assume N is small. That's why, when I doubt, I always consider N large. Using a O(log(n)) container may be a bit less efficient for low N, but it will not become catastrophic if N becomes big. If performance is needed and there is no guarantee about N, hybrid approaches are best, and that's how good libraries tend to work.

adamzerner 6y ago
Usually N has to be really, really big before it matters, right? If so, it seems easy enough to tell when it won't reach that point.

kyberias 6y ago

Why is there so much dark gray text on dark gray background? Impossible to read.

deleted 6y ago

[deleted]

ncmncm 6y ago

Of course if you are looking to see whether a lower-case letter is one of a set, you use a bitmap: bool isvowel(char c){ return (1<<c-'a')&0x104111; } Often O(1) is better than O(n) even for small n. Often O(1) is better than O(1). Modern compilers will turn bool isvowel(char c){ switch(c){ case'a':case'e':case'i':case'o':case'u': return true; } return false; } into sort-of the same code (after a range check). https://godbolt.org/z/aMcdY6 https://godbolt.org/z/aMcdY6 Looking at the code actually produced, the compiler has noticed that all the vowels are even-numbered characters (0,4,8,14,20), so combined the range check with a "rotate-right" so it can compress 0x104111 down to 0x495, and shift that right and check the low bit of the result instead of doing a "bt", or bit-test. It's anybody's guess why that is considered better; shifts are supposed to be constant-time; but checking the low bit is a byte-sized operation. So, maybe bool isvowel(char c){ return (0x104111>>c-'a')&1; } is better: https://godbolt.org/z/M784cK https://godbolt.org/z/M784cK

fluffything 6y ago
> So, maybe [...] is better You were one click away of using LLVM's Machine Code Analyzer (MCA) within godbolt to see why one of the two isvowel one-liners is objectively better than the other: https://godbolt.org/z/fGEv3c https://godbolt.org/z/fGEv3c This version: bool isvowel(char c){ return (0x104111>>c-'a')&1; } puts way more pressure on Port 2 on skylake, reducing the number of IPC that can be scheduled. The first version is therefore a bit better. ;)
- ncmncm 6y ago
  Today I learned six new things: - Clang thinks compressing 0x104111 to 0x495 is a good idea - Clang thinks 0x495>>((c-'a')>>1)&1 is better than 1<<c-'a'&0x104111 - LLVM has a machine code analyzer - Godbolt has a button to apply it - Clang is wrong about that - Gcc-9 and newer prefers to index into a jump table, instead of bitmasking. (!) Yet another reason to set up a periodic contribution to Godbolt.
  - fluffything 6y ago

lxe 6y ago

Great read. It's dangerous to overlook the practical aspects of the real-world hardware on which the code runs and over-index on the theoretical optimization. Your convoluted O(1) implementation can be slower than a naive O(n) one if you're doing something practically time-consuming.

lolptdr 6y ago

Newbie question: why would a hash function ever result in hash collision? Why can't a hash function guarantee a unique output value?

detaro 6y ago
A hash function has a limited range of outputs (e.g. for a hashtable it might be a number only a few bits large), whereas the space of possible inputs is larger or even unrestricted - e.g. could be arbitrary text. If you have a space of possible inputs that isn't larger thant the outputs, then you can indeed design hash functions that do not collide.
deleted 6y ago
[deleted]
Cribbin 6y ago
Think what happens when the number of possible outputs is smaller than the number of possible inputs. If we have a hash function f(n) that outputs a number between 1-100, but n can be any number between 1-1000, then some inputs must result in collisions.
andjd 6y ago
Hash functions represent a chunk of data with fewer bits than the original data, hence there's always a _chance_ of a collision. With cryptographic hashes, the output of the hash function is relatively large in size, making the probability of an accidental hash collision vanishingly small. For example, sha-256 hash algorithm can result in over 115 quattuorvigintillion different values. The hashing functions used with hash tables typically reduce the hashed value to one of only tens or hundreds of values, making collisions unavoidable. Typically, a hash table will try and manage the number of available slots to be roughly equal to the number of items stored in the hash to achieve performance that is a good balance of lookup time and memory requirements. For an extreme example, In Ruby, hashes of less than a certain size (6, I believe) are just represented internally as a list because the overhead of using an actual hash table is greater than just iterating through every item in the list.
Jtsummers 6y ago

senderista 6y ago

Related: linked lists are way overused in chaining hash tables when dynamic arrays could be used instead. One reason sometimes given is that linked lists are amenable to the "move-to-front" heuristic (move just-accessed element to the head of the list), but one can do the same thing in dynamic arrays by swapping the just-accessed element with the first element (a better heuristic though is to fix some k and swap with the kth element if the accessed element is outside the top k, or swap with the preceding element if it's in the top k).

senderista 6y ago

A good rule of thumb is "if it fits in a cache line, then computation is free", where "computation" could mean search, hashing, compression, etc. This means, e.g., that linear search generally beats binary search if the whole array fits in a single cache line (or half a cache line if it's unaligned).

c-smile 6y ago

For the value of "small-N" I am using 8 usually. Here is why: https://terrainformatica.com/2017/10/15/when-linear-search-is-faster-than-stdmapfind-and-stdunordered_mapfind/ https://terrainformatica.com/2017/10/15/when-linear-search-i... And in Sciter objects (key/value maps) are using adaptive approach - if number of properties is less than 8 then it is linked list, otherwise - hash table.

swiftcoder 6y ago

While this is correct about the theoretical effects of small N, an equally important factor in this day and age would be the cache. If that lovely little linked list causes O(N) cache misses through Java-style pointer-chasing... you are suddenly looking a a very slow hashmap. Cache effects tend to mean that open addressing works out faster/more predictable in real world conditions.

developer2 6y ago

Based on the specific example (hashing buckets for a hash map/table)… just use a hashing function that uses a random seed per map/table instance during hashing to prevent insertion attacks, eg. SipHash. This prevents an attacker from being able to purposely engineer the overloading of a single bucket with too many entries, allowing the implementer to use a standard linked list per bucket without worrying about external influences. Then, if you're still worried about the one in a trillion chance that a single bucket receives too many entries… yeah, you're over-engineering and wasting your own time, and the mental capacity of every developer who comes after you to try and understand your attempts to circumvent the problem in supposedly "smarter" ways.