当前位置: 首页 > news >正文

大数据算法

1. TOP K 算法

有10个⽂件,每个⽂件1G,每个⽂件的每⼀⾏存放的都是⽤户的 query,每个⽂件的 query 都可能重复。要求你按照 query 的频度排序。

方法1:
顺序读取10个⽂件,按照 hash(query)%10 的结果将 query 写⼊到另外 10 个⽂件(记为)中。这样新⽣成的⽂件每个的⼤⼩⼤约也 1G(假设 hash 函数是随机的)。找⼀台内存在 2G 左右的机器,依次对⽤hash_map(query, query_count)来统计每个 query 出现的次数。利⽤快速/堆/归并排序按照出现次数进⾏排序。将排序好的 query 和对应的 query_cout 输出到⽂件中。这样得到了 10 个排好序的⽂件(记为)。对这 10 个⽂件进⾏归并排序(内排序与外排序相结合)。
方法2:
与⽅案 1 类似,但在做完 hash,分成多个⽂件后,可以交给多个⽂件来处理,采⽤分布式的架构来处理(⽐如 MapReduce),最后再进⾏合并。

2. 不重复的数据

在 2.5 亿个整数中找出不重复的整数,注,内存不⾜以容纳这 2.5 亿个整数。
解答:
1)⽅案 1:采⽤ 2-Bitmap(每个数分配 2bit,00 表示不存在,01 表示出现⼀次,10 表示多次,11 ⽆意义)进⾏,共需内存 2^32 * 2bit=1 GB 内存,还可以接受。然后扫描这 2.5 亿个整数,查看 Bitmap 中相对应位,如果是 00 变 01,01 变 10,10 保持不变。所描完事后,查看 bitmap,把对应位是 01 的整数输出即可。
2)⽅案 2:也可采⽤与第 1 题类似的⽅法,进⾏划分⼩⽂件的⽅法。然后在⼩⽂件中找出不重复的整数,并排序。然后再进⾏归并,注意去除重复的元素。

3. 判断数据是否存在

给 40 亿个不重复的 unsigned int 的整数,没排过序的,然后再给⼀个数,如何快速判断这个数是否在那 40 亿个数当中?
1)⽅案 1:oo,申请 512M 的内存,⼀个 bit 位代表⼀个 unsigned int 值。读⼊ 40 亿个数,设置相应的 bit 位,读⼊要查询的数,查看相应 bit 位是否为 1,为 1 表示存在,为 0 表示不存在。

4. 重复最多的数据

有⼀千万条短信,有重复,以⽂本⽂件的形式保存,⼀⾏⼀条,有重复。请⽤5分钟时间,找出重复出现最多的前 10 条。
解答:
1)分析: 常规⽅法是先排序,在遍历⼀次,找出重复最多的前 10 条。但是排序的算法复杂度最低为 nlgn。
2)可以设计⼀个 hash_table, hash_map<string, int>,依次读取⼀千万条短信,加载到 hash_table 表 中,并且统计重复的次数,与此同时维护⼀张最多 10 条的短信表。 这样遍历⼀次就能找出最多的前 10 条,算法复 杂度为 O(n)。

相关文章:

大数据算法

1. TOP K 算法 有10个⽂件&#xff0c;每个⽂件1G&#xff0c;每个⽂件的每⼀⾏存放的都是⽤户的 query&#xff0c;每个⽂件的 query 都可能重复。要求你按照 query 的频度排序。 方法1&#xff1a; 顺序读取10个⽂件&#xff0c;按照 hash(query)%10 的结果将 query 写⼊到…...

非暴力沟通读书笔记

浅读《非暴力沟通》&#xff0c;本书对于沟通的方式总结成了一个方法论&#xff0c;从13个章节去概述非暴力沟通的方法和重点。其中最重要的是非暴力沟通四要素&#xff0c;观察、感受、需要、请求。同时在沟通中注意观察&#xff0c;投入爱&#xff0c;重视倾听的力量&#xf…...

代码随想录【Day21】| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差 题目链接 题目描述&#xff1a; 给你一棵所有节点为非负值的二叉搜索树&#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例&#xff1a; 提示&#xff1a;树中至少有 2 个节点。 难点&#xff1a; 解答错误&#xff01;仅考虑了…...

注意啦,面试通过后,别忘了教师资格证认定

所有要「教师资格证认定」教程的宝子们看过来面试合格的小伙伴都可以进行认定工作 . 认定时间 查询各省份认定公告&#xff0c;确定认定时间范围。以下是公告汇总网址&#xff08;https://www.jszg.edu.cn/portal/qualification_cert/dynamics?id21691&#xff09; 认定次数 每…...

【LeetCode】No.154. 寻找旋转排序数组中的最小值 II -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/ 1. 题目介绍&#xff08;154. 寻找旋转排序数组中的最小值 II&#xff09; 已知一个长度为 n 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0…...

RestTemplate远程调用

我们现在项目中使用的RPC远程调用技术是Dubbo实际上除了Dubbo技术之外,还有很多远程调用的方法它们有些调用的思想都和Dubbo完全不同Dubbo是SpringCloudAlibaba提供的功能强大的RPC框架但是Dubbo功能也有限制,如果我们想调用的方法不是我们当前项目的组件或功能,甚至想调用的方…...

registerForActivityResult使用

目录 针对 activity 结果注册回调 启动 activity 以获取其结果 在单独的类中接收 activity 结果 测试 创建自定义协定 registerForActivityResult()是startActivityForResult&#xff08;&#xff09;的替代&#xff0c;简化了数据回调的写法 启动另一个 activity&#x…...

工作中,python真的有用吗?

普通上班族学Python有用吗&#xff1f; 那么&#xff0c;我也在这里提出一个问题&#xff1a;Python究竟适不适合办公人士来学习&#xff0c;以及学了之后究竟能不能给我的工作来带质一般的飞跃&#xff1f; 以我的亲身经历为例&#xff0c;我可以很负责的告诉大家&#xff0c…...

固态继电器控制电路

固态继电器控制电路 固态继电器&#xff08;SSR&#xff09;的种类和型号很多&#xff0c;因此其输入控制方法和控制电路也相应众多。固态继电器&#xff08;SSR&#xff09;的共同特点在于驱动电流或驱动电压小&#xff0c;即只需输入一个小信号即可控制SSR的开关。 如果需要…...

数仓、数据湖、湖仓一体、数据网格的探索与研究

第一代&#xff1a;数据仓库 定义 为解决数据库面对数据分析的不足&#xff0c;孕育出新一类产品数据仓库。数据仓库&#xff08;Data Warehouse&#xff09;是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合&#xff0c;用于支持管理决策和信息的全局共享。 数…...

设计模式系列 - 备忘录模式

介绍&定义 备忘录模式&#xff0c;也叫快照&#xff08;Snapshot&#xff09;模式&#xff0c;英文翻译是 Memento Design Pattern。在 GoF 的《设计模式》一书中&#xff0c;备忘录模式是这么定义的&#xff1a; Captures and externalizes an object’s internal state…...

详细介绍React生命周期和diffing算法

事件处理 1.通过onXxx属性指定事件处理函数(注意大小写) React使用的是自定义(合成)事件, 而不是使用的原生DOM事件 —— 为了更好的兼容性&#xff1b;React中的事件是通过事件委托方式处理的(委托给组件最外层的元素) ——为了的高效。 2.通过event.target得到发生事件的DOM…...

面向对象的特点

1、什么是对象对象的含义是指具体的某一个事物&#xff0c;即在现实生活中能够看得见摸得着的事物。在面向对象程序设计中&#xff0c;对象所指的是计算机系统中的某一个成分。在面向对象程序设计中&#xff0c;对象包含两个含义&#xff0c;其中一个是数据&#xff0c;另外一个…...

智慧校园平台源码 智慧教务 智慧电子班牌系统

系统介绍 智慧校园系统是通过信息化手段,实现对校园内各类资源的有效集成 整合和优化&#xff0c;实现资源的有效配置和充分利用&#xff0c;将校务管理过程的优化协调。为校园提供数字化教学、数字化学习、数字化科研和数字化管理。 致力于为家长和教师提供一个全方位、多层…...

Vue篇.03-组合式API [setup()]

单文件组件(1)<script setup><script setup> 是在单文件组件 (SFC) 中使用组合式 API 的编译时语法糖。当同时使用 SFC 与组合式 API 时该语法是默认推荐启用该语法&#xff0c;需要在 <script> 代码块上添加 setup attribute, 里面的代码会被编译成组件 s…...

QHashIterator-官翻

QHashIterator Class template <typename Key, typename T> class QHashIterator QHashIterator 类为 QHash 和 QMultiHash 提供 Java 风格的常量迭代器。更多内容… 头文件:#include qmake:QT core 所有成员列表&#xff0c;包括继承的成员废弃的成员 公共成员函数…...

[qiankun]-部署后线上问题

[qiankun]-部署后线上问题微服务加载问题-现象1现象描述问题分析解决方案微服务加载问题-现象2现象描述问题分析微服务加载问题-现象3现象描述分析解决方案属于项目打包后&#xff0c;部署到服务器上&#xff0c;所遇到的部分问题 微服务加载问题-现象1 现象描述 项目部署实…...

位图数组 布隆过滤器

文章目录位图数组获取索引获取索引状态设置索引状态布隆过滤器特点大致原理位图数组 一个int类型的整数用4字节,也就是32个bit位来表示&#xff0c;将整数类型的数组转换成位图数组&#xff0c;那么存储长度将变为原来的32倍 arr[0] 表示0-31 arr[1] 表示32-63 //...获取索引…...

多线程Thread常用方法和状态

Thread类 及常见方法 1、常见构造方法 方法说明Thread()创建线程对象Thread(Runnable target)使用 Runnable 对象创建线程对象Thread(String name)创建线程对象&#xff0c;并命名Thread(Runnable target, String name)使用 Runnable 对象创建线程对象&#xff0c;并命名Thre…...

Codeforces Round #836 (Div. 2)

A SSeeeeiinngg DDoouubbllee 题意&#xff1a;告诉你一个字符串。若该串上每一位上的字母都可以出现两次&#xff0c;求回文串 思路&#xff1a;正向再反向输出s即可 #include <bits/stdc.h> #define lowbit(x) x&(-x) #define ios cin.sync_with_stdio(false)…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...