假设我们有两个长,x和y.什么运营商或涉及x和y会产生另一个长,Z,这是最有可能等于应用相同的运算符或函数X和Y的不同的结果函数？
例如:增加将是一个糟糕的选择.1 + 4 = 5,但2 + 3也等于5.
编辑:让我解释为什么我问这个问题.我正在制作一个太空RPG游戏.游戏的环境(solarsystems)将从两个种子程序生成.这些种子由宇宙中系统的x和y坐标组成.所以玩家在冒险过程中很可能会遇到(500,501)和(501,500)系统.我需要一种方法来使这些太阳系产生独特.但是,我想确保尽可能多的坐标对会产生独特的种子.
编辑2:我测试了给我的两个解决方案.Accipitridae的答案远远优于Artelius的答案.以下是测试解决方案的代码:
HashSet<Long> set = new HashSet<Long>();
for(int x=0; x<1000; x++)
for(int y=0; y<1000; y++)
//I commented out one of the solutions at a time
set.add((long)(((x&0x7FFFFFFF) << 33) | ((y&0x7FFFFFFF) << 2) | ((x>>>62) & 2) | (y>>>63)));//Artelius
set.add((long)(x - y * 7046029254386353131l));//Accipitridae
System.out.println(set.size());
从HashSet的大小,我可以知道通过每种方法生成了多少独特的种子.对于这些参数,Artelius的解决方案产生了2048个独特的长度,而Accipitridae产生了1000000个,这意味着根本没有碰撞.
谢谢大家努力解决这个问题.:)
如果(x1, y1)和(x2, y2)是两个随机对输入,然后让f1 = f(x1,y1)与f2 = f(x2,y2).
你想做的是最小化
P( f(x1,y1) = f(x2,y2) )
= P(f1 = f2)
= sum for i in [LONG_MIN ... LONG_MAX]
of P(f1 = i) * P(f2 = i)
= sum for i in [LONG_MIN ... LONG_MAX]
of P(f1 = i)^2
因此,您希望最小化每个函数输出概率的平方和.由于概率之和必须为1,我们知道:
sum for i in [LONG_MIN ... LONG_MAX]
of P(f1 = i)
= 1
而且我们也知道,对于所有i,P(f1 = i)介于0和1(包括)之间.直观地说,最小化P(f1 = f2)是使概率分布f1尽可能均匀的问题.(这可以通过数学方法证明,但对于这个问题并不重要.)理想情况下,P(f1 = i)并且P(f1 = j)对于所有长期i和长期来说应该是相同的j.
现在让我们看看x和y的本质的一些不同的可能性.
首先是一般情况,其中x和y均匀分布在long的范围内.(换句话说,x是同样可能是任何一个长就可以了.所以为y.)在这种情况下,我们可以让f(x, y) = x+y,或者f(x,y) = x-y,或者f(x,y) = x XOR y,甚至f(x,y) = x和(假设正常的整数溢出),我们发现,我们有一个统一分布式f也是,这意味着这些功能都是"最优的".
但是这个f(x,y) = x例子告诉你,你在这里获得的确没有那么多.
但是,在实践中,您的x和y可能不会均匀分布.例如,如果x和y都是从范围[0,9999]中随机绘制的,那么使用f(x,y) = x + y * 10000将始终为不同的输入产生不同的输出.
如果在每个(x,y)对中,x和y很可能彼此靠近,例如(1240,1249),(1,3),( - 159720,-159721),那么f(x,y) = x实际上是相当的良好的候选功能.
如果x和y"可能不是很大",那么你应该将x的16个低位与y的16个低位组合,即f(x,y) = ((x&0xFFFF) << 16) | (y&0xFFFF),因为较低的位将比高位更均匀地分布.
如果x和y从不为负,这种方法非常有效.但如果它们是,则符号位(表示该数字是正数还是负数)可能比16个低位中的一些更均匀地分布.所以你可能想要使用它.例如
f(x,y) = ((x&0x7FFF) << 17) | ((y&0x7FFF) << 2) | ((x>>30) & 2) | (y>>31)
由于"可能不是很大"的情况很常见,我认为这个功能实际上通常会很好.
我喜欢Artelius的答案和分析.特别是建议使用
f(x,y)= x + y*K.
对于某些常数K很有意思,我想补充一些想法.我在这里做的不是新的,而是与Fibonacci散列非常密切相关 ,我认为这是由Knuth提出的.
如果我们使用64位整数,那么碰撞f(x1,y1)= f(x2,y2)意味着
0 =(dx + dy*K)mod 2 64,
其中dx = x1 - x2和dy = y1 - y2.这是一样的
K = -dx*dy -1 mod 2 64,
其中dy -1是模数逆模2 64.如果我们想选择K使得f(x1,y1)!= f(x2,y2),只要差异dx和dy都很小,那么我们必须选择K这样
K = -dx*dy -1 mod 2 64,
没有解决方案,dx和dy都很小.这可以通过例如选择接近phi*2 64的 K来实现,其中phi =(sqrt(5)-1)/ 2是黄金比率.黄金比率具有非常特殊的连续分数扩展,即在某种意义上它是一个很难用一小部分很好地逼近的数字.
因此,对于64位无符号整数,可以使用以下函数
f(x,y)= x + y*11400714819323198485;
或等效使用带符号的64位整数时
f(x,y)= x - y*7046029254386353131;