网站上线 文案,wordpress手机cms,wordpress编辑器排版,销售类电商网站如何做优化LSH是我同学的名字#xff0c;平时我会亲切的称呼他为离骚#xff0c;老师好#xff0c;左移#xff08;leftshift#xff09;#xff0c;小骚骚之类的#xff0c;最近他又多了一个新的外号#xff1a;局部敏感哈希#xff08;Locally sensitive hashing)。 好了… LSH是我同学的名字平时我会亲切的称呼他为离骚老师好左移leftshift小骚骚之类的最近他又多了一个新的外号局部敏感哈希Locally sensitive hashing)。 好了废话不多说直接转入正题 『写在前面』局部敏感哈希是一种NOIP禁用的算法因为使用了随机数若不感兴趣就无需往下看了。 『什么是LSH』 LSH就是局部敏感哈希听着名字就知道和普通的哈希不一样具体哪里不一样就先吊吊你的胃口稍后再说。先来了解LSH的各方面性能 首先先来思考一个问题 如果给你一堆数字然后查找一个数是否在这堆数中存在或者找到一个最相似的数字你会怎么办 Answer 1首先我们一定会想到线性查找直白的来说这简直就是最慢的一种方法直接用数组存好后一个一个来判断当数据规模小的时候还好但是到了规模很大的时候比如说有1亿个数据时还能在规定的时间内找到吗 2)其次我们会想到二分查找这种算法运用了分治的思想将O(n)的时间复杂度降低到了O(log n)的时间复杂度不过还需要排一次序但是也费不了多少时间这种方法相对来说是很可观的但是有时还满足不了我们的需求。 3这种想法也和 2差不了多少但是功能更强大能够实现维护插入删除等一系列操作没错它就是二叉查找树一种用树结构存储的方法但是有时却很慢放张图细细体会吧~ 比如说要查找4那么就一定会全部遍历一遍显然还是二分查找更快。 4红黑树其他平衡树平衡树的种类很多这些树能有效避免上图的情况小编曾写过一篇红黑树博客想看戳这里里面也有详细的二叉查找树讲解。 5好用的当然在后面——哈希算法这种算法只要操作一遍数后就可以做到O(1)的速度查找但是问题却在于如何处理哈希冲突有关哈希的讲解戳这里适当的mod正是关键但是往往我们处理不好这个问题引起很多问题比如2000和1000同时对10取模后将都是0原本差别很大但是现在没有了差别再比如1008和1000对10取模后分别是8和0原本差别不大但是现在差别相对变大了很多因此便请出了局部敏感哈希。 局部敏感哈希最大的特点在于保留原来的特性虽然不一定能完全避免哈希冲突但是能比一般哈希保留的更好保持最大可能的相似度。 『哈希思想及实现』小编表示这是一个高冷的话题离我太遥远等我学的更好时会自己写的现在就先放上大牛的博客吧局部敏感哈希。转载于:https://www.cnblogs.com/TFLS-gzr/p/11120479.html
