3 ms·

The conflation of "amortized" with "expected" feels a bit off to me. Amortized O(f) strongly suggests that the sum of n operations is very very close to O(n×f)

by sfink 4y ago

The conflation of "amortized" with "expected" feels a bit off to me. Amortized O(f) strongly suggests that the sum of n operations is very very close to O(n×f). I wouldn't say hashmap insertion is amortized O(1), because if you craft input that always incurs a hash collision, then n insertions is much worse than O(n). I would say that it's expected O(1), meaning that with high probability an insertion takes constant time. Conversely, "amortized" is only a useful description when it is known that some operations will take much longer than others, yet the total time is bounded. (If you bring up amortized time, you're pretty much implying that the distribution of times is uneven, otherwise you wouldn't have mentioned it.) For example, if you're doubling the length of an array on overflow, then I would say the amortized time of a push is O(1). It would seem weird to say that the expected time is O(1). If I wanted to be more complete, I'd say "normally a push is constant time, but when the array needs to be expanded then it's O(n). The amortized time is still constant, though." Expected time refers to a single operation. Amortized time describes the mean time of a series of operations.

ctrlmeta 4y ago
> Expected time refers to a single operation. Amortized time describes the mean time of a series of operations. Pardon my ignorance but I don't see the difference between these two sentences. Expected time of a single operation = Sum of time taken for all possible input cases / Number of cases (assuming each input case is equally likely to occur). Is it not? Isn't it then the same as amortized time?
- vient 4y ago
  A difference is in the number of times you use some operation. For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least). On the other hand, an individual array is usually sorted only once. Here it is more appropriate to speak about average or expected complexity of quicksort which is O(NlogN) but in you particular run it may become either better or worse and this will noticeably affect running time, by a factor dependent of N value. You can say about amortized time of quicksort though if you expect to sort different arrays a lot of times and you know their distribution, or at least the fact that they are sufficiently random shuffled or maybe sufficiently sorted beforehand.
  - ctrlmeta 4y ago
    Ah! Finally it clicked! Thanks for the nice example in your comment.
- aliceryhl 4y ago
  They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness). Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time. Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1). So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).
deleted 4y ago
[deleted]
orlp 4y ago
Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable spike in performance. The trick is to slowly already start copying data into the next larger buffer as you're filling the previous buffer. As an example in pseudocode C++: template<class T> struct ConstantTimeVector { T* buf; T* next_buf; size_t len; size_t cap; void push(T x) { if (len == cap) { free(buf); buf = next_buf; cap *= 2; next_buf = alloc(cap); } buf[len] = x; next_buf[len] = x; next_buf[len - cap / 2] = buf[len - cap / 2]; len += 1; } } You can apply a similar trick to hash tables to get expected O(1) time inserts without amortization, by already building the re-hashed table during the building of the previous table.
- sfink 4y ago
  Hah! That's awesome. I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble. And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the latency, not minimize it.
  - orlp 4y ago
    It does not necessarily add a branch to the lookup, look more closely: all current data exists in buf in its entirety. It is duplicated into next_buf. This might be problematic depending on T in C++ as it would need to invoke copy constructors. In Rust all types can trivially be memcpy'd into another location if you own it, so this design would be entirely valid (as long as next_buf is not publicly accessible at all, and we do not provide mutable access to the data). EDIT: after thinking a bit more, due to interior mutability you can't provide access at all, or you would need to invoke a branch like you said in Rust. If you want to provide mutable access to a piece of data and/or avoid copy constructors in favor of move constructors, then, yes you would need to do a branch.
Ferrotin 4y ago
Ordinary hash maps are still amortized expected O(1) — they will hit an O(n) case, guaranteed, when they need to grow the array, and it’s expected that the amortized runtime is O(1). Being merely “expected O(_)” would be appropriate for algorithms that lack amortization, such as quick sort.

by sfink 4y ago

ctrlmeta 4y ago

> Expected time refers to a single operation. Amortized time describes the mean time of a series of operations. Pardon my ignorance but I don't see the difference between these two sentences. Expected time of a single operation = Sum of time taken for all possible input cases / Number of cases (assuming each input case is equally likely to occur). Is it not? Isn't it then the same as amortized time?

vient 4y ago
A difference is in the number of times you use some operation. For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least). On the other hand, an individual array is usually sorted only once. Here it is more appropriate to speak about average or expected complexity of quicksort which is O(NlogN) but in you particular run it may become either better or worse and this will noticeably affect running time, by a factor dependent of N value. You can say about amortized time of quicksort though if you expect to sort different arrays a lot of times and you know their distribution, or at least the fact that they are sufficiently random shuffled or maybe sufficiently sorted beforehand.
- ctrlmeta 4y ago
  Ah! Finally it clicked! Thanks for the nice example in your comment.
aliceryhl 4y ago
They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness). Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time. Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1). So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).

deleted 4y ago

[deleted]

orlp 4y ago

Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable spike in performance. The trick is to slowly already start copying data into the next larger buffer as you're filling the previous buffer. As an example in pseudocode C++: template<class T> struct ConstantTimeVector { T* buf; T* next_buf; size_t len; size_t cap; void push(T x) { if (len == cap) { free(buf); buf = next_buf; cap *= 2; next_buf = alloc(cap); } buf[len] = x; next_buf[len] = x; next_buf[len - cap / 2] = buf[len - cap / 2]; len += 1; } } You can apply a similar trick to hash tables to get expected O(1) time inserts without amortization, by already building the re-hashed table during the building of the previous table.

sfink 4y ago
Hah! That's awesome. I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble. And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the latency, not minimize it.
- orlp 4y ago
  It does not necessarily add a branch to the lookup, look more closely: all current data exists in buf in its entirety. It is duplicated into next_buf. This might be problematic depending on T in C++ as it would need to invoke copy constructors. In Rust all types can trivially be memcpy'd into another location if you own it, so this design would be entirely valid (as long as next_buf is not publicly accessible at all, and we do not provide mutable access to the data). EDIT: after thinking a bit more, due to interior mutability you can't provide access at all, or you would need to invoke a branch like you said in Rust. If you want to provide mutable access to a piece of data and/or avoid copy constructors in favor of move constructors, then, yes you would need to do a branch.

Ferrotin 4y ago

Ordinary hash maps are still amortized expected O(1) — they will hit an O(n) case, guaranteed, when they need to grow the array, and it’s expected that the amortized runtime is O(1). Being merely “expected O(_)” would be appropriate for algorithms that lack amortization, such as quick sort.