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

C语言解决TopK问题

前言:

本文TopK问题是在数据量很大的前提下进行解决,当数据量足够大时,内存中存不下,只能存到文件硬盘中。当存到硬盘中,我们无法用建堆,一个一个pop取出最值的方式解决,因为我们没法在硬盘中去访问数组下标。那怎么解决呢?

问题背景:

假设有10亿个数据,内存存不下,数据在文件中,找出最大的前K个 K == 100

解题思路:

  1. 读取文件中前K个数据,在内存数组中建立一个小堆
  2. 再依次读取剩下数据,跟堆顶数据比较,大于堆顶,就替换他进堆,接着进行向下调整算法
  3. 所有数据读完,堆里面的数据就是最大的前100个

解析:

为什么不能用大堆?

假设最大的数据在前面已经进堆,那么堆顶元素就是最大的,此时堆顶元素就挡住了剩余其他前TopK的元素进堆

建立小堆的妙处:

只要大于堆顶,就会进堆,较大的数据就会往后面靠,小的数据在前面,不会影响剩下较大的数据进堆。

时间复杂度:O(N*logK)

空间复杂度:O(K)

相关文章:

C语言解决TopK问题

前言: 本文TopK问题是在数据量很大的前提下进行解决,当数据量足够大时,内存中存不下,只能存到文件硬盘中。当存到硬盘中,我们无法用建堆,一个一个pop取出最值的方式解决,因为我们没法在硬盘中去…...

磁盘存储链式结构——B树与B+树

红黑树处理数据都是在内存中,考虑的都是内存中的运算时间复杂度。如果我们要操作的数据集非常大,大到内存已经没办法处理了该怎么办呢? 试想一下,为了要在一个拥有几十万个文件的磁盘中查找一个文本文件,设计的…...

如何批量从sql语句中提取表名

简介 使用的卢易表 的提取表名功能,可以从sql语句中批量提取表名。采用纯文本sql语法分析,无需连接数据库,支持从含非sql语句的文件文件中提取,支持各类数据库sql语法。 特点 快:从成百个文件中提取上千个表名只需1…...

怎么把音频的速度调慢?6个方法调节音频速度

怎么把音频的速度调慢?调慢音频速度不仅可以帮助我们更好地捕捉细节,还能让我们在分析和学习时更加从容。这对于音乐爱好者来说,尤其有助于理解复杂的旋律和和声,使学习过程变得更加高效。而在语言学习中,放慢语速则能…...

K8s-services+pod详解1

一、Service 我们能够利用Deployment创建一组Pod来提供具有高可用性的服务。 虽然每个Pod都会分配一个单独的Pod IP,然而却存在如下两问题: Pod IP 会随着Pod的重建产生变化Pod IP 仅仅是集群内可见的虚拟IP,外部无法访问 这样对于访问这…...

从RNN讲起(RNN、LSTM、GRU、BiGRU)——序列数据处理网络

文章目录 RNN(Recurrent Neural Network,循环神经网络)1. 什么是RNN?2. 经典RNN的结构3. RNN的主要特点4. RNN存在问题——长期依赖(Long-TermDependencies)问题 LSTM(Long Short-Term Memory&a…...

python:假的身份信息生成模块faker

前言 发现一个有趣的python模块(faker),他支持生成多个国家语言下的假身份信息,包含人名、地址、邮箱、公司名、电话号码、甚至是个人简历! 你可以拿它做一些自动化测试,或一些跟假数据有关的填充工作。 代…...

spring task的使用场景

spring task 简介 spring task 是spring自带的任务调度框架按照约定的时间执行某个方法的工具,类似于闹钟 应用场景 cron表达式 周和日两者必定有一个是问号 简单案例...

美畅物联丨剖析 GB/T 28181 与 GB 35114:视频汇聚领域的关键协议

我们在使用畅联云平台进行视频汇聚时,经常会用的GB/T 28181协议,前面我们写了关于GB/T 28181的相关介绍,​ 详见《畅联云平台|关于GB28181你了解多少?》。 ​最近也有朋友向我们咨询GB 35114协议与GB/T 28181有什么不同…...

uni-app 开发的应用快速构建成鸿蒙原生应用

uni-app 是一个使用 Vue.js 开发所有前端应用的框架,它支持编译到 iOS、Android、小程序等多个平台。对于 HarmonyOS(鸿蒙系统),uni-app 提供了特定的支持,允许开发者构建鸿蒙原生应用。 一、uni-app 对 HarmonyOS 的支…...

代码随想录算法训练营| 669. 修剪二叉搜索树 、 108.将有序数组转换为二叉搜索树 、 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树 题目 参考文章 思路:这题其实就是删除不符合上下边界的节点。注意:这里删除不符合上下边界节点时,这个不符合上下边界的节点的左或右子树可能存在符合上下边界的节点,所i有每次比较完之后,要继…...

Django模型实现外键自关联

Django模型实现外键自关联 1、场景 省市区、评论 2、模型models.py from django.db import models 资讯评论:资讯,用户,是否取消,时间class CommentInfomation(models.Model):info = models...

Android ViewModel

一问:ViewModel如何保证应用配置变化后能够自动继续存在,其原理是什么,ViewModel的生命周期和谁绑定的? ViewModel 的确能够在应用配置发生变化(例如屏幕旋转)后继续存在,这得益于 Android 系统的 ViewMod…...

优先算法1--双指针

“一念既出,万山无阻。”加油陌生人! 目录 1.双指针--移动零 2.双指针-复写零 ok,首先在学习之前,为了方便大家后面的学习,我们这里需要补充一个知识点,我这里所谓的指针,不是之前学习的带有…...

利用弹性盒子完成移动端布局(第二次实验作业)

需要实现的效果如下&#xff1a; 下面是首先是这个项目的框架&#xff1a; 然后是html页面的代码&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"wid…...

C# 字符串(string)三个不同的处理方法:IsNullOrEmpty、IsInterned 、IsNullOrWhiteSpace

在C#中&#xff0c;string.IsNullOrEmpty、string.IsInterned 和 string.IsNullOrWhiteSpace 是三个不同的字符串处理方法&#xff0c;它们各自有不同的用途&#xff1a; 1.string.IsNullOrEmpty&#xff1a; 这个方法用来检查字符串是否为null或者空字符串&#xff08;"…...

读书笔记 - 虚拟化技术 - 0 QEMU/KVM概述与历史

《QEMU/KVM源码解析与应用》 - 王强 概述 虚拟化简介 虚拟化思想 David Wheeler&#xff1a;计算机科学中任何问题都可以通过增加一个中间层来解决。 虚拟化思想存在与计算机科学的各个领域。 主要思想&#xff1a;通过分层将底层的复杂&#xff0c;难用的资源虚拟抽象为简…...

常见的负载均衡

1.常见的负载均衡服务 负载均衡服务是分布式系统中用于分配网络流量和请求的关键组件&#xff0c;它可以帮助提高应用程序的可用性、可扩展性和响应速度。以下是一些常用的负载均衡服务&#xff1a; Nginx&#xff1a;一个高性能的Web服务器和反向代理&#xff0c;广泛用于实现…...

利用sessionStorage收集用户访问信息,然后传递给后端

这里只是简单的收集用户的停留时间、页面加载时间、当前页面URL及来源页面&#xff0c;以做示例 <html><head><meta http-equiv"content-type" content"text/html; charsetUTF-8"/><title>测试sessionStorage存储用户访问信息<…...

什么是Qseven?模块电脑(核心板)规范标准简介二

1.概念 Qseven是一种通用的、小尺寸计算机模块标准&#xff0c;适用于需要低功耗、低成本和高性能的应用。 Qseven模块电脑&#xff08;核心板&#xff09;采用230Pin金手指连接器 2.Qseven的起源 Qseven最初是由Congatec、SECO、MSC三家欧洲公司于2008年发起&#xff0c;旨在…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...