V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
wdc63
V2EX  ›  程序员

由两个整数生成一个独特的整数

  •  
  •   wdc63 · 2022-09-11 15:10:07 +08:00 · 3669 次点击
    这是一个创建于 564 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我有两个整数 a 、b 。我想得到一个独特的整数 c ,让 a 、b 任何一个发生变化时,c 的值都是独特唯一的,且不需要反运算,即无需通过 c 得到 a 、b 。 我想到的方法是 a*(b 的位数+1) + b ,例如 123,234=123*1000+234=123234 。 由于我的程序中有大量的这种运算,请问各位大佬对此有没有经验,提供一个开销最小最小最小的算法。

    33 条回复    2022-10-08 14:37:26 +08:00
    learningman
        1
    learningman  
       2022-09-11 15:15:16 +08:00
    你想的这个,(123,234)和(12.3234)得到的结果是一样的
    推荐随便找个 StringHash 算法
    wdc63
        2
    wdc63  
    OP
       2022-09-11 15:25:23 +08:00
    @learningman 只可能是整数,但是我发现有负数存在也会出现错误。另外在网上找到了这是个数学问题,配对函数,其中最出名的康拓尔配对函数:Pi(x,y)=(x+y)(x+y+1)/2+y ,但是也只支持自然数。
    lsylsy2
        3
    lsylsy2  
       2022-09-11 15:27:19 +08:00
    让 a 、b 任何一个发生变化时,c 的值都是独特唯一的,且不需要反运算,即无需通过 c 得到 a 、b 。

    你这其实是很经典的数字签名的场景,不过有一个问题:“独特唯一”其实是没有必要的,哪怕是网银的金融级别,也只是“重复的概率小到忽略不计”而已。

    你的“运算量”和“对独特唯一的要求”具体是多少?根据这两个要求挑选一个合适的签名算法或者哈希算法就行
    copper20
        4
    copper20  
       2022-09-11 15:28:18 +08:00   ❤️ 3
    假设你的 a b c 都是 int64 ,那么这个需求是不可能实现的。这个函数

    f: int64 x int64 -> int64

    定义域的基数远大于陪域的基数,就不可能是一个单射,是必然会发生碰撞的

    如果 a b c 都来自全体自然数集,那按康托尔的那个配对函数来就行了
    wdc63
        5
    wdc63  
    OP
       2022-09-11 15:31:59 +08:00
    @copper20 有负数,康托尔算法不支持。另外 a 、b 都在 10W 以下,合理的算法 c 值应该不会超出 int32 的范围吧。
    copper20
        6
    copper20  
       2022-09-11 15:32:40 +08:00
    @copper20 如果 a b c 都来自全体整数的话就可以先把整数集映射一一映射到自然数集然后再套康托尔那个函数

    if z >= 0, f(z) = 2 * z
    if z < 0, f(z) = 2 * -z - 1
    wdc63
        7
    wdc63  
    OP
       2022-09-11 15:32:41 +08:00
    @lsylsy2 需要大概单线程 1 毫秒 10 万级别
    wdc63
        8
    wdc63  
    OP
       2022-09-11 15:34:28 +08:00
    @copper20 谢谢,我按这个试试效率以及会不会溢出。
    wxf666
        9
    wxf666  
       2022-09-11 15:47:32 +08:00
    @wdc63 a, b 都在 10W 以下,那么共有 10W ^ 2 = 100 亿 种可能 > uint32 ≈ 42 亿,不可能不超出 int32 范围?
    zk8802
        10
    zk8802  
       2022-09-11 15:51:07 +08:00
    单线程每秒生成 10 ^ 8 个数,不考虑程序中具体实现和调用的开销的话(例如 CPython 就别想了),一般的快速哈希算法应该都可以满足楼主的要求。

    随便举一个例子: https://github.com/Cyan4973/xxHash
    Jooooooooo
        11
    Jooooooooo  
       2022-09-11 15:53:27 +08:00
    不要自己发明这种算法.
    LaTero
        12
    LaTero  
       2022-09-11 15:54:17 +08:00 via Android
    想要结果唯一,那结果一定是输入的位数的两倍以上。最直觉的方法,假设 a 和 b 32 位,结果 64 位
    ((int64)a << 32)+(int64)b
    速度非常快,和正负数或者补码 /反码无关
    wdc63
        13
    wdc63  
    OP
       2022-09-11 16:03:44 +08:00
    @LaTero 谢谢,你的算法应该不能保证结果是唯一的。
    wdc63
        14
    wdc63  
    OP
       2022-09-11 16:04:21 +08:00
    static int szudzikPair(int x, int y)
    {

    return (x >= y ? (x * x) + x + y : (y * y) + x);
    }

    static int szudzikPairSigned(int x, int y)
    {

    int a = (x >= 0 ? 2 * x : (-2 * x) - 1);
    int b = (y >= 0 ? 2 * y : (-2 * y) - 1);
    return szudzikPair(a, b) / 2;
    }

    5800x 单线程 10w 次( x 、y 均为负数)大概 3ms
    wdc63
        15
    wdc63  
    OP
       2022-09-11 16:06:03 +08:00
    @wdc63 debug 模式
    wxf666
        16
    wxf666  
       2022-09-11 16:11:55 +08:00
    @wdc63

    > @LaTero 的算法应该不能保证结果是唯一的

    这不就是你的 a*(b 的位数+1) + b 的二进制版么。。

    要不,举个反例?
    wdc63
        17
    wdc63  
    OP
       2022-09-11 16:12:01 +08:00
    @wxf666 是的,那使用 ulong 就行。
    wdc63
        18
    wdc63  
    OP
       2022-09-11 16:12:32 +08:00
    @wxf666 存在负数就会出现碰撞。
    LaTero
        19
    LaTero  
       2022-09-11 16:16:47 +08:00 via Android
    @wdc63 怎么碰撞?这算法这不就是把两个 32 位拼成 64 位? a 在高 32 位 b 在低位,别说负数,这算法浮点数也能用(可能会有 NaN 等)
    crab
        20
    crab  
       2022-09-11 16:17:38 +08:00
    类似用鼠标消息坐标 高低端存储 xy 坐标
    LaTero
        21
    LaTero  
       2022-09-11 16:22:35 +08:00 via Android
    @wdc63 另外数学版本 f(a,b)=a*2^32+b, a,b∈Z∩[-2^31, 2^31-1]也不会碰撞
    wdc63
        22
    wdc63  
    OP
       2022-09-11 16:28:14 +08:00
    @LaTero 噢,我理解错了,不好意思。
    xuanbg
        23
    xuanbg  
       2022-09-11 16:34:47 +08:00
    不对 A 、B 的性质加以限制的话,无论是加法、乘法还是他们的组合,无论如何组合,都无法保证结果的唯一性。
    wdc63
        24
    wdc63  
    OP
       2022-09-11 16:35:25 +08:00
    @LaTero 确实更快,谢谢
    chenzhekl
        25
    chenzhekl  
       2022-09-11 19:45:08 +08:00
    lz 给的算法也不是一个单射,反例:(123, 234) -> (123234), (12, 3234) -> (123234)。 @copper20 提到的 Cantor pairing function 应该是最好的选择了吧,不然就用哈希函数,然后自己处理极小概率的哈希碰撞。
    wdc63
        26
    wdc63  
    OP
       2022-09-11 20:14:19 +08:00
    @chenzhekl 我用的 LaTero 的算法: ((int64)a << 32)+(int64)b ,实测比康托尔配对函数快一倍,而且康托尔配对函数在 int32 范围内最大支持到 25000 左右。
    mlhadoop
        27
    mlhadoop  
       2022-09-11 20:55:33 +08:00
    + 运算符 不就好了。?
    mengzhuo
        28
    mengzhuo  
       2022-09-11 21:47:45 +08:00
    这个简单,wyhash 的原理,设大质数 P1 P2

    h1, h2 = (a xor P1) * (b xor P2)
    hash = h1 * h2

    https://github.com/wangyi-fudan/wyhash
    lrjia
        29
    lrjia  
       2022-09-12 00:22:51 +08:00
    直接用位运算,可能还会更快一些 ((int64)a << 32) & (int64)b
    mxT52CRuqR6o5
        30
    mxT52CRuqR6o5  
       2022-09-12 00:24:06 +08:00 via Android
    直接连起来不就好了
    yhvictor
        31
    yhvictor  
       2022-09-12 12:05:23 +08:00 via iPhone
    @wdc63 10w 以内……
    那就 a*10w+b 不就得了
    正负都算上就 20w
    aguesuka
        32
    aguesuka  
       2022-09-13 12:09:48 +08:00
    long merge(int a, int b){
    int pair[2] = {a, b};
    return *((long*) &pair);
    }

    这个方法不用位运算, 也许是最快的. 不过也许您应该考虑使用 struct 或者 union
    wdc63
        33
    wdc63  
    OP
       2022-10-08 14:37:26 +08:00
    @yhvictor 你这个算法鲁棒性不行,0*100000+100000 = 1*100000+0 ,况且不是一定完完全全十万内,绝大部分情况是,有少概率情况数据可能超过。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1989 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 61ms · UTC 16:21 · PVG 00:21 · LAX 09:21 · JFK 12:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.