做网站制作挣钱吗,北京商场营业时间,花卉电子商务网站开发,wordpress对接易支付宝在所有具有性能优化的数据结构中#xff0c;我想大家使用最多的就是 hash 表#xff0c;是的#xff0c;在具有定位查找上具有 O(1)的常量时间#xff0c;多么的简洁优美#xff0c;但是在特定的场合下#xff1a; ①#xff1a;对 10 亿个不重复的整数进行排序。 ②我想大家使用最多的就是 hash 表是的在具有定位查找上具有 O(1)的常量时间多么的简洁优美但是在特定的场合下 ①对 10 亿个不重复的整数进行排序。 ②找出 10 亿个数字中重复的数字。 当然我只有普通的服务器就算 2G 的内存吧在这种场景下我们该如何更好的挑选数据结构和算法呢
一、问题分析
这年头大牛们写的排序算法也就那么几个首先我们算下放在内存中要多少 G: (10 亿 * 32)/(102410241024*8)3.6G可怜的 2G 内存直接爆掉所以各种神马的数据结构都玩不起来了当然使用外排序还是可以解决问题的由于要走 IO 所以暂时剔除因为我们要玩高性能无望后我们想想可不可以在二进制位上做些手脚 比如我要对{1,5,7,2}这四个 byte 类型的数字做排序该怎么做呢我们知道 byte 是占 8 个 bit 位其实我们可以将数组中的值作为 bit 位的 keyvalue 用”01“来标识该 key 是否出现过下面看图 从图中我们精彩的看到我们的数组值都已经作为 byte 中的 key 了最后我只要遍历对应的 bit 位是否为 1 就可以了那么自然就成有序数组了。 可能有人说我增加一个 13 怎么办很简单一个字节可以存放 8 个数那我只要两个 byte 就可以解决问题了。 可以看出我将一个线性的数组变成了一个 bit 位的二维矩阵最终我们需要的空间仅仅是:3.6G/320.1G 即可要注意的是 bitmap 排序不是 N 的而是取决于待排序数组中的最大值在实际应用上关系也不大比如我开 10 个线程去读 byte 数组那么复杂度为:O(Max/10)。
二、代码
我想 bitmap 的思想大家都清楚了这一次又让我们见证了二进制的魅力当然这些移位都是位运算的工作了熟悉了你就玩转了。
1、Clear 方法将数组的所有 bit 位置 0
比如要将当前 4 对应的 bit 位置 0 的话只需要 1 左移 4 位取反与 B[0] 即可。 #region 初始化所用的bit位为0/// summary/// 初始化所用的bit位为0/// /summary/// param namei/paramstatic void Clear(byte i){//相当于 i%8 的功能var shift i 0x07;//计算应该放数组的下标var arrindex i 3;//则将当前byte中的指定bit位取0后其他对方数组bit位必然不变这就是 1 的妙用var bitPos ~(1 shift);//将数组中的指定bit位置一 “ 操作”a[arrindex] (byte)(bitPos);}#endregion2、Add 方法将 bit 置 1 操作
同样也很简单要将当前 4 对应的 bit 位置 1 的话只需要 1 左移 4 位与 B[0] | 即可。 #region 设置相应bit位上为1/// summary/// 设置相应bit位上为1/// /summary/// param namei/paramstatic void Add(byte i){//相当于 i%8 的功能var shift i 0x07;//计算应该放数组的下标var arrindex i 3;//将byte中的 1 移动到i位var bitPos 1 shift;//将数组中的指定bit位置一 “| 操作”a[arrindex] | (byte)bitPos;}#endregion3、Contain 方法判断当前 bit 位是否是 1
如果看懂了 Clear 和 Add我相信最后一个方法已经不成问题了。 #region 判断当前的x在数组的位中是否存在/// summary///判断当前的x在数组的位中是否存在/// /summary/// param namei/param/// returns/returnsstatic bool Contain(byte i){var j a[i 3] (1 (i 0x07));if (j 0)return false;return true;}#endregion最后上总的代码 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class Program{static byte n 7;static byte[] a;public static void Main(){//节省空间的做法a new byte[(n 3) 1];for (byte i 0; i n; i)Clear(i);Add(4);Console.WriteLine(插入4成功);var s Contain(4);Console.WriteLine(当前是否包含4:{0}, s);s Contain(5);Console.WriteLine(当前是否包含5:{0}, s);Console.Read();}#region 初始化所用的bit位为0/// summary/// 初始化所用的bit位为0/// /summary/// param namei/paramstatic void Clear(byte i){//相当于 i%8 的功能var shift i 0x07;//计算应该放数组的下标var arrindex i 3;//则将当前byte中的指定bit位取0后其他对方数组bit位必然不变这就是 1 的妙用var bitPos ~(1 shift);//将数组中的指定bit位置一 “ 操作”a[arrindex] (byte)(bitPos);}#endregion#region 设置相应bit位上为1/// summary/// 设置相应bit位上为1/// /summary/// param namei/paramstatic void Add(byte i){//相当于 i%8 的功能var shift i 0x07;//计算应该放数组的下标var arrindex i 3;//将byte中的 1 移动到i位var bitPos 1 shift;//将数组中的指定bit位置一 “| 操作”a[arrindex] | (byte)bitPos;}#endregion#region 判断当前的x在数组的位中是否存在/// summary///判断当前的x在数组的位中是否存在/// /summary/// param namei/param/// returns/returnsstatic bool Contain(byte i){var j a[i 3] (1 (i 0x07));if (j 0)return false;return true;}#endregion}}
