5 ms·

Why don't you just use a set?

• KirinDave 8y ago
  Constructing sets has a running time, too. All you're really doing when you build a set is sorting.
  • recursive 8y ago
    That's not true for any reasonable set implementation. Sorting is unnecessarily time-intensive for maintaining distinctness. Hashing is sufficient.
    • KirinDave 8y ago
      Which set implementation are you referring to? And also remember the context here: you're removing duplicate value's from an array. So you're inserting N items into a set. If the set insertion or enumeration involves even a O(log(n)) operation, you're at nlogn.
      • recursive 8y ago
        A hashset has O(1) membership testing and amortized O(1) element insertion.
        • haxton 8y ago
          You don't even need the amortized insertion. You know the max set size from the original list of items.
          • KirinDave 8y ago
            But you don't get to pick the input type. What's your adaptive, non-probabilistic perfect hash function for all data types? I'm only aware of partial solutions to that problem, of which top down Radix sort is in fact one. But once you do that you don't need the table to solve the problem anyways, you've already got your discrimination function and you'd just pass that over the data. I cannot see why the tabular part of the hash table proposed solution is anything more than cargo culting.
        • KirinDave 8y ago
          But it requires a perfect hash. You need to guarantee over any potential input that you don't have collisions. How do you do that over all inputs? If there is a generalized non-probabilistic perfect hash function I am unaware of it and I'd like to be aware of it.
          • recursive 8y ago
            No, it doesn't require a perfect hash. There are collision mitigations. In practice there several that can get to O(1). I'm not sure if there is a way to achieve O(1) in the worst case. But the worst case can be made arbitrarily unlikely, even against adversarial inputs.
            • KirinDave 8y ago
              > I'm not sure if there is a way to achieve O(1) in the worst case. Then you're not at O(1). You cannot say "O(1) except in the worst case". That is like saying, "It is blue except when you look at it." But you don't need these mitigations (most of which are O(log n)) because you never had the hash table. You should look at American Flag sort, because morally it's actually doing something that closely approximates what you're thinking about. That's why I brought it up elsewhere in the thread.
              • recursive 8y ago
                It's O(1) in the sense that git works. Git uses "commit hashes". If these collide, something would break, on par with the universe stopping working, I presume. But I'm sure, since this never actually happens in practice.
                • KirinDave 8y ago
                  https://arstechnica.com/information-technology/2017/02/watershed-sha1-collision-just-broke-the-webkit-repository-others-may-follow/ https://arstechnica.com/information-technology/2017/02/water... It was a bad design to rely on hashing algorithms to never collide. But it's worth noting that even SHA1 is much more robust than most hash table algorithms, which are meant to run even faster.
      • leshow 8y ago
        A set could literally be: type HashSet<K> = HashMap<K, ()>; In which case it has all the properties of a hashmap except it doesn't use values. That's what we need for this problem.
    • KirinDave 8y ago
      Also, sorting is O(n), which is exactly what your perfect hash table would be, recursive.