SakuraTears的博客

越努力越幸运

和朋友的一次关于数组问题讨论

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 6.1k 阅读时长 ≈ 6 分钟

前言

前两天下班和一朋友一起，被问到如下问题：如何移除一个数组中某些符合条件（或不符合条件）的元素形成新的数组，要求数组长度也应该变化（这是我后面加的）。

这两天研究下了这个问题，感觉比较有意思，也从中学到了一些其它该注意的东西。

特此来分享一下。

如有问题欢迎批评指正。

正文

对于上面的问题，最简单也最应该想到的一个应该是借助List这个工具类。

是的，我写下大致如下代码：

（1）使用List帮助类实现,借助remove方法

优点：代码简洁，便于理解，不易出错

缺点：数组和List转换耗时，效率不算太高，使用List remove方法时应注意线程安全问题，如果是基本数据类型，需要转换为包装类，拆箱装箱也是影响效率的一个因素。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 过滤形成新的数组（转换为List，通过List里面remove(安全的)移除元素）
 * @param sourceArray
 * @param predicate
 * @param type
 * @param <T>
 * @return
 */
public static <T> T[] getArray1(T[] sourceArray,Predicate<T> predicate,Class<T> type){
    //asList生成的是一个List的内部类，无法调用add remove delete方法会抛出异常
    List<T> sourceList= new ArrayList<>(Arrays.asList(sourceArray));
    //使用Java8 函数式接口，移除不符合条件的元素
    sourceList.removeIf(predicate);
    return sourceList.toArray((T[]) Array.newInstance(type,0));
}

注： Predicatepredicate 相当于一个判断条件（lambda表达式，Java8语法），具体的问题也可以写明，就是那种for list 在加上 if 条件判断的，这儿我就不啰嗦了。Java 8里面对于集合类，新增了 removeIf方法，我们可以看下它，其实就是我们上面说的那个。

upload successful

关于这种写法，有需要注意的几点：

  1. for-each，for, iterator 这三种对于List的循环，for，iterator是可以遍历并进行remove操作的，但是for-each是不可以的。有兴趣的可以研究研究，这不是我们的重点。

  2. 看到我上面使用的泛型T，其实使用Object[]也是可以的，要注意一个问题，泛型T是不能包含int,long等基本数据类型的，使用的话只能转化为它们的包装类。

  3. Object[]是没有限制的，但是Object[]转换为Integer[]或者int[]或者其他不能直接转换，如下写法是错误的，会出现问题。

    1
    2
    Object [] objects=new Object[10];
    Integer [] a=(Integer[])objects;

    正确的转换方法应该循环里面的元素，并对它们强转添加进数组；或者使用下面的方法。

    1
    2
    3
    Object [] objects=new Object[10];
    //Integer [] a=(Integer[])objects;
    Integer [] a=(Integer[])Array.newInstance(Integer.class,objects.length);

  4. 当我们把数组转换成List的时候，为了不想循环遍历添加，可能会想到使用Arrays.asList(T t) 这个方法，这个方法生成的List是一个Arrays里面的一个内部类ArrayList。

upload successful

看下这个内部类你会发现它没有对remove、add等方法的实现，也就是继承自AbstractList。

1
2
3
public E remove(int index) {
	throw new UnsupportedOperationException();
}

也就是执行它们时会抛出异常，如果想使用remove方法，应该把它转为具体实现，如ArrayList。

1
List<T> sourceList= new ArrayList<>(Arrays.asList(sourceArray));

为什么它要使用内部类处理这个方法呢？也是比较有趣的，我这儿还没做深入研究，有时间研究下。

(2)使用两次循环实现。

原理是第一次数组循环查找符合条件（或不符合条件）的个数count，后面在创建一个指定长度（原数组总长度-count）的数组，然后在遍历循环一遍原数组，将符合条件（或不符合条件）的元素添加进新的数组。

优点：简单直接，易于理解，基本数据类型数组的处理应该比List方法有优势。

缺点：两次循环应该比较耗时，对于长Array应该显现的明显。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 过滤形成新的数组（两次循环查找符合条件的，移动过去）
 * @param sourceArray
 * @param predicate
 * @param type
 * @param <T>
 * @return
 */
public static <T> T[] getArray2(T[] sourceArray,Predicate<T> predicate,Class<T> type){
    int count=0;
    for (T t:sourceArray){
        if(predicate.test(t)){
            count++;
        }
    }
    //都不符合条件
    if(count==0){
        return Arrays.copyOf(sourceArray,sourceArray.length);
    }
    //都符合条件
    if(count==sourceArray.length){
        return (T[]) Array.newInstance(type,0);
    }

    T [] targetArray=(T[]) Array.newInstance(type,sourceArray.length-count);
    int index=0;
    for (T t:sourceArray){
        if(!predicate.test(t)){
           targetArray[index]=t;
           index++;
        }
    }
    return targetArray;
}

注意：还有一种情况，如果过滤的数据（符合条件或者不符合条件的）出现次数较低，我们是不是可以考虑一次拿出一整段进行处理。当然，如果频率较高，比如在一堆自然数中取偶数，明显奇数偶数出现频率相近，都为50%，那么我们可能用上面这种方法效率也很好。

(3)预先设置等长数组，而后截取得到目标数组

对比上一种方法，这是一种空间换时间的做法。

开始时创建一个和原数组相同大小的数组，遍历后把元素放进去，最后将数组截短。
这种方法仅仅循环一次。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 对比第二种方法，这属于空间换时间的做法
 * @param sourceArray
 * @param predicate
 * @param type
 * @param <T>
 * @return
 */
public static <T> T[] getArray3(T[] sourceArray,Predicate<T> predicate,Class<T> type){
    //直接创建一个空的一样长的数组
    T[] tempArray=(T[]) Array.newInstance(type,sourceArray.length);
    //不符合条件的数量
    int count=0;
    for (T t:sourceArray){
        //拿到不符合过滤条件的，一个个赋值给新数组
        if(!predicate.test(t)){
            tempArray[count]=t;
            count++;
        }
    }
    //最后这个数组长度<=原数组长度
    //特殊处理下
    if(count==0){
        return (T[]) Array.newInstance(type,0);
    }
    return Arrays.copyOf(tempArray,count);
}

(4)借助List的toArray方法

借助List实现循环一次把符合条件的放到里面，再把List强转成数组。也是不错的实现方法。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 借助list拿到符合条件的，在强转成数组
 * @param sourceArray
 * @param predicate
 * @param type
 * @param <T>
 * @return
 */
public static <T> T[] getArray4(T[] sourceArray,Predicate<T> predicate,Class<T> type){
    //记录符合条件的元素下标
    List<T> targetList=new ArrayList<>();
    for (T t:sourceArray){
        if(!predicate.test(t)){
            targetList.add(t);
        }
    }
    return targetList.toArray((T[]) Array.newInstance(type,0));
}

无论上面哪种方法，其底层都使用了System.arraycopy方法。

1
2
3
4
5
6
7
8
9
10
/**
* 数组复制核心方法
* @param src 原数组
* @param srcPos 原数组要复制的起始位置下标
* @param dest 目标数组
* @param destPos 目标数组的起始位置下标
* @param length 要复制的长度
* @return
*/
public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

(5)Java8串行处理方式

Java8中使用Stream操作集合工具类来对其进行处理。分为串行和并行两种方式。先来看看串行。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Java8 串行流语法(收集符合条件的)
 * @param sourceArray
 * @param predicate
 * @param type
 * @param <T>
 * @return
 */
public static <T> T[] getArray5(T[] sourceArray,Predicate<T> predicate,Class<T> type){
    return Arrays.stream(sourceArray).sequential().
            filter(predicate).
            collect(Collectors.toList()).
            toArray((T[]) Array.newInstance(type,0));
}

其底层也是元素的循环遍历。

（6）Java8并行处理方式

我们应该知道，无论方法怎样，至少应该遍历数组一次以判断该元素是否符合条件。当数据量较大时，这儿会成为方法运行时间的瓶颈，由于List家族中ArrayList是有序的，我们可以使用多线程对它进行分割，每段进行遍历筛选结果，最后再把结果合起来。

并行流就是利用分支/合并框架实现的，使用了多线程。当数组数据量较大时效率是明显的。

Java8的相关API已经封装好，我们可以直接使用。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Java8 并行流语法(收集符合条件的)
 * @param sourceArray
 * @param predicate
 * @param type
 * @param <T>
 * @return
 */
public static <T> T[] getArray6(T[] sourceArray,Predicate<T> predicate,Class<T> type){
    return Arrays.stream(sourceArray).parallel().
            filter(predicate).
            collect(Collectors.toList()).
            toArray((T[]) Array.newInstance(type,0));
}

(7)自己动手，丰衣足食

我们其实是可以借助多线程自己实现一个相似工具类的。

可以使用分支/合并框架自己实现一个多线程的处理。

关于这一块，我有一篇文章 一道Java试题引发的思考
中有具体例子及测试。

大家可以看下，数据量大的情况下并行效率还是比较明显的。

我这儿对这个例子就不在验证了。

注意：使用并行流（或者说多线程）要注意的点。

首先是数据量，数据量的主要意义就在于单线程处理的耗时（处理数据的时间）已经超过了多线程耗时（数据处理时间+拆分数据时间+合并结果时间），这一点是比较难把控的。其次一点是要确定这些数据可以使用多线程处理，不会产生意外的情况，比如我们这个问题，我想删除两个数相差1的所有元素，剩下的元素生成一个新的数组，多线程显然不易解决这种问题，或者解决起来较复杂。

测试

测试的话今天就省了，（3）、（4）、（5）都是不错的写法，（6）话具体问题具体分析，（7）的话有想法的可以试试，（1），（2）不推荐。

因为数据量大小，数据类型都对方法有些影响。

比如较短的原数组，基本数据类型，（3）方法效率很快的，对比（4）、（5）是没有数据拆箱操作的。换成长数组，引用数据类型，（6）可能效率就高了。

结语

开始写这篇文章的时候脑子不好使，根本没想到Java8的Stream，失误。我甚至一开始想的都是些可能不安全（（1）方法），或者比较繁琐（（2）方法）的方法，过了一天晾了晾脑子就好使多了。

在处理时，因为数组底层操作都是基于System.arraycopy嘛，我想到是不是循环一次记录符合条件（不符合条件）的元素下标（可用List记录），然后建立一个目标数组，使用System.arraycopy一段一段的将数据copy进去。

无奈才疏学浅，想了半天使用System.arraycopy时的两个起始位置，copy长度始终弄错了，仔细想了下，估计这种方法效率也不怎么高。

哈哈，于是就没写。

大家有什么好的、耳目一新的方法也可以说出来交流交流。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

您的支持就是我创作的动力！

欢迎关注我的其它发布渠道