精华内容
下载资源
问答
  • 数据量很大的排序问题 大量数据如何排序  【尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/51119499  同学某天参加腾讯面试,技术面的时候,面试官问了排序问题:   问题一:若有...

    数据量很大的排序问题 大量数据如何排序

        【尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/51151674
        同学某天参加腾讯面试,技术面的时候,面试官问了排序问题:
       问题一:若有1T的数据,需要实现由大到小排序,你用什么办法,说说你的思路和想法?
       问题二:有10个G的数据,如果两条数据一样,则表示该两条数据重复了,现在给你512的内存,把这10G中重复次数最高的10条数据取出来。
       分析:问题一和问题二思路基本是一样的,对于这种题目,利用常规的排序方法(如插入排序,快速排序……),自然是不能解决问题的!因此数据量太大。注意内部排序和外部排序的区别
       排序算法分为内部排序和外部排序:
        (1)内部排序:
    指的是待排序记录存放在计算机随机存储器(内存)中进行的排序过程;我们熟悉常用的冒泡排序,选择排序,插入排序,快速排序,堆排序,归并排序,希尔排序……等都属于内部排序方法;
         内部排序算法的比较:



        (2)外部排序:指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中需要对外存进行访问的排序过程;
          基本思路:外部排序指的是大文件的排序,即待排序的记录存储在外部存储器上,在排序过程中需进行多次的内、外存之间的交换。首先将打文件记录分成若干个子文件,然后读入内存中,并利用内部排序的方法进行排序;然后把排序好的有序子文件(称为:归并段)重新写入外存,再对这些归并段进行逐个归并,直到整个有序文件为止。
         例子:假设有10 000个记录的文件需要排序,则先把这10 000个记录文件分成10个归并段(R1…~R10,每段1000个记录),然后逐个读入归并段进行内部排序(共10次),然后把排序好的归并段重新写入外存中,再进行两两归并,直到得到一个有序文件为止。

    先来看看各位大神对问题解答:http://bbs.csdn.net/topics/390360278?page=1
    思路一:
    【1】先排序, 10G数据分成40份,每份256M,排序,合并相同数据并加上计数器,写到临时文件chunk01~chunk20。
    【2】对每一chunk, 读入内存,对每一条数据,再依次读入其后续个chunk, 合并相同数据的计数,后写入一个文件count。为了避免重复计数,在计数累加后需要将原来chunk的计数清零并回写文件。
     以chunk01为例。假设chunk01中有数据A-8(数据A, 8次),chunk02中有A-2,那么合并chunk02后
      chunk01的内存中为A-10, chunk02中为A-0,这时把chunk02写回文件,然后读入chunk03继续处理处理。最后把chunk01中计数不为0的数据(chunk01里不会有计数为0的,但是后面的chunk会有)写入文件count.
    【3】对count文件进行按重复次数排序。(分组,排序,然后每组选前10,再排序)
    思路二:
       对于问题二,个人觉得,分组统计,最后合并的方法是不可取的,因为有可能某个值A,在你每个分组中出现的次数都没有排进前10,但是将它在每个分组中的次数加起来,是能排进前10的。所以应该还是计数排序。
       其次是这10G数据时什么,是10G个BYTE,还是10G个字符串。因为BYTE的范围0-255,也就是说这个问题就变成了,找0-255范围内,出现次数最多的10个数,用int64[255]来计数,遍历一次,每个数值对应下标里面记录其出现的次数就可以了,用int64是因为DWORD表示不了10G。如果是字符串,或者是其他2进制数据块,就比较复杂,需要多次遍历。2进制数据块有多少个字节,就需要准备多少个int64[255]计数数组
       假定每条记录,就是每个2进制数据块长10个字节,对于不足10字节的记录,不足的部分以0计算需要的计数数组为int64[10][255],对于每条记录的第一个字节相同的,算为相同记录的情况下,得出表:
    A********* 1000次
    B********* 900次
    C********* 900次
    D********* 890次
    ...统计结果计入int64[0][255]
    然后对于100次的A*********,统计
    AE******** 50次
    AA******** 50次
    AD******** 49次
    AC******** 47次
    ...统计结果计入int64[1][255]
    依此类推
    AEDBBCADE* 10次
    AEDBBCADB* 9次
    AEDBBCADC* 9次
    AEDBBCADA* 8次
    ...统计结果计入int64[8][255]
    最终
    AEDBBCADEA 3次
    AEDBBCADEF 3次
    AEDBBCADEC 2次
    AEDBBCADEB 2次
    ...统计结果计入int64[9][255]
    将这个结果放入另一个int64[255] res,这个就是当前的最终结果
    然后逐个向前递归
    对于int64[8][255]中排行第二的“AEDBBCADB* 9次”
    统计出前10,得到一个新的int64[9][255],将其与res中的结果比较,得出这20个中的前10,更新res
    依此类推,得出最终结果
    展开全文
  • 数据库的索引可以提高我们的查询速度,是存储在磁盘上的,但当数据量很大的时候,索引的大小可能有几个G甚至更多。当我们利用索引查询的时候,能把整个索引都加载到内存吗?显然是不可以的,能做的就是一次一次的...

    1、数据库索引

    • 数据库的索引可以提高我们的查询速度,是存储在磁盘上的,但当数据量很大的时候,索引的大小可能有几个G甚至更多。当我们利用索引查询的时候,能把整个索引都加载到内存吗?显然是不可以的,能做的就是一次一次的加载磁盘页,这里的磁盘对应着所引述的节点。
    • 索引树

    在这里插入图片描述

    • 磁盘页
      在这里插入图片描述
    • 如果索引采用二叉排序树,那么IO的最多次数就是取决于这个树的高度。
      在这里插入图片描述

    2、B树比二叉排序树快的原因

    • B树是一个多路平衡查找树,它的每一个节点最多包含k个孩子,因此k被称作B树的阶,k的大小取决于磁盘页的大小。
    • 一个m阶B树的定义如下
    • 1.根结点至少有两个子女。
    • 2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m
    • 3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
    • 4.所有的叶子结点都位于同一层。
    • 5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
      在这里插入图片描述
    • 当查找某一个元素的时候,这个元素在二叉排序树上必须一个节点一个节点的比较。IO的次数与比较次数的相同的。而在B树中,每一个方块都会被家在今内存。例如,当查找5的时候,5先与9比较,第一次IO,然后走左分支,然后进入第二个方块,由于方块在内存中,所以与2和6的比较就在内存中比较了,而内存要比IO快10000倍左右。下面也是同理,这就提升了整个的查询速度,实际上就是减少IO的操作,访问磁盘。而平衡二叉树就是一直在IO。

    3、B+树

    • 除了具备B树的五条特征之外,还包含如下特征:
    • 1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
    • 2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    • 3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
      在这里插入图片描述
    • 这里面的根节点8是左分支最大的,15是右分支最大的
    • 同时每一个节点都带有指向下一个节点的指针,形成了有序链表。
    • B-树的中间节点和叶子节点都带有卫星数据(数据记录)
      在这里插入图片描述
    • 但是在B+树,只有叶子节点带有卫星数据,其余中间节点仅仅是索引。没有任何关联数据
      在这里插入图片描述
      需要补充的是,在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。

    B+树比B树性能优越在哪?

    • 首先在B+树的中间节点中不含有卫星数据,这里就能放置更多的节点,只放索引,所以同样大小的磁盘,可以容纳更多的节点元素。这就意味着相同数据量的情况下,B+树比B树更加矮胖,因此查询的IO次数也就更少。
    • 其次B+树查找的查询必须要找到叶子节点,而B树可以找到中间节点也可以找到叶子节点,相比之下B+树的性能更加稳定。
    • 最后一点是查询范围时,更加方便。如果是B树根据中序遍历只能一点一点的找到。而对于B+树之间有指针可以直接找到。
      在这里插入图片描述
      总结:B+树比B树更优越的原因有三点:1、单一节点存储更多的元素,使得查询的IO次数更少,2、所有查询都要查找到叶子节点,查询性能稳定。3、所有叶子节点形成有序链表,便于范围查询
    展开全文
  • 排序汇总

    2021-03-07 22:08:13
    对一组数据进行排序:首选是快速排序算法,但是在实际项目中,时候我们根据应用场景应该有多选择,例如: 根据这组数据什么特征: 例如 :如果有大量重重复元素,三路排序效果更好(java中的排序接口...

    在这里插入图片描述

    对一组数据进行排序:首选的是快速排序算法,但是在实际的项目中,很多时候我们根据应用场景应该有很多选择,例如:

    根据这组数据有什么特征:

    例如 :如果有大量重重复元素,用三路排序效果更好(java中的排序接口就是三路快速排序)

    例如: 如果是否大部分的数据距离他正确的位置是否很近?是否近几乎有序(或有序):我们利用插入排序更好一些(应用场景:银行业务按照发生的时间进行排序)

    例如:数据的取值范围是否有限?比如对学生成绩排序(北京高考成绩分数0-750),我们采用基数排序效果更好

    对排序有什么额外要求:

    例如是否需要稳定排序(通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。):如果需要稳定排序,快速排序不适合,归并排序是更好的选择

    归并排序 分组 两两合并
    三路快排 分成三部分, <Key = Key >Key
    在这里插入图片描述

    基数排序

    每个元素的位数要相同
    001 221 109 078
    1、随意分配,按照最低位(第三位)分配到不同的桶中
    2、收集,编号为0的开始收集,从下向上收集
    3、第二次分配,按照第二位分配
    4、再次收集 相同的规则(输出特点,按照第二位排序的同时,第二位相同的前提下,最萨比无额位也是有序排列的)
    5、第三次分配,按照第一位分配
    6、收集,输出结果达到排列结果

    希尔排序
    1、分组 每隔几个人为一组(谁都行,一般选择总长度的一般)
    2、组内排序(相对位置不变(0 4 8 )排序后 仍在只在这三个位置上
    3、再次找到分组间隔,这次的间隔减半
    4、直到间隔为1为止
    5、组内排序选择使用插入排序
    问题:为什么不直接用插入排序 效率高得多

    插入排序
    从第一个元素开始,依次将元素插入到数组中,每次增加一个,直到全部放入位置

    选择排序
    每一次选择一个最小的,放到第一位
    新的数组抛出第一位,重复操作

    堆排序Heap排序
    堆的概念
    大顶堆:根节点是堆中所有节点中的最大值,成为大顶堆,>=左,>=右
    堆排序
    先存入二叉树,遍历使得,根节点大于孩子节点值
    取完对顶元素后,将最小值放入堆顶
    1、构造一个大顶堆,取堆顶数组
    2、再将剩下的数字构成一个大顶堆,取堆顶数字(剩下元素中的最大值)
    3、重复以上操作,直到取完堆中的数字,最终得到一个从大到小排列的数字

    桶排序
    放最大值数个桶,每个桶记录每个数字出现的次数

    展开全文
  • 归并排序 详解

    2020-12-17 16:23:27
    数据量很大的时候 nlogn的优势将会比n^2越来越大,当n=10^5的时候,nlogn的算法要比n^2的算法快6000倍,那么6000倍是什么概念呢,就是如果我们要处理一个数据集,nlogn的算法要处理一天的话,.

    算法复杂度:O(nlogn)

    也许有很多同学说,原来也学过很多O(n^2)或者O(n^3)的排序算法,有的可能优化一下能到O(n)的时间复杂度,但是在计算机中都是很快的执行完了,没有看出来算法优化的步骤,那么我想说有可能是你当时使用的测试用例太小了,我们可以简单的做一下比较:

     

    当数据量很大的时候 nlogn的优势将会比n^2越来越大,当n=10^5的时候,nlogn的算法要比n^2的算法快6000倍,那么6000倍是什么概念呢,就是如果我们要处理一个数据集,用nlogn的算法要处理一天的话,用n^2的算法将要处理6020天。这就基本相当于是15年。一个优化改进的算法可能比一个比一个笨的算法速度快了许多,这就是为什么我们要学习算法。

    核心思想:分治。

    下面我们来看归并排序的思路(先讲思路再来具体讲归并的细节)

     

    归并排序(Merge Sort)

     

     

     

     

    当我们要排序这样一个数组的时候,归并排序法首先将这个数组分成一半。如图:

     

     

     

    然后想办法把左边的数组给排序,右边的数组给排序,之后呢再将它们归并起来。当然了当我们对左边的数组和右边的素组进行排序的时候,再分别将左边的数组和右边的数组分成一半,然后对每一个部分先排序,再归并。如图:

     

     

     

    对于上面的每一个部分呢,我们依然是先将他们分半,再归并,如图:

     

     

     

    分到一定细度的时候,每一个部分就只有一个元素了,那么我们此时不用排序,对他们进行一次简单的归并就好了。如图:

     

     

     

    归并到上一个层级之后继续归并,归并到更高的层级,如图:

     

     

     

    直至最后归并完成。

     

     

     

    那么如何归并呢?我们是否可以用O(n)的算法将两个数组归并到一起形成一个数组呢?如果可以的话,我们将可以用递归的过程来实现整个归并。这是你想起来很简单但是操作起来并不是那么简单的问题。

     

     

    归并细节:

    比如有两个已经排序好的数组,如何将他归并成一个数组?

    我们可以开辟一个临时数组来辅助我们的归并。也就是说他比我们插入排序也好,选择排序也好多使用了存储的空间,也就是说他需要o(n)的额外空间来完成这个排序。只不过现在计算机中时间的效率要比空间的效率重要的多。无论是内存也好还是硬盘也好可以存储的数据越来越多,所以设计一个算法,时间复杂度是要优先考虑的。

     

     

     

    整体来讲我们要使用三个索引来在数组内进行追踪。

     

     

     

     

     

     

    蓝色的箭头表示最终选择的位置,而红色的箭头表示两个数组当前要比较的元素,比如当前是2与1比较,1比2小,所以1放到蓝色的箭头中,蓝色的箭头后移,1的箭头后移。

     

     

     

     

     

    然后2与4比较,2比4小那么2到蓝色的箭头中,蓝色箭头后移,2后移,继续比较.......

     

     

    归并思路就是这样了,最后唯一需要注意的是那个先比较完的话,那么剩下的直接不需要比较,把后面的直接移上去就可以了,这个需要提前判定一下。

    展开全文
  • C++内部的sort是由快排,直接插入和堆排序混合的,具体详情见STL源码剖析,当数据量比较大的时候先用的快排,当数据量的时候用直接插入,因为当数据量变小时,快排中的每个部分基本有序,接近直接插入的最好情况的...
  • 我的问题是,为什么冒泡排序和选择排序在对数组进行逆序排序的时候花的时间比对随机数组进行排序所花的时间少呢? [code="java"]import java.util.Random; public class ArrayUtil { public static void ...
  • 大话数据结构

    2019-01-10 16:35:22
    想想看,在你准备的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。 4.2栈的定义 89 类似的多软件,比如word、photoshop等,都有撤消(undo)的操作,也是栈这种思想方式来实现的。 4.2.1栈的定义 89...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    想想看,在你准备的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。 4.2栈的定义 89 类似的多软件,比如word、photoshop等,都有撤消(undo)的操作,也是栈这种思想方式来实现的。 4.2.1栈的定义 89...
  • 想想看,在你准备的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。 4.2栈的定义 89 类似的多软件,比如word、photoshop等,都有撤消(undo)的操作,也是栈这种思想方式来实现的。 4.2.1栈的定义 89...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    想想看,在你准备的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。 4.2 栈的定义 89 类似的多软件,比如Word、Photoshop等,都有撤消(undo)的操作,也是栈这种思想方式来实现的。 4.2.1 栈的...
  • 想想看,在你准备的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。 4.2栈的定义 89 类似的多软件,比如word、photoshop等,都有撤消(undo)的操作,也是栈这种思想方式来实现的。 4.2.1栈的定义 89...
  • 第4章 栈与队列 87 4.1 开场白 88 想想看,在你准备的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。 4.2 栈的定义 89 类似的多软件,比如Word、Photoshop等,都有撤消(undo)的操作,也是栈这种...
  • 带你彻底了解到底什么是算法复杂度 在工作中,当我们在项目中用到一个算法的时候,总会有一个问题绕不开,那就是算法...直到有一次当我想对一个数据量很大的问题排序的时候,我发现api中的方法明显不行了。就连...
  • 数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    二者有何相同和不同之处,抽象数据类型主要特点是什么? 使用抽象数据类型主要好处是什么?【北京邮电大学 1994 一(8分)】 4. 回答问题(每题 2分)【山东工业大学 1997 一 (8分)】 (1)在数据结构课程中...
  • 当然,数据不多的时候问题不大,但是如果数据量很大且空行比较多的时候,这样的操作不仅麻烦还容易出错。那,有什么方法可以快速的将这些没用的空行全部删除呢?这里,潜伏君给大家分享几种实用的小技巧,希望能对你...
  • // 为什么会出现这种排序结果呢❓ // 因为在忽略sortFn情况下,元素会按照转换为字符串各个字符Unicode位点进行排序,如下 let equalValues = ['0', '1', '5', '...
  • 4.4 我指针操作int数组的时候遇到了麻烦。 4.5 我有一个char*型指针碰巧指向一些int型变量,我想跳过它们。为什么((int*)p)++;这样的代码不行? 4.6 为什么不能对void*指针进行算术操作? 4.7 我有些解析外部...
  • Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。 15、final, finally, finalize的区别。  final 用于声明属性,方法和类,分别表示属性不可变,方法不可覆盖,类不可继承。 ...
  • 4.4 我指针操作int数组的时候遇到了麻烦。 46 4.5 我有一个char *型指针碰巧指向一些int型变量,我想跳过它们。为什么((int *)p)++; 这样的代码不行? 47 4.6 为什么不能对void *指针进行算术操作? 47 4.7...
  • 另外,图灵公司论坛上丰富资料和活跃讨论也使我们眼界开,受益良多。  翻译工作并非阐述自己思想,翻译第一要务是忠实地传达原著者思想。虽然无法自由地表达自己想法,然而,翻译快乐就在于:使...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    4.4 我指针操作int数组的时候遇到了麻烦。 46 4.5 我有一个char *型指针碰巧指向一些int型变量,我想跳过它们。为什么((int *)p)++; 这样的代码不行? 47 4.6 为什么不能对void *指针进行算术操作? 47 4.7...
  • MySQL

    2019-09-11 18:30:00
    MySQL之前一只觉得数据库没什么,会...索引是一个排序的列表,这个列表中存储着索引的值和包含这个值的数据所在的物理地址,数据量庞大的时候,索引可以快速定位需要查找的数据对应的物理地址,不需要扫描全表的数据...
  • 对于一个有上亿数据量的数据查找,需要大概20次左右磁盘IO,就是200ms,所以真慢; 那如何解决平衡二叉查找树带来磁盘IO过多问题呢?答案是降低树高度,树高度...
  • mysql 索引

    2020-05-14 12:01:04
    索引重要性 索引影响数据库性能, 数量量了以后,内存不能完全存放数据,查询量变多,索引会越来越重要 索引大大减少了存储引擎需要扫描的数据量 索引可以帮助我们进行排序以避免使用临时...什么时候用B树索引?
  • <div><p><strong>UPDATE(...单元测试的时候就可以完整的测试Presenter应用逻辑的正确性。这里根据上面的例子给出了Presenter的单元测试样例。 2. View可以进行组件化。在MVP当中,View不依赖Model。这样就...
  • 当我们解析一个很大的JSON字符串的时候,如果需要500ms才能解析完,这个时候就会影响用户体验,在这段时间内什么也做不了,这个时候webWorker是最理想的解决办法 webWorker 它有自己的运行环境,不会可以在后台运行...

空空如也

空空如也

1 2 3 4 5 6
收藏数 102
精华内容 40
关键字:

数据量很大的时候用什么排序