`
harry
  • 浏览: 184563 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

使用位图做整型ID去重的一种方法

阅读更多

什么是位图算法

英文叫做bitmap,也有叫做bitset,Java SDK的util包中就包含一个BitSet的实现

《编程珠玑》中提到一个位图算法的例子:

输入:一个文件,里面大约有1千万行数据,每个数据是7位整数,同时每个数是唯一的,即不允许有2个数相同,这些整数不与其他任何数产生关联。

输出:将这个整数按升序排列,并生成到一文件中

限制:能够使用内存为1M,但是附存足够大,运行时间最多为几分钟,10s为最合适的时间。

用位图算法解决可以这么做:用含有1千万个位的整型数组来表示这个文件,文件中有的数据则标识为1,没有则标识为0,最后从第一位读至最后一位,即为有序的集合。

利用位图算法过滤重复ID

首先阐述一下算法思路:

使用一个足够大的位图,每一位表示一个整数的ID,有ID需要处理前,去位图里面查找对应的位是否为0,0表示未处理过,等处理过后就置成1.比如现在有个位图,二进制是00000000,来个id值是3,那么我们需要把位图置成00001000,如果重复的id值3再过来,通过判断这个位图的第三位是1就知道已经处理过了。

。。。。

 

详情请到我的新博客:

http://xiaofengmetis.com/?p=60

 

分享到:
评论

相关推荐

    Redis精确去重计数方法(咆哮位图)

    Redis中的精确去重计数方法,特别是在大数据场景下,是一个重要的议题。传统的Set或HyperLogLog数据结构在处理海量数据时可能存在空间效率低下或精度损失的问题。为了解决这些问题,咆哮位图(RoaringBitmap)...

    45丨位图:如何实现网页爬虫中的URL去重功能?1

    位图是一种特殊的数组,其中的每个元素只占用一个比特位,可以用来标记某个元素(如URL)是否存在。对于10亿个URL,如果用位图表示,只需大约125MB的内存(10亿/8字节/字节/位),这极大地降低了内存需求。位图的...

    使用位图创建工具栏

    位图创建工具栏是一种常见的设计方法,通过将多个功能图标集成在一个位图中,然后在程序运行时根据需要显示出来。下面我们将详细讨论如何使用位图创建工具栏以及相关知识点。 首先,我们需要理解位图(Bitmap)的...

    CBitmapButton位图按钮控件演示(两种方法+相应单击消息)(VC6)

    位图按钮控件在Windows应用程序开发中是一种常见的控件,它可以提供比普通文字按钮更丰富的视觉效果。在VC++环境中,我们通常使用MFC库中的`CBitmapButton`类来实现这种功能。在这个名为"BMPButton"的项目中,开发者...

    使用位图设计畸形界面

    总的来说,使用位图设计畸形界面是一个富有挑战性和创新性的过程,它需要设计师具备深厚的位图处理技巧,对视觉艺术的敏锐感知,以及敢于打破常规的勇气。通过这种方式设计出来的界面,不仅能吸引用户的注意力,还能...

    高级数据结构及应用之使用bitmap进行字符串去重的方法实例

    在高级数据结构及应用中,使用Bitmap进行字符串去重是一种常用的方法,这种方法可以快速判断某字符是否出现过,从而实现字符串去重。通过选择合适的底层数据结构,可以提高字符串去重的效率。在实际应用中,我们可以...

    一个使用位图自绘窗体的例子

    位图自绘是一种在计算机图形编程中常见的技术,主要用于创建复杂或自定义的用户界面。在Windows编程中,MFC(Microsoft Foundation Classes)库提供了一种便捷的方式来实现这一功能。本例中的“一个使用位图自绘窗体...

    在按钮上使用位图和文字

    - 对于添加文字,我们可以使用`BS_ICON`和`BS_TEXT`样式结合,或者创建一个包含位图和文本的单一资源。 2. **加载位图** - 使用`LoadImage`函数从资源中加载位图。这个函数可以处理`.bmp`文件或其他位图格式,并...

    三种位图的常见方法,深入分析位图结构

    本文将深入探讨位图的结构,并介绍三种常见的位图创建方法。这些方法涉及到位图的内部表示、颜色模式以及数据压缩,特别是RLE(Run-Length Encoding)压缩。 位图结构主要包括以下几个部分: 1. **文件头**:这是...

    NX二次开发-获取NX自身位图的两种方法

    第一种方法主要关注的是如何从NX的工具条中获取位图资源。 **步骤1.1:** 首先观察并找到希望获取位图的工具条按钮或图标。 **步骤1.2:** 在工具条空白区域右击,这一步可能会让人感到有些隐蔽,但却是关键步骤之一...

    使用位图资源的图形菜单

    在Windows编程中,图形用户界面(GUI)的设计与实现是一个重要的环节,而“使用位图资源的图形菜单”就是一种让界面更加生动、吸引用户的手段。位图资源是指在程序中存储的图像数据,可以是图标、按钮或者菜单项的...

    画透明位图的方法

    另一种方法是动态生成遮罩,这种方法适用于已知位图中存在特定颜色作为透明色的情况。在绘制时,程序会检测位图中的这种颜色,并将其转换为透明。这种方式减少了存储资源的消耗,但需要预先知道位图的透明色。 以下...

    C++ Builder不规则图像透明贴图(位图的透明显示)三种方法及简单动画v1.3源代码

    本项目提供了三种不同的方法来实现这一功能,并且包含了简单的动画效果。以下是这些方法的详细说明: 1. **Alpha通道透明**: Alpha通道是一种用于表示像素透明度的颜色通道。在位图中,每个像素除了红、绿、蓝...

    MFC 位图 按钮 多种方法

    你可以使用CButton的SetBitmap()函数,传入位图资源ID来设置按钮的位图。虽然这种方式相对简单,但它限制了自定义行为,例如,你可能无法轻松地改变按钮在不同状态下的位图,或者实现复杂的按钮动画效果。 为了更好...

    C#生成单色位图的方法.zip_C# 单色位图_C# 单色位图_C# 图片转单色_c#单色位图

    在C#编程中,生成单色位图是一种常见的图像处理技术,主要应用于简化图像、创建二值化图像或实现特定的视觉效果。本教程将详细解释如何使用C#来生成单色位图,并且添加信息头,使得图像更加规范且易于处理。 首先,...

    易语言位图特有创建方法源码

    在易语言中,可以使用`创建图形`命令来创建一个空的位图对象,这个命令会返回一个表示位图的句柄。例如: ```易语言 .位图句柄 = 创建图形(宽度, 高度) // 假设宽度和高度分别为100和200像素 ``` 这里的`宽度`和...

    一个位图动画程序

    位图动画程序是一种将一系列静态位图图像组合起来,通过快速连续播放来形成动态效果的技术。在计算机图形学中,位图(Bitmap)是图像的一种数据存储格式,它由像素阵列组成,每个像素有自己的颜色信息。位图动画通常...

    使用读取VC位图图像

    首先,位图(Bitmap)是一种常见的图像文件格式,用于存储像素数据。在Windows API中,我们可以使用GDI(Graphics Device Interface)库来处理位图。GDI提供了丰富的函数和结构体,使得在C++中操作位图变得可能。 ...

    海量数据去重排序bitmap(位图法)在java中实现的两种方法

    另一种实现位图法的方法是使用基本类型数组来存储位图。这种方法需要手动实现位图的操作,例如,设置位、获取位等。 下面是使用基本类型数组实现位图法的示例代码: ```java public class BitMap { public static...

Global site tag (gtag.js) - Google Analytics