• 关于

    空间复杂性有什么用

    的搜索结果

回答

算法是比较复杂又基础的学科,每个学编程的人都会学习大量的算法。而根据统计,以下这18个问题是面试中最容易遇到的,本文给出了一些基本答案,供算法方向工程师或对此感兴趣的程序员参考。 1)请简单解释算法是什么? 算法是一个定义良好的计算过程,它将一些值作为输入并产生相应的输出值。简单来说,它是将输入转换为输出的一系列计算步骤。 2)解释什么是快速排序算法? 快速排序算法能够快速排序列表或查询。它基于分割交换排序的原则,这种类型的算法占用空间较小,它将待排序列表分为三个主要部分: ·小于Pivot的元素 ·枢轴元素Pivot(选定的比较值) ·大于Pivot的元素 3)解释算法的时间复杂度? 算法的时间复杂度表示程序运行完成所需的总时间,它通常用大O表示法来表示。 4)请问用于时间复杂度的符号类型是什么? 用于时间复杂度的符号类型包括: ·Big Oh:它表示小于或等于目标多项式 ·Big Omega:它表示大于或等于目标多项式 ·Big Theta:它表示与目标多项式相等 ·Little Oh:它表示小于目标多项式 ·Little Omega:它表示大于目标多项式 5)解释二分法检索如何工作? 在二分法检索中,我们先确定数组的中间位置,然后将要查找的值与数组中间位置的值进行比较,若小于数组中间值,则要查找的值应位于该中间值之前,依此类推,不断缩小查找范围,直至得到最终结果。 6)解释是否可以使用二分法检索链表? 由于随机访问在链表中是不可接受的,所以不可能到达O(1)时间的中间元素。因此,对于链表来说,二分法检索是不可以的(对顺序链表或排序后的链表是可以用的)。 7)解释什么是堆排序? 堆排序可以看成是选择排序的改进,它可以定义为基于比较的排序算法。它将其输入划分为未排序和排序的区域,通过不断消除最小元素并将其移动到排序区域来收缩未排序区域。 8)说明什么是Skip list? Skip list数据结构化的方法,它允许算法在符号表或字典中搜索、删除和插入元素。在Skip list中,每个元素由一个节点表示。搜索函数返回与key相关的值的内容。插入操作将指定的键与新值相关联,删除操作可删除指定的键。 9)解释插入排序算法的空间复杂度是多少? 插入排序是一种就地排序算法,这意味着它不需要额外的或仅需要少量的存储空间。对于插入排序,它只需要将单个列表元素存储在初始数据的外侧,从而使空间复杂度为O(1)。 10)解释什么是“哈希算法”,它们用于什么? “哈希算法”是一个哈希函数,它使用任意长度的字符串,并将其减少为唯一的固定长度字符串。它用于密码有效性、消息和数据完整性以及许多其他加密系统。 11)解释如何查找链表是否有循环? 要知道链表是否有循环,我们将采用两个指针的方法。如果保留两个指针,并且在处理两个节点之后增加一个指针,并且在处理每个节点之后,遇到指针指向同一个节点的情况,这只有在链表有循环时才会发生。 12)解释加密算法的工作原理? 加密是将明文转换为称为“密文”的密码格式的过程。要转换文本,算法使用一系列被称为“键”的位来进行计算。密钥越大,创建密文的潜在模式数越多。大多数加密算法使用长度约为64到128位的固定输入块,而有些则使用流方法。 13)列出一些常用的加密算法? 一些常用的加密算法是: ·3-way ·Blowfish ·CAST ·CMEA ·GOST ·DES 和Triple DES ·IDEA ·LOKI等等 14)解释一个算法的最佳情况和最坏情况之间有什么区别? ·最佳情况:算法的最佳情况解释为算法执行最佳的数据排列。例如,我们进行二分法检索,如果目标值位于正在搜索的数据中心,则这就是最佳情况,最佳情况时间复杂度为0。 ·最差情况:给定算法的最差输入参考。例如快速排序,如果选择关键值的子列表的最大或最小元素,则会导致最差情况出现,这将导致时间复杂度快速退化到O(n2)。 15)解释什么是基数排序算法? 基数排序又称“桶子法”,是通过比较数字将其分配到不同的“桶里”来排序元素的。它是线性排序算法之一。 16)解释什么是递归算法? 递归算法是一个解决复杂问题的方法,将问题分解成较小的子问题,直到分解的足够小,可以轻松解决问题为止。通常,它涉及一个调用自身的函数。 17)提到递归算法的三个定律是什么? 所有递归算法必须遵循三个规律: ·递归算法必须有一个基点 ·递归算法必须有一个趋向基点的状态变化过程 ·递归算法必须自我调用 18)解释什么是冒泡排序算法? 冒泡排序算法也称为下沉排序。在这种类型的排序中,要排序的列表的相邻元素之间互相比较。如果它们按顺序排列错误,将交换值并以正确的顺序排列,直到最终结果“浮”出水面。 满意记得采纳哈

玄学酱 2019-12-02 01:18:44 0 浏览量 回答数 0

回答

我也在开发中遇到这个问题,下面是我的想法,仅供参考首先,我觉得规划css的有个影响因素,就是网站的设计思路,如果网站是有一个整个的设计风格的话,规划的时候可以将模块的粒度适度放大。结构拆分基础框架:包含重置样式、栅格、css3动画模块,还是可以加上矢量图标库(iconfont)、辅助类通用样式库: 基本的复用模块,如button、form、table等,这个设计的时候要注意复用性和维护性业务样式:包含网站各页面之间的网站特有的样式,如导航、列表页、评论等解决方案: 可以归纳一下常用的css问题,如兼容多浏览器的高度不固定的垂直水平居中、png透明图片支持等。。代码规范命名空间+模块化+语义命名,可以参考Amaze UI HTML/CSS 规范兼容性列表:这个视业务需求而定了,如果逼格高一点,如ie8+基本和hack说再见了javascript组件:复杂的交互组件都是和javascript配合,建议公司内部有统一的规范,如果没有,可以参考业内的bootstrap、aralejs都可以开发工具现在通过预处理器开发样式很常见了吧,如果是node,就用stylus或者less,像est的样式工具库应该可以帮你提高效率哈文档文档不多说了,对于团队的维护性不言而喻,推荐一个专门用于css自动化文档工具 -- Hologram,不过依赖于ruby业界参考Semantic UI顾名思义,语义化的css库,组件的划分我觉得可以参考一下哈Amaze UI中国首个开源 HTML5 跨屏前端框架,采用less编写,移动优先,文档很详细,建议仔细阅读,收获不少bootstrap什么的就不用说了

a123456678 2019-12-02 02:23:15 0 浏览量 回答数 0

问题

有什么办法能避免数据损失呢?

游客nlekadieflg4i 2020-01-06 11:43:39 38 浏览量 回答数 1

阿里云试用中心,为您提供0门槛上云实践机会!

0元试用32+款产品,最高免费12个月!拨打95187-1,咨询专业上云建议!

问题

数据损失对业务是致命的威胁

小熊软糖bear 2019-12-27 16:12:37 30 浏览量 回答数 0

回答

首先,我们先来聊聊各类数据模型。下列相关信息参考自Emil Eifrem的博文及NoSQL数据库说明。文档类数据库传承:受Lotus Notes启发而来。数据模型:文档汇总,包括键-值汇总。实例: CouchDB, MongoDB优势: 数据建模自然、程序员易于上手、开发流程短、兼容网页模式、便于达成CRUD(即添加、查询、更新及删除的简称)。图形类数据库传承:来自 Euler 及图形理论。数据模型:节点及关系,二者结合能够保持键-值间的成对状态实例: AllegroGraph, InfoGrid, Neo4j优势:轻松玩转复杂的图形问题、处理速度快关系类数据库传承:源自 E. F. Codd在大型共享数据库中所提出的数据关系模型理论数据模型:以关系组为基础实例: VoltDB, Clustrix, MySQL优势:性能强大、联机事务处理系统扩展性好、支持SQL访问、视图直观、擅长处理交易关系、与程序员间的交互效果优异面向对象类数据库传承:源自图形数据库方面的研究成果数据模型: 对象实例: Objectivity, Gemstone优势:擅长处理复杂的对象模型、快速的键-值访问及键-功能访问并且兼具图形数据库的各类功能键-值存储传承: Amazon Dynamo中的paper概念及分布式hash表数据模型:对成对键-值的全局化汇总实例: Membase, Riak优势:尺寸掌控得当、擅长处理持续的小规模读写需求、速度快、程序员易于上手BigTable Clones传承自:谷歌BigTable中的paper概念数据模型:纵列群,即在某个表格模型中,每行在理论上至少可以有一套单独的纵列配置实例: HBase, Hypertable, Cassandra优势:尺寸掌控得当、擅长应对大规模写入负载、可用性高、支持多数据中心、支持映射简化数据结构类服务传承: 不明实例: Redis数据模型: 执行过程基于索引、列表、集合及字符串值优势:为数据库应用引入前所未有的新鲜血液网格类数据库传承:源自数据网格及元组空间研究数据模型:基于空间的构架实例: GigaSpaces, Coherence优势:优良的性能表现及上佳的交易处理扩展性我们该为自己的应用程序选择哪套方案?选择的关键在于重新思考我们的应用程序如何依据不同数据模型及不同产品进行有针对性的协同工作。即用正确的数据模型处理对应的现实任务、用正确的产品解决对应的现实问题。要探究哪类数据模型能够切实为我们的应用程序提供帮助,可以参考“到底NoSQL能在我们的工作中发挥什么作用?”一文。在这篇文章中,我试着将各种不同特性、不同功能的常用创建系统中的那些非常规的应用实例综合起来。将应用实例中的客观需求与我们的选择联系起来。这样大家就能够逆向分析出我们的基础架构中适合引入哪些产品。至于具体结论是NoSQL还是SQL,这已经不重要了。关注数据模型、产品特性以及自身需要。产品总是将各种不同的功能集中起来,因此我们很难单纯从某一类数据模型构成方式的角度直接找到最合用的那款。对功能及特性的需求存在优先级,只要对这种优先级具备较为清晰的了解,我们就能够做出最佳选择。如果我们的应用程序需要…复杂的交易:因为没人愿意承受数据丢失,或者大家更倾向于一套简单易用的交易编程模式,那么请考虑使用关系类或网格类数据库。例如:一套库存系统可能需要完整的ACID(即数据库事务执行四要素:原子性、一致性、隔离性及持久性)。顾客选中了一件产品却被告知没有库存了,这类情况显然容易引起麻烦。因为大多数时候,我们想要的并不是额外补偿、而只是选中的那件货品。若是以扩展性为优先,那么NoSQL或SQL都能应对自如。这种情况下我们需要关注那些支持向外扩展、分类处理、实时添加及移除设备、负载平衡、自动分类及整理并且容错率较高的系统。要求持续保有数据库写入功能,则需要较高的可用性。在这种情况下不妨关注BigTable类产品,其在一致性方面表现出众。如有大量的小规模持续读写要求,也就是说工作负载处于波动状态,可以关注文档类、键-值类或是那些提供快速内存访问功能的数据库。引入固态硬盘作为存储媒介也是不错的选择。以社交网络为实施重点的话,我们首先想到的就是图形类数据库;其次则是Riak这种关系类数据库。具备简单SQL功能的常驻内存式关系数据库基本上就可以满足小型数据集合的需求。Redis的集合及列表操作也能发挥作用。如果我们的应用程序需要…在访问模式及数据类型多种多样的情况下,文档类数据库比较值得考虑。这类数据库不仅灵活性好,性能表现也可圈可点。需要完备的脱机报告与大型数据集的话,首选产品是Hadoop,其次则是支持映射简化的其它产品。不过仅仅支持映射简化还不足以提供如Hadoop一样上佳的处理能力。如果业务跨越数个数据中心,Bigtable Clone及其它提供分布式选项的产品能够应对由地域距离引起的延迟现象,并具备较好的分区兼容性。要建立CRUD应用程序,首选文档类数据库。这类产品简化了从外部访问复杂数据的过程。需要内置搜索功能的话,推荐Riak。要对数据结构中的诸如列表、集合、队列及发布/订阅信息进行操作,Redis是不二之选。其具备的分布式锁定、覆盖式日志及其它各种功能都会在这类应用状态下大放异彩。将数据以便于处理的形式反馈给程序员(例如以JSON、HTTP、REST、Javascript这类形式),文档类数据库能够满足这类诉求,键-值类数据库效果次之。如果我们的应用程序需要…以直观视图的形式进行同步交易,并且具备实时数据反馈功能,VoltDB算得上一把好手。其数据汇总以及时间窗口化的表现都非常抢眼。若是需要企业级的支持及服务水平协议,我们需要着眼于特殊市场。Membase就是这样一个例子。要记录持续的数据流,却找不到必要的一致性保障?BigTable Clone交出了令人满意的答卷,因为其工作基于分布式文件系统,所以可以应对大量的写入操作。要让操作过程变得尽可能简单,答案一定在托管或平台即服务类方案之中。它们存在的目的正是处理这类要求。要向企业级客户做出推荐?不妨考虑关系类数据库,因为它们的长项就是具备解决繁杂关系问题的技术。如果需要利用动态方式建立对象之间的关系以使其具有动态特性,图形类数据库能帮上大忙。这类产品往往不需要特定的模式及模型,因此可以通过编程逐步建立。S3这类存储服务则是为支持大型媒体信息而生。相比之下NoSQL系统则往往无法处理大型二进制数据块,尽管MongoDB本身具备文件服务功能。如果我们的应用程序需要…有高效批量上传大量数据的需求?我们还是得找点有对应功能的产品。大多数产品都无法胜任,因为它们不支持批量操作。文档类数据库或是键-值类数据库能够利用流畅的模式化系统提供便捷的上传途径,因为这两类产品不仅支持可选区域、添加区域及删除区域,而且无需建立完整的模式迁移框架。要实现完整性限制,就得选择一款支持SQL DLL的产品,并在存储过程或是应用程序代码中加以运行。对于协同工作极为依赖的时候就要选择图形类数据库,因为这类产品支持在不同实体间的迅速切换。数据的移动距离较短且不必经过网络时,可以在预存程序中做出选择。预存程序在关系类、网格类、文档类甚至是键-值类数据库中都能找到。如果我们的应用程序需要…键-值存储体系擅长处理BLOB类数据的缓存及存储问题。缓存可以用于应对网页或复杂对象的存储,这种方案能够降低延迟、并且比起使用关系类数据库来说成本也较低。对于数据安全及工作状态要求较高的话可以尝试使用定制产品,并且在普遍的工作范畴(例如向上扩展、调整、分布式缓存、分区及反规范化等等)之外一定要为扩展性(或其它方面)准备解决方案。多样化的数据类型意味着我们的数据不能简单用表格来管理或是用纵列来划分,其复杂的结构及用户组成(也可能还有其它各种因素)只有文档类、键-值类以及Bigtable Clone这些数据库才能应付。上述各类数据库都具备极为灵活的数据类型处理能力。有时其它业务部门会需要进行快速关系查询,引入这种查询方式可以使我们不必为了偶尔的查看而重建一切信息。任何支持SQL的数据库都能实现这类查询。至于在云平台上运行并自动充分利用云平台的功能——这种美好的愿望目前还只能是愿望。如果我们的应用程序需要…支持辅助索引,以便通过不同的关键词查找数据,这要由关系类数据库及Cassandra推出的新辅助索引系统共同支持才能实现。创建一套处于不断增长中的数据集合(真正天文数量级的数据)然而访问量却并不大,那么Bigtable Clone是最佳选择,因为它会将数据妥善安排在分布式文件系统当中。需要整合其它类型的服务并确保数据库提供延后写入同步功能?那最好的实现方式是捕捉数据库的各种变化并将其反馈到其它系统中以保障运作的一致性。通过容错性检查了解系统对供电中断、隔离及其它故障情况的适应程度。若是当前的某项技术尚无人问津、自己却感觉大有潜力可挖,不妨在这条路上坚持走下去。这种情况有时会带来意料之外的美好前景。尝试在移动平台上工作并关注CouchDB及移动版couchbase。哪种方案更好?25%的状态改善尚不足以让我们下决心选择NoSQL。选择标准是否恰当取决于实际情况。这类标准对你的方案有指导意义吗?如果你的公司尚处于起步阶段,并且需要尽快推出自己的产品,这时不要再犹豫不决了。无论是SQL还是NoSQL都可以作为参考。

a123456678 2019-12-02 03:00:14 0 浏览量 回答数 0

问题

经典动态规划:高楼扔鸡蛋 6月2日 【今日算法】

游客ih62co2qqq5ww 2020-06-02 16:06:52 3 浏览量 回答数 1

问题

ZooKeeper介绍、分析、理解

小柒2012 2019-12-01 21:21:22 11496 浏览量 回答数 2

回答

  算法,数据结构是关键,另外还有组合数学,特别是集合与图论,概率论也重要。推荐买一本《算法导论》,那本书行,看起来超爽。。。基本掌握语法还不行啊,语法的超熟练掌握,不然出了错误很难调试的。。。最重要的是超牛皮的头脑啦,分析能力,逻辑推理能力很重要。ACM很好玩啦,祝你成功。。。   acm是3人一组的,以学校为单位报名的,也就是说要得到学校同意,还要有2个一起搞的。其实可能是你不知道你们学校搞acm的地方,建议你好好询问下你们学校管科技创新方面的人。建议你找几个兴趣相同的一起做,互相探讨效果好多了,团队合作也是acm要求的3大能力之一。   数据结构远远不够的,建议你看算法导论,黑书,oj的话个人觉得还是poj好,有水题有好题,而且做的人多,要解题报告什么的也好找。我们就是一些做acm的学生一起搞,也没老师,这样肯定能行的。   基础的话是语言,然后数据结构,然后算法。   ACM有三个方向:算法,数学,实现   要求三种能力:英文,自学,团队协作   简单的说,你要能读懂英文的题意描述,要有一门acm能使用的编程语言,要会数据结构,有一点数学基础,一点编程方面天赋,要有兴趣和毅力(最重要),就具有做ACM的基本条件了。   做acm我推荐c,c++也可以,java在某些情况下好用,但是大多数情况的效率和代码量都不大好,所以建议主用c++,有些题目用java   还有什么问题,可以问我啊。   不好意思,没见过用java描述的acm书籍,大多数是用伪命令,其他有的用的c,c++,老一些的用pascal。java只是用来做高精度的一些题的,个人觉得不用专门看这方面的书,java的基本部分学好就够用了。所以我还是推荐主用c++,在高精度和个别题再用java。你可以找找java描述的算法设计与分析,这个好像有   数据结构:C语言版 清华大学出版社 严蔚敏 《数据结构》   算法:清华大学出版社 王晓东 《算法设计与分析》   麻省理工大学 中译本:机械工业出版社 《算法导论》   基本上这三本书就已经足够了,建议一般水平的人先不要看算法导论,待另外两本书看的差不多的时候,再看算法导论加深理解。   另外还有很多针对性更强的书籍,不过针对性太强,这里就不多介绍了。   以上一些都是些算法方面的书,最好的方式就是做题与看书相结合,很多在线做题的网站,PKU,ZOJ很多,推荐PKU,题目比较多,参与的人比较多。做一段时间的题,然后看书,研究算法,再做题,这样进步比较快。   还有关于ACM竞赛,我有自己的一点话说。   首先说下ACM/ICPC是个团队项目,最后的参赛名额是按照学校为单位的,所以找到志同道合的队友和学校的支持是很重要的。   刚刚接触信息学领域的同学往往存在很多困惑,不知道从何入手学习,在这篇文章里,我希望能将自己不多的经验与大家分享,希望对各位有所帮助。   一、语言是最重要的基本功   无论侧重于什么方面,只要是通过计算机程序去最终实现的竞赛,语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA,众所周知,作为面向对象的王牌语言,JAVA在大型工程的组织与安全性方面有着自己独特的优势,但是对于信息学比赛的具体场合,JAVA则显得不那么合适,它对于输入输出流的操作相比于C++要繁杂很多,更为重要的是JAVA程序的运行速度要比C++慢10倍以上,而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽,这无疑对算法设计提出了更高的要求,是相当不利的。其实,笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维,因为对于小程序来说这不旦需要花费更多的时间去编写代码,也会降低程序的执行效率。   接着说C和C++。许多现在参加讲座的同学还在上大一,C的基础知识刚刚学完,还没有接触过C++,其实在赛场上使用纯C的选手还是大有人在的,它们主要是看重了纯C在效率上的优势,所以这部分同学如果时间有限,并不需要急着去学习新的语言,只要提高了自己在算法设计上的造诣,纯C一样能发挥巨大的威力。   而C++相对于C,在输入输出流上的封装大大方便了我们的操作,同时降低了出错的可能性,并且能够很好地实现标准流与文件流的切换,方便了调试的工作。如果有些同学比较在意这点,可以尝试C和C++的混编,毕竟仅仅学习C++的流操作还是不花什么时间的。   C++的另一个支持来源于标准模版库(STL),库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度,这可以节省一些时间。但是,与此相对的,使用STL要在效率上做出一些牺牲,对于输入规模很大的题目,有时候必须放弃STL,这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法;另外,熟练和恰当地使用STL必须经过一定时间的积累,准确地了解各种操作的时间复杂度,切忌对STL中不熟悉的部分滥用,因为这其中蕴涵着许多初学者不易发现的陷阱。   通过以上的分析,我们可以看出仅就信息学竞赛而言,对语言的掌握并不要求十分全面,但是对于经常用到的部分,必须十分熟练,不允许有半点不清楚的地方,下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍,都有可能酿成错误:   在去年清华的赛区上,有一个队在做F题的时候使用了cout和printf的混合输出,由于一个带缓冲一个不带,所以输出一长就混乱了。只是因为当时judge team中负责F题的人眼睛尖,看出答案没错只是顺序不对(答案有一页多,是所有题目中最长的一个输出),又看了看程序发现只是输出问题就给了个Presentation error(格式错)。如果审题的人不是这样而是直接给一个 Wrong Answer,相信这个队是很难查到自己错在什么地方的。   现在我们转入第二个方面的讨论,基础学科知识的积累。   二、以数学为主的基础知识十分重要   虽然被定性为程序设计竞赛,但是参赛选手所遇到的问题更多的是没有解决问题的思路,而不是有了思路却死活不能实现,这就是平时积累的基础知识不够。今年World Final的总冠军是波兰华沙大学,其成员出自于数学系而非计算机系,这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学,此外对于物理、电路等等也可能有一定应用,但是不多。因此,大一的同学也不必为自己还没学数据结构而感到不知从何入手提高,把数学捡起来吧。下面我来谈谈在竞赛中应用的数学的主要分支。   1、离散数学——作为计算机学科的基础,离散数学是竞赛中涉及最多的数学分支,其重中之重又在于图论和组合数学,尤其是图论。   图论之所以运用最多是因为它的变化最多,而且可以轻易地结合基本数据结构和许多算法的基本思想,较多用到的知识包括连通性判断、DFS和BFS,关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大,但是往往也是竞赛中的难题所在,如果有初学者对于这部分的某些具体内容暂时感到力不从心,也不必着急,可以慢慢积累。   竞赛中设计的组合计数问题大都需要用组合数学来解决,组合数学中的知识相比于图论要简单一些,很多知识对于小学上过奥校的同学来说已经十分熟悉,但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现,但是如果积累不够,任何一道这方面的题目却都有可能成为难题。   2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决,这部分在竞赛中的比重并不大,但只要来上一道,也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现,在运用密码学常识确定大概的过程之后,核心算法往往要涉及数论的内容。   3、计算几何——计算几何相比于其它部分来说是比较独立的,就是说它和其它的知识点很少有过多的结合,较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大,但也永远不会成为最弱的题。   4、线性代数——对线性代数的应用都是围绕矩阵展开的,一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。   5、概率论——竞赛是以黑箱来判卷的,这就是说你几乎不能动使用概率算法的念头,但这也并不是说概率就没有用。关于这一点,只有通过一定的练习才能体会。   6、初等数学与解析几何——这主要就是中学的知识了,用的不多,但是至少比高等数学多,我觉得熟悉一下数学手册上的相关内容,至少要知道在哪儿能查到,还是必要的。   7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道,但是一些题目的叙述背景往往需要和这部分有一定联系,掌握得牢固一些总归没有坏处。   以上就是竞赛所涉及的数学领域,可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学,因为数学是一切一切的基础。   三、数据结构与算法是真正的核心   虽然数学十分十分重要,但是如果让三个只会数学的人参加比赛,我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。   先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的,至于树,我个人觉得需要建树的问题有但是并不多。(但是树往往是很重要的分析工具)除此之外,排序和查找并不需要对所有方式都能很熟练的掌握,但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度,就又该说说哈希表了,竞赛时对时间的限制远远多于对空间的限制,这要求大家尽快掌握“以空间换时间”的原则策略,能用哈希表来存储的数据一定不要到时候再去查找,如果实在不能建哈希表,再看看能否建二叉查找树等等——这都是争取时间的策略,掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。   接着说说算法。算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。   常用算法中的另一类是以“相似或相同子问题”为核心的,包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划,如何抽象出重复的子问题是很多题目的难点所在,笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法(比如Floyd-Warshall算法),并且多阅读一些定理的证明,这虽然不能有什么直接的帮助,但是长期坚持就会对思维很有帮助。   四、团队配合   通过以上的介绍大家也可以看出,信息学竞赛对于知识面覆盖的非常广,想凭一己之力全部消化这些东西实在是相当困难的,这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间,具体的情况因成员的组成不同而不同,这里我就不再多说了。   五、练习、练习、再练习   知识的积累固然重要,但是信息学终究不是看出来的,而是练出来的,这是多少前人最深的一点体会,只有通过具体题目的分析和实践,才能真正掌握数学的使用和算法的应用,并在不断的练习中增加编程经验和技巧,提高对时间复杂度的感性认识,优化时间的分配,加强团队的配合。总之,在这里光有纸上谈兵是绝对不行的,必须要通过实战来锻炼自己。   大家一定要问,我们去哪里找题做,又如何检验程序是否正确呢。这大可不必担心,现在已经有了很多网上做题的站点,这些站点提供了大量的题库并支持在线判卷,你只需要把程序源码提交上去,马上就可以知道自己的程序是否正确,运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点,笔者不建议大家在所有这些站点上做题,选择一个就可以了,因为每个站点的题都有一定的难易比例,系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。   1、Ural:   Ural是中国学生对俄罗斯的Ural州立大学的简称 ,那里设立了一个Ural Online Problem Set,并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强,得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计,Ural的题目类型大概呈如下的分布:   题型   搜索   动态规划   贪心   构造   图论   计算几何   纯数学问题   数据结构   其它   所占比例   约10%   约15%   约5%   约5%   约10%   约5%   约20%   约5%   约25%   这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。   2、UVA:   UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ,并且支持ONLINE JUDGE,形式和Ural大学的题库类似。不过和Ural不同的是,UVA题目多的多,而且比较杂,而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从,要么难以找到合适的题目,要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法,那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛,因此那里强人无数,不过你先要使自己具有听懂他们在说什么的素质:)   3、ZOJ:   ZOJ是浙江大学建立的ONLINE JUDGE,是中国大学建立的第一个同类站点,也是最好和人气最高的一个,笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站,但是这里的中国学生比较多,因此让人觉得很亲切。这里目前有500多道题目,难易分配适中,且涵盖了各大洲的题目类型并配有索引,除此之外,ZOJ的JUDGE系统是几个网站中表现得比较好的一个,很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛,只要是注册的用户都可以参加。   说起中国的ONLINE JUDGE,去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统;而我们学校也是去年开始参加比赛,现在也有可能推出自己的提交系统,如果能够做成,到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索,这是一件好事,同时也意味着更激烈的竞争。

小旋风柴进 2019-12-02 01:20:20 0 浏览量 回答数 0

回答

[递归]-分- [递推] 和 [回归] 递归的概念及递归算法的结构 1、所谓的递归,是指函数在执行过程中自己调用了自己或者说某种数据结构在定义时又引用了自身。这两种情况都可理解为递归。比如: void fun() { .. fun() .. }//fun 以上函数fun就是一个递归函数。而针对于各种数据结构中的递归结构就更多了,如单链表,广义表,树。在这些递归结构中,具有一个相同的特征:其中的某个域的数据类型是其结点类型本身。 2、递归算法的大致结构为: a、递归出口 b、递归体 一个递归算法,当其问题求解的规模越来越小时必定有一个递归出口,就是不再递归调用的语句。递归体则是每次递归时执行的语句序列。比如以下简要描述的递归函数中: f(n)=1 (当n=0时) f(n)=n*f(n-1) (当n>0时) 这个递归函数,实际是求n的阶乘。当n=0时,不再递归调用,而当其值置为1;当n>0时,就执行n*f(n-1),这是递归调用。从整体上理解递归算法的大致结构有利于我们在设计递归算法时,从总体上把握算法的正确性。 二、栈与递归的关系:递归的运行 递归在实现过程中是借助于栈来实现的。高级语言的函数调用,每次调用,系统都要自动为该次调用分配一系列的栈空间用于存放此次调用的相关信息:返回地址,局部变量等。这些信息被称为工作记录(或活动记录)。而当函数调用完成时,就从栈空间内释放这些单元,但是,在该函数没有完成前,分配的这些单元将一直保存着不被释放。递归函数的实现,也是通过栈来完成的。在递归函数没有到达递归出口前,都要不停地执行递归体,每执行一次,就要在工作栈中分配一个工作记录的空间给该“层”调用存放相关数据,只有当到达递归出口时,即不再执行函数调用时,才从当前层返回,并释放栈中所占用的该“层”工作记录空间。请大家注意,递归调用时,每次保存在栈中的是局部数据,即只在当前层有效的数据,到达下一层时上一层的数据对本层数据没有任何影响,一切从当前调用时传过来的实在参数重新开始。 由此可见,从严老师P版教材中,利用栈将递归向非递归转化时所采用的方法,实质是用人工写的语句完成了本该系统程序完成的功能,即:栈空间中工作记录的保存和释放。大家在以后的作题时,可以参照以上的分析来理解递归函数的运行过程。实际上,现在的考试中,已经很少见到有学校要求运用栈与实现递归转化为非递归来解题了,所以,大家能理解这个算法更好,不能理解的也不用太担心。我曾就此问题专门向严老师咨询过,严老师说之所以在C版的教材中没有讲到这个算法,也是考虑到了目前国内学校在这方面已经基本不作要求。但是,递归算法的运行过程应该心中有数。 三、递归与递推的关系 “递归算法的执行过程分递推与回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。在回归阶段,当获得最简单的情况后,逐级返回,依次获得稍复杂问题的解。”(摘自于“高程”教材) “递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解,当N=1时,解或已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,3、、、i-1的一系列解,构造出问题规模为i的解。直到最终得到问题规模为N的解。” 由此可见,递推是递归的一个阶段,递归包含着递推。当然,对于实际的算法设计,知不知道这两者之间的关系并不重要,重要的是我们能找出这其中的递推规律和回归时机。 四、适合于用递归实现的问题类型 必须具有两个条件的问题类型才能用递归方法求得: 1、规模较大的一个问题可以向下分解为若干个性质相同的规模较小的问题,而这些规模较小的问题仍然可以向下分解。 2、当规模分解到一定程度时,必须有一个终止条件,不得无限分解。 由此可见适合于递归实现的问题类型有: 1、函数定义是递归的。如阶乘,FIB数列。 2、数据结构递归的相关算法。如:树结构。 3、解法是递归的。如:汉诺塔问题。 五、递归算法的设计 从递归算法的结构来分析,进行递归算法的设计时,无非要解决两个问题:递归出口和递归体。即要确定何时到达递归出口,何时执行递归体,执行什么样的递归体。递归算法算法设计的关键是保存每一层的局部变量并运用这些局部变量。由此,递归算法的设计步骤可从以下三步来作: 1、分析问题,分解出小问题; 2、找出小问题与大问题之间的关系,确定递归出口; 3、用算法语言写出来。 六、递归算法向非递归算法的转化方法 1、迭代法 如果一个函数既有递归形式的定义,又有非递归的迭代形式的定义,则通常可以用循环来实现递归算法的功能。 2、消除尾递归 尾递归,是一类特殊的递归算法。它是指在此递归算法中,当执行了递归调用后,递归调用语句后面再没有其它可以执行的语句了,它即没有用到外层的状态,也没有必要保留每次的返回地址,因为其后不再执行其它任何*作,所以可以考虑消除递归算法。这种情况下,我们可以用循环结构设置一些工作单元来帮助消除尾递归,这些工作单元用于存放一层层的参数。 3、利用栈 当一个递归算法不利于用迭代法和消除尾递归法实现向非递归算法的转化时,可以考虑用栈来实现。实现的过程实际上就是用人工的方法模拟系统程序来保存每层的参数,返回地址,以及对参数进行运算等。 一般情况下,对于递归算法向非递归算法的转化问题,特别是结构定义时的递归算法,我们通常先写出递归算法,然后再向非递归算法转化,而不是首先就尝试写出非递归算法来。

祁同伟 2019-12-02 01:25:44 0 浏览量 回答数 0

回答

曾经因为看不懂数据结构和算法,而一度怀疑是自己太笨,实际上,很多人在第一次接触这门课时,都会有这种感觉,觉得数据结构和算法很抽象,晦涩难懂,宛如天书。正是这个原因,让很多初学者对这门课望而却步,希望以下分享能为初学者排忧解难。 我个人觉得,其实真正的原因是你没有找到好的学习方法,没有抓住学习的重点。实际上,数据结构和算法的东西并不多,常用的、基础的知识点更是屈指可数。只要掌握了正确的学习方法,学起来并没有看上去那么难,更不需要什么高智商、厚底子。 还记得大学里每次考前老师都要划重点吗?今天,我就给你划划我们这门课的重点,再告诉你一些我总结的学习小窍门。相信有了这些之后,你学起来就会有的放矢、事半功倍了。 什么是数据结构?什么是算法? 大部分数据结构和算法教材,在开篇都会给这两个概念下一个明确的定义。但是,这些定义都很抽象,对理解这两个概念并没有实质性的帮助,反倒会让你陷入死抠定义的误区。毕竟,我们现在学习,并不是为了考试,所以,概念背得再牢,不会用也就没什么用。 虽然我们说没必要深挖严格的定义,但是这并不等于不需要理解概念。下面我就从广义和狭义两个层面,来帮你理解数据结构与算法这两个概念。 从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。 图书馆储藏书籍你肯定见过吧?为了方便查找,图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。 那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法。 从狭义上讲,是指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶,我们可以直接拿来用。我们要讲的这些经典数据结构和算法,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,可以高效地帮助我们解决很多实际的开发问题。 那数据结构和算法有什么关系呢?为什么大部分书都把这两个东西放到一块儿来讲呢? 这是因为,数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。 比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。 数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的数据结构就是没用的。 现在你对数据结构与算法是不是有了比较清晰的理解了呢?有了这些储备,下面我们来看看,究竟该怎么学数据结构与算法。 看到数据结构和算法里的“算法”两个字,很多人就会联想到“数学”,觉得算法会涉及到很多深奥的数学知识。那我数学基础不是很好,学起来会不会很吃力啊? 数据结构和算法课程确实会涉及一些数学方面的推理、证明,尤其是在分析某个算法的时间、空间复杂度的时候,但是这个你完全不需要担心。 学习的重点在什么地方? 提到数据结构和算法,很多人就很头疼,因为这里面的内容实在是太多了。这里,我就帮你梳理一下,应该先学什么,后学什么。你可以对照看看,你属于哪个阶段,然后有针对地进行学习。 想要学习数据结构与算法,首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。 这个概念究竟有多重要呢?可以这么说,它几乎占了数据结构和算法这门课的半壁江山,是数据结构和算法学习的精髓。 数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。所以,如果你只掌握了数据结构和算法的特点、用法,但是没有学会复杂度分析,那就相当于只知道操作口诀,而没掌握心法。只有把心法了然于胸,才能做到无招胜有招! 所以,复杂度分析这个内容,你也一定要花大力气来啃,必须要拿下,并且要搞得非常熟练。否则,后面的数据结构和算法也很难学好。 搞定复杂度分析,下面就要进入数据结构与算法的正文内容了。 为了让你对数据结构和算法能有个全面的认识,我画了一张图,里面几乎涵盖了所有数据结构和算法书籍中都会讲到的知识点。 但是,作为初学者,或者一个非算法工程师来说,你并不需要掌握图里面的所有知识点。很多高级的数据结构与算法,比如二分图、最大流等,这些在我们平常的开发中很少会用到。所以,你暂时可以不用看。我还是那句话,咱们学习要学会找重点。如果不分重点地学习,眉毛胡子一把抓,学起来肯定会比较吃力。 所以,结合我自己的学习心得,还有这些年的面试、开发经验,我总结了20个最常用的、最基础数据结构与算法,不管是应付面试还是工作需要,只要集中精力逐一攻克这20个知识点就足够了。 这里面有10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树;10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。 掌握了这些基础的数据结构和算法,再学更加复杂的数据结构和算法,就会非常容易、非常快。 与此同时,为了帮助大家学习算法,准备了一份学习资料,获取方式:关注我的公众号“程序媛不是程序猿”,回复“算法”即可弹出领取地址。对于新手来说很适用。 在学习数据结构和算法的过程中,你也要注意,不要只是死记硬背,不要为了学习而学习,而是要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”。对于每一种数据结构或算法,我都会从这几个方面进行详细讲解。只要你掌握了《数据结构与算法之美》每节课里讲的内容,就能在开发中灵活应用。 学习数据结构和算法的过程,是非常好的思维训练的过程,所以,千万不要被动地记忆,要多辩证地思考,多问为什么。如果你一直这么坚持做,你会发现,等你学完之后,写代码的时候就会不由自主地考虑到很多性能方面的事情,时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。你的编程内功就真正得到了修炼。 一些可以让你事半功倍的学习技巧 前面我给你划了学习的重点,作为一个过来人,现在我就给你分享一下,学习的一些技巧。掌握了这些技巧,可以让你化被动为主动,学起来更加轻松,更加有动力! 边学边练,适度刷题 “边学边练”这一招非常有用。建议你每周花1~2个小时的时间,集中把这周的三节内容涉及的数据结构和算法,全都自己写出来,用代码实现一遍。这样一定会比单纯地看或者听的效果要好很多! 有面试需求的同学,可能会问了,那我还要不要去刷题呢? 我个人的观点是可以“适度”刷题,但一定不要浪费太多时间在刷题上。我们学习的目的还是掌握,然后应用。除非你要面试Google、Facebook这样的公司,它们的算法题目非常非常难,必须大量刷题,才能在短期内提升应试正确率。如果是应对国内公司的技术面试,即便是BAT这样的公司,你只要彻底掌握这个专栏的内容,就足以应对。 多问、多思考、多互动 学习最好的方法是,找到几个人一起学习,一块儿讨论切磋,有问题及时寻求老师答疑。但是,离开大学之后,既没有同学也没有老师,这个条件就比较难具备了。 打怪升级学习法 学习的过程中,我们碰到最大的问题就是,坚持不下来。是的,很多基础课程学起来都非常枯燥。为此,我自己总结了一套“打怪升级学习法”。 游戏你肯定玩过吧?为什么很多看起来非常简单又没有乐趣的游戏,你会玩得不亦乐乎呢?这是因为,当你努力打到一定级别之后,每天看着自己的经验值、战斗力在慢慢提高,那种每天都在一点一点成长的成就感就不由自主地产生了。 知识需要沉淀,不要想试图一下子掌握所有 在学习的过程中,一定会碰到“拦路虎”。如果哪个知识点没有怎么学懂,不要着急,这是正常的。因为,想听一遍、看一遍就把所有知识掌握,这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。 这些内容是我根据平时的学习和工作、面试经验积累,精心筛选出来的。只要掌握这些内容,应付日常的面试、工作,基本不会有问题。 以上内容出自近70000+程序员的算法课堂《数据结构与算法之美》,这个专栏是市面上唯一一门真正适用于工程师的专栏,专栏中列举大量实际软件开发中的场景,给你展示如何利用数据结构和算法解决真实的问题。整个专栏会涵盖100 多个算法真实项目场景案例,更难得的是它跟市面上晦涩的算法书籍不同的是,还手绘了一些清晰易懂的详解图(总共有 300 多张)。 手绘图—出自《数据结构与算法之美》 专栏已经更新完毕,72 篇文章,27 万字,这个专栏作者并非只是单纯地把某个知识点讲清楚,而是结合作者的理解、实践和经验来讲解,我相信它是一个跟所有国内、国外经典书籍都不一样的专栏,一个可以长期影响一些人的专栏。 这个专栏不会像《算法导论》那样,里面有非常复杂的数学证明和推理。作者会由浅入深,从概念到应用,一点一点给你解释清楚。你只要有高中数学水平,就完全可以学习。 当然,当然希望你最好有些编程基础,如果有项目经验就更好了。这样给你讲数据结构和算法如何提高效率、如何节省存储空间,你就会有很直观的感受。因为,对于每个概念和实现过程,作者都会从实际场景出发,不仅教你“是什么”,还会教你“为什么”,并且告诉你遇到同类型问题应该“怎么做”。 强烈推荐这个专栏给想攻克算法的同学,它改变了无数对算法恐惧的同学,我整理了一些专栏的评价给大家参考。

游客arp6khj2dsufi 2019-12-02 03:09:08 0 浏览量 回答数 0

回答

看数据量咯,也就是那200ms的价值,在可观的未来,如果数据量会暴涨,上方案2######在大家心里可以承受的时间范围内就方案2。 假如批量数据处理方案2需要1个小时,这时候方案1的重要性来了,毕竟时间减少了一半。######数据量增多到预想的情况下,你跑一下看看能否接受这种效率,能的话方案2。。当然从性能来讲当然选方案1了######确认算法保证没错的情况用1######刨除数据量、硬件成本、时间成本,没法判断的。 真实处理的数据量是多少,能否通过分布式提高效率,可以接受的最长业务处理时间是多少?离开这些谈算法,都是没意义的。 实际上,现代的计算时间早就是大白菜了,所以99.99%的时候,算法2都比1要合适。虽然慢一倍,但是算法的排错修改时间肯定远远小于1,至于慢的速度,拿十倍20倍的硬件堆就是。###### 引用来自“魔力猫”的评论 刨除数据量、硬件成本、时间成本,没法判断的。 真实处理的数据量是多少,能否通过分布式提高效率,可以接受的最长业务处理时间是多少?离开这些谈算法,都是没意义的。 实际上,现代的计算时间早就是大白菜了,所以99.99%的时候,算法2都比1要合适。虽然慢一倍,但是算法的排错修改时间肯定远远小于1,至于慢的速度,拿十倍20倍的硬件堆就是。 用硬件对不妨是一个解决办法,但还是要结合实际的业务场景来决定的 关键还是要看你这个计算再在你整个要解决的业务场景中所占的比重,比重越高性能要求越高######再写一层封装,自动选择算法不就行了吗。 比如说什么情况下用算法1,什么情况下用算法2。这样还有个扩展性的好处,以后你又发现了新算法。你还可以加在里面,什么时候用算法3都是没有问题的。######一个运算就消耗200ms,A星寻路算法(图形寻路比较高效且适用性比较广以及相对复杂的逻辑算法,在此随便举例而已),如果是这个时间级别都得使劲优化。400ms的方案二直接pass掉,哪怕方案一只耗时200ms,你测试一下并发量看看,耗时100ms的业务并发就很糟糕了(单机情况),自己实测一下你就知道200ms的差距是什么概念了。 如果并发情况加锁同步执行一个200ms耗时的算法,加锁同步也就可以理解为顺序执行,你想想1s也就执行5次而已,那些说堆硬件的简直胡扯,堆硬件只是没办法的办法。哪怕是方案一,我觉得如果还有优化的空间还得优化。 如果软件没有并发需求,即不会有多用户同时触发执行此算法的情况下,方案二当然是可以的。######有条件的情况,当然是越快的算法越好,根据数据量取优的话,需要大量测试,根据曲线取临界值的

kun坤 2020-05-30 22:45:53 0 浏览量 回答数 0

问题

选择VPS主机的六大要点

孙康 2019-12-01 22:06:06 10294 浏览量 回答数 3

回答

1. 原始单据与实体之间的关系 可以是一对一、一对多、多对多的关系。在一般情况下,它们是一对一的关系:即一张原始单据对应且只对应一个实体。在特殊情况下,它们可能是一对多或多对一的关系,即一张原始单证对应多个实体,或多张原始单证对应一个实体。 这里的实体可以理解为基本表。明确这种对应关系后,对我们设计录入界面大有好处。 〖例1〗:一份员工履历资料,在人力资源信息系统中,就对应三个基本表:员工基本情况表、社会关系表、工作简历表。这就是“一张原始单证对应多个实体”的典型例子。 2. 主键与外键 一般而言,一个实体不能既无主键又无外键。在E—R 图中, 处于叶子部位的实体, 可以定义主键,也可以不定义主键(因为它无子孙), 但必须要有外键(因为它有父亲)。 主键与外键的设计,在全局数据库的设计中,占有重要地位。当全局数据库的设计完成以后,有个美国数据库设计专家说:“键,到处都是键,除了键之外,什么也没有”,这就是他的数据库设计经验之谈,也反映了他对信息系统核心(数据模型)的高度抽象思想。 因为:主键是实体的高度抽象,主键与外键的配对,表示实体之间的连接。 3. 基本表的性质 基本表与中间表、临时表不同,因为它具有如下四个特性: 原子性。基本表中的字段是不可再分解的。原始性。基本表中的记录是原始数据(基础数据)的记录。演绎性。由基本表与代码表中的数据,可以派生出所有的输出数据。稳定性。基本表的结构是相对稳定的,表中的记录是要长期保存的。理解基本表的性质后,在设计数据库时,就能将基本表与中间表、临时表区分开来。 4. 范式标准 基本表及其字段之间的关系, 应尽量满足第三范式。但是,满足第三范式的数据库设计,往往不是最好的设计。为了提高数据库的运行效率,常常需要降低范式标准:适当增加冗余,达到以空间换时间的目的。〖例2〗:有一张存放商品的基本表,如表1所示。“金额”这个字段的存在,表明该表的设计不满足第三范式,因为“金额”可以由“单价”乘以“数量”得到,说明“金额”是冗余字段。但是,增加“金额”这个冗余字段,可以提高查询统计的速度,这就是以空间换时间的作法。在Rose 2002中,规定列有两种类型:数据列和计算列。“金额”这样的列被称为“计算列”,而“单价”和“数量”这样的列被称为“数据列”。640?wx_fmt=png 表1 商品表的表结构 5. 通俗地理解三个范式 通俗地理解三个范式,对于数据库设计大有好处。在数据库设计中,为了更好地应用三个范式,就必须通俗地理解三个范式(通俗地理解是够用的理解,并不是最科学最准确的理解): 第一范式:1NF是对属性的原子性约束,要求属性具有原子性,不可再分解 第二范式:2NF是对记录的惟一性约束,要求记录有惟一标识,即实体的惟一性; 第三范式:3NF是对字段冗余性的约束,即任何字段不能由其他字段派生出来,它要求字段没有冗余。 没有冗余的数据库设计可以做到。但是,没有冗余的数据库未必是最好的数据库,有时为了提高运行效率,就必须降低范式标准,适当保留冗余数据。具体做法是:在概念数据模型设计时遵守第三范式,降低范式标准的工作放到物理数据模型设计时考虑。降低范式就是增加字段,允许冗余。 6. 要善于识别与正确处理多对多的关系 若两个实体之间存在多对多的关系,则应消除这种关系。消除的办法是,在两者之间增加第三个实体。这样,原来一个多对多的关系,现在变为两个一对多的关系。要将原来两个实体的属性合理地分配到三个实体中去。 这里的第三个实体,实质上是一个较复杂的关系,它对应一张基本表。一般来讲,数据库设计工具不能识别多对多的关系,但能处理多对多的关系。 〖例3〗:在“图书馆信息系统”中,“图书”是一个实体,“读者”也是一个实体。这两个实体之间的关系,是一个典型的多对多关系:一本图书在不同时间可以被多个读者借阅,一个读者又可以借多本图书。为此,要在二者之间增加第三个实体,该实体取名为“借还书”,它的属性为:借还时间、借还标志(0表示借书,1表示还书),另外,它还应该有两个外键(“图书”的主键,“读者”的主键),使它能与“图书”和“读者”连接。 7. 主键PK的取值方法 PK是供程序员使用的表间连接工具,可以是一无物理意义的数字串, 由程序自动加1来实现。也可以是有物理意义的字段名或字段名的组合。不过前者比后者好。当PK是字段名的组合时,建议字段的个数不要太多,多了不但索引占用空间大,而且速度也慢。 8. 正确认识数据冗余 主键与外键在多表中的重复出现, 不属于数据冗余,这个概念必须清楚,事实上有许多人还不清楚。非键字段的重复出现, 才是数据冗余!而且是一种低级冗余,即重复性的冗余。高级冗余不是字段的重复出现,而是字段的派生出现。〖例4〗:商品中的“单价、数量、金额”三个字段,“金额”就是由“单价”乘以“数量”派生出来的,它就是冗余,而且是一种高级冗余。冗余的目的是为了提高处理速度。 只有低级冗余才会增加数据的不一致性,因为同一数据,可能从不同时间、地点、角色上多次录入。因此,我们提倡高级冗余(派生性冗余),反对低级冗余(重复性冗余)。 9. E--R图没有标准答案 信息系统的E--R图没有标准答案,因为它的设计与画法不是惟一的,只要它覆盖了系统需求的业务范围和功能内容,就是可行的。反之要修改E--R图。尽管它没有惟一的标准答案,并不意味着可以随意设计。好的E—R图的标准是:结构清晰、关联简洁、实体个数适中、属性分配合理、没有低级冗余。 10. 视图技术在数据库设计中很有用 与基本表、代码表、中间表不同,视图是一种虚表,它依赖数据源的实表而存在。视图是供程序员使用数据库的一个窗口,是基表数据综合的一种形式, 是数据处理的一种方法,是用户数据保密的一种手段。 为了进行复杂处理、提高运算速度和节省存储空间, 视图的定义深度一般不得超过三层。若三层视图仍不够用, 则应在视图上定义临时表, 在临时表上再定义视图。这样反复交迭定义, 视图的深度就不受限制了。 对于某些与国家政治、经济、技术、军事和安全利益有关的信息系统,视图的作用更加重要。这些系统的基本表完成物理设计之后,立即在基本表上建立第一层视图,这层视图的个数和结构,与基本表的个数和结构是完全相同。并且规定,所有的程序员,一律只准在视图上操作。 只有数据库管理员,带着多个人员共同掌握的“安全钥匙”,才能直接在基本表上操作。请读者想想:这是为什么? 11. 中间表、报表和临时表 中间表是存放统计数据的表,它是为数据仓库、输出报表或查询结果而设计的,有时它没有主键与外键(数据仓库除外)。临时表是程序员个人设计的,存放临时记录,为个人所用。基表和中间表由DBA维护,临时表由程序员自己用程序自动维护。 12. 完整性约束表现在三个方面 域的完整性:用Check来实现约束,在数据库设计工具中,对字段的取值范围进行定义时,有一个Check按钮,通过它定义字段的值城。 参照完整性:用PK、FK、表级触发器来实现。用户定义完整性:它是一些业务规则,用存储过程和触发器来实现。 13. 防止数据库设计打补丁的方法是“三少原则” 1、一个数据库中表的个数越少越好。只有表的个数少了,才能说明系统的E--R图少而精,去掉了重复的多余的实体,形成了对客观世界的高度抽象,进行了系统的数据集成,防止了打补丁式的设计; 2、一个表中组合主键的字段个数越少越好。因为主键的作用,一是建主键索引,二是做为子表的外键,所以组合主键的字段个数少了,不仅节省了运行时间,而且节省了索引存储空间; 3、一个表中的字段个数越少越好。只有字段的个数少了,才能说明在系统中不存在数据重复,且很少有数据冗余,更重要的是督促读者学会“列变行”,这样就防止了将子表中的字段拉入到主表中去,在主表中留下许多空余的字段。所谓“列变行”,就是将主表中的一部分内容拉出去,另外单独建一个子表。这个方法很简单,有的人就是不习惯、不采纳、不执行。 数据库设计的实用原则是:在数据冗余和处理速度之间找到合适的平衡点。“三少”是一个整体概念,综合观点,不能孤立某一个原则。该原则是相对的,不是绝对的。“三多”原则肯定是错误的。试想:若覆盖系统同样的功能,一百个实体(共一千个属性) 的E--R图,肯定比二百个实体(共二千个属性)的E--R图,要好得多。 提倡“三少”原则,是叫读者学会利用数据库设计技术进行系统的数据集成。数据集成的步骤是将文件系统集成为应用数据库,将应用数据库集成为主题数据库,将主题数据库集成为全局综合数据库。 集成的程度越高,数据共享性就越强,信息孤岛现象就越少,整个企业信息系统的全局E—R图中实体的个数、主键的个数、属性的个数就会越少。提倡“三少”原则的目的,是防止读者利用打补丁技术,不断地对数据库进行增删改,使企业数据库变成了随意设计数据库表的“垃圾堆”,或数据库表的“大杂院”,最后造成数据库中的基本表、代码表、中间表、临时表杂乱无章,不计其数,导致企事业单位的信息系统无法维护而瘫痪。 “三多”原则任何人都可以做到,该原则是“打补丁方法”设计数据库的歪理学说。“三少”原则是少而精的原则,它要求有较高的数据库设计技巧与艺术,不是任何人都能做到的,因为该原则是杜绝用“打补丁方法”设计数据库的理论依据。 14. 提高数据库运行效率的办法 在给定的系统硬件和系统软件条件下,提高数据库系统的运行效率的办法是:在数据库物理设计时,降低范式,增加冗余, 少用触发器, 多用存储过程。 当计算非常复杂、而且记录条数非常巨大时(例如一千万条),复杂计算要先在数据库外面,以文件系统方式用C++语言计算处理完成之后,最后才入库追加到表中去。这是电信计费系统设计的经验。 发现某个表的记录太多,例如超过一千万条,则要对该表进行水平分割。水平分割的做法是,以该表主键PK的某个值为界线,将该表的记录水平分割为两个表。若发现某个表的字段太多,例如超过八十个,则垂直分割该表,将原来的一个表分解为两个表。 对数据库管理系统DBMS进行系统优化,即优化各种系统参数,如缓冲区个数。在使用面向数据的SQL语言进行程序设计时,尽量采取优化算法。 总之,要提高数据库的运行效率,必须从数据库系统级优化、数据库设计级优化、程序实现级优化,这三个层次上同时下功夫。

茶什i 2019-12-27 15:54:46 0 浏览量 回答数 0

问题

ES 在数据量很大的情况下(数十亿级别)如何提高查询效率啊?【Java问答学堂】28期

剑曼红尘 2020-05-28 09:45:28 15 浏览量 回答数 1

问题

广西地区备案,手机号码有限制

龟大王 2019-12-01 21:14:46 7502 浏览量 回答数 2

问题

游戏云间之三:游戏运维

起航 2019-12-01 21:43:27 23458 浏览量 回答数 17

回答

基础类 常见十大算法 优劣术语稳定性 原本a在b前,a=b,排序之后位置任然不变。不稳定性则相反内排序 所有排序都在内存中完成。外排序数据放磁盘,排序通过磁盘内存的数据传输事件复杂度 算法执行耗费的时间 空间复杂度 算法执行耗费的内存 In/out-place: 不占/占额外内存 冒泡排序: 选择排序: 插入排序: 希尔排序: 归并排序: 快速排序: 堆排序: 计数排序: 桶排序: 基数排序: 提高类 常见算法面试题 Problem 1 : Is it a loop ? (判断链表是否有环?) Assume that wehave a head pointer to alink-list. Also assumethat we know the list is single-linked. Can you come upan algorithm to checkwhether this link list includes a loop by using O(n) timeand O(1) space wheren is the length of the list? Furthermore, can you do sowith O(n) time and onlyone register? 方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。 同样的,可以找到链表的中间节点。同上。 Problem 2:设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。 提示:双指针查找 Problem 3:用最简单的方法判断一个LONG整形的数A是2^n(2的n次方) 提示:x&(x-1) Problem 4:两个烧杯,一个放糖一个放盐,用勺子舀一勺糖到盐,搅拌均匀,然后舀一勺混合物会放糖的烧杯,问你两个烧杯哪个杂质多? 提示:相同。假设杂质不等,那么将杂质放回原杯中,则杯中物体重量必变化,不合理。 Problem 5:给你a、b两个文件,各存放50亿条url,每条url各占用64字节,内存限制是4G,让你找出a、b文件共同的url。 法1:使用hash表。使用a中元素创建hash表,hash控制在适当规模。在hash中查找b的元素,找不到的url先存在新文件中,下次查找。如果找到,则将相应的hash表项删除,当hash表项少于某个阈值时,将a中新元素重新hash。再次循环。 法2:对于hash表项增加一项记录属于的文件a,b。只要不存在的表项即放入hash表中,一致的项则删除。注意:可能存在很多重复项,引起插入,删除频繁。 Problem 6:给你一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词。现在给你一个字典,用户输入一个单词,让你根据字典找出这个单词有多少个兄弟单词。 提示:将每个的单词按照字母排序,则兄弟单词拥有一致的字母排序(作为单词签名)。使用单词签名来查找兄弟单词。 Problem 7:五桶球,一桶不正常,不知道球的重量和轻重关系,用天平称一次找出那桶不正常的球。 Problem 8:给两个烧杯,容积分别是m和n升(m!=n),还有用不完的水,用这两个烧杯能量出什么容积的水? m, n, m+n, m-n以及线性叠加的组合 Problem 9:写出一个算法,对给定的n个数的序列,返回序列中的最大和最小的数。 Problem 10:你能设计出一个算法,只需要执行1.5n次比较就能找到序列中最大和最小的数吗?能否再少? 提示:先通过两两比较,区分大小放入“大”,“小”两个数组中。从而最大数在“大”数组中,最小数在“小”数组中。 Problem 11:给你一个由n-1个整数组成的未排序的序列,其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性-时间算法。 提示:累加求和 Problem 12:void strton(constchar* src, const char*token) 假设src是一长串字符,token存有若干分隔符,只要src的字符是token中的任何一个,就进行分割,最终将src按照token分割成若干单词。找出一种O(n)算法? 提示:查表的方法,将所有的字符串存储在长度为128的数组中,并将作为分隔符的字符位置1,这样即可用常数时间判断字符是否为分隔符,通过n次扫描,将src分割成单词。 Problem 13:一个排好序的数组A,长度为n,现在将数组A从位置m(m<n,m未知)分开,并将两部分互换位置,假设新数组记为B,找到时间复杂度为O(lgn)的算法查找给定的数x是否存在数组B中? 提示:同样采用二分查找。核心思想就是确定所查找数所在的范围。通过比较3个数(头,尾,中间)和所查找数之间的关系,可以确定下次查找的范围。 Problem 14:一个排好序的数组A,长度为n,现在将数组A从位置m(m<n,m已知)分开,并将两部分互换位置,设计一个O(n)的算法实现这样的倒置,只允许使用一个额外空间。(循环移位的效率不高) 提示:(A’B’)’ =BA Problem 15:给出Vector的一个更好实现。(STL的vector内存的倍增的,但是每次倍增需要拷贝已存元素,平均每个元素需要拷贝一次,效率不高) 提示:可使用2^n的固定长度作为每次分配的最小单位,并有序的记录每个块的首地址。这中结构同样可以实现线性查找,并且拷贝代价很低(仅有指针) Problem 16:给出已排序数组A,B,长度分别为n,m,请找出一个时间复杂度为(lgn)的算法,找到排在第k位置的数。 提示:二分查找。 Problem 17:给出任意数组A,B,长度分别为n,m,请找出一个时间复杂度为(lgn)的算法,找到排在第k位置的数。 提示:通过最小堆记录k个数,不断更新,扫描一次完毕。 这个提示有问题,求最优算法! Problem 18:假设数组A有n个元素,元素取值范围是1~n,判定数组是否存在重复元素?要求复杂度为O(n)。 法1:使用n的数组,记录元素,存在记为1,两次出现1,即重复。 法2:使用m的数组,分别记录大小:n/m, 2n/m …..的元素个数。桶方法 法3:累加求和。可用于求仅有一个元素重复的方法。 Problem 19:给定排好序的数组A,大小为n,现给定数X,判断A中是否存在两数之和等于X。给出一个O(n)的算法。 提示:从中间向两边查找。利用有序的条件 Problem 20:给定排好序的数组A,大小为n,请给出一个O(n)的算法,删除重复元素,且不能使用额外空间。 提示,既然有重复,必有冗余空间。将元素放入数组的前面,并记录下次可放位置,不断向后扫描即可。 Problem 21:给定两个排好序的数组A,B,大小分别为n,m。给出一个高效算法查找A中的哪些元素存在B数组中。 注意:一般在大数组中执行二分查找,将小数组的元素作为需查找的对象。 更优算法(轩辕刃提供):可以使用两个指针遍历AB,比较当前大小就可以了...时间复杂度o(n+m) Problem 22:问:有1000桶酒,其中1桶有毒。而一旦吃了,毒性会在1周后发作。现在我们用小老鼠做实验,要在1周内找出那桶毒酒,问最少需要多少老鼠。 答案:10只。将酒编号为1~1000 将老鼠分别编号为1 2 4 8 16 32 64 128 256 512 喂酒时 让酒的编号等于老鼠编号的加和如:17号酒喂给1号和16号老鼠 76号酒喂给4号、8号和64号老鼠 七天后将死掉的老鼠编号加起来 得到的编号就是有毒的那桶酒 因为2的10次方等于1024 所以10只老鼠最多可以测1024桶酒 证明如下:使用二进制表示:01, 10, 100, 1000,… , 1,000,000,000。对于任何一个小于1024的数,均可以采用前面的唯一一组二进制数来表示。故成立。 Problem 23:设计一组最少个数砝码,使得天平能够称量1~1000的重量。 如果砝码只能放单边,1,2 ,4 , 512最好。(只能单加) 如果允许砝码双边放,1, 3, 9, 27…. 最好。(可加可减)已知1,3,如何计算下一个数。现可称重量1,2,3,4。设下个数为x,可称重量为, x-4, x-3, x-2, x-1, x, x+1,x+2, x+3, x+4。为使砝码最好,所称重量应该不重复(浪费)。故x=9。同理,可得后面。 图形算法题 Problem 24:如何判断一个点是否在一个多边形内? 提示:对多边形进行分割,成为一个个三角形,判断点是否在三角形内。 一个非常有用的解析几何结论:如果P2(x1,y1),P2(x2,y2),P3(x3,y3)是平面上的3个点,那么三角形P1P2P3的面积等于下面绝对值的二分之一: | x1 y1 1 | | x2 y2 1 | = x1y2 + x3y1 + x2y3 –x3y2 – x2y1 – x1y3 | x3 y3 1 | 当且仅当点P3位于直线P1P2(有向直线P1->P2)的右侧时,该表达式的符号为正。这个公式可以在固定的时间内,检查一个点位于两点确定直线的哪侧,以及点到直线的距离(面积=底*高/2)。 这个结论:可以用来判断点是否在点是否在三角形内。法1:判断点和三角形三边所行程的3个三角形的面积之和是否等于原来三角形的面积。(用了三次上面的公式)。 法2:判断是否都在三条边的同一边,相同则满足,否则不在三角形内。 Problem 25:给出两个n为向量与0点形成角的角平分线。 提示:对两条边进行归一化,得到长度为1的两点,取两个的中点即可。 实战类型 1,确定函数名字与原型 2,严进宽出 3,边界考虑 4,出错处理 5,性能优化(时间复杂度,空间复杂度) 6,循环的掌握 7,递归的应用 8,2个指针跑步 9, Hash算法

happycc 2019-12-02 02:11:37 0 浏览量 回答数 0

问题

性能优化总结:CPU和Load、NIO以及多线程:报错

kun坤 2020-06-07 21:31:24 0 浏览量 回答数 1

回答

对于算法的学习,我也是从一个小白一步步走来,当然,现在仍然很菜,,,不过,鉴于我觉得还有一些人比我更菜了,我决定谈谈我算法学习过程走过的坑,以及自己总结的一些经验。 切勿盲目刷题:刷题前的知识积累 说实话,想要提高自己的算法,真的没啥捷径,我觉得最好的捷径就是脚踏实地着多动手去刷题,多刷题。 但是,我必须提醒的是,如果你是小白,也就是说,你连常见的数据结构,如链表、树以及常见的算法思想,如递归、枚举、动态规划这些都没学过,那么,我不建议你盲目疯狂着去刷题的。而是先去找本书先去学习这些必要的知识,然后再去刷题。 因为,如果这些基础都不懂的话,估计一道题做了几个小时,然后看答案都看不懂,做题没有任何思路,这是很难受的。久而久之,估计没啥动力了,我刚开始就是这样,一道题答案看一天,然而还是不大懂,什么回溯啊,暴力啊,还不知道是啥意思。 也就是说,假如你要去诸如leetcode这些网站刷题,那么,你要先具备一定的基础,这些基础包括: 1、常见数据结构:链表、树(如二叉树)。(是的,链表和二叉树是重点,图这些可以先放着) 2、常见算法思想:贪婪法、分治法、穷举法、动态规划,回溯法。(贪婪、穷举、分治是基础,动态规划有难度,可以先放着) 以上列出来的算是最基本的吧。就是说你刷题之前,要把这些过一遍再去刷题。如果你连这些最基本的都不知道的话,那么你再刷题的过程中,会很难受的,思路也会相对比较少。 总之,千万不要急,先把这些基本的过一遍,力求理解,再去刷题。 在这里,我推荐基本我大一时看过的书籍吧,感觉还是非常不错的,如果对于数据结构时零基础的话,那么我建议你可以看《数据结构与算法分析:C语言描述版》这本书,这本书自认为真的很 nice,当时我把这本书里面的全部都看了,并且 coding 了一遍,感觉整个人有了质的飞跃。 后面我时在一些学校的OJ刷题,当时看的一本书叫做《挑战程序设计大赛》,日本作家写的,我觉得这本书也很nice,里面有分初级,中级和高级三个模块,基础比较差的可以从初级开始看起。 当然,这两本书,你可以在这个Github上找到:https://github.com/iamshuaidi/CS-Book 总结下: 提高数据结构与算法没啥捷径,最好的捷径就是多刷题。但是,刷题的前提是你要先学会一些基本的数据结构与算法思想。 AC不是目的,我们要追求完美 如何刷题?如何对待一道算法题? 我觉得,在做题的时候,一定要追求完美,千万不要把一道题做出来之后,提交通过,然后就赶紧下一道。我认为这意义不大,因为一道题的解法太多了,有些解法态粗糙了,我们应该要寻找最优的方法。 算法能力的提升和做题的数量是有一定的关系,但并不是线性关系。也就是说,在做题的时候,要力求一题多解,如果自己实在想不出来其他办法了,可以去看看别人是怎么做的,千万不要觉得模仿别人的做法是件丢人的事。 我做题的时候,我一看到一道题,可能第一想法就是用很粗糙的方式做,因为很多题采用暴力法都会很容易做,就是时间复杂度很高。之后,我就会慢慢思考,看看有没其他方法来降低时间复杂度或空间复杂度。最后,我会去看一下别人的做法,当然,并不是每道题都会这样执行。 衡量一道算法题的好坏无非就是时间复杂度和空间复杂度,所以我们要力求完美,就要把这两个降到最低,令他们相辅相成。 我举道例题吧: 问题: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法? 这道题我在以前的分章分析过,不懂的可以先看下之前写的:递归与动态规划—基础篇1 方法1::暴力递归 这道题不难,或许你会采取下面的做法: public int solve(int n){ if(n <= 2){ return n; }else{ return solve(n-1) + solve(n-2); } } 这种做法的时间复杂度很高,指数级别了。但是如果你提交之后侥幸通过了,然后你就接着下一道题了,那么你就要好好想想了。 方法二:空间换时间 力求完美,我们可以考虑用空间换时间:这道题如何你去仔细想一想,会发现有很多是重复执行了。不行你可以画个图 所以可以采取下面的方法: //用一个HashMap来保存已经计算过的状态 static Map<Integer,Integer> map = new HashMap(); public static int solve(int n){ if(n <= 2){ return n; }else{//是否计算过 if(map.containsKey(n)){ return map.get(n); }else{ int m = solve(n-1) + solve(n-2); map.put(n, m); return m; } } } 这样,可以大大缩短时间。也就是说,当一道题你做了之后,发现时间复杂度很高,那么可以考虑下,是否有更好的方法,是否可以用空间换时间。 **方法三:**斐波那契数列 实际上,我们可以把空间复杂度弄的更小,不需要HashMap来保存状态: public static int solve(int n){ if(n <= 2){ return n; } int f1 = 0; int f2 = 1; int sum = 0; for(int i = 1; i<= n; i++){ sum = f1 + f2; f1 = f2; f2 = sum; } return sum; } 我弄这道题给你们看,并不是在教你们这道题怎么做,而是有以下目的: 1、在刷题的时候,我们要力求完美。 2、我想不到这些方法啊,怎么办?那么你就可以去看别人的做法,之后,遇到类似的题,你就会更有思路,更知道往哪个方向想。 3、可以从简单暴力入手做一道题,在考虑空间与时间之间的衡量,一点点去优化。 挑战自己,跳出舒适区 什么叫舒适区?在刷题的时候,可能有一类题是你比较懂的,你每次一看就有思路,然后半个小时就撸好代码,提交代码,然后通过了,然后,哇,又多刷了一道题,心里很舒服。 但是,记住,前期你可以多刷这种题练手,提升自己的乐趣,但,我还是建议你慢慢跳出舒适区,去做一些自己不擅长的题,并且找段时间一直刷这种题。例如,我觉得我在递归方面的题还是挺强的, 但是,我对动态规划的题,很菜,每次都要想好久,每次遇到这种题都有点害怕,没什么信心。不过有段时间我觉得只刷动态规划的题,直接在 leetcode 选定专题,连续做了四五十道,刚开始很难受,后来就慢慢知道了套路了,一道题从两三个小时最后缩到半小时,简单的十几分钟就搞定。感觉自己对这类型的题也不惧怕的。 当然,对于动态规划的学习,大家也可以看我这篇广受好评的文章:为什么你学不过动态规划?告别动态规划,谈谈我的经验 所以,建议你,一定要学好跳出自己的舒适区。 一定要学会分类总结 有些人以为 leetcode 的题刷的越多,就一定能越厉害,其实不然,leetcode 虽然有 1000 多道题,但题型就那么几类,我们前期在刷的时候,我是建议按照题型分类刷题的,例如我这整理刷二叉树相关,然后刷链表相关,然后二分法,然后递归等等,每刷一种题型,都要研究他们的套路,如果你愿意去总结,那么 leetcode 的题,其实你刷几百道,有目的、挑选的刷,我觉得就差不多了。 我看过一本书,叫做《程序员代码面试指南:IT 名企算法与数据结构题目最优解》,这本书就非常不错,里面按照栈,队列,链表,二叉树,字符串等一个专题一个专题来刷的,并且每道题都给出了最优解,而且里面的题有一定的难度,感兴趣的,真心不错,如果你把这本书的题全部搞定,并且总结相关套路,那么你的算法一定有很大的提升。 推荐一些刷题网站 我一般是在leetcode和牛客网刷题,感觉挺不错,题目难度不是很大。 在牛客网那里,我主要刷剑指Offer,不过那里也有个在线刷leetcode,不过里面的题量比较少。牛客网刷题有个非常方便的地方就是有个讨论区,那里会有很多大佬分享他们的解题方法,不用我们去百度找题解。所以你做完后,实在想不出,可以很方便着去看别人是怎么做的。 至于leetcode,也是大部分题目官方都有给出答案,也是个不错的刷题网站。你们可以两个挑选一个,或者两个都刷。 当然,还有其他刷题的网站,不过,其他网站没刷过,不大清除如何。 至于leetcode,有中文版和英文版 leetcode有中文版 英文版 根据自己的兴趣选。 学习一些解题技巧 说实话,有些题在你没看别人的解法前,你好不知道有这么美妙优雅的解法,看了之后,卧槽,居然还可以这样。而我们在刷题的过程中,就要不断累积这些技巧,当你累计多了,你就会形成一种 神经反应,一下子就想到了某种方法。解题技巧很多,例如数组下标法、位图法、双指针等等,我自己也分享过一篇总结一些算法技巧的文章 再说数据结构发重要性 前面我主要是说了我平时都是怎么学习算法的。在数据结构方法,我只是列举了你们一定要学习链表和树(二叉堆),但这是最基本的,刷题之前要掌握的,对于数据结构,我列举下一些比较重要的: 1、链表(如单向链表、双向链表)。 2、树(如二叉树、平衡树、红黑树)。 3、图(如最短路径的几种算法)。 4、队列、栈、矩阵。 对于这些,自己一定要动手实现一遍。你可以看书,也可以看视频,新手可以先看视频,不过前期可以看视频,之后我建议是一定要看书。 例如对于平衡树,可能你跟着书本的代码实现之后,过阵子你就忘记,不过这不要紧,虽然你忘记了,但是如果你之前用代码实现过,理解过,那么当你再次看到的时候,会很快就记起来,很快就知道思路,而且你的抽象能力等等会在不知不觉中提升起来。之后再学习红黑树啊,什么数据结构啊,都会学的很快。 对于有哪些值得学习的算法,我之前也总结过,这里推荐给大家程序员必须掌握的核心算法有哪些?,这篇文章居然 40多万阅读量了,有点受宠若惊。 最最重要 动手去做,动手去做,动手去做。重要的话说三遍。 千万不要找了一堆资源,订好了学习计划,我要留到某某天就来去做… 千万不要这样,而是当你激情来的时候,就马上去干,千万不要留到某个放假日啊什么鬼了,很多这种想法的人,最后会啥也没做的。 也不要觉得要学习的有好多啊,不知道从哪学习起。我上面说了,可以先学习最基本的,然后刷题,刷题是一个需要长期坚持的事情,一年,两年。在刷题的过程中,可以穿插和学习其他数据结构。 总结一下吧 所以我给大家的建议就是,先学习基本的数据结构以及算法思想,不要盲目刷题,接着刷题的过程中,不能得过且过,尽量追求最优解,还有就是要跳出舒适区,逼自己成长,刷题的过程中,要学会分类总结。 当然,最重要的,就是你去动手了,不然,一切免谈! 看在熬夜写过的份上,送我个赞呗,嘻嘻。 1、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。 2、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。 原文链接:https://blog.csdn.net/m0_37907797/article/details/104765116

剑曼红尘 2020-03-11 22:24:48 0 浏览量 回答数 0

问题

【Java学习全家桶】1460道Java热门问题,阿里百位技术专家答疑解惑

管理贝贝 2019-12-01 20:07:15 27612 浏览量 回答数 19

回答

面试官心理分析 这个问题是肯定要问的,说白了,就是看你有没有实际干过 es,因为啥?其实 es 性能并没有你想象中那么好的。很多时候数据量大了,特别是有几亿条数据的时候,可能你会懵逼的发现,跑个搜索怎么一下 5~10s,坑爹了。第一次搜索的时候,是 5~10s,后面反而就快了,可能就几百毫秒。 你就很懵,每个用户第一次访问都会比较慢,比较卡么?所以你要是没玩儿过 es,或者就是自己玩玩儿 demo,被问到这个问题容易懵逼,显示出你对 es 确实玩儿的不怎么样? 面试题剖析 说实话,es 性能优化是没有什么银弹的,啥意思呢?就是不要期待着随手调一个参数,就可以万能的应对所有的性能慢的场景。也许有的场景是你换个参数,或者调整一下语法,就可以搞定,但是绝对不是所有场景都可以这样。 性能优化的杀手锏——filesystem cache 你往 es 里写的数据,实际上都写到磁盘文件里去了,查询的时候,操作系统会将磁盘文件里的数据自动缓存到 filesystem cache 里面去。 es 的搜索引擎严重依赖于底层的 filesystem cache,你如果给 filesystem cache 更多的内存,尽量让内存可以容纳所有的 idx segment file 索引数据文件,那么你搜索的时候就基本都是走内存的,性能会非常高。 性能差距究竟可以有多大?我们之前很多的测试和压测,如果走磁盘一般肯定上秒,搜索性能绝对是秒级别的,1秒、5秒、10秒。但如果是走 filesystem cache,是走纯内存的,那么一般来说性能比走磁盘要高一个数量级,基本上就是毫秒级的,从几毫秒到几百毫秒不等。 这里有个真实的案例。某个公司 es 节点有 3 台机器,每台机器看起来内存很多,64G,总内存就是 64 * 3 = 192G。每台机器给 es jvm heap 是 32G,那么剩下来留给 filesystem cache 的就是每台机器才 32G,总共集群里给 filesystem cache 的就是 32 * 3 = 96G 内存。而此时,整个磁盘上索引数据文件,在 3 台机器上一共占用了 1T 的磁盘容量,es 数据量是 1T,那么每台机器的数据量是 300G。这样性能好吗? filesystem cache 的内存才 100G,十分之一的数据可以放内存,其他的都在磁盘,然后你执行搜索操作,大部分操作都是走磁盘,性能肯定差。 归根结底,你要让 es 性能要好,最佳的情况下,就是你的机器的内存,至少可以容纳你的总数据量的一半。 根据我们自己的生产环境实践经验,最佳的情况下,是仅仅在 es 中就存少量的数据,就是你要用来搜索的那些索引,如果内存留给 filesystem cache 的是 100G,那么你就将索引数据控制在 100G 以内,这样的话,你的数据几乎全部走内存来搜索,性能非常之高,一般可以在 1 秒以内。 比如说你现在有一行数据。id,name,age .... 30 个字段。但是你现在搜索,只需要根据 id,name,age 三个字段来搜索。如果你傻乎乎往 es 里写入一行数据所有的字段,就会导致说 90% 的数据是不用来搜索的,结果硬是占据了 es 机器上的 filesystem cache 的空间,单条数据的数据量越大,就会导致 filesystem cahce 能缓存的数据就越少。其实,仅仅写入 es 中要用来检索的少数几个字段就可以了,比如说就写入 es id,name,age 三个字段,然后你可以把其他的字段数据存在 mysql/hbase 里,我们一般是建议用 es + hbase 这么一个架构。 hbase 的特点是适用于海量数据的在线存储,就是对 hbase 可以写入海量数据,但是不要做复杂的搜索,做很简单的一些根据 id 或者范围进行查询的这么一个操作就可以了。从 es 中根据 name 和 age 去搜索,拿到的结果可能就 20 个 doc id,然后根据 doc id 到 hbase 里去查询每个 doc id 对应的完整的数据,给查出来,再返回给前端。 写入 es 的数据最好小于等于,或者是略微大于 es 的 filesystem cache 的内存容量。然后你从 es 检索可能就花费 20ms,然后再根据 es 返回的 id 去 hbase 里查询,查 20 条数据,可能也就耗费个 30ms,可能你原来那么玩儿,1T 数据都放 es,会每次查询都是 5~10s,现在可能性能就会很高,每次查询就是 50ms。 数据预热 假如说,哪怕是你就按照上述的方案去做了,es 集群中每个机器写入的数据量还是超过了 filesystem cache 一倍,比如说你写入一台机器 60G 数据,结果 filesystem cache 就 30G,还是有 30G 数据留在了磁盘上。 其实可以做数据预热。 举个例子,拿微博来说,你可以把一些大V,平时看的人很多的数据,你自己提前后台搞个系统,每隔一会儿,自己的后台系统去搜索一下热数据,刷到 filesystem cache 里去,后面用户实际上来看这个热数据的时候,他们就是直接从内存里搜索了,很快。 或者是电商,你可以将平时查看最多的一些商品,比如说 iphone 8,热数据提前后台搞个程序,每隔 1 分钟自己主动访问一次,刷到 filesystem cache 里去。 对于那些你觉得比较热的、经常会有人访问的数据,最好做一个专门的缓存预热子系统,就是对热数据每隔一段时间,就提前访问一下,让数据进入 filesystem cache 里面去。这样下次别人访问的时候,性能一定会好很多。 冷热分离 es 可以做类似于 mysql 的水平拆分,就是说将大量的访问很少、频率很低的数据,单独写一个索引,然后将访问很频繁的热数据单独写一个索引。最好是将冷数据写入一个索引中,然后热数据写入另外一个索引中,这样可以确保热数据在被预热之后,尽量都让他们留在 filesystem os cache 里,别让冷数据给冲刷掉。 你看,假设你有 6 台机器,2 个索引,一个放冷数据,一个放热数据,每个索引 3 个 shard。3 台机器放热数据 index,另外 3 台机器放冷数据 index。然后这样的话,你大量的时间是在访问热数据 index,热数据可能就占总数据量的 10%,此时数据量很少,几乎全都保留在 filesystem cache 里面了,就可以确保热数据的访问性能是很高的。但是对于冷数据而言,是在别的 index 里的,跟热数据 index 不在相同的机器上,大家互相之间都没什么联系了。如果有人访问冷数据,可能大量数据是在磁盘上的,此时性能差点,就 10% 的人去访问冷数据,90% 的人在访问热数据,也无所谓了。 document 模型设计 对于 MySQL,我们经常有一些复杂的关联查询。在 es 里该怎么玩儿,es 里面的复杂的关联查询尽量别用,一旦用了性能一般都不太好。 最好是先在 Java 系统里就完成关联,将关联好的数据直接写入 es 中。搜索的时候,就不需要利用 es 的搜索语法来完成 join 之类的关联搜索了。 document 模型设计是非常重要的,很多操作,不要在搜索的时候才想去执行各种复杂的乱七八糟的操作。es 能支持的操作就那么多,不要考虑用 es 做一些它不好操作的事情。如果真的有那种操作,尽量在 document 模型设计的时候,写入的时候就完成。另外对于一些太复杂的操作,比如 join/nested/parent-child 搜索都要尽量避免,性能都很差的。 分页性能优化 es 的分页是较坑的,为啥呢?举个例子吧,假如你每页是 10 条数据,你现在要查询第 100 页,实际上是会把每个 shard 上存储的前 1000 条数据都查到一个协调节点上,如果你有个 5 个 shard,那么就有 5000 条数据,接着协调节点对这 5000 条数据进行一些合并、处理,再获取到最终第 100 页的 10 条数据。 分布式的,你要查第 100 页的 10 条数据,不可能说从 5 个 shard,每个 shard 就查 2 条数据,最后到协调节点合并成 10 条数据吧?你必须得从每个 shard 都查 1000 条数据过来,然后根据你的需求进行排序、筛选等等操作,最后再次分页,拿到里面第 100 页的数据。你翻页的时候,翻的越深,每个 shard 返回的数据就越多,而且协调节点处理的时间越长,非常坑爹。所以用 es 做分页的时候,你会发现越翻到后面,就越是慢。 我们之前也是遇到过这个问题,用 es 作分页,前几页就几十毫秒,翻到 10 页或者几十页的时候,基本上就要 5~10 秒才能查出来一页数据了。 有什么解决方案吗? 不允许深度分页(默认深度分页性能很差) 跟产品经理说,你系统不允许翻那么深的页,默认翻的越深,性能就越差。 类似于 app 里的推荐商品不断下拉出来一页一页的 类似于微博中,下拉刷微博,刷出来一页一页的,你可以用 scroll api,关于如何使用,自行上网搜索。 scroll 会一次性给你生成所有数据的一个快照,然后每次滑动向后翻页就是通过游标 scroll_id 移动,获取下一页下一页这样子,性能会比上面说的那种分页性能要高很多很多,基本上都是毫秒级的。 但是,唯一的一点就是,这个适合于那种类似微博下拉翻页的,不能随意跳到任何一页的场景。也就是说,你不能先进入第 10 页,然后去第 120 页,然后又回到第 58 页,不能随意乱跳页。所以现在很多产品,都是不允许你随意翻页的,app,也有一些网站,做的就是你只能往下拉,一页一页的翻。 初始化时必须指定 scroll 参数,告诉 es 要保存此次搜索的上下文多长时间。你需要确保用户不会持续不断翻页翻几个小时,否则可能因为超时而失败。 除了用 scroll api,你也可以用 search_after 来做,search_after 的思想是使用前一页的结果来帮助检索下一页的数据,显然,这种方式也不允许你随意翻页,你只能一页页往后翻。初始化时,需要使用一个唯一值的字段作为 sort 字段。 往期回顾: 【Java问答学堂】1期 为什么使用消息队列?消息队列有什么优点和缺点?Kafka、ActiveMQ、RabbitMQ、RocketMQ 都有什么区别,以及适合哪些场景? 【Java问答学堂】2期 如何保证消息队列的高可用? 【Java问答学堂】3期 如何保证消息不被重复消费?或者说,如何保证消息消费的幂等性? 【Java问答学堂】4期 如何保证消息的可靠性传输?(如何处理消息丢失的问题?) 【Java问答学堂】5期 如何保证消息的顺序性? 【Java问答学堂】6期 如何解决消息队列的延时以及过期失效问题? 【Java问答学堂】7期 如果让你写一个消息队列,该如何进行架构设计? 【Java问答学堂】8期 es 的分布式架构原理能说一下么(es 是如何实现分布式的啊)? 【Java问答学堂】9期 es 写入数据的工作原理是什么啊?es 查询数据的工作原理是什么啊?

剑曼红尘 2020-04-28 14:17:05 0 浏览量 回答数 0

问题

【Java问答学堂】10期 es 在数据量很大的情况下(数十亿级别)如何提高查询效率啊?

剑曼红尘 2020-04-28 14:16:56 0 浏览量 回答数 1

回答

最好一个表,要不然,会员和其他表的关联会出问题,比如会员买东西,会员发表评论,你总不能把评论表也搞成两个,购买记录也搞成两个表吧?后患无穷######搞个字段用来区分会员类型不就OK了?######一个表   用一个字段区分  线下,线上    你线上也需要注册的? 也就是说你的表的会员都有  帐号,密码字段    你在加个 初始密码是否使用 的字段就完了 至于你说的初始密码的逻辑 //登录 if(线下){ if(!初始密码是否使用){ 初始密码是否使用 = true; } } ...执行登录 ######回复 @ZhangKevin2 : 判断不只是js判断,服务端也要判断 js是可以绕过的,除了问题就大条了######那我就登录的时候 判断 写个正则,凡是DOWN_开头的 帐户名ID都是线下的,否则就执行普通线上注册的用户登录? 然后线上普通注册的 在注册的时候我在写个JS 限制不能以DOWN_开头注册就行了? 那线下的帐户名和初始密码 是用EXCEL直接导入数据库会员表里?###### 引用来自“NikoG”的答案 搞个字段用来区分会员类型不就OK了? 是啊,这个不就解决了吗?然后在付款的时候判断一下不就得了吗?反正那些行为线下会员优惠点的话,直接判断一下不就得了吗? ######楼主考虑的复杂了吧,你这个情况就如上面提到的,用一个字段识别一下即可。另外,你最后说的VIP和普通会员,与你现在的情况其实是一个性质的。 就和论坛中有不同的用户组一样,不同的组不同的权限,而且也强烈建议你使用权限来区分各用户组所能进行的操作,这样也有利于你日后的扩展。给你一个参考的基础库结构: ID:int(索引) UserID:nvarchar(用户名) Password:nvarchar(密码) Int:int(boolean,是否完成初始化) Group:int(用户组)(另建用户组表,定义各组的权限) Rebate:int(折扣,也可在用户组中定义折扣率,此处的折扣率可用做针对单个用户的私有权限) ######回复 @psaux : 当然CHAR了,MD5之后固定的位数######password直接用char吧,事先确定了使用的hash加密方式和位数。######因为就一个线下和线上 2种情况,所以我觉得没必要搞个用户组来单独搞权限操作######如果线上会员和线下会员区别很大,建议分开表。只是要区分线上线下而已,可以只用一个字段识别。线下会员首次登录需要改密码使用登录次数字段+判断初始密码是否未更改来实现######回复 @ZhangKevin2 : 使用SQL的Left Join就可以。会员类型(线上线下)放置详细表######THANS,登录次数字段还没用过。。 其实还有一点很麻烦,一般会员,如果想登录块点都是分2个会员表,一个是 帐号和密码会员表用户登录,与之相关联的是会员详细信息表,比如会员的个人资料等等。 如此 如果结合线上线下的话 更纠结。。###### 显然分成两个表比较好 而且分成两个系统开发测试也快。 ###### 显然一个表,会员是一个对象,线上线下只是这个对象的属性。你的需求和苏宁电器的会员很类似,苏宁7000多万会员也分线下pos端申请和线上易购网申请,我们用的是一个表,这里存在一个线上线下同步问题,如果会员量小不用考虑都指向一个表就行。另外我们会根据地理区域分库,也就是水平分割,否则检索太慢。首次登陆改密码这个很多会员都有这样的需求,也可以用属性来区别。另外我说的会员一个表是逻辑上的一个表,由于会员有很多属性,都放一个表会影响性能,可以根据业务类型进行垂直切割。 ###### 引用来自“风飞雪”的答案 显然一个表,会员是一个对象,线上线下只是这个对象的属性。你的需求和苏宁电器的会员很类似,苏宁7000多万会员也分线下pos端申请和线上易购网申请,我们用的是一个表,这里存在一个线上线下同步问题,如果会员量小不用考虑都指向一个表就行。另外我们会根据地理区域分库,也就是水平分割,否则检索太慢。首次登陆改密码这个很多会员都有这样的需求,也可以用属性来区别。另外我说的会员一个表是逻辑上的一个表,由于会员有很多属性,都放一个表会影响性能,可以根据业务类型进行垂直切割。 求详细点。。。  之前做的都是普通会员和VIP会员,ECSHOP二次开发等等,这次虽然项目不大也不难,但我还是想尽力做完善点,关键是我们公司策划烂到家了 天天改需求,线上线下会员肯定会有区别,但以后有多大区别还不晓得。 最烦的是有区别又有联系,如果分2个表 以后还要联表。 有些业务处理也麻烦。但如果放在一个表里,2种会员字段数也不一样,线上可能就5个,线下可能还要身份证什么的因为是发卡一对一发展现实中的会员,而且线下会员安全性要求更高 ###### 引用来自“ZhangKevin2”的答案 引用来自“风飞雪”的答案 显然一个表,会员是一个对象,线上线下只是这个对象的属性。你的需求和苏宁电器的会员很类似,苏宁7000多万会员也分线下pos端申请和线上易购网申请,我们用的是一个表,这里存在一个线上线下同步问题,如果会员量小不用考虑都指向一个表就行。另外我们会根据地理区域分库,也就是水平分割,否则检索太慢。首次登陆改密码这个很多会员都有这样的需求,也可以用属性来区别。另外我说的会员一个表是逻辑上的一个表,由于会员有很多属性,都放一个表会影响性能,可以根据业务类型进行垂直切割。 求详细点。。。  之前做的都是普通会员和VIP会员,ECSHOP二次开发等等,这次虽然项目不大也不难,但我还是想尽力做完善点,关键是我们公司策划烂到家了 天天改需求,线上线下会员肯定会有区别,但以后有多大区别还不晓得。 最烦的是有区别又有联系,如果分2个表 以后还要联表。 有些业务处理也麻烦。但如果放在一个表里,2种会员字段数也不一样,线上可能就5个,线下可能还要身份证什么的因为是发卡一对一发展现实中的会员,而且线下会员安全性要求更高 建议一个,如果按你的思路以后如果手机可以注册,为了区别手机注册的还要建个会员表?如果会员系统提供接口给别的系统用,你还要根据会员号去不同的表里查找?显然这样会给系统开发带来不必要的麻烦,这些一个字段就可以解决。现在存储设备如此便宜,为了减少系统复杂而浪费些空间非常值得。不同注册方法的会员字段不同,没有值得让它空着好了,不要太完美了。我们很多表都冗余了浮点和字符的字段,因为需求总是不断变化,时不时的要增加字段,这种冗余字段的方法带来了很多方便。设计系统和表结构首先一个原则就是尽可能的简单,然后再考虑性能最后考虑空间问题。如果会员有上百万建议切割表,将不常用的字段放在另一张表中。 一些拙见,不足之处还望不吝赐教。

kun坤 2020-06-08 16:18:16 0 浏览量 回答数 0

回答

先说结论: 不要对接!不要对接!不要对接! 开个玩笑,以上仅代表个人观点,大家也知道这种“三体式警告”根本没有用的,我自己也研究如何对接,说不定做完后就觉得“真香”了。 为什么要对接? 首先讨论一下为什么要把 Flutter 对接到 Web 生态。 Flutter 现在是一个炙手可热的跨平台技术,能够一套代码运行在 Android、iOS、PC、IoT 以及浏览器上,被认为是下一代跨平台技术。相比于 Weex 和 React Native 可以很好地解决多平台一致性问题,原生渲染性能相近,上层没有 JS 那么厚的封装层次,整体性能会略好一些。 但是大部分兴冲冲去学 Flutter 的人疑惑的第一个问题就是:为什么 Flutter 要用 Dart?一个全新的语言意味着新的学习成本,难道 JS 不香吗?JS 不香不是还有 TypeScript 吗!事实上 Flutter 抛弃的岂止是 JS 这门语言,也抛弃了 HTML 和 CSS,设计了一套解耦得更好的 Widget 体系,Flutter 抛弃的是整个 Web,致力于打造一个新的生态,但是这个生态无法复用 Web 生态的代码和解决方案。尤其是之前所有跨平台方案 Hybrid、React Native、Weex 都是对接 Web 生态的,这让 Flutter 显得有些格格不入,也让大部分前端开发者望而却步。 下面是我整理出来的,前端开发者使用 Flutter 的各方面成本: 因为 Flutter 的开发模式和前端框架比较像(可以说就是抄的 React),所以框架的学习成本并不高,稍微高一些的是 Dart 语言的学习成本,另外还要学习如何用 Widget 组装 UI,虽然很多布局 Widget 设计得和 CSS 很像,灵活度还是差了很多。要想在真实项目中用起来,还要改造整个工具链,以“Native First”的视角做开发,开发 Flutter 和开发原生应用的链路是比较像的,和开发前端页面有较大差异。最高的还是生态成本,前端生态的积累无论是代码还是技术方案都很难复用,这是最痛的一点,生态也是 Flutter 最弱的一环。 无论是为了先进的技术理念还是出于商业私心,先不管 Flutter 为什么抛弃 Web 生态,现实问题是最大的 UI 开发者群体是前端,最丰富的生态是 Web 生态,我觉得 Web 技术也是开发 UI 最高效的方式。如果能在上层使用 Web 技术栈开发,在底层使用 Flutter 实现跨平台渲染,不是可以很好的兼顾开发效率、性能和跨平台一致性吗?还能复用 Web 技术栈大量的技术积累。 可能这些理由也不够充分,暂且先照着这个假设继续分析,最后再重新讨论到底该不该对接。 关于 Flutter 和 Web 生态的对接涉及两个方面: 从 Web 到 Flutter。就是使用 Web 技术栈来开发,然后对接到 Flutter 上实现跨平台渲染。对 Web 来说是解决性能和跨平台一致性问题,对 Flutter 来说是解决生态复用问题。从 Flutter 到 Web。就是官方已经实现的 Web support for Flutter,把已经用 Dart 开发好的 App 编译成 HTML/JS/CSS 然后运行在浏览器上,可以用于降级和外投场景。 如何实现“从 Web 到 Flutter”? 首先分析一下 Flutter 的架构图,看看可以从哪里下手。 Flutter 可以分为 Framework 和 Engine 两部分,Engine 部分比较底层也比较稳定了,最好不要动,需要改的是用 Dart 实现的 Framework。要想对接 Web 生态的话,JS 引擎肯定是要引入的,至于是否保留 Dart VM 有待讨论。图中最上面 Material 和 Cupertino 两个 UI 库前端是不需要的,前端有自己的。关键是 Widget 这部分,是替换成 HTML/CSS 的方式写 UI,还是继续保留 Widget 但是把语言换成 JS,不同方案给出的解法也不一样。 有不少方案可以实现对接,业界有挺多尝试的,我总结了下面三种方式: - TS 魔改:用 JS 引擎替换掉 Dart VM,用 JS/TS 重新实现 Flutter Framework(或者直接 dart2js 编译过来)。 - JS 对接:引入 JS 引擎同时保留 Dart VM,用前端框架对接 Flutter Framework。 - C++ 魔改:用 JS 引擎替换掉 Dart VM,用 C++ 重新实现 Flutter Framework。 TS 魔改 TS 魔改就是完全抛弃掉 Dart VM,用 TypeScript 重新实现一遍用 Dart 写的 Flutter Framework。 为啥是 TS 而不是 JS?这不是因为 TS 是个大热门嘛,而且向下兼容 JS,现在几乎所有时髦的框架都要用 TS 重写了。 这种方案的出发点是“如果能把 Flutter 的 Dart 换成 JS 就好了”,最容易想到的路就是把 Dart 翻译成 TS,或者直接用 dart2js 把代码编译成 js,但是编译出来的代码包含很多 dart:ui 之类的库的封装,生成的包也挺大的,也比较难定制需要导出的接口,不如干脆用 TS 重写一遍,工具链更熟悉一些,还可以加一些定制。 理论上讲翻译之后 Flutter 绝大部分功能都依然支持,可以复用各种 npm 包,还可以动态化,但是丧失了 AOT 能力,JS 语言的执行性能应该是不如 Dart 的。而且所有节点的布局运算都发生在 JS,底层只需要提供基础的图形能力就好了,就好像是基于 Canvas API 写了一套 UI 框架,性能未必有现存前端框架的性能高。 此外最大的问题是如何与官方 Flutter 保持一致,假如现在是从 v1.13 版本翻译过来的,以后官方升级到了 v1.15 要不要同步更新?这个过程没啥技术含量,而且需要持续投入,做起来比较恶心。 另外还需要考虑上层是用 Widget 的方式写 UI,还是用前端熟悉的 HTML+CSS。如果依然用 Widget 的话,那大部分前端组件还是用不了的,UI 还是得重写一遍。反正要重写的话,成本也没降下来,那就用 Dart 重写呗…… 直接用官方原版 Flutter 也避免每次更新都要翻译一遍 Dart 代码。所以既然选择了对接前端生态,那就要对接 CSS,不然就没有足够的价值。然而 CSS 和 Widget 的对接也是很繁琐的过程,而且存在完备性问题。 JS 对接 翻译代码的方式不够优雅,那就保留 Dart,把 JS/CSS 对接到 Widget 上面不就好了? 当然可以,这种方式是仅把 Flutter 当做了底层的渲染引擎,上层保持前端框架的写法,仅把渲染部分对接到 Flutter。现存的很多前端框架都把底层渲染能力做了抽象,可以对接到不同渲染引擎上,如 Vue/Rax 同时支持浏览器和 Weex,用同样的方式,可以再支持一个 Flutter。 这种方式对前端框架的兼容性比较好,但是链路太长了,业务代码调用前端框架接口做渲染,一顿操作之后发出了渲染指令,这个渲染指令要基于通信的方式传给 Flutter Framework,这中间涉及一次 JS 到 C++ 再到 Dart 的跨语言转换,然后再接收到渲染指令之后还要转成相应的 Widget 树,从 CSS 到 Widget 的转换依然很繁琐。而且 Widget 本身是可以带有状态的,本身就是响应式更新的,在更新时会重新生成 widget 并 diff,如果在前端更新 UI 的话,前端框架在 js 里 diff 一次 vdom,传到 Flutter 之后又 diff 一次 widget。 如果要绕过 Widget 直接对接图中的 Rendering 这一层,可以绕过 widget diff 但是得改 Flutter Framework 的渲染链路,既然要改 Flutter Framework 那为什么不直接用 TS 魔改呢,还绕过了 JS 到 Dart 的通信,又回到了第一种方案。 总结来说,这个方案的优点是:实现简单、能最大化保留前端开发体验,缺点是:渲染链路长、通信成本高、响应式逻辑冲突、CSS 转 Widget 不完备等。 C++ 魔改 想要干掉 Dart VM,就需要用其他语言重新实现用 Dart 开发的 Framework,用 JS/TS 可以,用 C++ 当然可以,最硬核的方式就是用 C++ 重新实现 Flutter 的 Framework,然后接入 JS 引擎,通过 binding 把 C++ 接口透出到 JS 环境,上层应用还是用 JS 做开发。 把 Framework 层下沉到 C++ 之后,不仅会有更好的性能,也能支持更多语言。原本 Flutter Framework 是在 Dart VM 之上的,必须依赖 Dart VM 才能运行,所以对 Dart 有强依赖;用 C++ 重新实现之后,JS 引擎是在 C++ 版 Framework 之上的,框架本身并不依赖 JS 引擎,还可以对接其他各种语言,如对接了 JVM 之后可以支持 Java 和 Kotlin,对接回 Dart VM 可以继续支持 Dart。 这个方案可以增强性能,也能保持和 Flutter 的一致性,但是改造成本和维护成本都相当高。C++ 的开发效率肯定不如 Dart,当 Flutter 快速迭代之后如何跟进是很大的问题,如果跟进不及时或者实现不一致那很可能就分化了。从 CSS 到 Widget 的转换也是不得不面对的问题。 几种方案对比 把上面几种方案画在同一张图里是这个样子的: 图中实线部分表示了跨语言的通信,太过频繁会影响性能,虚线部分表示了其他对接可能性。 从下到上,Flutter Engine 是不需要动的,这一层是跨平台的关键。Framework 则有三种语言版本,JS/TS、Dart、C++,性能是 C++ 版本最好,成本是 Dart 版本最低。然后还需要向上处理 HTML/CSS 和 Widget 的问题,可以直接对接一个前端框架,也可以直接在 C++ 层实现(不然需要透出的 binding 接口就太多了,用通信的方式也太过频繁了)。 如何实现“从 Flutter 到 Web”? 这个功能官方已经实现了,可以把使用 Dart 开发的 App 编译成 Web App 运行在浏览器上,官方文档以介绍用法和 API 为主,我这里简单分析一下内部具体的实现方案。 实现原理 结合 Flutter 的架构图来看,要实现 Web 到 Flutter 需要改造的是上层 Framework,要实现 Flutter 到 Web 需要改造的则是底层 Engine。 Framework 对 Engine 的核心依赖是 dart:ui,这是库是在 Engine 里实现的,抽象出了绘制 UI 图层的接口,底层对接 skia 的实现,向上透出 Dart 语言的接口。这样来看,对接方式就比较简单了: 使用 dart2js 把 Framework 编译成 JS 代码。基于浏览器的 API 重新实现 dart:ui,即 dart:web_ui。 把 Dart 编译成 JS 没什么问题,性能可能会有一点影响,功能都是可以完全保留的,关键是 dart:web_ui 的实现。在原生 Engine 中,dart:ui 依赖 skia 透出的 SkCanvas 实现绘制,这是一套很底层的图形接口,只定义了画线、画多边形、贴图之类的底层能力,用浏览器接口实现这一套接口还是很有挑战的。上图可以看到 Web 版 Engine 是基于 DOM 和 Canvas 实现的,底层定义了 DomCanvas 和 BitmapCanvas 两种图形接口,会把传来的 layer tree 渲染成浏览器的 Element tree,但是节点上仅包含了 position, transform, opacity 之类的样式,只用到 CSS 很小的一个子集,一些更复杂的绘制直接用 2D canvas 实现。 存在的问题 我编译了一个还算复杂的 demo 试了一下,性能很不理想,滑动不流畅,有时候图片还会闪动。生成出来的 js 代码有 1.1MB (minify 之后,未 gzip),节点层次也比较深,我评估这个页面用前端写不会超过 300KB,节点数可以少一半以上。 另外再看一下 Flutter 仓库的 issue,过滤出 platfrom-web 相关的,可以看到大量:文字编辑失效、找不到光标、ListView 在 ios 上不可滚动、checkbox/button 行为不正常、安卓滚动卡顿图片闪烁、字体失效、某些机型视频无法播放、文字选中后无法复制、无法调试…… 感觉 flutter for web 已经陷入泥潭,让人回想起前端当年处理各种浏览器兼容性的噩梦。 这些性能和兼容性问题,核心原因是浏览器未暴露足够的底层能力,以及浏览器处理手势、用户输入和方式和 Flutter 差异巨大。 实现 Flutter Engine 需要的是底层的图形接口和系统能力,虽然canvas 提供了相似的图形接口,如果全部用 canvas 实现的话很难处理可访问性、文本选择、手势、表单等问题,也会存在很多兼容性问题。所以真实方案里用的是 Canvas + DOM 混合的方式,封装层次太高了,渲染链路太长。就好像 Flutter Framework 里进行了一顿猛如虎的操作之后,节点生成好了、布局算好了、绘制属性也处理好了,就差一个画布画出来了,然后交到浏览器手里,又生成一遍 Element,再算一遍布局,在处理一遍绘制,最终才交给了底层的图形库画出来。 再比如长页面的滚动,浏览器里只要一条 CSS (overflow:scroll) 就可以让元素可滚动,手势的监听以及页面的滚动以及滚动动画都是浏览器原生实现的,不需要与 JS 交互,甚至不需要重新 layout 和 paint,只需要 compositing。如上图所示,在 Flutter 中 Animation 和 Gesture 是用 Dart 实现的,编译过来就是 JS 实现的,浏览器本身并不知道这个元素是否可滚,只是不断派发 touchmove 事件,JS 根据事件属性计算节点偏移,然后运算动画,然后把 transform 或者新的 position 作用到节点上,然后浏览器再来一遍完整的渲染流程…… 优化方案 性能和兼容性的问题还是要解决的,短期内先把 issue 解掉,长线的优化方案,官方有两种尝试: 使用 CSS Painting API 做绘制。 a, 这是还处于提案状态的新标准,可以用 JS 实现一些绘制功能,自定义 CSS 属性。 b. 目前还未实现,需要等浏览器先把 CSS Houdini 支持好。 使用 WebAssembly 版本的 Skia 做绘制 https://skia.org/user/modules/canvaskit a, 这样可以发挥 wasm 的性能优势,并且保持 skia 功能的一致。但是目前 wasm 在浏览器环境里未必有性能优势,这里不展开讨论了。 b. 已经部分实现,参考这里的配置启用功能: https://github.com/flutter/flutter/issues/41062#issuecomment-533952994 这两个方案都是想更多的利用到浏览器的底层能力,只有浏览器暴露了更多底层能力,才能更好的实现 Flutter 的 Web Engine。不过这个要等挺久的时间,我们也参与不了,现阶段想要使用 flutter for web,还是得保持现有架构,一起参与进去把 issue 解决掉,优先保障功能,其次优化性能。 一种适应性更好的架构 如果理想化一点,能不能从架构角度让 Flutter 和 Web 生态融合的更好一些呢? 回顾文章最开始的官方架构图,上面是 Framework(Dart),下面是 Engine(C++),切分在 Foundation 这一层,双方之间的交互是几何图形信息。如果还保持这个架构,把切分层次划分的更靠上一些,如下图所示,划分在 Widgets 和 Rendering 这一层,理论上讲对 Flutter 的开发者来说是无感知的,因为上层的开发语言和 Widget 接口都是不变的。 切分在这一层,Framework 和 Engine 之间的交互就不再是几何图形而是节点信息,Widget 的组合、setState 响应式更新、Widget diff 都还在 Dart 中,展开后的 RenderObject 的布局、绘制、裁剪、动画全都在 C++ 中,不仅有更好的性能,还可以与 Engine 有更好的结合。 或者说,还原本保留 Engine 的设计,把下沉的这部分逻辑上划分成 Renderer,就有了如下三层的结构: 这样划分出来的每一层都有明确的定位: Framework: 开发框架。为开发者提供可编程 API,实现响应式的开发模式,提供细粒度 Widget 供开发者自由封装和组合。Renderer: 渲染引擎。专门实现布局、绘制、动画、手势的的处理,这部分功能相对独立,是可以与开发框架解耦的,也不必与特定语言绑定。Engine: 图形引擎。实现跨平台一致的图形接口,合成输入的层并绘制到屏幕上,处理好平台力的接入和适配。 这样切分除了有性能优势以外,也使得渲染引擎摆脱了对 Dart 的依赖,能够支持多种语言,也能支持多种开发模式。对接到 Dart VM 就可以用 Dart 写代码,对接到 JS 引擎就可以用 JS 写代码,对接到 JVM 还可以写 Java,但是无论怎么写,底层的渲染能力是一样的,一套统一的布局算法,动画和手势的处理行为也是一致的。 在这样的架构下,对接 Web 生态就更容易了。Dart 和 Widget 是前端不想要的,希望能换成 JS 和 CSS,但是又想要底层的跨平台一致渲染引擎,那从 Renderer 层开始对接就好了,绕过了所有不想要的,也保留了所有想要的。 要实现 Flutter for Web 也更简单了一些。在 Engine 层做对接,一直苦于浏览器透出的底层能力不够,如果是在 Renderer 之上做对接就更容易一些,基于 JS/CSS/DOM/Canvas 的能力封装出一套 Rendering 接口,供 Widget 调用就好了,这样可以使渲染链路更短一些,但是依然要处理 Widget 和 DOM/CSS 之间的兼容性问题。 再讨论一遍:为什么要对接? 技术上已经分析完了,要想搞定 Flutter 生态和 Web 生态的对接,需要投入很大的成本,所以真正决定做之前,要先讨论清楚为什么要做对接?到底要不要做对接? 首先 Google 官方对 Flutter 的定位就是个问题。Flutter 设计之初就是不考虑 Web 生态的,甚至在刻意回避,倡导的是更贴近原生的开发方式。我之所以在开头说不要对接,原因也很简单:两种技术设计理念不同,不是朝着一个方向发展的,生态不通,技术方案不通,强行融合很可能让彼此都丧失了优势。但是业界又有很多团队在做这种尝试,说明需求是存在的,如果 Google 抵制这个方向,那就不好做了。不过现在官方已经支持了 Flutter for Web,已经向 Web 生态迈了一步,未来是否进一步与 Web 融合,也是有可能的。 另外就是跨平台技术本身的问题,浏览器发展了二三十年,已经是个很强大的跨平台产品了,几乎是 Web 的代名词了,这一点无人能敌。但是也臃肿不堪,有大量历史包袱,性能和体验不够好,和 Native 的结合度差,尤其在移动和 IoT 平台。虽然硬件性能在不断提升,但这是所有软件共享的,浏览器的性能和体验总会比 Native 差一些,差的这一些很可能就是新业务和新场景的发挥空间。观察一下近几年新诞生的业务场景,很多都是利用到了 Native 新提供的能力才火爆起来的,如 AI/AR/ 视频 / 直播 等,有因为新的 Web API 而孵化生出来的商业模式吗? 原文链接: https://mp.weixin.qq.com/s?__biz=MzAxNDEwNjk5OQ==&mid=2650405725&idx=1&sn=0b7476f7c7c01df7fdafda578f9ceb98&chksm=83953345b4e2ba53917ac30b709c07be15bd1c2fd5ae2a8ecfbb129b3813f771621b8fac95ca&scene=27#wechat_redirect

剑曼红尘 2020-03-10 09:54:40 0 浏览量 回答数 0

问题

经典动态规划:高楼扔鸡蛋(进阶篇) 6月3日【今日算法】

游客ih62co2qqq5ww 2020-06-03 15:10:38 7 浏览量 回答数 1

问题

SaaS模式云数据仓库MaxCompute 百问百答合集(持续更新20200921)

亢海鹏 2020-05-29 15:10:00 15821 浏览量 回答数 4

回答

12月17日更新 请问下同时消费多个topic的情况下,在richmap里面可以获取到当前消息所属的topic吗? 各位大佬,你们实时都是怎样重跑数据的? 有木有大神知道Flink能否消费多个kafka集群的数据? 这个问题有人遇到吗? 你们实时读取广业务库到kafka是通过什么读的?kafka connector 的原理是定时去轮询,这样如果表多了,会不会影响业务库的性能?甚至把业务库搞挂? 有没有flink 1.9 连接 hive的例子啊?官网文档试了,没成功 请问各位是怎么解决实时流数据倾斜的? 请问一下,对于有状态的任务,如果任务做代码升级的时候,可否修改BoundedOutOfOrdernessTimestampExtractor的maxOutOfOrderness呢?是否会有影响数据逻辑的地方呢? 老哥们有做过统计从0点开始截止到现在时刻的累计用户数吗? 比如五分钟输出一次,就是7点输出0点到7点的累计用户,7:05输出0点到7:05的累计用户。 但是我这里有多个维度,现在用redis来做的。 想知道有没有更好的姿势? 实时数仓用什么存储介质来存储维表,维表有大有小,大的大概5千万左右。 各位大神有什么建议和经验分享吗? 请教个问题,就是flink的窗口触发必须是有数据才会触发吗?我现在有个这样的需求,就是存在窗口内没有流数据进入,但是窗口结束是要触发去外部系统获取上一个窗口的结果值作为本次窗口的结果值!现在没有流数据进入窗口结束时如何触发? kafkaSource.setStartFromTimestamp(timestamp); 发现kafkasource从指定时间开始消费,有些topic有效,有效topic无效,大佬们有遇到过吗? 各位大佬,flink两个table join的时候,为什么打印不出来数据,已经赋了关联条件了,但是也不报错 各位大佬 请教一下 一个faile的任务 会在这里面存储展示多久啊? 各位大佬,我的程序每五分钟一个窗口做了基础指标的统计,同时还想统计全天的Uv,这个是用State就能实现吗? 大佬们,flink的redis sink是不是只适用redis2.8.5版本? 有CEP 源码中文注释的发出来学习一下吗? 有没有拿flink和tensorflow集成的? 那位大神,给一个java版的flink1.7 读取kafka数据,做实时监控和统计的功能的代码案例。 请问下风控大佬,flink为风控引擎做数据支撑的时候,怎么应对风控规则的不断变化,比如说登录场景需要实时计算近十分钟内登录次数超过20次用户,这个规则可能会变成计算近五分钟内登录次数超过20次的。 想了解一下大家线上Flink作业一般开始的时候都分配多少内存?广播没办法改CEP flink支持多流(大于2流)join吗? 谁能帮忙提供一下flink的多并行度的情况下,怎么保证数据有序 例如map并行度为2 那就可能出现数据乱序的情况啊 请教下现在从哪里可以可以看单任务的运行状况和内存占用情况,flink页面上能看单个任务的内存、cpu 大佬们 flink1.9 停止任务手动保存savepoint的命令是啥? flink 一个流计算多个任务和 还是一个流一个任务好? flink 1.9 on yarn, 自定义个connector里面用了jni, failover以后 就起不来了, 报错重复load so的问题。 我想问一下 这个,怎么解决。 难道flink 里面不能用jni吗。 ide里面调试没有问题,部署到集群就会报错了,可能什么问题? 请教一下对于长时间耗内存很大的任务,大家都是开checkpoint机制,采用rocksdb做状态后端吗? 请问下大佬,flink jdbc读取mysql,tinyin字段类型自动转化为Boolean有没有好的解决方法 Flink 1.9版本的Blink查询优化器,Hive集成,Python API这几个功能好像都是预览版,请问群里有大佬生产环境中使用这些功能了吗? 想做一个监控或数据分析的功能,如果我flink 的datastreaming实现消费Kafka的数据,但是我监控的规则数据会增加或修改,但是不想停这个正在运行的flink程序,要如何传递这个动态变化的规则数据,大神给个思路,是用ConnectedStream这个吗?还是用Broadcast ?还有一个,比如我的规则数据是存放在Mysql表中,用什么事件隔30秒去触发读取mysql规则表呢?谢谢! 想做一个监控或数据分析的功能,如果我flink 的datastreaming实现消费Kafka的数据,但是我监控的规则数据会增加或修改,但是不想停这个正在运行的flink程序,要如何传递这个动态变化的规则数据,大神给个思路,是用ConnectedStream这个吗?还是用Broadcast ?还有一个,比如我的规则数据是存放在Mysql表中,用什么事件隔30秒去触发读取mysql规则表呢?谢谢! 各位大佬,在一个 Job 计算过程中,查询 MySQL 来补全额外数据,是一个好的实践嘛?还是说流处理过程中应该尽量避免查询额外的数据? Flink web UI是jquery写的吗? 12月9日更新 成功做完一次checkpoint后,会覆盖上一次的checkpoint吗? 数据量较大时,flink实时写入hbase能够异步写入吗? flink的异步io,是不是只是适合异步读取,并不适合异步写入呀? 请问一下,flink将结果sink到redis里面会不会对存储的IO造成很大的压力,如何批量的输出结果呢? 大佬们,flink 1.9.0版本里DataStream api,若从kafka里加载完数据以后,从这一个流中获取数据进行两条业务线的操作,是可以的吗? flink 中的rocksdb状态怎么样能可视化的查看有大佬知道吗? 感觉flink 并不怎么适合做hive 中的计算引擎来提升hive 表的查询速度 大佬们,task端rocksdb状态 保存路径默认是在哪里的啊?我想挂载个新磁盘 把状态存到那里去 flink 的state 在窗口滑动到下一个窗口时候 上一个窗口销毁时候 state会自己清除吗? 求助各位大佬,一个sql里面包含有几个大的hop滑动窗口,如15个小时和24个小时,滑动步长为5分钟,这样就会产生很多overlap 数据,导致状态会很快就达到几百g,然后作业内存也很快达到瓶颈就oom了,然后作业就不断重启,很不稳定,请问这个业务场景有什么有效的解决方案么? 使用jdbcsink的时候,如果连接长时间不使用 就会被关掉,有人遇到过吗?使用的是ddl的方式 如何向云邪大佬咨询FLink相关技术问题? 请问各位公司有专门开发自己的实时计算平台的吗? 请问各位公司有专门开发自己的实时计算平台的吗? 有哪位大佬有cdh集成安装flink的文档或者手册? 有哪位大佬有cdh集成安装flink的文档或者手册? 想问下老哥们都是怎么统计一段时间的UV的? 是直接用window然后count嘛? Flink是不是也是这样的? 请问现在如有个实时程序,根据一个mysql的维表来清洗,但是我这个mysql表里面就只有几条信息且可能会变。 我想同一个定时器去读mysql,然后存在对象中,流清洗的时候读取这个数据,这个想法可行吗?我目前在主类里面定义一个对象,然后往里面更新,发现下面的map方法之类的读不到我更新进去的值 有大佬做过flink—sql的血缘分析吗? 12月3日更新 请教一下,为什么我flume已经登录成功了keytab认证的kafka集群,但是就是消费不到数据呢? flink 写入mysql 很长一段时间没有写入,报错怎么解决呢? flink timestamp转换为date类型,有什么函数吗 Run a single Flink job on YARN 我采用这种模式提交任务,出现无法找到 开启 HA 的ResourceManager Failed to connect to server: xxxxx:8032: retries get failed due to exceeded maximum allowed retries number: 0 有大佬遇到过吗 ? 各位大佬,请问有Flink写S3的方案吗? flink 连接hbase 只支持1.4.3版本? onnector: type: hbase version: "1.4.3" 请问 flink1.9能跑在hadoop3集群上吗? 滑动窗口 排序 报错这个是什么原因呢? 这个pravega和kafka有啥区别? flink 开发里数据源配置了RDS,但是在RDS里没有看到创建的表,是为什么呢? Tumbling Window里的数据,是等窗口期内的数据到齐之后一次性处理,还是到了一条就处理一条啊 双流join后再做time window grouping. 但是双流join会丢失时间属性,请问大家如何解决 stream processing with apache flink,这本书的中译版 现在可以买吗? flink on yarn时,jm和tm占用的内存最小是600M,这个可以修改吗? 各位大佬,使用默认的窗口Trigger,在什么情况下会触发两次啊?窗口关闭后,然后还来了这个窗口期内的数据,并且开了allowedLateness么? flink web里可以像storm那样 看每条数据在该算子中的平均耗时吗? 各位大佬,flink任务的并发数调大到160+以后,每隔几十分钟就会出现一次TM节点连接丢失的异常,导致任务重启。并发在100时运行比较稳定,哪位大佬可以提供下排查的思路? 感觉stateful function 是下一个要发力的点,这个现在有应用案例吗? 我有2个子网(a子网,b子网)用vpn联通,vpn几周可能会断一次。a子网有一个kafka集群,b子网运行我自己的flink集群和应用,b子网的flink应用连接到a子网的kafka集群接收消息来处理入库到数仓去。我的问题是,如果vpn断开,flink consumer会异常整个作业退出吗?如果作业退出,我重连vpn后,能从auto checkpoint再把flink应用恢复到出错时flink kafka consumer应该读取的partition/offset位置吗?flink的checkpoint除了保存自己开发的算子里的state,kafkaconsumer里的partition/offset也会保存和恢复吗? flink的反压为什么不加入metrics呢 hdfs是不是和flink共用一个集群? flink消费kafka,可以从指定时间消费的吗?目前提供的接口只是根据offset消费?有人知道怎么处理? flink 的Keyby是不是只是repartition而已?没有将key相同的数据放到一个组合里面 电商大屏 大家推荐用什么来做吗? 我比较倾向用数据库,因为有些数据需要join其他表,flink充当了什么角色,对这个有点迷,比如统计当天订单量,卖了多少钱,各个省的销量,销售金额,各个品类的销售量销售金额 开源1.9的sql中怎么把watermark给用起来,有大神知道吗? 有没有人能有一些flink的教程 代码之类的分享啊 采用了checkpoint,程序停止了之后,什么都不改,直接重启,还是能接着继续运行吗?如果可以的话,savepoint的意义又是什么呢? 有人做过flink 的tpc-ds测试吗,能不能分享一下操作的流程方法 checkpoint是有时间间隔的,也就可以理解为checkpoint是以批量操作的,那如果还没进行ckecnpoint就挂了,下次从最新的一次checkpoint重启,不是重复消费了? kafka是可以批量读取数据,但是flink是一条一条处理的,应该也可以一条一条提交吧。 各位大佬,flink sql目前是不是不支持tumbling window join,有人了解吗? 你们的HDFS是装在taskmanager上还是完全分开的,请问大佬们有遇到这种情况吗? 大佬们flink检查点存hdfs的话怎么自动清理文件啊 一个128M很快磁盘就满了 有谁遇到过这个问题? 请教一下各位,这段代码里面,我想加一个trigger,实现每次有数据进window时候,就输出,而不是等到window结束再输出,应该怎么加? 麻烦问下 flink on yarn 执行 客户端启动时 报上面错,是什么原因造成的 求大佬指点 ERROR org.apache.flink.client.program.rest.RestClusterClient - Error while shutting down cluster java.util.concurrent.ExecutionException: org.apache.flink.runtime.concurrent.FutureUtils$RetryException: Could not complete the operation. Number of retries has been exhausted. 大家怎么能动态的改变 flink WindowFunction 窗口数据时间 flink on yarn之后。yarn的日志目录被写满,大家如配置的? Flink1.9 启动 yarn-session报这个错误 怎么破? yarn 模式下,checkpoint 是存在 JobManager的,提交任务也是提交给 JobManager 的吧? heckpoint机制,会不会把window里面的数据全部放checkpoint里面? Flink On Yarn的模式下,如果通过REST API 停止Job,并触发savepiont呢 jenkins自动化部署flink的job,一般用什么方案?shell脚本还是api的方式? 各位大佬,开启增量checkpoint 情况下,这个state size 是总的checkpoint 大小,还是增量上传的大小? 想用状态表作为子表 外面嵌套窗口 如何实现呢 因为状态表group by之后 ctime会失去时间属性,有哪位大佬知道的? 你们有试过在同样的3台机器上部署两套kafka吗? 大家有没有比较好的sql解析 组件(支持嵌套sql)? richmapfuntion的open/close方法,和处理数据的map方法,是在同一个线程,还是不同线程调用的? flink on yarn 提交 参数 -p 20 -yn 5 -ys 3 ,我不是只启动了5个container么? Flink的乱序问题怎么解决? 我对数据流先进行了keyBy,print的时候是有数据的,一旦进行了timeWindow滑动窗口就没有数据了,请问是什么情况呢? 搭建flinksql平台的时候,怎么处理udf的呀? 怎么查看sentry元数据里哪些角色有哪些权限? 用java api写的kafka consumer能消费到的消息,但是Flink消费不到,这是为啥? 我state大小如果为2G左右 每次checkpoint会不会有压力? link-table中的udaf能用deltaTrigger么? flink1.7.2,场景是一分钟为窗口计算每分钟传感器的最高温度,同时计算当前分钟与上一分钟最高温 001 Flink集群支持kerberos认证吗?也就是说flink客户端需要向Flink集群进行kerberos认证,认证通过之后客户端才能提交作业到Flink集群运行002 Flink支持多租户吗? 如果要对客户端提交作业到flink进行访问控制,你们有类似的这种使用场景吗? flink可以同时读取多个topic的数据吗? Flink能够做实时ETL(oracle端到oracle端或者多端)么? Flink是否适合普通的关系型数据库呢? Flink是否适合普通的关系型数据库呢? 流窗口关联mysql中的维度表大佬们都是怎么做的啊? 怎么保证整个链路的exactly one episode精准一次,从source 到flink到sink? 在SQL的TUMBLE窗口的统计中,如果没数据进来的,如何让他也定期执行,比如进行count计算,让他输出0? new FlinkKafkaConsumer010[String]("PREWARNING",new JSONKeyValueDeserializationSchema(true), kafkaProps).setStartFromGroupOffsets() ) 我这样new 它说要我传个KeyedDeserializationSchema接口进去 flink里面broadcast state想定时reload怎么做?我用kafka里的stream flink独立模式高可用搭建必需要hadoop吗? 有人用增量cleanupIncrementally的方式来清理状态的嘛,感觉性能很差。 flink sink to hbase继承 RichOutputFormat运行就报错 kafka 只有低级 api 才拿得到 offset 吗? 有个问题咨询下大家,我的flinksql中有一些参数是要从mysql中获取的,比如我flink的sql是select * from aa where cc=?,这个问号的参数需要从mysql中获取,我用普通的jdbc进行连接可以获的,但是有一个问题,就是我mysql的数据改了之后必须重启flink程序才能解决这个问题,但这肯定不符合要求,请问大家有什么好的办法吗? flink里怎样实现多表关联制作宽表 flink写es,因为半夜es集群做路由,导致写入容易失败,会引起source的反压,然后导致checkpoint超时任务卡死,请问有没有办法在下游es处理慢的时候暂停上游的导入来缓解反压? flink 写parquet 文件,使用StreamingFileSink streamingFileSink = StreamingFileSink.forBulkFormat( new Path(path), ParquetAvroWriters.forReflectRecord(BuyerviewcarListLog.class)). withBucketAssigner(bucketAssigner).build(); 报错 java.lang.UnsupportedOperationException: Recoverable writers on Hadoop are only supported for HDFS and for Hadoop version 2.7 or newer 1.7.2 NoWindowInnerJoin这个实现,我看实现了CleanupState可更新过期时间删除当前key状态的接口,是不是这个1.7.2版本即使有个流的key一直没有被匹配到他的状态也会被清理掉,就不会存在内存泄漏的问题了? flink1.7.2 想在Table的UDAF中使用State,但是发现UDAF的open函数的FunctionContext中对于RuntimeContext是一个private,无法使用,大佬,如何在Table的UDAF中使用State啊? Flink有什么性能测试工具吗? 项目里用到了了KafkaTableSourceSinkFactory和JDBCTableSourceSinkFactory。maven打包后,META-INF里只会保留第一个 标签的org.apache.flink.table.factories.TableFactory内容。然后执行时就会有找不到合适factory的报错,请问有什么解决办法吗? 为什么这个这段逻辑 debug的时候 是直接跳过的 各位大佬,以天为单位的窗口有没有遇到过在八点钟的时候会生成一条昨天的记录? 想问一下,我要做一个规则引擎,需要动态改变规则,如何在flink里面执行? flink-1.9.1/bin/yarn-session.sh: line 32: construc 我要用sql做一个规则引擎,需要动态改变规则,如何在flink里面执行? 我要用sql做一个规则引擎,需要动态改变规则,如何在flink里面执行? 一般公司的flink job有没有进程进行守护?有专门的工具或者是自己写脚本?这种情况针对flink kafka能不能通过java获取topic的消息所占空间大小? Flink container was removed这个咋解决的。我有时候没有数据的时候也出现这 大家有没有这种场景,数据从binlog消费,这个信息是订单信息,同一个订单id,会有不同状态的变更 问大家个Hive问题,新建的hive外部分区表, 怎么把HDFS数据一次性全部导入hive里 ? flink里面的broadcast state值,会出现broad流的数据还没put进mapstat Flink SQL DDL 创建表时,如何定义字段的类型为proctime? 请问下窗口计算能对历史数据进行处理吗?比如kafka里的写数据没停,窗口计算的应用停掉一段时间再开起 请问下,想统计未退费的订单数量,如果一个订单退费了(发过来一个update流),flink能做到对结果进行-1吗,这样的需求sql支持吗? 使用Flink sql时,对table使用了group by操作。然后将结果转换为流时是不是只能使用的toRetractStream方法不能使用toAppendStream方法。 百亿数据实时去重,有哪位同学实践过吗? 你们的去重容许有误差?因为bloom filter其实只能给出【肯定不存在】和【可能存在】两种结果。对于可能存在这种结果,你们会认为是同一条记录? 我就运行了一个自带的示例,一运行就报错然后web页面就崩了 flink定时加载外部数据有人做过吗? NoSuchMethodError: org.apache.flink.api.java.Utils.resolveFactory(Ljava/lang/ThreadLocal;Ljava/lang/Object;)Ljava/util/Optional 各位知道这个是那个包吗? flink 可以把大量数据写入mysql吗?比如10g flink sql 解析复杂的json可以吗? 在页面上写规则,用flink执行,怎么传递给flink? 使用cep时,如何动态添加规则? 如何基于flink 实现两个很大的数据集的交集 并集 差集? flink的应用场景是?除了实时 各位好,请教一下,滑动窗口,每次滑动都全量输出结果,外部存储系统压力大,是否有办法,只输出变化的key? RichSinkFunction close只有任务结束时候才会去调用,但是数据库连接一直拿着,最后成了数据库连接超时了,大佬们有什么好的建议去处理吗?? 为啥我的自定义函数注册,然后sql中使用不了? 请问一下各位老师,flink flapmap 中的collector.collect经常出现Buffer pool is destroyed可能是什么原因呢? 用asyncIO比直接在map里实现读hbase还慢,在和hbase交互这块儿,每个算子都加了时间统计 请教一下,在yarn上运行,会找不到 org.apache.flink.streaming.util 请问下大佬,flink1.7.2对于sql的支持是不是不怎么好啊 ,跑的数据一大就会报错。 各位大佬,都用什么来监控flink集群? flink 有那种把多条消息聚合成一条的操作吗,比如说每五十条聚合成一条 如何可以让checkpoint 跳过对齐呢? 请问 阿里云实时计算(Blink)支持这4个源数据表吗?DataHub Kafka MQ MaxCompute? 为啥checkpoint时间会越来越长,请问哪位大佬知道是因为啥呢? 请问Flink的最大并行度跟kafka partition数量有关系吗? source的并行度应该最好是跟partition数量一致吧,那剩下的算子并行度呢? Flink有 MLIB库吗,为什么1.9中没有了啊? 请教一下,有没有flink ui的文章呢?在这块内存配置,我给 TM 配置的内存只有 4096 M,但是这里为什么对不上呢?请问哪里可以看 TM 内存使用了多少呢? 请教个问题,fink RichSinkFunction的invoke方法是什么时候被调用的? 请教一下,flink的window的触发条件 watermark 小于 window 的 end_time。这个 watermark 为什么是针对所有数据的呢?没有设计为一个 key 一个 watermark 呢? 就比如说有 key1、key2、key3,有3个 watermark,有 3个 window interval不支持left join那怎么可以实现把窗口内左表的数据也写到下游呢? 各位 1、sink如何只得到最终的结果而不是也输出过程结果 ;2、不同的运算如何不借助外部系统的存储作为另外一个运算的source 请教各位一个问题,flink中设置什么配置可以取消Generic这个泛型,如图报错: 有大佬在吗,线上遇到个问题,但是明明内存还有200多G,然后呢任务cancel不了,台也取消不了程序 flink遇到The assigned slot container_1540803405745_0094_01_000008_1 was removed. 有木有大佬遇到过。在flink on yarn上跑 这个报错是什么意思呢?我使用滑动窗口的时候出现报错 flink 双流union状态过期不清理有遇到的吗? 大家有没有这种场景,数据从binlog消费,这个信息是订单信息,同一个订单id,会有不同状态的变更,如果订单表与商品明细join查询,就会出现n条重复数据,这样数据就不准了,flink 这块有没有比较好的实战经验的。 大佬们、有没有人遇到过使用一分钟的TumblingEventTimeWindows,但是没有按时触发窗口、而是一直等到下一条消息进来之后才会把这个窗口的数据发送出去的? flink 有办法 读取 pytorch的 模型文件吗? 大佬们、有没有人遇到过使用一分钟的TumblingEventTimeWindows,但是没有按时触发窗口、而是一直等到下一条消息进来之后才会把这个窗口的数据发送出去的? flink timestamp转换为date类型,有什么函数吗 flink 写入mysql 很长一段时间没有写入,报错怎么解决呢? flink 有办法 读取 pytorch的 模型文件吗? 有没有大佬知道实时报表怎么做?就是统计的结果要实时更新,热数据。 刚接触flink 1.9 求问flink run脚本中怎么没有相关提交到yarn的命令了 请教一下,flink里怎么实现batch sink的操作而不导致数据丢失

问问小秘 2019-12-02 03:19:17 0 浏览量 回答数 0

问题

【archsummit 回顾】阿里云章文嵩:构建大型云计算平台分布式技术的实践

云课堂 2019-12-01 21:03:36 14448 浏览量 回答数 9

回答

递归4—递归的弱点 之所以没有把这段归为算法的讨论,因为这里讨论的不在是算法,而只是讨论一下滥用递归的不好的一面。 递归的用法似乎是很容易的,但是递归还是有她的致命弱点,那就是如果运用不恰当,滥用递归,程序的运行效率会非常的低,低到什么程度,低到出乎你的想像。当然,平时的小程序是看不出什么的,但是一旦在大项目里滥用递归,效率问题将引起程序的实用性的大大降低。 例子:求1到200的自然数的和。 第一种做法: #include <stdio.h> void main() { int i; int sum=0; for(i=1;i<=200;i++) { sum+=i; } printf("%d\n",sum); } 该代码中使用变量2个,计算200次。再看下个代码: #include <stdio.h> int add(int i) { if(i==1) { return i; } else { return i+add(i-1); } } void main() { int i; int sum=0; sum=add(200); printf("%d\n",sum); } 但看add()函数,每次调用要声明一个变量,每次调用要计算一次,所以应该是200个变量,200次计算,对比一下想想,如果程序要求递归次数非常多的时候,而且类似与这种情况,我们还能用递归去做吗。这个时候宁愿麻烦点去考虑其他办法,也要尝试摆脱递归的干扰。 21:21 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet 程序算法5—递归3—递归的再次挖掘 递归的魅力就在于递归的代码,写出来实在是太简练了,而且能解决很多看起来似乎有规律但是又不是一下子能表达清楚的一些问题。思路清晰了,递归一写出来问题立即就解决了,给人一重感觉,递归这么好用。我们在此再更深的挖掘一下递归的用法。 之前再强调一点,也许有人会问,你前边的例子用递归似乎是更麻烦了。是,是麻烦了,因为为了方便理解,只能举一些容易理解的例子,一般等实际应用递归的时候,远远不是这种状态。 好了我们现在看一个数字的序列;有一组数的集合{1,2,4,7,11,16,22,29,37,46,56……}我故意多给几项,一般是只给前4项让你找规律的。序列给了,要求是求前50项的和。规律。有。还是没有。一看就象有,但是又看不出来,我多给了几项,应该很快看出来了,哦,原来每相邻的两项的差是个自然数排列,2-1=1,4-2=2,7-4=3,11-7=4,16-11=5…… 好了,把规律找出来了,一开始可能觉得没头绪,没问题,咱们把这个序列存放到一个数组总可以吧。那我们就声明一个数组,存放前50个数据,一个一个相加总可以了。于是有了下边的写法: #include <stdio.h> void main() { int i,a[50],sum=0; a[0]=1; for(i=1;i<50;i++) { a[i]=a[i-1]+i; } for(i=0;i<50;i++) { sum+=a[i]; } printf("%d\n",sum); } 好了,代码运行一下,结果出来了,正确不正确呢。自己测试吧,把50项改成1、2、3、4、5……项,试试前多少项是不是正确,虽然这不是正确的测试方法,但是的确是常用的测试方法。 等到这个代码已经完全理解了,完全明白了正个计算过程,我们就应该对这段代码进行改写优化了,毕竟这个代码还是不值得用一个数组的,那么我们尝试着只用变量去做一下: #include <stdio.h> void main() { int i; int number=1; int sum=0; for(i=0;i<50;i++) { number+=i; sum+=number; } printf("%d\n",sum); } 不知道我这样写是不是跨度大了点,但是我不准备详细解释了,很多东西需要你去认真分析的,所以很多东西如果不懂,自己想清楚比别人解释的效果会更好,因为别人讲只能让你理解,如果你自己去想,你就在理解的同时学会了思考。 这个代码写出来,不要继续看下去,先自己尝试着把这个题目用递归做一下看看自己能不能写出来,当然,递归并不是那么轻松就能使用的,有时候也是需要去细心设计的。如果做出来了,对比一下下边的代码,如果没有写出来,建议认真分析后边的代码,然后最好是能完全掌握,能自己随时把这行代码写出来: #include <stdio.h> int add(int n,int num,int i) { num+=i; if(i>=n-1) { return num; } else { return num+add(n,num,i+1); } } void main() { int sum; sum=add(50,1,0); /*50表示前50象项*/ printf("%d\n",sum); } 当然这个代码中的n只是一个参考变量,如果把if(i>=n-1)中的n该成50,那么就不需要这个n了,函数两个参数就可以了,这样写是为了修改方便。 20:28 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet 程序算法4—递归2—递归的魅力 两天没有再写下去,因为毕竟有时候会有点心情问题,有时候觉得心情不好,一下子什么东西都想不起来了,很多时候写一些东西是需要状态的,一旦状态有了,想的东西才能顺利的写出来,虽然有些东西写出来在别人看来很垃圾,但是起码自己觉得还是相当满意的,我写这个本来就没有多少技术含量,只是想给初学程序的人一些指引,加快他们对程序的领悟。 好了,言归正传,继续上次递归的讨论,看看递归的魅力所在。 有这样一个问题,说一个猴子和一堆苹果,猴子一天吃一半,然后再吃一个,10天后剩下一个了,也就是说吃了10次,剩下1个了。问原来一共有多少苹果。 当然我们的目的不是求出苹果的数量,而是寻求一种解决问题的方法,这个问题一出来,通常对程序掌握深度不一样的朋友对这个题会有不同的认识,首先介绍一种解决方法,这种人脑袋还是比较聪明的,思路非常的明确,也有可能语言工具掌握的也不错,代码写出来非常准确,先看一下代码再做评价吧: #include <stdio.h> void main() { int day=10; int apple; int i,j; for(i=1;;i++) { apple=i; for(j=0;j<day;j++) { if(apple%2==0&&apple>0) { apple/=2; apple--; } else { break; } } if(j==day&&apple==1) { printf("%d\n",i); return; } } } 程序的大概思路很明确,简单介绍一下,这种写法就是从一个苹果开始算起,for(i=1;;i++)的作用就是改变苹果的数量,如果1个符合条件,那就试试2个,然后3个、4个一直到适合为止,里边的for循环就是把每一次取得的苹果的数目进行计算,如果每次都能顺利的被2整除(也就是说每次都能保证猴子能正好吃一半),然后再减一一直到最后,如果最后苹果剩下是一个而且天数正好是10天,那么就输出一下苹果的数目,整个程序退出,如果看不明白的没关系,这个写法非常的不适用,我们叫写出这种算法的人傻X,虽然这种人脑袋也挺聪明,能写出一些新鲜的写法,但是又脏又臭,代码既不简练又不高效。 所以说,有时候有些人以为自己学的很好了,自己所做的一切都是最好的,这种想法是不正确的,也许有些初学者没有什么经验写出来的代码却更让人容易明白点,那么也是先看看代码: #include <stdio.h> void main() { int day[11]; int i; day[0]=1; for(i=1;i<11;i++) { day[i]=(day[i-1]+1)*2; } printf("%d\n",day[10]); } 代码不长,而且也恰当的应用了题目中的规律,不是说要吃一半然后再吃一个吗。那我用数组来存放每天苹果的数量,用day[0]表示最后一天的苹果数量,那就是剩下的一个,然后就是找规律了,什么规律。就是如果猴子不多吃一个的话,那就是正好吃了一半,也就是说猴子当天吃了之后剩余的苹果的数目加1个然后再乘以2就是前一天的数目了,这样一想这个题目就简单的多了,于是这个题用数组就轻松的做出来了。 那么这个代码究竟是不是已经很好了呢,我们注意到,这里边每个数组元素只用了一次并没有被重复使用,再这种情况下我们是不是可以用一种方法代替数组呢。于是就有了更优化的写法,这个写法似乎已经是相当简练了: #include <stdio.h> void main() { int apple=1; int i; for(i=0;i<10;i++) { apple=(apple+1)*2; } printf("%d\n",apple); } 代码写到这里已经把问题完全抽象化了,所以我们就应该站在数学的角度去分析了。也许我们就应该结束了讨论,但是偏偏这个时候,又来了递归,悄悄的通过美丽的调用显示了一下她的魅力: #include <stdio.h> int apple(int i) { if(i==0) { return 1; } else { return (apple(i-1)+1)*2; } } void main() { int i; i=apple(10); printf("%d\n",i); } 原理都还是一样的,但是写出来的格式已经完全变掉了,没有了for循环。假想一个复杂的问题远比这个问题复杂,而且没有固定循环次数,那么我们再使用循环虽然也能解决问题,但是可能面临循环难以设计、控制等问题,这个时候用递归可能就会让问题变的非常的清晰。 另外说一点,一般我这里的代码,并不是从最差到最好的,基本排列是从最差到最合适的代码(当然是本人认为最合适的,也许还有更好的,本人能力所限了),然后最后给出一种比较违反常规的代码,一般是不赞成用最后一种代码的,当然有时候最后一种代码也许是最好的选择,看情况吧。 20:25 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet 10月15日 程序算法3—递归1—递归小显威力 现在用C语言实现一个字符串的倒序输出,当然,方法也是很多的,但是如果程序中能有相对优化的方法或者简单明了易读的方法,那对你自己或者别人都是一种幸福。 第一种写法,这类写法既浪费内存又不实用,一般是刚学程序的才这样做,程序的结构很简单,利用的是数组: #include <stdio.h> void main() { char c[2000]; int i,length=0; for(i=0;i<2000;i++) { scanf("%c",&c[i]); if(c[i]=='\n') { break; } else { length++; } } for(i=length;i>0;i--) { printf("%c",c[i-1]); } printf("\n"); } 这段代码中的数组,声明大了浪费内存空间,声明小了又怕不够,所以写这种代码的人一般写完之后会祈祷,祈祷测试的人不要输入的太多,太多就不能完全显示了。 与其这么提心吊胆,于是又有人想出了第二种方法,终于解决了一些问题,而且完全实现了程序的实际要求,于是,这种人经过一番苦想,觉得问题终于可以解决了,这种方法看起来是一种很不错的方法。 #include <stdio.h> #include <malloc.h> void main() { int i; char *c; c=(char *)malloc(1*sizeof(char)); for(i=0;;i++) { *(c+i)=getchar(); if(*(c+i)=='\n') { *(c+i)='\0'; break; } else c=(char *)realloc(c,(i+2)*sizeof(char)); } for(--i;i>=0;i--) { putchar(*(c+i)); } printf("\n"); free(c); } 怎么样。不错,准确的应用内存,几乎没有浪费什么空间,这种方法也体现了一下指针的强大功能,写这个程序虽然不敢说这个人已经掌握了指针的应用,但是起码可以说他已经会用指针了。代码写出来,看起来已经有点美感。 但是也有一些人还是比较喜欢动脑筋的,经过一番思考,终于想出了第三种比较容易写的方法,也许有写初学者可能觉得有些难度,但是事实上这个东西一点都不难,如果稍微有点程序功底之后再看这段代码,应该是相当轻松。 #include <stdio.h> void run() { char c; c=getchar(); if(c!='\n') { run(); } else { return; } putchar(c); } void main() { run(); printf("\n"); } 写出的代码让人眼前一亮,哇。原来递归功能简单而又好用,那我们为什么不好好利用呢。但是递归也不一定就是最好的选择,因为有时候虽然递归用起来很方便,但是效率却不高,以后的讨论中还会详细说明。

一键天涯 2019-12-02 01:24:01 0 浏览量 回答数 0

问题

【算法】五分钟算法小知识:洗牌算法

游客ih62co2qqq5ww 2020-05-06 13:22:45 11 浏览量 回答数 1
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 企业信息查询 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站