编程Java

Java核心技术1-算法

字数统计: 3.1k字   |   阅读时长: 13分
,

摘要: 本文是《Java核心技术 10th》中关于泛型算法的要点总结。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

泛型算法基础

泛型集合接口有一个很大的优点：算法只需要实现一次。

例如：求集合中最大元素的算法。我们并不想实现一系列方法：j

1
2
3
static <T extends Comparable> T max(T[] a)
static <T extends Comparable> T max(ArrayList<T> v)
static <T extends Comparable> T max(LinkedList<T> l)

为了高效地使用这个算法所需要的最小集合接口。采用 get 和 set 方法进行随机访问要比直接迭代层次高。

下面的代码将 max 方法实现为能够接收任何实现了 Collection 接口的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static <T extends Comparable> T max(Collection<T> c) {
    if(c.isEmpty()) {
        throw new NoSuchElementException();
    }
    Iterator<T> iter = c.iterator();
    T largest = iter.next();
    whlie(iter.hasNext()) {
        T next = iter.next();
        if(largest.compareTo(next) < 0) {
            largest = next;
        }
    }
    return largest;
}

准的 C++ 类库已经有几十种非常有用的算法，每个算法都是在泛型集合上操作的。Java 类库中的算法没有如此丰富，但是，也包含了基本的排序、二分查找等实用算法。

排序与打乱

排序

Collections 类中的 sort 方法对实现了 List 接口的集合进行排序。

1
2
List<String> staff = new LinkedList<>();
Collections.sort(staff);

该方法假定列表元素实现了 Comparable 接口。此外也可以用 List 接口的 sort 方法并传入一个 Comparable 对象。例如：

1
staff.sort(Comparator.comparingDouble(Employee::getSalary));

倒序排序的写法:

1
staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed());

对于列表，可以使用归并排序对进行高效的排序。然而，Java 程序设计语言并不是这样实现的。而是直接将所有元素转入一个数组，对数组进行排序，然后，再将排序后的序列复制回列表。

因为集合不需要实现所有的“可选”方法，因此，所有接受集合参数的方法必须描述什么时候可以安全地将集合传递给算法。传入的列表必须是可修改的，但不必要是可以改变大小的。

  • 如果列表支持 set 方法，则是可修改的。
  • 如果列表支持 add 和 remove 方法，则是可改变大小的。

打乱

Collections 类中的 shuffle。

1
2
ArrayList<Card> cards = ...;
Collections.shuffle(card);

如果提供的列表没有实现 RandomAccess 接口，shuffle 方法将元素复制到数组中，然后打乱数组元素的顺序，最后再将打乱顺序后的元素复制回列表。

二分查找

Collections 类的 binarySearch 方法。提供的集合要实现 List 接口。如果集合没有采用 Comparable 接口的 compareTo 方法进行排序，就还要提供一个比较器对象。

1
2
i = Collections.binarySearch(e, element)
i = Collections.binarySearch(e, element, comparator)

如果 binarySearch 方法返回的数值大于等于 0，则表示匹配对象的索引。c.get(i)　即为所查找的 element。

如果返回值 i 小于 0，则可以利用返回值计算应该将 element 插入到集合哪个位置: insertionPoint = -i - 1;。

注意：只有采用随机访问，二分查找才有意义。

简单算法

有一些简单方法，可以很容易通过循环实现。但是使用这些算法会使得代码更清晰。

java.util.Collections API 总结

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
35
36
// 返回集合中最小的或最大的元素（为清楚起见，参数的边界被简化了）。
static <T extends Comparable<? super T>> Tmin(Collection<T> elements)
static <T extends Comparable<? super T>> Tmax(Collection<T> elements)
static <T> min(Collection<T> elements, Comparator<?super T> c)
static <T> max(Collection<T> elements, Comparator<?super T> c)

// 将原列表中的所有元素复制到目标列表的相应位置上。目标列表的长度至少与原列表一样。
static <T> void copy(List<? super T> to, List<T> from)

// 将列表中所有位置设置为相同的值。
static <T> void fill(List<? super T> l, T value)

// 将所有的值添加到集合中。如果集合改变了，则返回true。
static <T> boolean addAll(Collection<? super T> c, T... values) 

// 用newValue取代所有值为oldValue的元素。
static <T> boolean replaceAll(List<T> l, T oldValue, TnewValue) 

// 返回l中第一个或最后一个等于s子列表的索引。如果l中不存在等于s的子列表，则返回-1。例如，1为[s, t,a, r] , s为[t, a, r]，两个方法都将返回索引1。
static int indexOfSubList(List<? > l, List<? > s) 
static int lastIndexOfSubList(List<? > l, List<? > s) 

// 交换给定偏移量的两个元素。
static void swap(List<? > l, int i, int j) 

// 逆置列表中元素的顺序。例如，逆置列表[t, a, r]后将得到列表[r, a, t]。这个方法的时间复杂度为O (n), n为列表的长度。
static void reverse(List<? > l)

// 旋转列表中的元素，将索引i的条目移动到位置(i + d)% l.size()。例如，将列表[t, a, r]旋转移2个位置后得到[a, r, t]。这个方法的时间复杂度为O(n), n为列表的长度。
static void rotate(List<? > l, int d) 

// 返回c中与对象o相同的元素个数。
static int frequency(Collection<? > c, Object o) 

// 如果两个集合没有共同的元素，则返回true。
boolean disjoint(Collection<? > c1, Collection<? > c2)

java.util.Collection<T>

1
2
// 删除所有匹配的元素。
default boolean removeIf(Predicate<? super E> filter)

java.util.List<E>

1
2
// 对这个列表的所有元素应用这个操作。
default void replaceAll(UnaryOperator<E> op)

批操作

成批赋值或删除元素。例如：

  • 从 coll1 中删除 coll2 中出现的元素
1
coll1.removeAll(coll2);
  • 从 coll1 中删除未在 coll2 中出现的元素
1
coll1.retainAll(coll2);
  • 返回两个集 a 和 b 的交集
1
2
Set<String> result = new HashSet<>(a);
result.retainAll(b)
  • 对视图应用批量删除
1
2
3
Map<String, Employee> staffMap = ...; // ID -> 员工对象
Set<String> terminatedIDs = ...; // 将不再聘用的 ID
staffMap.keySet().removeAll(terminatedIDs); // 建立键集，并删除终止聘用关系的 ID
  • 把批量操作限制在子范围视图里
1
2
relocated.addAll(staff.subList(0, 10));
relocated.subList(0, 10).clear();

集合与数组转换

有时需要在传统数组和集合之间进行转换。

数组转集合：Arrays.asList 包装器

1
2
String[] values = ...;
HashSet<String> staff = new HashSet<>(Arrays.asList(values));

集合转数组：toArray 方法

可以直接用 toArray 方法，但这样得到的是 Object 数组。

1
Object[] values = staff.toArray();

下面这样的强制类型转换是错的。

1
String[] values = (String[]) staff.toArray();

必须使用 toArray 方法的一个变体形式，提供一个所需类型而且长度为 0 的数组。这样一来，返回的数组就会创建为相同的数组类型。

1
String[] values = staff.toArray(new String[0]);

也可以传入给定长度的数组，如果够长的话不会创建新数组：

1
String[] values = staff.toArray(new String[staff.size()]);

自己编写算法

如果编写自己的算法（实际上，是以集合作为参数的任何方法），应该尽可能地使用接口，而不要使用具体的实现。也就是将集合接口作为方法参数。

遗留的集合

在集合框架出现之前的一些遗留的容器类，已经集成到集合框架中，如下图：

Vector

1
2
// 返回遍历向量中元素的枚举对象。
Enumeration<E> elements()

Hashtable

Hashtable 类与 HashMap 类的作用一样，有相同的接口。

java.util.Hashtable<K, V>

1
2
3
4
5
// 返回一个遍历散列表中键的枚举对象。
Enumeration<K> keys()

// 返回一个遍历散列表中元素的枚举对象。
Enumeration<V> elements()

枚举 Enumeration

遗留集合使用 Enumeration 接口对元素序列进行遍历。Enumeration 接口有两个方法，即 hasMoreElements 和 nextElement。这两个方法与 Iterator 接口的 hasNext 方法和 next 方法十分类似。

Hashtable 类的 elements 方法将产生一个用于描述表中各个枚举值的对象：

1
2
3
4
Enumeration<Employee> e = staff.elements();
while(e.hasMoreElements()) {
    Employee e = e.nextElement();
}

java.util.Enumeration<E>

1
2
3
4
5
// 如果还有更多的元素可以查看，则返回true。
boolean hasMoreElements()

// 返回被检测的下一个元素。如果 hasMoreElements() 返回false，则不要调用这个方法。
E nextElement()

属性映射 Properties

属性映射（property map）是一个类型非常特殊的映射结构。它有下面3个特性：

  • 键与值都是字符串。
  • 表可以保存到一个文件中，也可以从文件中加载。
  • 使用一个默认的辅助表。

实现属性映射的 Java 平台类称为 Properties。属性映射通常用于程序的特殊配置选项。

java.util.Properties

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 创建一个空的属性映射。
Properties()

// 创建一个带有一组默认值的空的属性映射。
Properties(Properties defaults)

// 获得属性的对应关系；返回与键对应的字符串。如果在映射中不存在，返回默认表中与这个键对应的字符串。
String getProperty(String key)

// 获得在键没有找到时具有的默认值属性；它将返回与键对应的字符串，如果在映射中不存在，就返回默认的字符串。
String getProperty(String key, String defaultValue)

// 从InputStream加载属性映射。
void load(InputStream in)

// 把属性映射存储到OutputStream。
void store(OutputStream out, String commentString)

栈 Stack

java.util.Stack<E>

1
2
3
4
5
6
7
8
// 将item压入栈并返回item。
E push(E item)

// 弹出并返回栈顶的item。如果栈为空，请不要调用这个方法。
E pop()

// 返回栈顶元素，但不弹出。如果栈为空，请不要调用这个方法。
E peek()

位集

Java 平台的 BitSet 类用于存放一个位序列，位集包装在字节里，使用位集比用 Boolean 对象的 ArrayList 更高效。

C++ 中的 bitset 模板与 Java 平台的 BitSet 功能一样。

java.util.BitSet

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
// 创建一个位集。
BitSet(int initialCapacity)

// 返回位集的“逻辑长度”，即1加上位集的最高设置位的索引。
int length()

// 获得一个位。
boolean get(int bit)

// 设置一个位。
void set(int bit)

// 清除一个位。
void clear(int bit)

// 这个位集与另一个位集进行逻辑“AND”。
void and(BitSet set)

// 这个位集与另一个位集进行逻辑“OR”。
void or(BitSet set)

// 这个位集与另一个位集进行逻辑“XOR”。
void xor(BitSet set)

// 清除这个位集中对应另一个位集中设置的所有位。
void andNot(BitSet set)

BitSet 测试: 找出 2 ~ 2000000 之间所有素数

这里要遍历一个有 200 万个位的位集，初始化为开状态，已知素数的倍数对应的位都关掉，留下的是素数。最终素数个数为 148933。

我们对比 Java 和 C++ 的代码和运行结果。

Java 代码

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
import java.util.BitSet;

public class Sieve {
    public static void main(String[] args) {
        int n = 2000000;
        long start = System.currentTimeMillis();
        BitSet vec = new BitSet(n + 1);
        for(int i = 2; i <= n; i++) {
            vec.set(i);
        }
        for(int i = 2; i * i <= n; i++) {
            if(vec.get(i)) {
                for(int j = 2 * i; j <= n; j += i) {
                    vec.clear(j);
                }
            }
        }
        int cnt = 0;
        for(int i = 2; i <= n; i++) {
            if(vec.get(i)) {
                cnt++;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println(cnt + " primes");
        System.out.println((end - start) + " milliseconds");
    }
}

运行时间如下：

1
35 milliseconds

把 vec 从 BitSet 改为 ArrayList<boolean> 之后，时间变为：

1
252 milliseconds

C++ 代码

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
#include <bitset>
#include <iostream>
#include <ctime>

using namespace std;

int main()
{
    const int N = 2000000;
    clock_t cstart = clock();
    bitset<N + 1> vec;
    for(int i = 2; i <= N; ++i)
        vec.set(i);
    for(int i = 2; i <= N; ++i)
    {
        if(vec.test(i))
        {
            for(int j = 2 * i; j <= N; j += i)
                vec.reset(j);
        }
    }
    int cnt = 0;
    for(int i = 2; i <= N; ++i)
    {
        if(vec.test(i))
            ++cnt;
    }
    clock_t cend = clock();
    double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;

    cout << cnt << " primes" << endl;
    cout << millis << " milliseconds" << endl;
}

运行时间如下：

1
152.574 milliseconds

把 bitset<N + 1> vec 改为 vector<bool> vec(N + 1) 之后，时间变为：

1
171.881 milliseconds
Share