1

I have a problem where I am trying to find the relationship between parts and the parts that make them up. Like if a boiler is made with two side plates and one bottom plate, and the side plates have five bolts and the bottom four, than a tractor has $2*5 +1*4 = 14$ bolts. Except think 3.5 million parts and possibly ten levels deep.

Anyways, We want to prevent repeating interactions. If engines a and b require boilers we don't want to print out how many bolts are in the boiler twice.

Background out of the way, this is what I came up with. I generated the square roots of the first fifteen primes. My theory is that a linear combination of integers from one to 3.5 million multiplied by these will form an orthoginal set.

I set up the structure like a tree, repeated parts and all.

Tree Structure

Then I go down to the deepest level. Say the connection between part 1 and part 5. My hash fuction between the two is the part number of the lower level times the first prime, so $1*\sqrt2$.

each level I go up I sum the hash functions for the children with the current lowest part number multiplied with the Nth prime, where N is the highest N of all its children plus one.

So $H(3, 7) = 7 * \sqrt5+H(7, 11)+H(7,5)+H(7, 2)$

with $\sqrt5$ being the 3rd prime, and $H(7, 2)$ having a "depth" of 2

The way that you compute the connection between parts not directly connected is the sum of the hashes of the connections that contain that part minus the sum of connections from there.

So $H(3, 11) = H(3, 7) - H(7, 11)$

And $H(12, 7) = H(12, 3) - H(3, 7) + H(12, 13) - H(13, 7)$

$= H(12, 3) - H(3, 7) + H(12, 13) - (H(13, 10) - H(10, 7))$

$= H(12, 3) - H(3, 7) + H(12, 13) - H(13, 10) + H(10, 7)$

I calculated all the first degree connections and some higher degree ones.

Table of calculations

The question is, does a hash uniquely determine not only a relationship between the two parts, but also where on the tree they are, so that if the indicies are the same and hashes different the numbers should be summed like the total number of bolts above. And if two hash numbers are identical they must be talking about the same two indicies and suggest that they are repeated?

kleineg
  • 1,795

1 Answers1

1

First, a potential easier solution: you already have unique hashes, in the form of your (pairs of, though I'm not sure why you're using pairs exactly) part IDs: why not just use them? While building your output, just keep track of which part IDs you've already run your recursion on and how many bolts they needed, and if you come across a part ID that you've already calculated, just use that value (and don't print the duplicate).

Now, to answer your actual question: yes, in theory, but with implementation issues. Your hashing should never produce exact duplicates: the linear independence of the $\sqrt{p}$ over $\mathbb{Q}$ combined with the fact that a part's highest-$p$ coefficient is exactly its part ID. However you are not working in an infinite-precision setting, so it's possible that you'll have clashes in cases where the theoretical hashes are not exactly equal, but are closer than the precision that you are operating to.

user3482749
  • 6,660
  • The problem is that we do need the relationship between the higher level parts and the lower level ones, and that depends on the branch closer to the trunk. Once we have perfect copies of the structure we can disregard everything within. But we do not know where the copy begins, and it is billions of times more likely to have a incorrect duplicate flag by solely depending on part and component part and quantity. We have seen cases where we have seen the same quantities for the same indices on different branches. – kleineg Jan 22 '21 at 01:06
  • Given that there is a chance of incorrectly flagging a correlation for removal, is there some precision that would minimize this chance? – kleineg Jan 22 '21 at 01:07
  • My worry is that since we will generate so many, if there is an even distribution of numbers, that the chance of a duplicate is very high. In a room of 40 people the likelihood that at least two people will have the same birthday is quite high, and there is only $1/365$ chance of a match between any two people, far less than the number of people. This could be mitigated by comparing both the two indices and the hash as above, but I was hoping for less information being stored.. – kleineg Jan 22 '21 at 01:15
  • And as for why there is a pair, that is how the data is stored. A part id, the part id of a component, and how many of those components are used. – kleineg Jan 22 '21 at 01:42
  • Your first comment makes no sense to me. If it's the same part, it's the same part, regardless of anything else. There's no possibility of a collision using the part IDs. For your second: Not that isn't silly. Your third comment is essentially nonsense, because we aren't drawing our part IDs randomly. For your fourth: there's no need to keep it that way. What you care about is how many bolts (in total) go into each part. How your input data is stored has essentially no relation to how your output data should be stored. – user3482749 Jan 22 '21 at 16:38
  • More generally, if you do want to keep to this (rather strange) approach, why make your hashes numbers? Just store them as vectors instead, and remove the issue entirely. – user3482749 Jan 22 '21 at 16:42
  • We can have more than one path where we start at part a and end at part b. In the tractor example above we need to keep data for boiler-side plate-bolt and boiler-bottom plate-bolt. But we have to remove any that take the same path. – kleineg Jan 24 '21 at 06:36
  • As for encoding them in vectors, I know of no easy way to do that in the programming language I'm using. single float comparison is lightning fast (the entire program may run 1-2 days) and takes little memory (I've seen inefficient data storage blow up a 64GB RAM server) – kleineg Jan 24 '21 at 06:39
  • @kleineg For your first point: no you don't. You just need to calculate the total for each part. For your second: float comparison and arithmetic is definitely not going to be faster than vector comparison and construction. If your programming language can't handle vectors, I suggest you change to one made in the last 50 years. – user3482749 Jan 24 '21 at 17:29