Fork me on GitHub

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

前言

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

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

特此来分享一下。

如有问题欢迎批评指正。

正文

对于上面的问题,最简单也最应该想到的一个应该是借助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));
}

注: Predicate predicate 相当于一个判断条件(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);

  1. 当我们把数组转换成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长度始终弄错了,仔细想了下,估计这种方法效率也不怎么高。

哈哈,于是就没写。

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




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

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%