• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    • 查看作者
    • 《算法第四版》课后练习题1.1.38答案

      习题1.1.38

      二分查找与暴力查找。根据1.1.10.4节给出的暴力查找法编写一个程序 BruteForceSearch,在你的计算机上比较它和 BinarySearch处理largeW.txt 和 largeT.txt所需的时间。

      要点分析

      一.  暴力查找法

      1.1.10.4节(课本第29页底部)

      public static int rank(int key, int[] a) {
          for (int i = 0; i < a.length; i++)
              if (a[i] == key) return i;
          return -1;
      }

      二.  BinarySearch

      关于BinarySearch类实现在课本第5页中部,如果您没带课本

      《算法第四版》课后练习题1.1.21-1.1.25答案 一文中的第1.1.22题中给出了BinarySearch类的具体代码和使用范例。

      其实有关二分查找,我们在后面的学习中会专门学习,所以这里只简单提一下,首先,二分查找的速度非常之快,但是也有缺点,就是该算法满足以下两个条件:

      • 必须采用顺序存储结构
      • 必须按关键字大小有序排列[1]

      所以我们在使用的过程中,可以用Arrays.sort();方法先将数组排序

      三.  基于文件的输入输出

      因为要用到两个文件中数据来测试两个方法的执行效率,所以我们会用到基于文件的输入输出这个知识点,在课本的第25页有详细的讲解,下文的知识要点中,我们也会讲解如何基于文件输入输出。

      四.  数据下载

      laegeW.txt 和 largeT.txt
      c8mc

      五.  In类使用

      我们如何在程序中调用上文中的laegeW.txt 和 largeT.txt 这两个文件的中的数据呢,在课本的第5页,BinarySearch中曾经给出过使用方法,采用的是课本标准库中的In和Out两个类(课本第25页),这里再以一个具体实例,解释一下如何使用该类:

      首先,我们在E盘Test文件夹中创建一个test.txt的文件,并编辑1 2 3 4 5 6 7 8 这几个数字保存(中间用空格或者回车隔开)

      import edu.princeton.cs.algs4.In;
      
      public class Test3 {
          public static void main(String[] args) {
              int[] a = In.readInts(args[0]);
              //注意这里的In是采用基于文件的输入,详情可以查看《算法》第25页
              //args[0]通过命令行传入一个txt文本路径,比如E:\Test\test.txt
              //这里Test.txt里的内容为1 2 3 4 5 6 7 8 9,此时已经存入a这个数组中
              for (int i = 0; i < a.length; i++) {
                  System.out.print(a[i] + " ");
              }
      
          }
      }
      
      输出:
      1 2 3 4 5 6 7 8 9

      六.  统计时间

      如何查看系统处理这个两个文件需要的时间呢?我们一般采用下面的方法进行检验:

      public static void main(String[] args) {
          long startTime = System.currentTimeMillis();//获取当前的时间
          long  sum = 0;
          for (int i = 1; i <= 10000000; i++) {
                sum += i;
          }
          System.out.println(sum);
          long endTime = System.currentTimeMillis();
          System.out.println("该程序一共运行了:"+(endTime-startTime)+"ms");
      
      }
      
      输出:
      50000005000000
      该程序一共运行了:7ms

      参考答案

      首先我们来看在largeW.txt文件中,100万个数据,BruteForceSearch的运行时间为5ms

      import edu.princeton.cs.algs4.In;
      
      import java.util.Arrays;
      
      public class Thirty_eight {
          /**
           * @description: 暴力查找法
           * @param: key 要查找的元素
           * @param: a 在a这个数组中查找
           * @return: 查找的元素所以
           */
          public static int rank(int key, int[] a) {
              for (int i = 0; i < a.length; i++)
                  if (a[i] == key) return i;
              return -1;
          }
      
          public static void main(String[] args) {
              int[] a = In.readInts(args[0]);
              long time1 = System.currentTimeMillis();//获取当前的时间
              int b = rank(122922297, a);
              //为了突出比较结果,我在两个文档的最后面添加了一个数据中最大的数字122922297
              // 作为要查找的元素,索引为100,0000
              if (b != -1)
                  System.out.println("您查找的元素索引为" + b);
              else
                  System.out.println("您查找的元素不存在");
              long time2 = System.currentTimeMillis();
              System.out.println("该程序一共运行了:" + (time2 - time1) + "ms");
          }
      }
      
      输出:
      您查找的元素索引为1000000
      该程序一共运行了:5ms

      而BinarySearch方法为0ms:

      import edu.princeton.cs.algs4.In;
      
      import java.util.Arrays;
      
      public class Thirty_eight {
      
          /**
           * @description: 二分查找(BinarySearch)方法,课本第5页
           * @param: a 要查找的数组
           * @param: key 要查找的元素
           * @return: 要查找的元素的索引
           */
          public static int rank(int[] a, int key) {
              int lo = 0;
              int hi = a.length - 1;
              while (lo <= hi) {
                  int mid = (lo + hi) / 2;
                  if (key < a[mid]) {
                      hi = mid - 1;
                  } else if (key > a[mid]) {
                      lo = mid + 1;
                  } else {
                      return mid;
                  }
              }
              return -1;
          }
      
          public static void main(String[] args) {
              int[] a = In.readInts(args[0]);
              Arrays.sort(a);
              long time1 = System.currentTimeMillis();//获取当前的时间
              int b = rank(a,122922297);
      
              //为了突出比较结果,我在两个文档的最后面添加了一个数据中最大的数字122922297
              // 作为要查找的元素,索引为100,0000
              if (b != -1)
                  System.out.println("您查找的元素索引为" + b);
              else
                  System.out.println("您查找的元素不存在");
              long time2 = System.currentTimeMillis();
              System.out.println("该程序一共运行了:" + (time2 - time1) + "ms");
          }
      }
      您查找的元素索引为1000000
      该程序一共运行了:0ms

      接下来是 largeT.txt 文件中,1000万个数据,BruteForceSearch的运行时间为8ms

      import edu.princeton.cs.algs4.In;
      
      import java.util.Arrays;
      
      public class Thirty_eight {
          /**
           * @description: 暴力查找法
           * @param: key 要查找的元素
           * @param: a 在a这个数组中查找
           * @return: 查找的元素所以
           */
          public static int rank(int key, int[] a) {
              for (int i = 0; i < a.length; i++)
                  if (a[i] == key) return i;
              return -1;
          }
      
          public static void main(String[] args) {
              int[] a = In.readInts(args[0]);
              long time1 = System.currentTimeMillis();//获取当前的时间
              int b = rank(122922297, a);
              //为了突出比较结果,我在两个文档的最后面添加了一个数据中最大的数字122922297
              // 作为要查找的元素,索引为1000,0000
              if (b != -1)
                  System.out.println("您查找的元素索引为" + b);
              else
                  System.out.println("您查找的元素不存在");
              long time2 = System.currentTimeMillis();
              System.out.println("该程序一共运行了:" + (time2 - time1) + "ms");
          }
      }
      输出:
      您查找的元素索引为10000000
      该程序一共运行了:7ms

      再来看看BinarySearch方法依旧是0ms:

      import edu.princeton.cs.algs4.In;
      
      import java.util.Arrays;
      
      public class Thirty_eight {
      
          /**
           * @description: 二分查找(BinarySearch)方法,课本第5页
           * @param: a 要查找的数组
           * @param: key 要查找的元素
           * @return: 要查找的元素的索引
           */
          public static int rank(int[] a, int key) {
              int lo = 0;
              int hi = a.length - 1;
              while (lo <= hi) {
                  int mid = (lo + hi) / 2;
                  if (key < a[mid]) {
                      hi = mid - 1;
                  } else if (key > a[mid]) {
                      lo = mid + 1;
                  } else {
                      return mid;
                  }
              }
              return -1;
          }
      
          public static void main(String[] args) {
              int[] a = In.readInts(args[0]);
              Arrays.sort(a);
              long time1 = System.currentTimeMillis();//获取当前的时间
              int b = rank(a,122922297);
      
              //为了突出比较结果,我在两个文档的最后面添加了一个数据中最大的数字122922297
              // 作为要查找的元素,索引为1000,0000
              if (b != -1)
                  System.out.println("您查找的元素索引为" + b);
              else
                  System.out.println("您查找的元素不存在");
              long time2 = System.currentTimeMillis();
              System.out.println("该程序一共运行了:" + (time2 - time1) + "ms");
          }
      }
      您查找的元素索引为10000000
      该程序一共运行了:0ms

      可以看到,BinarySearch方法再数据量越大的文件中,优势突出越明显。

      (注意:电脑配置不同,这里程序的运行结果是不一样的。)

      参考资料

      [1] 百度百科:二分查找

    • 0
    • 0
    • 0
    • 977
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: