3 ms·

Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for mos

• toxik 5y ago
  They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.
  • touisteur 5y ago
    Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.
    • karpierz 5y ago
      Mergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.
      • touisteur 5y ago
        Which is where you get problematic tail latencies. Or your data fits on the stack.
    • phkahler 5y ago
      Heapsort is O(n * Log(n)) worst case. It is also O(n * Log(n)) in most cases, including already sorted data. Most implementations also seem to have a slightly larger constant factor than quicksort, but I think that's largely due to implementation details (one should not actually swap values that are likely to be immediately swapped again). Which one is right really does come down to a decision based on how much you care about Typical/Average/WorstCase time complexity and the actual size of your data set.
• jcelerier 5y ago
  > I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs. we must not use the same programs :-(