数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题

首先来测试一下

import java.util.ArrayList;

public class Main {

    private static double testMap(Map map, String filename){

        long startTime = System.nanoTime();

        System.out.println(filename);
        ArrayList words = new ArrayList<>();
        if(FileOperation.readFile(filename, words)) {
            System.out.println("Total words: " + words.size());

            for (String word : words){
                if(map.contains(word))
                    map.set(word, map.get(word) + 1);
                else
                    map.add(word, 1);
            }

            System.out.println("Total different words: " + map.getSize());
            System.out.println("Frequency of PRIDE: " + map.get("pride"));
            System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        String filename = "pride-and-prejudice.txt";

        BSTMap bstMap = new BSTMap<>();
        double time1 = testMap(bstMap, filename);
        System.out.println("BST Map: " + time1 + " s");

        System.out.println();

        LinkedListMap linkedListMap = new LinkedListMap<>();
        double time2 = testMap(linkedListMap, filename);
        System.out.println("Linked List Map: " + time2 + " s");

    }
}

现在我们就可以运行一下我们的程序,对于二分搜素树BSTMap很快就得出了结果,而对于LinkedListMap则等了很长时间才出结果

数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题
对于这个十几万的数据,基于二分搜索树的映射用了0.74秒。
数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题
而对于链表的映射用了32秒

映射的时间复杂度总结

数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题
前面基于代码的方式我们直观的看到了基于二分搜素树实现的映射和基于链表的映射他们的时间复杂度的差距。

有序映射和无序映射

  • 有序映射中的键具有顺序性<--基于搜索树的实现
  • 无序映射中的键没有顺序性<--基于哈希表的实现

集合和映射的关系

这一章我们学习了集合和映射两种相对比较高层的数据结构,在具体实现这两种数据结构的时候,都可以既使用链表,又使用二分搜素树。

实现过程中,其实有很多相同之处,甚至可以理解为:对于映射来说,本身就是一个集合
数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题
分享到:
赞(0)

评论抢沙发

评论前必须登录!