美文网首页
joda-collection 之 Grid解析

joda-collection 之 Grid解析

作者: 阿骨打金 | 来源:发表于2017-03-30 10:34 被阅读22次

    joda-collection官网说明了是提供jdk和guava之外的collection操作,所以提供了Grid操作;
    Grid顾名思义就是网格的意思,也就是有个(x,y)坐标确定一个元素;

    如何引入

    现在基本都是采用maven构建方式,在需要的项目pom中添加依赖:

    <dependency>
      <groupId>org.joda</groupId>
      <artifactId>joda-collect</artifactId>
      <version>0.7</version>
    </dependency>
    

    源码解析

    继承关系

    • Grid定义为接口,AbstractGrid为实现该接口的抽象类
    • DenseGridImmutableGrid(抽象类),SparseGrid均实现了AbstractGrid抽象类
    • DenseImmutableGridEmptyGridSingletonGridSparseImmutableGrid实现了Immutable抽象类
    • 其中AbstractGridDenseImmutableGridEmptyGridSingletonGridSparseImmutableGrid为包访问权限

    看代码

    ImmutableGridcopyOf方法

    该方法为从grid获取到具有immutablegrid

    public static <R> ImmutableGrid<R> copyOf(Grid<R> grid) {
        if (grid == null) {
            throw new IllegalArgumentException("Grid must not be null");
        }
        if (grid instanceof ImmutableGrid) {
            return (ImmutableGrid<R>) grid;
        }
        validateCounts(grid.rowCount(), grid.columnCount
        if (grid.size() == 0) {
            return new EmptyGrid<R>(grid.rowCount(), grid.columnCount());
        }
        if (grid.size() == 1) {
            Cell<R> cell = grid.cells().iterator().next();
            return new SingletonGrid<R>(grid.rowCount(), grid.columnCount(), cell);
        }
        if (grid.size() >= (grid.rowCount() * grid.columnCount() / 2)) {
            return DenseImmutableGrid.create(grid);
        }
        return new SparseImmutableGrid<R>(grid);
    }
    
    • 如果grid为空的,那么返回EmptyGrid;其实返回这个用处不大,本来就是个immutable的,不能往里插数据
    • 如果grid所持有的对象个数为1,那么返回的是SingletonGrid;
    • 如果grid所持有的对象个数大于等于grid总大小的一般,就用DenseImmutableGrid(非稀疏的不可变grid),否则返回的是SparseImmutableGrid(稀疏的不可变grid)

    关于稀疏(dense)grid和非稀疏(sparse)grid

    两者的区别在于存储的方式不同:dense采用的的数组的方式存储信息,而sparse采用SortedSet<Cell<V>>来作为存储结构;下边先介绍Cell是什么玩意

    Cell接口是Grid的一个内部接口,MutableCellImmutableCell采用相同的存储结构且都实现AbstractCell抽象类,存储结构为row,column,value

    接下来看看SparseGrid的实现
        private final int rowCount;
        private final int columnCount;
        private final SortedSet<Cell<V>> cells;
        public static <R> SparseGrid<R> create(int rowCount, int columnCount) {
            return new SparseGrid<R>(rowCount, columnCount, new TreeSet<Cell<R>>(AbstractCell.<R>comparator()));
        }
    

    首先,通过SortedSet来存储,在creat方法中可以看到,实际采用的是SortedSet的实现类TreeSet来存储;然后存储总行数和总列数;为什么不直接声明为TreeSet来存储呢,主要是为了扩展性考虑,面向接口编程嘛;对于稀疏的采用Set来存储而不是数组,可以节省存储空间

    AbstractCell实现了Comparator接口,利用row和column来进行排序;

    cell(int row, int column)方法来获取指定的cell

    @Override
    public Cell<V> cell(int row, int column) {
        if (exists(row, column)) {
            SortedSet<Cell<V>> tail = cells.tailSet(finder(row, column));
            if (tail.size() > 0) {
                Cell<V> cell = tail.first();
                if (cell.getRow() == row && cell.getColumn() == column) {
                    return cell;
                }
            }
        }
        return null;
    }
    
    @Override
    public boolean exists(int row, int column) {
        return row >= 0 && row < rowCount() && column >= 0 && column < columnCount();
    }
    

    通过SortedSet来查询具体的cell;

    再来看看DenseGrid
    private final int rowCount;
    private final int columnCount;
    private int size;
    private final V[] values;
    

    从代码里看出,采用的是数组的存储方式,因为当数据比较稠密的时候,浪费的空间的少量的,这种方式相比较SparseGrid,效率会高,实现比较简单;

    public static <V> DenseGrid<V> create(int rowCount, int columnCount) {
        return new DenseGrid<V>(rowCount, columnCount);
    }
    private DenseGrid(int rowCount, int columnCount) {
        validateCounts(rowCount, columnCount);
        this.rowCount = rowCount;
        this.columnCount = columnCount;
        this.values = (V[]) new Object[rowCount * columnCount];
    }
    

    代码里可以看出来,最开始构造方法就已经分配了最大容量的数组;

    @Override
    public V get(int row, int column) {
        if (exists(row, column)) {
            return values[row * columnCount + column];
        }
        return null;
    }
    
    @Override
    public Cell<V> cell(int row, int column) {
        V value = get(row, column);
        return (value != null ? ImmutableCell.of(row, column, value) : null);
    }
    

    从get的代码可以看出来,就是简单的数组下标定位,效率非常高;其他一些需要get的操作都是通过数组下标的方式来做的,例如public List<V> column(int column)public List<V> row(int row)等方法;

    总结下,稀疏Grid和非稀疏Grid最大的区别就是以时间换空间还是以空间换时间的问题;通过不同的存储结构来实现;


    总结

    • 从Grid的源码分析来看,执行效率还是不错的
    • Grid的使用场景还是有一些的,比如一些业务场景中的需要多个map来实现的业务逻辑,可以考虑Grid的实现方式,看看哪种实现方式更方便及效率更高;

    相关文章

      网友评论

          本文标题:joda-collection 之 Grid解析

          本文链接:https://www.haomeiwen.com/subject/swuuottx.html