异或产生的思考

刚才做一道算法题,觉得它的解很有启发性,题目是:给定一个int数组,数组只有一个数字只出现了一次,其他都是成对出现的,数组是乱序的,请找出这个数字 https://leetcode.com/problems/single-number/description/

题目很简单,我的做法是先排序,然后再遍历入栈,若栈顶元素与当前元素相同则出栈,最后栈中剩余的那个数即为所求。时间复杂度为 O(nlogn),但是还有个非常精妙的做法是使用异或操作(xor:相同位为0,不同为1):将所有的数都异或,则最终的异或结果即为所求,时间复杂度为 O(n),我惊讶的是这个想法。

我想,这可能是一种非常快速且节约资源的对比算法,例如,假如我有两个无序数组,我想快速对比两个数组的元素是否相同,我并不需要非常准确的结果,我只希望其占用的系统资源尽量低。一个可行的做法是分别对两个数组中的元素做异或操作,然后对比结果,如果相同,则说明这两个数组“有可能相同”,如果不同,则说明这两个数组“一定不同”

之所以说有可能相同,是因为不同的数组也可能计算出相同的异或结果。例如:[1100, 0011] 的异或结果为 1111,但是 [1010, 0101] 的异或结果也是 1111,但它们确实是两个完全不同的数组

这很像布隆过滤器,它们都不要求绝对的准确率,但是对时间、空间复杂度却有很高要求,事实上,我觉得这两个方法从某种角度来看近乎是同一个方法。

我想到一个可能的应用:做数据校验

我们知道,数据在网络传输过程中是不稳定的,从小的说,一般数据报文在传输时会在报文头部或者尾部添加校验位,用于校验数据传输过程中是否出现错误,往大了说,一般在下载东西的时候,别人不仅会提供下载文件,还会提供一个校验文件,也是校验下载的内容是否完整的,这个校验文件一般使用一些数字签名算法例如md5等,我想应该也可以使用这种异或的简单算法:先将待下载文件平均切分成n份,然后对它们做异或,最终得到的异或结果就可以当作校验文件。用户下载完文件后,也将文件切分为n份,然后将得到的异或结果与别人提供的结果做对比,达到校验完整性的作用。

我觉得这个东西可能在加密方面也能有点应用,我甚至觉得它应该可以用来神经网络上,这样应该可以大大加快模型的推理速度

例如卷积神经网络,它本质就是一个模式匹配的过程,那异或不也是模式匹配吗,稍有不同的是,在卷积过程中,相同则为1,不同则为0,这与异或正好相反,不过可以使用 1-x 的方法来解决

再者,我甚至可以认为对多个数据异或的过程就是一个编码的过程,相当于做了数据降维,这个过程是否可以用在 encoder-decoder 模式的网络中

Leave a Comment