Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

github.com

Post reply on HN
Print view View original

31–40 of 52 posts

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#31

Post by ascar »

jrockway wrote: post #26

This is neat. I decided to diff two pods in a replicated Kubernetes service. It seemed that it was going to take forever to run, so I just wrote a short Go program to do the same thing (load two JSON files into a map[string]interface{}, cmp.Diff them) while it was going: https://gist.github.com/jrockway/73982949b3d2ce9b443528042c4... My program runs in less than 10 milliseconds (/usr/bin/time reports 0.00 seconds), a…

Well you are kinda comparing apples and oranges here.

According to their readme they don't just match on keys, but even try to detect changed keys for the same content, even when the two files have a different inner order of elements.

Your diff is probably equivalent to a pretty print and then running regular diff on it, i.e. not even sorting the file.

Having said that and assuming your file wasn't extraordinary large, a 5min runtime makes this tool kinda unusable.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#32

Post by IshKebab »

jrockway wrote: post #26

This is neat. I decided to diff two pods in a replicated Kubernetes service. It seemed that it was going to take forever to run, so I just wrote a short Go program to do the same thing (load two JSON files into a map[string]interface{}, cmp.Diff them) while it was going: https://gist.github.com/jrockway/73982949b3d2ce9b443528042c4... My program runs in less than 10 milliseconds (/usr/bin/time reports 0.00 seconds), a…

Yes but does your code actually do tree diffing or does it just do line based diffing?

Proper tree diffing is a really hard (I would say unsolved) problem. The "standard" algorithm is O(N^4)!

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#33

Post by IshKebab »

acidbaseextract wrote: post #7

It's cool, but does seem quite slow. I'm diffing two 45kB CSVs on a fast computer and after 10 minutes I'm still at: Diffing: 0% ... 0/93195 [00:00

Tree diffing algorithms have very bad complexity (e.g. O(N^4)!) so this will probably only work on really small examples.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#34

Post by dan-robertson »

meetups323 wrote: post #16
dan-robertson wrote: post #10

Earlier quoted context omitted.

I think it’s ended up with a quadratic algorithm for diffing sequences and a quadratic log algorithm for diffing dictionaries. To understand why the sequences problem is quadratic, consider a sequence A of length m being doffed with a sequence B of length n. We want to express our diff in the minimum number of operations where an operation is removing, adding, or editing an element in the sequence. Construct a graph…

Quadratic doesn't need to equal "bad", especially in this case. Two 45 kB items is 2 billion entries. Allocating 2 billion bytes is easy enough. Iterating over 2 billion bytes is also not terrible. The GP says the process is estimated to take 150 hours, or half a million seconds, or 1.62e15 cycles... so around 1 million cycles per cell.

If it’s doing anything nontrivial (eg computing the weights of the diagonal edges by comparing the rows as sequences) then you’re basically screwed. The problem with quadratic is that it doesn’t scale but it’s fast enough for small inputs that it is hard to notice until you get a large input.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#35

Post by jrockway »

rmetzler wrote: post #30
jrockway wrote: post #26

This is neat. I decided to diff two pods in a replicated Kubernetes service. It seemed that it was going to take forever to run, so I just wrote a short Go program to do the same thing (load two JSON files into a map[string]interface{}, cmp.Diff them) while it was going: https://gist.github.com/jrockway/73982949b3d2ce9b443528042c4... My program runs in less than 10 milliseconds (/usr/bin/time reports 0.00 seconds), a…

It's neat that you built what you needed in a few lines of code. I must say, I don't quite like the output of Graphtage, I like your's a little bit more, but without a context it's not easy to see how podIP is nested. Usecases might be a little bit different, but please allow me to share my solution. The problem with diffing JSON and yaml is, that these formats aren't line based and hashes don't need to be ordered. B…

The diff I did is aware of the structure of the object. It's not just sorted lines.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#36

Post by kmarc »

jrockway wrote: post #35
rmetzler wrote: post #30

Earlier quoted context omitted.

It's neat that you built what you needed in a few lines of code. I must say, I don't quite like the output of Graphtage, I like your's a little bit more, but without a context it's not easy to see how podIP is nested. Usecases might be a little bit different, but please allow me to share my solution. The problem with diffing JSON and yaml is, that these formats aren't line based and hashes don't need to be ordered. B…

The diff I did is aware of the structure of the object. It's not just sorted lines.

Apart from the interesting conversation here, just to make sure...

You are all aware of kubectl diff[1], right? I understand that sometimes you just want to diff two k8s objects, kubectl diff is not a tool for that.

[1]: https://www.mankier.com/1/kubectl-diff

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#37

Post by hermitcrab »

deknos wrote: post #28

and now please, build a tool which converts all these thinks, like imagemagick for machinereadable documents.

If you mean convert between data formats (e.g. between, CSV,YAML,JSON, XML) there are programs already that can do that. For example our Easy Data Transform. However there are wrinkles because some of these formats are trees and some are tables. Flattening a tree into a table isn't too hard. But unflattening a table back into the same tree as the original is trickier. Has anyone got any good references on that?

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#38

Post by BadOakOx »

It seems, nobody is satisfied with the recent JSON diff utilities and everybody has a different take on it.

A few weeks back I started my semantic JSON compare too: https://paldys.github.io/semantic-json/

Your data stays in the browser. The list compare is pretty naive at the moment, and it doesn't allow key changes as Graphtage promises.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#39

Post by rmccue »

IshKebab wrote: post #33
acidbaseextract wrote: post #7

It's cool, but does seem quite slow. I'm diffing two 45kB CSVs on a fast computer and after 10 minutes I'm still at: Diffing: 0% ... 0/93195 [00:00

Tree diffing algorithms have very bad complexity (e.g. O(N^4)!) so this will probably only work on really small examples.

I have a use case for diffing trees, so would love to know of any optimal algorithms you may know of; I'm operating generally with less than 100 nodes, so it's not a huge concern, but I'm finding that discovering _any_ algorithms for this has been tough.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#40

Post by mariushn »

jkaptur wrote: post #20
pimlottc wrote: post #12

Cheers for making this a local tool. So many versions of this sort of tool are online-only, which is a non-starter for proprietary data.

My diff tool, diff.so, is a web app, but it doesn’t send the text to the server (unless you publish). I wish there were a technical mechanism that could guarantee and enforce that, and certify it to users.

It doesn't recognize JSON input. Could you please do this, auto-format it and show the diff similarly to Graphtage?
Post reply on HN