用Java语言利用多线程分治实现,快速的找出3.7亿个字中第一个不重复的字符:
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class FindFirstNonRepeatCharacter {
private static final int THREAD_POOL_SIZE = 4; // 线程池大小
private static final int CHUNK_SIZE = 1000000; // 每个线程处理的字符数
public static void main(String[] args) throws Exception {
String input = "大约有3.7亿个字的字符串"; // 待处理的字符串
ExecutorService executorService = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
Map<Character, Integer> characterCountMap = new HashMap<>();
int start = 0;
int end = CHUNK_SIZE;
// 分割字符串,将每个子串交给一个线程处理
while (start < input.length()) {
if (end > input.length()) {
end = input.length();
}
String chunk = input.substring(start, end);
Callable<Map<Character, Integer>> callable = new CharacterCountTask(chunk);
Future<Map<Character, Integer>> future = executorService.submit(callable);
// 合并每个线程的结果到总的字符计数器中
Map<Character, Integer> chunkCharacterCountMap = future.get();
for (Map.Entry<Character, Integer> entry : chunkCharacterCountMap.entrySet()) {
char character = entry.getKey();
int count = entry.getValue();
characterCountMap.put(character, characterCountMap.getOrDefault(character, 0) + count);
}
start = end;
end += CHUNK_SIZE;
}
// 找到第一个不重复的字符
char firstNonRepeatCharacter = '\0';
for (int i = 0; i < input.length(); i++) {
char character = input.charAt(i);
if (characterCountMap.get(character) == 1) {
firstNonRepeatCharacter = character;
break;
}
}
executorService.shutdown();
System.out.println("第一个不重复的字符是:" + firstNonRepeatCharacter);
}
static class CharacterCountTask implements Callable<Map<Character, Integer>> {
private final String input;
CharacterCountTask(String input) {
this.input = input;
}
@Override
public Map<Character, Integer> call() {
Map<Character, Integer> characterCountMap = new HashMap<>();
for (int i = 0; i < input.length(); i++) {
char character = input.charAt(i);
characterCountMap.put(character, characterCountMap.getOrDefault(character, 0) + 1);
}
return characterCountMap;
}
}
}