现用一台2G内存4核CPU的电脑,尽可能快速的找出3.7亿个字中第一个不重复的字符,Java代码利用多线程分治和hash实现
时间: 2023-05-30 12:01:59 浏览: 59
首先,我们需要将3.7亿个字分成多个小块,每个小块的大小为1MB左右,然后利用多线程处理每个小块。
每个线程处理小块的过程如下:
1. 读入小块内容到内存中;
2. 遍历小块中的每一个字符,利用hash算法计算出该字符的hash值;
3. 将hash值作为key,该字符在小块中的位置作为value,存入一个HashMap中;
4. 遍历HashMap,找出第一个value为1的字符,并记录该字符在小块中的位置;
5. 将该位置加上小块在总数据中的偏移量,就得到了整个数据中第一个不重复的字符的位置。
Java代码如下:
```java
import java.io.*;
import java.util.*;
public class FirstNonRepeatingChar {
private static final int BLOCK_SIZE = 1024 * 1024; // 每个小块的大小
private static final int THREAD_NUM = 4; // 线程数
private static final int MOD = 1000000007; // hash取模的值
public static void main(String[] args) throws Exception {
long start = System.currentTimeMillis();
// 读入数据
BufferedReader br = new BufferedReader(new FileReader("data.txt"));
StringBuilder sb = new StringBuilder();
String line;
while ((line = br.readLine()) != null) {
sb.append(line);
}
br.close();
String data = sb.toString();
// 将数据分成多个小块
List<String> blocks = new ArrayList<>();
int len = data.length();
int blockNum = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;
for (int i = 0; i < blockNum; i++) {
int startIdx = i * BLOCK_SIZE;
int endIdx = Math.min((i + 1) * BLOCK_SIZE, len);
blocks.add(data.substring(startIdx, endIdx));
}
// 多线程处理每个小块
List<Thread> threads = new ArrayList<>();
List<Result> results = new ArrayList<>();
for (int i = 0; i < blockNum; i++) {
String block = blocks.get(i);
Result result = new Result(i * BLOCK_SIZE, -1);
results.add(result);
Thread thread = new Thread(new Runnable() {
@Override
public void run() {
Map<Integer, Integer> map = new HashMap<>();
int len = block.length();
for (int j = 0; j < len; j++) {
int c = block.charAt(j);
int h = hash(c);
if (map.containsKey(h)) {
map.put(h, -1);
} else {
map.put(h, j);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 0) {
int pos = entry.getValue();
result.pos = result.offset + pos;
break;
}
}
}
});
threads.add(thread);
}
for (Thread thread : threads) {
thread.start();
}
for (Thread thread : threads) {
thread.join();
}
// 找出所有不重复字符中最靠前的一个
int minPos = -1;
for (Result result : results) {
if (result.pos >= 0 && (minPos == -1 || result.pos < minPos)) {
minPos = result.pos;
}
}
System.out.println("第一个不重复的字符的位置:" + minPos);
System.out.println("耗时:" + (System.currentTimeMillis() - start) + "ms");
}
private static int hash(int c) {
long h = 0;
h = h * 31 + c;
return (int) (h % MOD);
}
private static class Result {
int offset;
int pos;
public Result(int offset, int pos) {
this.offset = offset;
this.pos = pos;
}
}
}
```
这里我们采用了hash算法,将每个字符映射成一个数字,然后将该数字作为key,该字符在小块中的位置作为value,存入HashMap中。如果遇到重复字符,将value设为-1。最后遍历HashMap,找出第一个value为1的字符,并记录该字符在小块中的位置。最后将该位置加上小块在总数据中的偏移量,就得到了整个数据中第一个不重复的字符的位置。