Ask HN: I just wrote an O(N) diffing algorithm – what am I missing?

Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by keithwhor on Monday October 28, 2019 @08:34PM (#21383262)

Hmm -- assumed time complexity for well-built hash functions for get / put operations is O(1), is it not? Sure, absolute worst-case means every operation is going to collide. Hash functions themselves are O(1)... I'm not sure what you mean by "implicit factor of D"? Like hashing is going inflate the runtime by a small factor basically equivalent to the edit distance in Myers' approach?

I've been looking through a little bit more literature and it's clear to me that my implementation as it stands is not equipped to solve the Longest Common Substring problem [0]. Right now it's too greedy. I think with a tweak it could.

I think I'm mostly just surprised because when I sat down at my computer today, I had the impression that diffing was a "hard problem" -- to be able to implement something that (apparently) works in a short timeframe made me feel as though I did something wrong. (I have this code running in a staging environment now with a code editor, and it seems to be working smoothly and as expected.)

[0] https://en.wikipedia.org/wiki/Longest_common_substring_probl...

[ Parent | on HN ]

Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by hhmc on Tuesday October 29, 2019 @03:05PM (#21390870)

Replying here because I can't edit my orignal comment. But I stand by what I said -- in the pathalogical case all of your keys map to the same bucket, and you hit O(N^2) or O(N log N) behaviour (depending on what exactly happens within your bucket).

I appreciate that in the typical case this won't happen, but big O denotes limiting behaviour, which in this case in O(N^2) or O(N log N) depending on your hash map implementation.

[ Parent | on HN ]

Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by hhmc on Tuesday October 29, 2019 @04:31AM (#21385106)

My understanding is that from a purely theoretical point of view you can call the operations Θ(1), but not O(1) -- since the worst case must account for the pathological case.

[ Parent | on HN ]

Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by Yessing on Tuesday October 29, 2019 @07:37AM (#21385983)

by definition Θ(1) implies O(1).

A sandwich means you have a slice of bread on the upper side.

[ Parent | on HN ]