精华内容
下载资源
问答
  • 这些数据分布在很的Excel表格中。![图片](https://img-ask.csdn.net/upload/201604/30/1462018292_154317.jpg)
  • 初始条件:left = 0, right = length 因为数组从下标0开始,所以实际代码中可以是 num.length - 1 终止:left 向左查找:right = mid 这是因为向右判断,一般需要保留比较元素,否则某些晴情况下会丢失数据 ...
    
    

    二分法

    二分法又可以被称为二分查找,它描述了在有序集合中搜索特定值的过程。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。

    对于二分法的思想大家都能讲出几句,但我们仍然很难讲其与实际应用完美的结合到一起,所以我们尽量汇总二分法的应用场景,和大家一起深入,共勉!

    一、常见问题

    给定一个由数字组成的有序数组 nums,并给你一个数字 target。问 nums 中是否存在 target。如果存在,则返回其在 nums 中的索引。如果不存在,则返回 - 1。

    这是二分查找中最简单的一种形式。当然二分查找也有很多的变形,这也是二分查找容易出错,难以掌握的原因。

    常见变体有:

    • 如果存在多个满足条件的元素,返回最左边满足条件的索引。
    • 如果存在多个满足条件的元素,返回最右边满足条件的索引。
    • 数组不是整体有序的。 比如先升序再降序,或者先降序再升序。
    • 将一维数组变成二维数组…等等

    在这里插入图片描述

    二、二分查找中使用的术语

    如前所述,二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时,都应该考虑二分查找。如果集合是无序的,我们可以总是在应用二分查找之前先对其进行排序。但要注意排序的成本

    • target: 要查找的值
    • index: 查找时的当前位置
    • leftright: 左右指针
    • mid: 左右指针的中点,用来确定我们应该向左查找还是向右查找的索引

    在最简单的形式中,二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符,并比较查找目标或将查找条件应用于集合的中间值;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。如果查以空的一半结束,则无法满足条件,并且无法找到目标。

    注意:

    1. 二分法搜索可以采用许多替代形式
    2. 可能并不总是直接搜索特定值
    3. 你不一定能直接缩小一半的查找范围

    看过之后的几个模版,并结合配套的例题,相信你会有自己的想法。

    在这里插入图片描述

    三、模版 I - 基础二分查找

    模版 I 是基础的二分查找,用于查找可以通过访问数组中的单个索引来确定的元素或条件。

    3.1 复杂度分析

    • 平均时间复杂度: O(logN)
    • 最坏时间复杂度: O(logN)
    • 最优时间复杂度: O(1)

    3.2 关键点

    • 二分查找的最基础和最基本的形式。
    • 查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特定元素)。
    • 不需要后处理,因为每一步中,你都在检查是否找到了元素。如果到达末尾,则知道未找到该元素。

    3.3 区分语法

    1. 初始条件:
    • left = 0
    • right = arrar.length-1 或 number
    1. 终止:left > right
    2. 向左查找:right = mid-1
    3. 向右查找:left = mid+1

    3.4 javascript 基础模版

    var search = function(nums, target) {
      left = 0; // 初始左边界
      right = nums.length - 1; // 初始右边界
      while (left <= right) {
        let mid = left + Math.floor((right - left) / 2); //防止溢出
        if (nums[mid] < target) {
          // 收缩左边界
          left = mid + 1;
        } else if (nums[mid] > target) {
          // 收缩右边界
          right = mid - 1;
        } else {
          return mid; // 找到了当前值
        }
      }
      return -1;
    };
    

    3.5 代码分析

    1. 确定初始的左右边界:
      • left: 0
      • right: nums.length-1
      • mid: (left + (right - left) >> 1)
    2. 如果中间元素值nums[mid] < target:证明中间值左侧包括中间值都不符合要求,可以直接排除,left = mid + 1
    3. 如果中间元素值nums[mid]:证明中间值右侧包括中间值都不符合要求,可以直接排除,right = mid - 1
    4. 如果中间元素值nums[mid] = target:直接返回mid的下标
    5. 重新定义了左右边界,也需要重新计算中间值,我们需要继续进行范围的排除
    6. 定义搜索的条件,应该是搜索区间都不为空,即left <= right

    3.6 LeetCode 实战

    下面五题,难度递增,每篇题解都包含原题链接、模版分析、Js 题解,大家可以放心食用,我们一起加油~

    1. 二分查找(easy)
    2. 搜索插入的位置(easy)
    3. x 的平方根(easy)
    4. 猜数字大小(easy)
    5. 搜索旋转排序数组(middle)

    在这里插入图片描述

    四、模版 II - 依赖当前元素与右元素的关系

    模板 II 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

    4.1 关键点

    • 查找条件需要访问元素的直接右邻居。
    • 使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
    • 保证查找空间在每一步中至少有 2 个元素。
    • 需要进行后处理。 当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。

    4.2 区分语法

    • 初始条件:left = 0, right = length 因为数组从下标0开始,所以实际代码中可以是 num.length - 1
    • 终止:left <= right
    • 向左查找:right = mid 这是因为向右判断,一般需要保留比较元素,否则某些晴情况下会丢失数据
    • 向右查找:left = mid+1

    4.3 javascript 基础模版

    var search = function(nums, target) {
      left = 0; // 初始左边界
      right = nums.length - 1; // 初始右边界
      while (left <= right) {
        var mid = left + Math.floor(left + (right - left) / 2); //防止溢出
        if (target == nums[mid]) {
          right = mid + 1; // 继续寻找左侧是否仍存在满足条件的元素,但包含当前元素
        } else if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      if (left != nums.length && nums[left] === target) return left;
      return -1;
    };
    

    4.4 代码分析

    首先定义搜索区间为 [left, right],注意是左右都闭合,之后会用到这个点。

    1. 终止搜索条件为 left <= right。
    2. 循环体内,我们不断计算 mid ,并将 nums[mid] 与 目标值比对。
    3. 如果 nums[mid] 等于目标值, 则收缩左边界,注意它此时不代表最终结果
    4. 如果 nums[mid] 小于目标值, 说明目标值在 mid 右侧,这个时候搜索区间可缩小为 [mid + 1, right]
    5. 如果 nums[mid] 大于目标值, 说明目标值在 mid 左侧,这个时候搜索区间可缩小为 [left, mid - 1]
    6. 最后我们要判断 left 值是否等于 target,如果不等于,证明没找到
    7. 如果 left 出了右边边界了,说明也没有找到

    4.5 LeetCode 实战

    下面 3 题,难度递增,每篇题解都包含原题链接、模版分析、Js 题解,大家可以放心食用,我们一起加油~

    1. 第一个错误的版本(easy)
    2. 寻找峰值(middle)
    3. 寻找旋转排序数组中的最小值(middle)

    在这里插入图片描述

    五、模板 III - 依赖当前元素与左右两个元素之间的关系

    模板 III 是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

    5.1 关键点

    • 实现二分查找的另一种方法。
    • 搜索条件需要访问元素的直接左右邻居。
    • 使用元素的邻居来确定它是向右还是向左。
    • 保证查找空间在每个步骤中至少有 3 个元素。
    • 需要进行后处理。当剩下 2个元素时,循环 / 递归结束。需要评估其余元素是否符合条件。

    5.2 区分语法

    • 初始条件:left = 0, right = length - 1
    • 终止:left + 1 === right
    • 向左查找:right = mid
    • 向右查找:left = mid

    5.3 javascript 基础模版

    function binarySearch(nums, target) {
      const len = nums.length;
      if (len === 0) return -1;
      let left = 0;
      let right = len - 1;
      while (left + 1 < right) {
        let mid = left + ((right - left) >> 1);
        if (nums[mid] === target) {
          return mid;
        } else if (nums[mid] < target) {
          left = mid;
        } else {
          right = mid;
        }
      }
      if (nums[left] == target) return left;
      if (nums[right] == target) return right;
      return -1;
    }
    

    5.4 代码分析

    因为我们的判断区间最少为 2 个元素,所以我们要注意循环的执行条件

    1. 简单的判断边界: nums.length === 0,return -1
    2. 定义初始的左右边界:left = 0, right = nums.length - 1
    3. 确定执行条件:left + 1 < right,这也意味着查找区间要存在 3 个元素;
    4. 向左查找时:right = mid
    5. 向左查找时:left = mid
    6. 判断剩下的两个元素哪个符合目标元素,并返回结果;

    5.5 LeetCode 实战

    下面 3 题,难度递增,每篇题解都包含原题链接、模版分析、Js 题解,大家可以放心食用,我们一起加油~

    1. 在排序数组中查找元素的第一个和最后一个位置(hard)

    在这里插入图片描述

    六、二分查找模板分析

    本小结引自于LeetCode二分专题

    上面提到的三个模版,大家在做题的时候很难完全套用进去,大部分时候,都是寻找最合适的方式并不断调整

    6.1 模版差异

    这 3 个模板的不同之处在于:

    在这里插入图片描述

    • 左、中、右索引的分配。
    • 循环或递归终止条件。
    • 后处理的必要性。

    个人感觉模版I最实用(其实是另外两个模版掉头发啊!)

    6.2 模版示例

    模板I (left <= right)

    二分查找的最基础和最基本的形式。

    • 查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特定元素)。
    • 不需要后处理,因为每一步中,你都在检查是否找到了元素。如果到达末尾,则知道未找到该元素。

    模板II (left < right)

    一种实现二分查找的高级方法。

    • 查找条件需要访问元素的直接右邻居。
    • 使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
    • 保证查找空间在每一步中至少有 2 个元素。
    • 需要进行后处理。 当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。

    模板III (left + 1 < right)

    实现二分查找的另一种方法。

    • 搜索条件需要访问元素的直接左右邻居。
    • 使用元素的邻居来确定它是向右还是向左。
    • 保证查找空间在每个步骤中至少有 3 个元素。
    • 需要进行后处理。 当剩下 2 个元素时,循环 / 递归结束。 需要评估其余元素是否符合条件。

    七、其他经典问题

    八、写在最后

    本文解释了三种最常见的解题模版,并附上LeetCode实战,帮助我们理解二分法这种思想。

    如果对你有所帮助不妨给本项目的github 点个 star,这是对我最大的鼓励

    关于我

    • 花名:余光
    • WX:j565017805
    • 沉迷 JS,水平有限,虚心学习中

    其他沉淀

    展开全文
  • 问题描述:从json数组中,查找出满足指定定条件数据。 解决方法:【filter()】 var employeesData = [ { name: "王小明", mobile: "13900008789" }, { name: "陈霞", mobile: "13900008789" }, { name: ...

    问题描述:从json数组中,查找出满足指定定条件的数据。

    解决方法:【filter()】

    var employeesData = [
      { name: "王小明", mobile: "13900008789" },
      { name: "陈霞", mobile: "13900008789" },
      { name: "张悦", mobile: "13900008789" }
    ]
    
    var queryData = employeesData.filter(function(fp) {
      return fp.name === "王小明"
    })
    console.log(queryData)

     

    展开全文
  • 分页应该是极为常见的数据展现方式了,一般在数据集较大而无法在单个页面中呈现时会采用分页的方法。 各种前端UI组件在实现上也都会支持分页的功能,而数据交互呈现所相应的后端系统、数据库都对数据查询的分页提供...

    一、背景

    分页应该是极为常见的数据展现方式了,一般在数据集较大而无法在单个页面中呈现时会采用分页的方法。
    各种前端UI组件在实现上也都会支持分页的功能,而数据交互呈现所相应的后端系统、数据库都对数据查询的分页提供了良好的支持。
    以几个流行的数据库为例:

    查询表 t_data 第 2 页的数据(假定每页 5 条) 

    • MySQL 的做法:

    select * from t_data limit 5,5
    • PostGreSQL 的做法:
    select * from t_data limit 5 offset 5
    • MongoDB 的做法:
    db.t_data.find().limit(5).skip(5);

    尽管每种数据库的语法不尽相同,通过一些开发框架封装的接口,我们可以不需要熟悉这些差异。如 SpringData 提供的分页接口:

    public interface PagingAndSortingRepository
      extends CrudRepository {
    
      Page findAll(Pageable pageable);
    }

    这样看来,开发一个分页的查询功能是非常简单的。
    然而万事皆不可能尽全尽美,尽管上述的数据库、开发框架提供了基础的分页能力,在面对日益增长的海量数据时却难以应对,一个明显的问题就是查询性能低下!
    那么,面对千万级、亿级甚至更多的数据集时,分页功能该怎么实现?

    下面,我以 MongoDB 作为背景来探讨几种不同的做法。

    二、传统方案

    就是最常规的方案,假设 我们需要对文章 articles 这个表(集合) 进行分页展示,一般前端会需要传递两个参数:
    - 页码(当前是第几页)
    - 页大小(每页展示的数据个数)

    按照这个做法的查询方式,如下图所示:

     

    因为是希望最后创建的文章显示在前面,这里使用了_id 做降序排序
    其中红色部分语句的执行计划如下:

    {
      "queryPlanner" : {
        "plannerVersion" : 1,
        "namespace" : "appdb.articles",
        "indexFilterSet" : false,
        "parsedQuery" : {
          "$and" : []
        },
        "winningPlan" : {
          "stage" : "SKIP",
          "skipAmount" : 19960,
          "inputStage" : {
            "stage" : "FETCH",
            "inputStage" : {
              "stage" : "IXSCAN",
              "keyPattern" : {
                "_id" : 1
              },
              "indexName" : "_id_",
              "isMultiKey" : false,
              "direction" : "backward",
              "indexBounds" : {
                "_id" : [ 
                  "[MaxKey, MinKey]"
                ]
             ...
    }

    可以看到随着页码的增大,skip 跳过的条目也会随之变大,而这个操作是通过 cursor 的迭代器来实现的,对于cpu的消耗会比较明显。
    而当需要查询的数据达到千万级及以上时,会发现响应时间非常的长,可能会让你几乎无法接受!

    或许,假如你的机器性能很差,在数十万、百万数据量时已经会出现瓶颈

    三、改良做法

    既然传统的分页方案会产生 skip 大量数据的问题,那么能否避免呢?答案是可以的。
    改良的做法为:
    1. 选取一个唯一有序的关键字段,比如 _id,作为翻页的排序字段;
    2. 每次翻页时以当前页的最后一条数据_id值作为起点,将此并入查询条件中。

    如下图所示:

    修改后的语句执行计划如下:

    {
      "queryPlanner" : {
        "plannerVersion" : 1,
        "namespace" : "appdb.articles",
        "indexFilterSet" : false,
        "parsedQuery" : {
          "_id" : {
            "$lt" : ObjectId("5c38291bd4c0c68658ba98c7")
          }
        },
        "winningPlan" : {
          "stage" : "FETCH",
          "inputStage" : {
            "stage" : "IXSCAN",
            "keyPattern" : {
              "_id" : 1
            },
            "indexName" : "_id_",
            "isMultiKey" : false,
            "direction" : "backward",
            "indexBounds" : {
              "_id" : [ 
                "(ObjectId('5c38291bd4c0c68658ba98c7'), ObjectId('000000000000000000000000')]"
              ]
          ...
    }

     可以看到,改良后的查询操作直接避免了昂贵的 skip 阶段,索引命中及扫描范围也是非常合理的!

    性能对比

    为了对比这两种方案的性能差异,下面准备了一组测试数据。

    测试方案
    准备10W条数据,以每页20条的参数从前往后翻页,对比总体翻页的时间消耗

    db.articles.remove({});
    var count = 100000;
    
    var items = [];
    for(var i=1; i<=count; i++){
    
      var item = {
        "title": "论年轻人思想建设的重要性-" + i,
        "author" : "王小兵-" + Math.round(Math.random() * 50),
        "type" : "杂文-" + Math.round(Math.random() * 10) ,
        "publishDate" : new Date(),
      } ;
      items.push(item);
    
    
      if(i%1000==0){
        db.test.insertMany(items);
        print("insert", i);
    
        items = [];
      }
    }

    传统翻页脚本

    function turnPages(pageSize, pageTotal){
    
      print("pageSize:", pageSize, "pageTotal", pageTotal)
    
      var t1 = new Date();
      var dl = [];
    
      var currentPage = 0;
      //轮询翻页
      while(currentPage &lt; pageTotal){
    
         var list = db.articles.find({}, {_id:1}).sort({_id: -1}).skip(currentPage*pageSize).limit(pageSize);
         dl = list.toArray();
    
         //没有更多记录
         if(dl.length == 0){
             break;
         }
         currentPage ++;
         //printjson(dl)
      }
    
      var t2 = new Date();
    
      var spendSeconds = Number((t2-t1)/1000).toFixed(2)
      print("turn pages: ", currentPage, "spend ", spendSeconds, ".")  
    
    }

    改良翻页脚本

    function turnPageById(pageSize, pageTotal){
    
      print("pageSize:", pageSize, "pageTotal", pageTotal)
    
      var t1 = new Date();
    
      var dl = [];
      var currentId = 0;
      var currentPage = 0;
    
      while(currentPage ++ &lt; pageTotal){
    
          //以上一页的ID值作为起始值
         var condition = currentId? {_id: {$lt: currentId}}: {};
         var list = db.articles.find(condition, {_id:1}).sort({_id: -1}).limit(pageSize);
         dl = list.toArray();
    
         //没有更多记录
         if(dl.length == 0){
             break;
         }
    
         //记录最后一条数据的ID
         currentId = dl[dl.length-1]._id;
      }
    
      var t2 = new Date();
    
      var spendSeconds = Number((t2-t1)/1000).toFixed(2)
      print("turn pages: ", currentPage, "spend ", spendSeconds, ".")    
    }

    以100、500、1000、3000页数的样本进行实测,结果如下

    可见,当页数越大(数据量越大)时,改良的翻页效果提升越明显!
    这种分页方案其实采用的就是时间轴(TImeLine)的模式,实际应用场景也非常的广,比如Twitter、微博、朋友圈动态都可采用这样的方式。
    而同时除了上述的数据库之外,HBase、ElasticSearch 在Range Query的实现上也支持这种模式。

    四、完美的分页

    时间轴(TimeLine)的模式通常是做成“加载更多”、上下翻页这样的形式,但无法自由的选择某个页码。
    那么为了实现页码分页,同时也避免传统方案带来的 skip 性能问题,我们可以采取一种折中的方案。

    这里参考Google搜索结果页作为说明:

    通常在数据量非常大的情况下,页码也会有很多,于是可以采用页码分组的方式。
    以一段页码作为一组,每一组内数据的翻页采用ID 偏移量 + 少量的 skip 操作实现

    具体的操作如下图所示:

    实现步骤

    1. 对页码进行分组(groupSize=8, pageSize=20),每组为8个页码;

    2. 提前查询 end_offset,同时获得本组页码数量:

    db.articles.find({ _id: { $lt: start_offset } }).sort({_id: -1}).skip(20*8).limit(1)
    1.  分页数据查询以本页组 start_offset 作为起点,在有限的页码上翻页(skip),由于一个分组的数据量通常很小(8*20=160),在分组内进行skip产生的代价会非常小,因此性能上可以得到保证。

    小结

    随着物联网,大数据业务的白热化,一般企业级系统的数据量也会呈现出快速的增长。而传统的数据库分页方案在海量数据场景下很难满足性能的要求。

    在本文的探讨中,主要为海量数据的分页提供了几种常见的优化方案(以MongoDB作为实例),并在性能上做了一些对比,旨在提供一些参考。

    来源:华为云社区  作者:zale

    展开全文
  • 寻找最优的 TopN 算法 1 概要 在大量的数据记录中,依据某可排序的记录属性(一般为数字类型),找出最大的前 N 个记录,称为 TopN 问题。这是一个常常遇到的问题,也是一个比较简单的算法问题,却很少能有...

    寻找最优的 TopN 算法



    1 概要
    在大量的数据记录中,依据某可排序的记录属性(一般为数字类型),找出最大的前 N 个记录,称为
    TopN 问题。这是一个常常遇到的问题,也是一个比较简单的算法问题,却很少能有人能写出最优化的
    topn 算法。本文对常见的 TopN 算法,进行分析比较,最后给出最优的 TopN 算法:基于小根堆的筛选
    法.
    2 问题定义
    为了方便。我们把问题具体化:要求使用 C 语言来实现函数,在一个大小为 m 的,无序的整数数组中选
    取最大的 n 个整数。即,问题定义为一个函数的实现:
    int * topn(int *pdata, int m,int *ptop, int n);
    其中,pdata 指向保存大量整数的内存,整数的个数为 m,要求函数把前 n 个最大的整数保存到 ptop 指
    向的内存中,显然满足 m≥n≥0 。 同时假定 n<=m/2, 因为当 n 如果超过半数,可以问题转换为排
    除 n−m/2个最小的整数----这种转换减少了问题规模。并且,已经实现选择 n 个最值(最大或最小)
    的算法的情况下,排除 n 个最值的算法可以仿照实现。这里不再费时间叙述。
    我们虽然假设的数据类型为整数,其他任意的数据类型,只要其数据是可以排序的,都可以根据这里的
    算法,写出对应的算法实现。同样,我们虽然假定输入数据的方式为数组,实际输入的方式可以是任意
    其他方式(如文件,数据库等)。
    3 算法介绍
    3.1 算法 1 完整排序法
    对 pdata 中的数据,进行内部排序,然后选取前 n 个整数放到 ptop 中。如果使用较高效率的内部排序
    算法(如:快速排序,堆排序),复杂度为 m∗log2
    m .
    使用这种算法,结果数据是从大到小排序的。
    3.2 算法 2 基于有序数组的筛选法
    保持 ptop 中的结果数组有序,即满足 ptop[0]≥ptop[1]≥...≥ptop[n−1] ,遍历 pdata 中的数
    据,如果发现当前整数大于 ptop[n-1]就把数据插入到合适位置,以保持 ptop 中的仍然有序。算法复
    杂度为. m∗n
    使用这种算法,结果数据是从大到小排序的。显然,只从理论上的复杂度考虑,就可以看出来:当 n 较小的时候,算法 2 有较高的效率。但当 n 较大
    的时候,算法 1 会有较高的效率。
    仔细分析算法 2, 保持 ptop 中数据有序的目的,就是每次能找到最小的值,在有序数组中插入一个新元
    素,最坏需要 n 次操作才能保持数组有序。其实要快速找到最小的值,使用小根堆更合适,因为中堆中
    每次插入一个元素,最坏只需要 log2
    n 次操作,根据这个思路产生下面的算法 3。
    3.3 算法 3 基于小根堆的筛选法。
    使用大小为 n 的小根堆保存结果集,最小项为堆的根节点 ptop[0],遍历 pdata 中,如果当前数据大于
    ptop[0],并把数据替换根节点,并对根节点 SiftDown 操作,保持结果集仍然为小根堆。算法复杂度,
    只有 m∗log2
    n .- 更多关于小根堆的介绍,请看后面。
    显然有,
    m∗log2 nm∗log2 m , m∗log2 nm∗n
    所以,算法 3 的复杂度最低。
    这种算法,生成的结果数据是没有排序的。因为结果已经保存最小根堆种,如果需要排序,只需要完成
    常规堆排序流程的后半部分,排序需要的复杂度只有 n。
    4 实际测试结果
    测试环境:
    OS: Debain Linux kernel 2.6.26
    C Complier: gcc 4.3.4
    MEM: 768m
    CPU: Intel(R) Pentium(R) 4 CPU 2.40GHz

    5 算法分析
    1. 在任何情况下,算法 3 都是最优的。但算法 3 的实现较复杂。
    2. 如果不想实现复杂的算法 3,如果 n 相对于 m 很小,可以选择算法 2
    3. 如果不想实现复杂的算法 3, 如果 n 比较大,例如:接近了 m/2, 可以选择算法 1
    4. 如果不要求结果排序,算法 3 更有优势。
    5. 算法 1 和算法 2,结果自然就排号顺序了。是否要求排序与其时间花费无关。
    根据理论复杂度和实际的测试结果,更有下面的结论。
    当 m 值固定,n 的变化区间为[1,m/2],三种算法消耗时间随 n 变化的曲线,如下面的图示意。相应的,当 n 固定,m 的变化区间为[2*n, ∞ ),三种算法消耗算法随 m 变化的曲线,如下面的图示意。


    6 算法实现
    6.1 算法 1 实现
    使用标准 c 语言库支持的 qsort,直接就可以实现。
    //用于比较操作的函数
    static int cmpint(const void *p1, const void *p2)
    {
    return *((int *)p2) - *((int *)p1);
    }
    //算法实现
    int * topn1(int *pdata, int m,int *ptop, int n)
    {
    qsort(pdata, m, sizeof(int),cmpint);
    memcpy(ptop, pdata, n*sizeof(int));
    return ptop;
    }
    注意:如果自己实现 qsort 算法,会有一定效率的提高。但代码级的优化,这里不会对效率产生本质的
    影响。6.2 算法 2 实现
    比较简单,源代码如下
    int *topn2(int *pdata,int m,int *ptop,int n)
    {
    int i;
    for(i=0;i<m;i++)
    {
    //判断当前结果集的大小(数组的长度)
    int t = (i+1<n) ? (i+1):n;
    if(i>=n && pdata[i] <= ptop[n-1])
    continue;
    int j=t-1;
    for(;j>=1 && pdata[i]>ptop[j-1];j--)
    ptop[j] = ptop[j-1];
    ptop[j] = pdata[i];
    }
    return ptop;
    }
    注意:如果使用监视哨等优化手段,可以减少循环的判断条件。但这种代码级别的优化,这里不会对效
    率产生本质的影响。
    6.3 算法 3 实现
    6.3.1 小根堆概念定义
    小根堆精确定义:数组 x[1..n](注意,这里假定数组的第一个元素的索引为 1,是为了下面描述方便),
    如果满足:
    ∀i∋[2,n], x[i/2]≤x [i]
    就说明,这个数组就是小根堆
    为了下面描述方便,我们定义对数组 x[1..n]的子数组 x[u..v],( 1≤u≤v≤n ),如果满足:
    ∀i∋[2l, u],x[i/2]≤x [i]
    就说明:x 整个数组的[u..v]部分已经是小根堆了。
    6.3.2 我们需要的堆操作
    //如果[2..n]已经是堆了,-除了第一个元素,其他部分已经是小根堆。
    //通过下面的函数把第一个元素,往后交换,把整个数组变成堆。
    void siftdown_head(int *pheap,int n)
    {
    pheap --; //这样作是让第一个元素的索引变成 1, pheap[0]永远不会被访问到int t = pheap[1];
    int i =1;
    int c = i*2;
    while(c<=n)
    {
    if(c<n && pheap[c]>pheap[c+1])
    c++;
    if(pheap[c] < t)
    {
    pheap[i] = pheap[c];
    i = c;
    c = 2*i;
    }
    else
    break;
    }
    pheap[i] = t;
    }
    //如果除了最后一个元素外,其他部分[1..n-1]已经是堆了,
    //通过下面的函数,把最后一个元素往前交换,把整个数组调整成堆
    void siftup_rear(int *pheap,int n)

    pheap --;
    int t = pheap[n];
    int i;
    for(i=n; i>1;)
    {
    int p = i/2;
    if( pheap[p] > t)
    pheap[i] = pheap[p];
    else
    break;
    i=p;
    }
    pheap[i] =t;
    }
    更多关于堆的概念,可以在网上找到。最常见的应用是使用堆来实现高效率的优先级队列(如 c++的标
    准模板库)。在本文应用场景中,也可以把保存 topn 结果的数组看成是优先级队列,因为我们总是选择
    数值最小的值,进行出队操作(数值越小,优选级越大)。最后,队列中剩余的,自然就是数值较大的
    topn 结果。
    6.3.3 算法实现
    int * topn3(int *pdata, int m,int *ptop, int n){
    ptop[0] = pdata[0];
    int i;
    for(i=1; i<n;i++)
    {
    ptop[i] = pdata[i];
    siftup_rear(ptop,i+1);
    }
    for(i=n;i<m;i++)
    {
    register t = pdata[i];
    if(ptop[0] >= t)
    continue;
    ptop[0] = t;
    siftdown_head(ptop,n);
    ;
    }
    //如果不需要把结果排序,下面的这段循环可以乎略掉
    for(i=n-1; i>=1;i--)
    {
    int t = ptop[i];
    ptop[i] = ptop[0];
    ptop[0] = t;
    siftdown_head(ptop,i);
    }
    return ptop;
    }
    其实,在本文问题定义下,也可以直接使用 c++标准库的模板种的优先级队列,来实现 topn 算法。

     

    转自mail:cuichaox @gmail.com 
    转自blog: http://cuichaox.cublog.cn
    展开全文
  • 寻找道路

    千次阅读 2021-02-27 23:27:22
    在有向图G中,每条边的长度均为1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1.路径上的所有点的出边所指向的点都直接或间接与终点连通。 2.在满足条件1的情况下使路径最短。 ...
  • SQL语法——left join on 多条件

    万次阅读 多人点赞 2018-03-30 22:22:30
    left join on +多条件与where区别 重点 先匹配,再筛选where条件。 本文将通过几个例子说明两者的差别。 表1:product id amount 1 100 2 200 3 300 4 400 表2:product_details...
  • python 实现文件查找和某些项输出 本文是基于给定一文件(students.txt),查找其中GPA分数最高的 输出,同时输出其对应的姓名和学分 一.... 首先需要打开文件,读取文件的每一行,将姓名,学分,GPA值分别存到三个...
  • LeetCode题解:寻找峰值

    千次阅读 多人点赞 2020-12-15 09:48:40
    数组可能包含个峰值,在这种情况下,返回任何一个峰值所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞。 输入: nums = [1,2,1,3,5,6,4] 输出: 1 或 5 解释: 你的函数可以返回索引 1,其峰值元素为 2;或者...
  • 多重对应分析在超过两个以上定类变量时有时候非常有效,当然首先我们要理解并思考,如果只有三个或有限的几个变量完全可以通过数据变换和交互表变量重组可以转换成两个定类变量,这时候就可以用简单对应分析了。...
  • 数据结构知识整理

    万次阅读 多人点赞 2018-07-30 18:50:47
    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学中是指所有能...
  • 数据挖掘面试 150 道题(附答案)

    万次阅读 多人点赞 2019-09-21 13:50:38
    1. 某超市研究销售纪录数据后发现,买啤酒的人很大概率也会购买尿布,这种属于数据挖掘的哪类问题?(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 2. 以下两种描述分别对应哪两种对分类算法的评价标准...
  • “自动泊车、公路巡航控制和自动紧急制动等自动驾驶汽车功能在很大程度上是依靠传感器来实现的。...现在路面上的很汽车,甚至是展厅内的很新车,内部都配备有基于摄像头、雷达、超声波或LIDAR...
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题

    万次阅读 多人点赞 2012-03-22 12:51:07
    教你如何迅速秒杀掉:99%的海量数据处理面试题作者:July出处:结构之法算法之道blog前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢...
  • 数据挖掘——数据预处理

    千次阅读 2018-07-24 21:27:14
    一、背景 原始数据存在的几个问题:不一致;重复;含噪声;维度高。 1.1 数据挖掘中使用的数据的原则 ...尽可能赋予属性名和属性值明确的含义;... 数据集成:将数据源中的数据合并,并存放到...
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...
  • 简介 现在,您的计算机有四个 CPU 核;...本文是两篇系列文章的第一篇,讨论如何在线程环境中设计并发数据结构。对于本文,我们使用 POSIX Threads 库(也称为 Pthreads;见 参考资料 中的链接),但是也可以使用
  • 数据挖掘与数据建模步骤

    千次阅读 2014-11-14 15:20:24
    数据挖掘是利用业务知识从数据中发现和解释知识(或称为模式)的过程,这种知识是以自然或者人工形式创造的新知识。...20世纪90年代晚期发展的CRISP-DM,逐渐成为数据挖掘过程的一种标准化过程,被越来越数据挖掘实
  • 为什么要学数据结构?

    万次阅读 多人点赞 2019-11-19 09:45:23
    一、前言 在可视化化程序设计的今天,借助于...1) 能够熟练地选择和设计各种数据结构和算法 2) 至少要能够熟练地掌握一门程序设计语言 3) 熟知所涉及的相关应用领域的知识 其中,后两个条件比较容易实现,而第一个...
  • 最强数据集集合:50个最佳机器学习公共数据集   https://mp.weixin.qq.com/s/_A71fTgwSyaW5XTAySIGOA   原作 mlmemoirs 郭一璞 编译 量子位 报道 | 公众号 QbitAI 外国自媒体mlmemoirs根据github、福布斯、...
  • 文章目录 1. 引言 2. 传感器标定 2.1 标定场地 ... 数据层融合 3.1 融合的传统方法 3.2 深度学习方法 4. 任务层融合 4.1 传统之障碍物检测跟踪 4.2 传统之传感器定位 4.3 深度学习之障...
  • 案例上手 Python 数据可视化

    万次阅读 多人点赞 2019-02-27 23:30:05
    课程亮点 ...数据可视化是数据分析和机器学习的重要环节,比如数据清洗、特征工程、机器学习、数据分析(特别是报告)、评估等环节都会用到“数据可视化”技术。 数据可视化同时还广泛存在于各...
  • 数据挖掘

    千次阅读 多人点赞 2019-04-16 16:26:36
    数据挖掘其实是一种深层次的数据分析方法。数据挖掘可以描述为:按企业既定业务目标,对大量的企业数据进行探索和分析,揭示隐藏的、未知的或验证已知的规律性,并进一步将其模型化的先进有效的方法。 应用的技术...
  • 数据分析之数据预处理、分析建模、可视化

    万次阅读 多人点赞 2020-08-08 15:03:21
    数据预处理:数据清洗、数据集成、数据规约、数据变换; 数据分析模型:对比分析、漏斗分析、留存分析、A/B测试、用户行为路径分析、用户分群、用户画像分析等; 数据分析方法:描述统计、假设检验、信度分析、相关...
  • 数据挖掘报告

    万次阅读 热门讨论 2010-04-10 10:03:00
    研究方向前沿读书报告数据挖掘技术的算法与应用 目录第一章 数据仓库... 51.1 概论... 51.2 数据仓库体系结构... 61.3 数据仓库规划、设计与开发... 71.3.1 确定范围... 71.3.2 环境评估... 71.3.3 分析... 71.3.4 ...
  • 数据挖掘-数据预处理模块

    千次阅读 2016-05-02 00:28:20
     在数据挖掘中,海量的原始数据中存在着大量的不完整(有缺失值)、不一致、有异常的数据,严重影响到数据挖掘建模的执行效率,甚至可能导致挖掘结果的偏差,所以进行数据清洗显得尤为重要,数据清洗完成后接着进行...
  • 随着技术的发展,IT逐渐面临越来越的挑战,尤其是数据治理方面。而九州通医药集团在IT建设方面不畏艰险,自主研发ERP系统、物流系统,在解决企业自身问题的同时还创新投入商业化,为同行业提供服务,树立标杆形象...
  • 算法系列之二十一:实验数据与曲线拟合

    万次阅读 多人点赞 2013-10-16 22:17:15
    科学和工程遇到的很问题,往往只能通过诸如采样、实验等方法获得若干离散的数据,根据这些数据,如果能够找到一个连续的函数(也就是曲线)或者更加密集的离散方程,使得实验数据与方程的曲线能够在最大程度上近似...
  • 看这玩意复习你还会挂科?《数据结构篇》

    万次阅读 多人点赞 2020-01-14 15:12:42
    3.数据数据元素、数据对象的概念 数据(data):对客观事物的符号表示,含义很广,指数、图像、声音、文本等一切计算机可以处理的事物。 数据元素(data element):组成数据的基本单位。 数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 243,679
精华内容 97,471
关键字:

多条件寻找数据