search

d3 / d3-hierarchy

2D layout algorithms for visualizing hierarchical data.
https://d3js.org/d3-hierarchy
ISC License
1.13k stars 315 forks source link

deterministic shuffling #190

Closed Fil closed 2 years ago

Fil commented 2 years ago

fixes #189 note: shuffling is here to increase performance (#83)

@jessihamel

mbostock commented 2 years ago

I think it might have been better to initialize the LCG in d3.pack rather than d3.packEnclose, or at least to support the option of passing in a seed so that the randomness is configurable. (Or, a way to disable the shuffling, and require the caller to do the shuffling instead.) This PR re-initializes the LCG each time d3.packEnclose is invoked, which happens many times during d3.pack.

Also, I’m kinda confused that d3.packEnclose returns different results based on shuffling, but I imagine it might be possible if there are multiple enclosing circles that are exactly or almost exactly the same size?

mbostock commented 2 years ago

And actually, I don’t think this PR affected the determinism of d3.pack? Because this PR changed the behavior of d3.packEnclose, but that’s not used by d3.pack—we use an internal method that doesn’t do shuffling.

Edit: Wait, no, it does use the shuffle, here:

https://github.com/d3/d3-hierarchy/blob/9e0ac436c2dde7819cc6fad29e5bfe426b6637b8/src/pack/siblings.js#L108

It’s just really confusing because we have two functions called “packEnclose” that do different things. 🤦

https://github.com/d3/d3-hierarchy/blob/9e0ac436c2dde7819cc6fad29e5bfe426b6637b8/src/pack/siblings.js#L48

Fil commented 2 years ago

pack calls packChildren which calls packEnclose; the unit test is the case mentioned in #189, where the result would be unpredictable—it uses d3.pack, and fails (sometimes) if you replace lcg by Math.random.

The shuffling is here just to improve performance (as you explained in https://github.com/d3/d3-hierarchy/issues/83), so I don't think it needs to be configurable.

For the problem of repeated lcg instanciation: we want all calls to packEnclose to be deterministic; maybe a solution is to inline the implementation: https://github.com/d3/d3-hierarchy/pull/192