面试题:2G内存找出20亿个整数中出现次数最多的数

空间限制:2G内存找出20亿个整数中出现次数最多的数

我们假设整数是32位,也就是4B大小的int类型

极端情况:
  • 每个数都一样,该整数统计只需要8B大小的空间
  • 每个数都不一样,此时占用空间最大20亿 * 8B 接近 16GB

需要解决这个问题,我们可以先了解一个算法:

哈希分流:

哈希分流指的是通过哈希算法将数据或请求分散到多个处理单元上,以实现负载均衡高效率处理的技术。在不同的应用场景下,哈希分流有不同的具体实现方式和目的,但核心思想相同,即使用哈希算法对输入数据(如IP地址、用户ID等)进行计算,根据计算结果将数据分配到对应的服务器或处理单元。这样可以有效地分散请求或数据,避免某单一点过载,同时提高系统的可扩展性和稳定性。

哈希分流的应用场景包括但不限于:

  1. 负载均衡:在网络服务器负载均衡中,哈希分流可以将用户请求分散到多个服务器,根据用户的某些标识(如IP地址)来决定请求应由哪个服务器处理,从而均匀分配负载。
  2. 数据分片:在数据库管理或大数据处理中,哈希分流可以将数据分片存储在不同的服务器或节点上,提高数据处理的效率和响应速度。
  3. 缓存分配:在分布式缓存系统中,通过哈希算法将数据分散存储在多个缓存节点上,可以减少单个节点的压力,提高缓存系统的命中率和性能。

1. 拆分:

我们无法再2G内存中装入所有的数字所以考虑拆分,将20亿个数字拆成不同的份,分流到不同等份中。而我们采取哈希分流的原因就如上述所说。而2G内存最多能统计多少数呢,2^31 / 2 ^ 3 = 2 ^ 28个数,然后2^32 / 2 ^ 28 = 16,所以需要拆分成16份。

2. 统计:

  • 从一个存储20亿个整数的大文件依次读取数据通过哈希分流道16个小文件中
  • 依次使用2GB内存中统计小文件中的整数出现次数,找出最大值
  • 综合16个小文件中找出的最大值进行比较找出全局最大值

最后给大家推荐一个LinuxC/C++高级架构系统教程的学习资源与课程,可以帮助你有方向、更细致地学习C/C++后端开发,具体内容请见 https://xxetb.xetslk.com/s/1o04uB

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/576965.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

金融案例:统一查询方案助力数据治理与分析应用更高效、更安全

随着企业数据规模的增长和业务多元化发展,海量数据实时、多维地灵活查询变成业务常见诉求。同时多套数据库系统成为常态,这既带来了数据管理的复杂性,又加大了数据使用的难度,面对日益复杂的数据环境和严格的数据安全要求&#xf…

苹果发布开源模型;盘古大模型5.0将亮相;英伟达将收购 Run:ai

苹果首次发布开源语言模型 近期,苹果在 Hugging Face 发布了 OpenELM 系列模型。OpenELM 的关键创新是逐层扩展策略,该策略可在 transformer 模型的每一层中有效地分配参数,从而提高准确性。 与具有统一参数分配的传统语言模型不同&#xff…

rabbitmq集群配置

1,配置环境变量 MY_POD_NAME:当前Pod的名称 RABBITMQ_ERLANG_COOKIE:设置Erlang Cookie用于节点间通信安全验证,值来自/nfs/rabbitmq/lib/.erlang.cookie文件内容 RABBITMQ_NODENAME:根据Pod名称动态生成了RabbitMQ…

前端到全栈进阶之“前端框架”

从前端入门到全栈-系列介绍 你会学到什么? 可能学不到什么东西,该系列是作者本人工作和学习积累,用于复习 系列介绍 现在的 Web 前端已经离不开 Node.js,我们广泛使用的 Babel、Webpack、工程化都是基于 Node 的,各…

k8s-身份认证与权限

认证概述 Kubernetes作为一个分布式集群的管理工具,保证集群的安全性是其一个重要的任务。所谓的安全性其实就是保证对Kubernetes的各种客户端进行认证和鉴权操作。 在Kubernetes集群中,客户端通常有两类: User Account:一般是独…

vue elementui el-table 表格里边展示四分位图

vue elementui el-table 表格里边展示四分位图 直接上代码&#xff08;效果图在文章末尾&#xff09;&#xff1a; 父组件&#xff1a; <template> <el-table size"small":header-cell-style"headerCellStyle()"style"width: 100%;"…

Linux平台Unity下RTMP|RTSP低延迟播放器技术实现

技术背景 国产操作系统对于确保信息安全、促进技术创新、满足特定需求以及推动经济发展等方面都具有重要意义&#xff0c;多以Linux为基础二次开发。2014年4月8日起&#xff0c;美国微软公司停止了对Windows XP SP3操作系统提供支持&#xff0c;这引起了社会和广大用户的广泛关…

Spark 基础

/* Why Spark一、MapReduce编程模型的局限性1、繁杂&#xff1a;只有Map和Reduce两个操作&#xff0c;复杂的逻辑需要大量的样板代码2、处理效率低&#xff1a;2.1、Map中间结果写磁盘&#xff0c;Reduce写HDFS&#xff0c;多个Map通过HDFS交换数据2.2、任务调度与启动开销大3、…

C++中的queue(容器适配器)

目录 一、成员函数 一、构造函数 二、入栈 push 三、出栈 pop 四、判空 empty 五、队列大小 size 六、取队头元素 front 七、取队尾元素 back 八、入栈 emplace 九、交换函数 swap 二、非成员函数重载 一、关系运算符重载 二、交换函数 swap C中的queue不再是容…

HWOD:单词倒排

一、知识点 此题&#xff0c;笔者自己写的代码中flag的设置极为精妙 二、题目 1、描述 对字符串中的所有单词进行倒排。 说明&#xff1a; (1)、构成单词的字符只有26个大写或小写英文字母&#xff1b; (2)、非构成单词的字符均视为单词间隔符&#xff1b; (3)、要求倒…

Visual Studio 对 C++ 头文件和模块的支持

在 C 编程领域&#xff0c;头文件和模块的管理有时候确实比较令人头疼。但是&#xff0c;有许多工具和功能可以简化此过程&#xff0c;提高效率并减少出错的可能性。下面是我们为 C 头文件和模块提供的几种工具的介绍。 构建明细 通过菜单栏 Build > Run Build Insights&a…

uni-app中配置自定义条件编译

前提&#xff1a;官网提供的自定义编译不满足条件 package.json | uni-app官网 下文&#xff1a;不详细写&#xff0c;主要写关键思路 package.json文件 主要看scripts的执行命令&#xff0c;其他依赖就是用vue-cli方式创建uni-app项目生成的 {"name": "un…

命令行启动pytest自动化程序时,程序卡住不动了,不继续往下执行了

一、问题描述 在执行pytestallure自动化测试工具的时候&#xff0c;命令行启动程序时&#xff0c;程序卡住不继续往下执行&#xff0c;如下图所示。 代码主函数如下&#xff1a; 二、解决方法 测试客户项目时遇到2次此类问题&#xff0c;2次问题原因不一样。 原因一&#xf…

3d合并的模型为什么没有模型---模大狮模型网

在3D建模中&#xff0c;合并模型是常见的操作&#xff0c;它可以将多个模型合并成一个整体。然而&#xff0c;有时候在合并后却发现部分模型消失了&#xff0c;这可能会让人感到困惑和失望。本文将探讨为什么合并的3D模型中会出现没有模型的情况&#xff0c;并提供一些解决方法…

API和微服务设计的优化方式有哪些?

在构建响应迅速、用户体验良好的应用程序中&#xff0c;API性能的优化至关重要。在构建高性能的API时&#xff0c;采取综合策略是至关重要的。通过采用一系列策略&#xff0c;我们可以确保API在处理请求时高效运行&#xff0c;提供流畅的服务。 一、API和微服务设计的优化可以…

Edge下载文件提示无法安全下载的解决方法

问题描述&#xff1a;最近Edge在下载文件时总是提示&#xff1a;无法安全下载&#xff0c;本文记录一下解决方法。 提示截图&#xff1a; 解决方式一&#xff1a; 1. 点击下图红框的三个点&#xff0c;选择保留 2. 选择仍然保留 解决方式二&#xff1a; 第一种方式每下载一次…

MySQL双层游标嵌套循环方法

文章目录 1、需求描述2、思路3、创建存储过程 1、需求描述 1、在项目中&#xff0c;需要将A表中主键id&#xff0c;逐个取出&#xff0c;作为条件&#xff0c;在B表中去逐一查询&#xff0c;将B表查询到的结果集&#xff08;A表B表关系&#xff1a;一对多&#xff09;&#xf…

Qt下使用OpenCV截取图像并在QtableWidget表格上显示

文章目录 前言一、在QLabel上显示图片并绘制矩形框二、保存矩形框数据为CSV文件三、保存截取图像四、将截取图像填充到表格五、图形视图框架显示图像六、示例完整代码总结 前言 本文主要讲述了在Qt下使用OpenCV截取绘制的矩形框图像&#xff0c;并将矩形框数据保存为CSV文件&a…

【经验分享】MySQL集群部署一:主从模式

目录 前言一、基本介绍1.1、概念1.2、执行流程 二、部署2.1、通用配置2.2、主节点配置2.3、从节点配置2.4、主从测试2.5、谈一谈主节点历史数据同步问题 前言 MySQL的部署模式常见的包括以下几种&#xff1a; 独立服务器部署主从复制部署高可用性集群&#xff08;HA&#xff…

Angular创建项目

Angular创建项目 文章目录 Angular创建项目1. 创建项目1.1 直接安装1.2 跳过npm i安装 2. 运行程序 1. 创建项目 ng new 项目名称 1.1 直接安装 ng new angulardemo --同时会安装依赖包&#xff0c;执行的命令就是npm i 1.2 跳过npm i安装 ng new angulardemo --skip-inst…
最新文章