• 中文
    • English
  • 注册
  • 查看作者
  • 《算法第四版》课后练习题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
  • 2
  • 0
  • 2.7k
  • 请登录之后再进行评论

    登录
  • 0
    XLY.1
    还有把txt文件导入JAVA,是按照你说的那种在E盘创建文件吗?
  • 1
    XLY.1
    大哥这个数据下载没有网盘密码呀?
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

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

    单栏布局 侧栏位置: