Hacker News Reader

Comment by kccqzy | Hacker News Reader

Usually a fine approach would be to construct a hash table as we walk the array, and if the element is not seen put it in the hash table, otherwise "remove" it by setting it to the empty string. If the hash table implementation is good, we can pretty much find out whether an entry has been seen before in O(1) time, making the whole process O(n).

That's what the author called "alt" and I don't understand why the author objects to it. The memory needed is usually proportional to the number of distinct elements in the original array. You don't generally have to copy the original values (usually you just copy a pointer).

View on HN

> That's what the author called "alt" and I don't understand why the author objects to it.

His "neutral pseudocode" is Go, which lacks good support for parameterized types. As a result there would be quite a bit of boilerplate code in doing things this way.

This is also why the author remarks "For trivial examples this works well, but for more complicated types with complex keys, it may require creating new types."

This post is a nice example of why it is important to eliminate friction from a a language if you want to get people to use a particular feature. However, the goal of removing friction interacts poorly with an observation Bjarne Stroustrup once made, that:

* For new features, people insist on LOUD explicit syntax.

* For established features, people want terse notation.

That is, when a feature is new to a programmer, they want it to be loud to remind them that something unexpected is happening, and once it is known to them they want it to disappear so they can focus on their problem -- and if it doesn't disappear, the solution using it will be so noisy they won't do it that way.

I expect the ultimate solution to this problem involves IDE design, rather than language design....

I would go a bit higher on the abstraction level - instead of using a hash I would use a Set. I see that Golang has at least one implementation:

https://github.com/deckarep/golang-set

If for some reason going "high level" is not an option, this:

> For trivial examples this works well, but for more complicated types with complex keys, it may require creating new types.

surprises me. Producing a small, unequivocal identifier for a value (be it using some kind of hash function, or just the raw memory address) seems like a very basic language feature. Doesn't the Go standard library have something similar to

    func memory_address(o interface{}) int

    func hash(o interface{}) string

If yes, then "complex keys" would not be needed: They would always be ints, strings, or whatever the aforementioned function returns.

My initial reaction was that I'd use a map like one of the parent posters said. But instead of creating a Set we can just use a map[type]bool, which is essentially a Set.

Incidentally, I just wrote a Unique method today for a specific array.

      type Elements []Element
      func (es Elements) Uniq() []Element {
          seen := make(map[Element]bool, 0)
          results := make([]Element,0)
          for _,e := ranges es {
              if seen[e] {
                  continue
              }
              seen[e] = true
              results = append(results, e)
          }
          return results
      }

I did not think about performance all that much, but map lookup is pretty good and I iterate through the array one time.

(As a side-note, we know that the size will be below 100 so it's not perf critical)

EDIT: Wording EDIT2: To address one of your points, you could probably just create a hash yourself and use that as the map Key as well, as you have said.

A proper map based set is a map[type]void or whatever golang has for void.

Correct - for go, we would canonically use struct{} which occupies zero bytes of storage.

But how would you indicate something is found? What struct do you put in there?

Can you give me an example, I'm curious to know :)

Almost every language has a function that returns whether a key exists in the map. In go it would be something like:

    _, ok := m[thing_to_be_found]

So it doesn't matter what you put in there, including struct{}.

facepalm of course. Somehow that slipped my mind lol. I'm used to using the default zero-values in maps in go which is a lovely feature. But it means I don't often have to check if something is already in the map :P

EDIT: Now I still need to create an empty struct to use as a value when something is found, which is a bit less elegant in my eyes.

     var dummy struct{}
     found[key] = dummy

But that might just be taste, when reading it, the fact that it's a boolean value saying "found = true" just takes no overhead in parsing the meaning.

Thanks guys ;-)

You can just do

    found[key] = struct{}{}

Which still does not say much imo, but yeah it is an option :)

As a bit of a noob I certainly see that in JavaScript as things change. There will be a discussion about easily readable code and there are some explicit examples and everyone is happy about them because we all know what is happening, then the discussion turns to new syntax and it's terse and everyone is excited too ;)

I can't help but wonder "Hey guys do these conversations we just had make sense next to each other?"

Granted it's always a balancing act.

There's one valid objection to hashing (not the one the author expressed): you may have an array of items that you can compare, but you cannot hash.

For example, maybe you rely on a third-party service that lets you compare two items but does not provide you with a hash value.

Or maybe you simply don't know the distribution of the items, so it's hard for you to write a good hash function. For instance, the items may be large strings of text. You can of course compare them. But to create a good hash function for them, you'd need to know a bit more about how they are distributed in the space of all possible strings. Maybe hashing the first few characters is good enough -- but that won't work if most of your strings start with the same prefix. Maybe splitting into words and hashing word frequencies is good -- but not if many strings are just reorderings of the same words. And so on.

Hashing text is one of the easiest, most common uses of hashing.

As for your first example “you may be relying on a 3rd party service that compares things”, has this ever happened in the history of the universe?

Hashing text isn't hard but to do it efficiently you may need to know the distribution.

Imagine you want to dedupe 1000 text documents each 1TB in size. Hashing naively would require reading 1000 TB and would be horribly inefficient. Hashing the short prefix would be better but you need to know how long of a prefix is sufficient to avoid too many collisions.

Sorting might be safer from efficiency perspective in this case unless you know a bit more about your data set.

About 3rd party service: let's say you have images of faces and you want to dedupe them. A third party face comparison service could be a reasonable option. (And as another comment suggested, third party could be a different group in the same company, whose code base isn't trivial to modify.)

Isn't sorting 1000 of 1TB strings even more inefficient? You need to read and compare the 1TB strings 1000 * log(1000) or 3000 times, while hashing only needs 1000 times.

Typically, you can tell the order between two strings early, after you read just the starting few characters. So for comparison you would usually read maybe 10 bytes per file on average, or 3 x 1000 x 10 bytes = 30KB in total. Or maybe 30MB if the strings have long common prefixes.

Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible.

Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.

Maybe not, but I bet "someone else overrode == and you've been told not to mess with it" has.

You could still use a TreeSet which only requires ordering and equality, but not hashing.

As a side note, though, your earlier example would not be comparable via Equals, as it violates transitivity. Which is also what makes it impossible to generate a hash code consistent with its Equals implementation.

Oh yeah absolutely you can use better structures even without hashing, I was just saying that a hash table isn't always an option.

Lack of transitivity: you can still dedupe based on a transitive closure of whatever relationship I provide. It's easy if I want to dedupe numbers closer than 0.01 (using sorting) but much harder to do it efficiently for vectors.

> Which is also what makes it impossible to generate a hash code consistent with its Equals implementation.

How so? `return 0;` is always a legal hash function, albeit a pretty lousy one.

This is what I'd do too, and it is quite strange that it was dismissed like that. Maybe because it's not as much fun :)

BTW I believe it may be a bit more than just O(n) time on the whole. If your hash-table is auto-growing, you'll have to pay for its resizing. And OTOH if it's sized up front, then you'll have to allocate something proportional to the size of the full array, not just to the number of distinct elements.

As long as the resizing e.g. doubles the size each time, the total running time will still be O(n). Basically because

  1+2+4+...+2^k = O(2^k)

I think I get it. With doubling, the sum of all the work done for resizing is roughly (written chonologically backwards): n/2 + n/4 + ... ~= n, and O(n) + O(n) is still O(n). Thanks!

Yep! This is generally referred to as "amortized linear time". It's the difference between considering the cost "per operation" vs. "per algorithm". The former is technically correct (as an upper bound), but too pessimistic when you consider the algorithm as a whole.

See https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...

Although the examples are all about strings, there's no reason to be so specific. One nice property of the algorithms described in the article is that they only require the elements to be comparable (even better, the first two implementations only require them to have an equivalence relation), while yours requires that they be hashable.

Every object is hashable. Here's a hash function that works with anything:

    int hash(Object anything) { return 3; }

Most objects permit more effective hash functions with better distribution properties than that.

In practice, I think more types are hashable than are comparable.

One could use a tree-based set, which would only require being comparable, but that would get us back to average-case O(n log n).

That's fair, but in practical terms how often are you going to come across a problem like this when you're values aren't hashable? Maybe I'm missing something obvious, but I feel like the kind of types that aren't hashable are also the kind of types that you wouldn't have to do something like this with.

Is there an example of a type that has an equivalence operation but cannot have a hash operation? Seems to me that those two are identical. If you have a subset of elements within a type that defines identity, then you can hash that identity.

Yes, in a garbage-collected language a ref cell is typically unhashable since the only identifying data about it is the pointer location, which could change between calls to the hash function. However, you can still define equality pretty easily (just compare the pointer values). This is also my best example of something with an equivalence relation that is not comparable.

I don't have a ready example of something that is comparable but not hashable, but it isn't uncommon in my experience to come across an opaque type whose author simply didn't expose enough information to hash it, while they did expose a compare function.

If I recall correctly this is exactly what .net’s ‘Distinct()’ LINQ extension method does.

Yes: https://github.com/dotnet/corefx/blob/8750960d3fafa46a9b838c...

Very few hash tables actually run in O(1) time and they tend to be bounded. You cannot have any collisions at all, and you need to use a lookup with fast, constant cost.

Many hash tables in use today are actually either O(n^2) (for the homework kind), or O(n log n) for some large log factor like 32 (in the spirit of Bagwell's work).

> Many hash tables in use today are actually either O(n^2) or O(n log n)

Do you have any citation for such an extraordinary claim? Or are you not talking about lookup complexity where n is the size of the table?

I would think that a hash table with an O(n^2) or O(n log n) lookup is not a hash table at all. I mean, a simple linear search is O(n).

O(n) == O(n^2) when n = 1.

The whole point of this notation is to describe limiting behavior, the true value of N isn’t important in the slightest.

That is actually my point. Remember the goal is to nub an array into a set.

Perfect hash tables where there are no collisions are O(1) but they're not suitable for casual use, you need to guarantee your data set never collides hash buckets. That is why most implementations of "maps" in programming languages map to very wide trees after a certain size. A common example is HAMTs (Bagwell is famois for these).

They're flexible and perform well on modern hardware for arbitrary key lookiup.

If your constant time hash tables is taken to the worst case (as we do in O analysis) then that operation would collide with the same bucket and require a potentially full linear search of the data every time to see if it places into your oversubscribed bucket. That's O(n^2).

You could make it better by sorting on insert. That's O(n log n) because it's comparison based.

I've provided a much better solution and links to code that does it. Maps and hash tables don't solve this problem any better than just sorting the array.

It's worth noting that if we're ignoring preprocessing and the domain is well-constrained, we could probably make O(1) to do a bunch of these ops in bulk if we really wanna go off the deep end. But that's cheating because we'd be ignoring construction costs, as you are here.

...

It is a jokey way to restate the absurd essence of the parent's argument.

It's worth noting for clarification I'm talking about inserting to construct a set and reading out the keyspace. Not specifically reads, which is I think what folks below are objecting to.

The read side barely matters for the use case we're discussing.

Not sure why you're getting downvoted. It's plainly true that hash tables accesses are only O(1) amortized. The real worst case is ~O(n log n) (or whatever the bucket data structure is) in the case of collisions and/or filling up.

And we can always pre-allocate a huge array for the buckets, but the behavior of the hash function is always going to be a risk.

I don't know about the rest, but I downvoted both of you because your vague claims just add noise to the discussion. There's absolutely no sense whatsoever in the claim that the worst case for hash table access is O(n log n), when just a linear search will be O(n).

Gah, I see the confusion, in one sentence I was talking about single element access, and in the next about full copy, and I was just assuming the jump was clear to the reader but clearly it wasn't.

So just to be fully explicit:

Single element access in a hash table is only ~O(1) when it's amortized over many accesses of a table that assumes few collisions (due to size and a good hash function). But the real worst-case performance, in case of incessent collisions, is going to be the performance of whatever data structure hides behind each bucket: O(n) if it's a naive list, O(log_x n) if it's a simple tree, etc.

So copying a full list into a hash table is not O(n), it's O(n^2) if the buckets are backed by naive lists, O(n log_x n) if the buckets are backed by simple trees, or another superlinear bound for another backing data structure.

How about it?

And personally I would still prefer to de-dupe an array by dumping into a hashtable and back, but the OP is right, you have to be careful about implementation details of both the hashtable and the hashing function. The simple hashtable-and-back can produce much worse perf than sort-and-dedupe if stars don't align.

The task is not to find an object in a hash tables. It's to nub an array into a set.

Which is why we're not handwaving away the construction cost or ignoring key comparisons or other such thinking.

Saying, "A hash tables solves this" is the definition of noise, because if you have a perfect hash function for a data set to get the constants you want then you've already got the solution to the problem presented for discussion here. The hash tables itself just becomes cargo culting.

I'm being downvoted because I deserve to be. I got involved in a computer science discussion on hacker news and now I don't have the self-control to extricate myself because I love this subject.

What are you calling n?

That's exactly what came to mind immediately. Can't help but make a one-liner:

    Object.values(arr.reduce((o,s,i,a,k=s.toLowerCase()) => ((o[k] || (o[k]=s)), o), {}))

Which turns out to be pretty efficient: each string seen once, low memory overhead. Or a simpler version using Set:

    let set = new Set()
    arr.filter((s, i, c, k = s.toLowerCase()) => !set.has(k) && set.add(k))

You could also build the hash table "in-place" using an array of indices, the same length as the size of the array, to chain items. It'll be between O(n) and O(n^2) depending on how many collisions you get, but I suspect that on average it will be faster than sorting.

> That's what the author called "alt" and I don't understand why the author objects to it. The memory needed is usually proportional to the number of distinct elements in the original array.

Possibly the high constant cost, making them less than optimal for short sequences?

A Set would be even better IMO

A set would still have n log n complexity, though, wouldn't it? At least if the set was a tree.

The comment you're replying to is replying to a comment about using a hash map; I read it as a suggestion to replace that with a hash set, which would be O(n) in time & space for the article's problem. (You don't need the "value" half of the hash map for this problem.)

A set could have many implementations, it could be a HashSet and still have O(1) update/access. I was just referring to how using a hash map in this situation you actually don't need the value parameter-- so the correct data structure here is a set, not a map.

Why would a set have to be a tree? In fact would expect trees to be the less common way to implement sets (I would expect hash tables to be more common).

Reply on news.ycombinator.com