当前位置: 首页 > 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)…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...