首页
学习
活动
专区
工具
TVP
发布

✅上亿数据,限制1G内存,如何去重?

位图的优势空间效率优势:为徒极大的节省了存储空间,对于大量稀疏数据,特别是当元素数量远大于实际存在的项时,相比较于使用传统的列表、集合等数据结构,位图的空间占用极小。...查询速度:由于内存访问时按字节或字进行的。因此对单个元素的存在性检查时间复杂度为O(1),即常量时间,非常快速。...了解了什么是BitMap,那么我们就可以使用BitMap来解决大量数据去重的问题40亿个无符号整数内存只有1G,如果要去重的话,如何解决假设40亿个无符号整数数据都是10位的话,如果直接使用内存来存储,...总字节数转换为GB:4*4000000000 / 1024 / 1024 /1024 = 14.9 GB考虑到其中有一些重复的数据,即使这样1G的空间基本上也是不够的。...如果使用位图的话,40亿数据存储所需要的内存大概也就是 476M40亿无符号整数数据的总字节数是4000000000 字节,在位图中1个10位的无符号整数可以使用1 bit表示,然后1 字节 = 8 位

3200
您找到你想要的搜索结果了吗?
是的
没有找到

上亿数据,限制1G内存,如何去重?

位图的优势 空间效率优势:为徒极大的节省了存储空间,对于大量稀疏数据,特别是当元素数量远大于实际存在的项时,相比较于使用传统的列表、集合等数据结构,位图的空间占用极小。...查询速度:由于内存访问时按字节或字进行的。因此对单个元素的存在性检查时间复杂度为O(1),即常量时间,非常快速。...了解了什么是BitMap,那么我们就可以使用BitMap来解决大量数据去重的问题 40亿个无符号整数内存只有1G,如果要去重的话,如何解决 假设40亿个无符号整数数据都是10位的话,如果直接使用内存来存储...总字节数转换为GB:4*4000000000 / 1024 / 1024 /1024 = 14.9 GB 考虑到其中有一些重复的数据,即使这样1G的空间基本上也是不够的。...如果使用位图的话,40亿数据存储所需要的内存大概也就是 476M 40亿无符号整数数据的总字节数是4000000000 字节,在位图中1个10位的无符号整数可以使用1 bit表示,然后1 字节 = 8

8910

Linux内存描述之高端内存--Linux内存管理(五)

但是,当Linux物理内存超过1G时,线性访问机制就不够用了,因为只能有1G内存可以被映射,剩余的物理内存无法被内核管理,所以,为了解决这一问题,Linux把内核地址分为线性区和非线性区两部分,线性区规定最大为...当物理内存大于1G的时候, 内核是不能完全用低端内存管理全部物理内存的, 所以低端内存剩下的部分就是高端内存了, 高端内存没有直接映射的, 是动态映射到内核空间的....Linux内核高端内存的由来 2.1 为什么需要高端内存? 高端内存是指物理地址大于 896M 的内存。对于这样的内存,无法在“内核直接映射空间”进行映射。...1G) 2.3 Linux内核高端内存的理解 前 面我们解释了高端内存的由来。...引入高端内存映射这样一个概念的主要原因就是我们所安装的内存大于1G时,内核的1G线性地址空间无法建立一个完全的直接映射来触及整个物理内存空间,而对于80x86开启PAE的情况下,允许的最大物理内存可达到

12K22

Linux - Linux内存管理

移除交换空间 ---- 概念 内存管理是Linux系统重要的组成部分。...为了解决内存紧缺的问题,Linux引入了虚拟内存的概念。为了解决快速存取,引入了缓存机制、交换机制等。...当需要用到原始内容时,这些信息会被重新从交换空间读入物理内存Linux内存管理采取的是分页存取机制。...要深入了解Linux内存运行机制,需要知道下面提到的几个方面。 首先,Linux系统会不时地进行页面交换操作,以保持尽可能多的空闲物理内存。...其次,Linux进行页面交换是有条件的,不是所有页面在不用时都交换到虚拟内存中,Linux内核根据“最近最经常使用”算法,仅仅将一些不经常使用的页面文件交换到虚拟内存中。

50.9K41

Linux内存描述之内存节点node--Linux内存管理(二)

CPU访问本地内存的速度比访问远程内存的速度要快 Linux适用于各种不同的体系结构, 而不同体系结构在内存管理方面的差别很大....因此linux内核需要用一种体系结构无关的方式来表示内存....因此linux内核把物理内存按照CPU节点划分为不同的node, 每个node作为某个cpu结点的本地内存, 而作为其他CPU节点的远程内存, 而UMA结构下, 则任务系统中只存在一个内存node, 这样对于...系统中的NUMA结点都是从0开始编号的 3.1 linux-2.4中的实现 pgdat_next指针域和pgdat_list内存结点链表 而对于NUMA结构的系统中, 在linux-2.4.x之前的内核中所有的节点...-3.x~4.x的实现 node_data内存节点数组 在新的linux3.x~linux4.x的内核中,内核移除了pg_data_t的pgdat_next之指针域, 同时也删除了pgdat_list链表

7.5K20

Linux内存描述之内存页面page--Linux内存管理(四)

1 Linux如何描述物理内存 Linux把物理内存划分为三个层次来管理 层次 描述 存储节点(Node) CPU被划分为多个节点(node), 内存则被分簇, 每个CPU对应一个本地物理内存, 即一个...内存中的每个节点都是由pg_data_t描述,而pg_data_t由struct pglist_data定义而来, 该数据结构定义在include/linux/mmzone.h, line 615, 每个结点关联到系统中的一个处理器...简单来说, 页是一个数据块, 可以存放在任何页框(内存中)或者磁盘(被交换至交换分区)中 我们今天就来详细讲解一下linux下物理页帧的描述 2 页帧 内核把物理页作为内存管理的基本单位....因此在后来linux-2.4.x的更新中, 删除了这个字段, 取而代之的是page->flags的最高ZONE_SHIFT位和NODE_SHIFT位, 存储了其所在zone和node在内存区域表zone_table...3.2 内存页标识pageflags 其中最后一个flag用于标识page的状态, 这些状态由枚举常量enum pageflags定义, 定义在include/linux/page-flags.h?

7.9K11

Linux内存描述之概述--Linux内存管理(一)

2 (N)UMA模型中linux内存的机构 Linux适用于各种不同的体系结构, 而不同体系结构在内存管理方面的差别很大. 因此linux内核需要用一种体系结构无关的方式来表示内存....Linux内核通过插入一些兼容层, 使得不同体系结构的差异很好的被隐藏起来, 内核对一致和非一致内存访问使用相同的数据结构 2.1 (N)UMA模型中linux内存的机构 非一致存储器访问(NUMA)模式下...而内存管理的其他地方则认为他们就是在处理一个(伪)NUMA系统. 2.2 Linux物理内存的组织形式 Linux把物理内存划分为三个层次来管理 层次 描述 存储节点(Node) CPU被划分为多个节点..., 我们会在后面典型架构(x86)上内存区域划分详细讲解x86_32上的内存区域划分 因此Linux内核对不同区域的内存需要采用不同的管理方式和映射方式, 为了解决这些制约条件,Linux使用了三种区:...2.6 高端内存 由于能够被Linux内核直接访问的ZONE_NORMAL区域的内存空间也是有限的,所以LINUX提出了高端内存(High memory)的概念,并且允许对高端内存的访问

6.8K30

Linux内存描述之内存区域zone--Linux内存管理(三)

因此相对于任何一个CPU访问本地内存的速度比访问远程内存的速度要快, 而Linux为了兼容NUMAJ结构, 把物理内存相依照CPU的不同node分成簇, 一个CPU-node对应一个本地内存pgdata_t...Linux使用enum zone_type来标记内核所支持的所有内存区域 3.1 内存区域类型zone_type zone_type结构定义在include/linux/mmzone.h, 其基本信息如下所示...,ffff,f000这128T地址用于用户空间;而0xffff,8000,0000,0000以上的128T为系统空间地址, 这远大于当前我们系统中的内存空间, 因此所有的物理地址都可以直接映射到内核中,...位系统中, Linux内核虚拟地址空间只有1G, 而0~895M这个986MB被用于DMA和直接映射, 剩余的物理内存被成为高端内存....Linux必须处理如下两种硬件存在缺陷而引起的内存寻址问题: 一些硬件只能用某些特定的内存地址来执行DMA 一些体系结构其内存的物理寻址范围比虚拟寻址范围大的多。

8.8K31

Linux内存管理

本篇介绍 本篇介绍下Linux内存管理,用系统角度看内存的寻址和分配机制。 内容介绍 内存管理应该是系统中最难的模块之一了,而且历史也悠久,就先来简单回顾下。...分页机制可以完全避免内存碎片问题么? 公布下答案: 的确有分页机制就可以完全不需要分段机制,目前linux是在分段的基础上实现了分页,这个也有考虑到是兼容性问题。...,如果没指定fd,那就是匿名映射,可以简单理解成就是分配了一块内存,当malloc大于128kb时候就不用brk了,直接mmap映射分配内存了。...mmap流程如下: image.png 缺页异常 linux 是在不得不使用物理内存的时候才会分配物理内存。这句话该怎么理解呢?...这儿需要解释下MemAvailable 一般会大于等于MemFree,因为前者除了空闲内存外,还包含活跃的文件映射页面,不活跃的文件映射页面,可回收的slab页面以及其他可回收的内核页面。

13.4K50

Linux 内存管理

操作系统内存管理包括物理内存管理和虚拟内存管理:       我们这篇主要介绍Linux的虚拟内存管理。...Linux仅把可执行映像的一小部分 装入物理 内存. 当需要访问未装入的页面时 . 系统产生一个缺页中断 , 把需要的页读入 物理内存。 ...把页装入物理内存。   ·   五.swap对换空间 ----      32位Linux系统的每个进程可以有4 GB的虚拟 内存空间 ....它监测内核中的 pages_high 和pages_low 标记,如果空闲内存空间值小于 pages_low 值, kswwapd 进程开始扫描并尝试每次回收 32 个页面,如此重复直至空闲内存空间大于...例如:32位Linux的每个用户进程都可以访问4GB的线性地址空间, 而实际的物理内存可能远远少于4GB. 采用分页机制 ,Linux仅把可执行映像的一小部分装入物理内存

7.4K10

Linux内存修改

虚拟内存是为了满足物理内存不足采用的策略,利用磁盘空间虚拟出一块逻辑内存,用作虚拟内存的空间也就是交换分区。...作为物理内存的扩展,Linux会在物理内存不足时,使用交换分区的逻辑内存,内核会把暂时不用的内存块信息写到交换空间,这样物理内存就得到了释放,这块儿内存就可以用于其他目的,而需要用到这些内容的时候,这些信息就会被重新从交换分区读入物理内存...Linux内存管理采用的是分页存取机制,为了保证物理内存得到充分的利用,内核会在适当的时间把物理内存中不经常使用的数据块儿自动交换到虚拟内存中,而将充分使用的信息保留到物理内存中。...例如通过阿里云安装的系统,不会自动给我们分配Swap虚拟内存空间;Swap分区或虚拟内存文件,是在系统物理内存不够用的时候,由系统内存管理程序将那些很长时间没有操作内存数据,临时保存到Swap分区虚拟内存文件中...当那些程序要再次重新运行时,会再从Swap分区或虚拟内存文件中恢复之前保存的数据到内存中。

13.1K41
领券