网上看到一道题。https://github.com/Skinney/WordSorter
简单的描述就是,对一个已知的文本文件按行字符串自然序进行排序,结果输出到另一个文件。
设计了一系列算法。
先搞一个最简单的。
Allen01_SimpleSort
1 读取数据。
2 排序。
3 写回。
4 单线程完成所有任务。
数据都是字符串,可以使用桶排先预排序一下。
Allen02_String_Bucket
桶排。按照每一行字符串的前2个字符分为26*26个桶。
数据读取和数据入桶线程分开。
写文件线程必须等待数据入桶线程完成任务。并且对桶内数据进行排序。
面向字符串处理。
字符串处理太慢,改为字节处理。
Allen04_Bytes_Bucket
桶排。
数据读取和数据入桶线程分开。
写文件线程必须等待数据入桶线程完成任务。并且对桶内数据进行排序。
面向字节处理。
数据先按照数据块入一个中间queue,入桶线程解析数据块为多个字节数组,入桶。
桶内的数据排序过程可以并行化。
Allen05_Fixed_Sorter
桶排。
数据读取和数据入桶线程分开。
一组桶内排序线程按照桶的数量对桶内数据排序工作做固定划分。
写文件线程必须等待排序线程完成任务。
面向字节处理。
线程桶内数据排序的划分,由于是固定的,有可能导致线程的工作负载不同。
Allen06_Dynamic_Sorter
桶排。
数据读取和数据入桶线程分开。
一组桶内排序线程按照本身排序工作的进度竞争得到下一个需要排序的桶。
写文件线程必须等待排序线程完成任务。
面向字节处理。
这个方案还搞了一个变种,使用26*26*27的桶,效果不太好。
一个桶内数据排序完成,数据就可以写出了,单独有一个线程监控桶内数据排序情况,排好序了就尽量写出。
Allen08_Concurrent_Writer
桶排。
数据读取和数据入桶线程分开。
一组桶内排序线程按照本身排序工作的进度竞争得到下一个需要排序的桶。
写文件线程和排序线程并发运行。
面向字节处理。
写文件线程和排序线程通过queue通信。
原始的桶内数据使用java自带的ArrayList保存,感觉有点重量级。
自己实现了一个简单的list,来保持桶内数据。自行管理数组容量,动态扩展。
/**
* 简单列表,代替ArrayList。
* */
public class AllenSimpleList implements AllenList {
private int capacity = 16;
private byte[][] datas = new byte[capacity][];
private int next = 0;
public void addData(byte[] data) {
if (next != capacity) {
datas[next++] = data;
} else {
int new_capacity = capacity << 1;
byte[][] new_datas = new byte[new_capacity][];
System.arraycopy(datas, 0, new_datas, 0, capacity);
new_datas[next++] = data;
capacity = new_capacity;
datas = new_datas;
}
}
public int getLength() {
return next;
}
public void mergeOtherList(AllenSimpleList other) {
if (capacity < next + other.next) {
int new_capacity = next + other.next;
byte[][] new_datas = new byte[new_capacity][];
System.arraycopy(datas, 0, new_datas, 0, next);
System.arraycopy(other.datas, 0, new_datas, next, other.next);
capacity = new_capacity;
datas = new_datas;
next = capacity;
} else {
System.arraycopy(other.datas, 0, datas, next, other.next);
next += other.next;
}
}
public void sort() {
AllenSorter.sort(datas, 0, next);
}
public void write(OutputStream out) throws Exception {
for (int i = 0; i < next; i++) {
out.write(datas[i]);
}
}
@Override
public void addData(int threadIndex, byte[] data) {
addData(data);
}
同时,原有排序线程和写出线程使用queue通信,可以配置为忙查询。
Allen08_Concurrent_Writer_Need_Strategy
使用了AllenSimpleList。
需要一个Strategy来控制程序。Strategy可以控制
是否设置线程的优先级。
使用何种策略进行排序线程和写文件线程的通信,queue还是轮询.
写文件线程是否会Yield。
数据入桶也可以并行化。
有可能导致桶内数据并发修改时不一致。
第1个方案,每一个线程一个单独的数据桶。
/**
* 多个simpleList,按照线程号分流。
* */
public class AllenSafeSimpleList implements AllenList {
private AllenSimpleList[] list;
public AllenSafeSimpleList(int threadCount) {
list = new AllenSimpleList[threadCount];
for (int i = 0; i < list.length; i++) {
list[i] = new AllenSimpleList();
}
}
public void addData(int threadIndex, byte[] data) {
list[threadIndex].addData(data);
}
@Override
public void sort() {
for (int i = 1; i < list.length; i++) {
if (list[i].getLength() > 0) {
list[0].mergeOtherList(list[i]);
}
}
list[0].sort();
}
@Override
public void write(OutputStream out) throws Exception {
list[0].write(out);
}
}
第2个方案,主备方案。
/**
* 2个simpleList,主备分流。
* */
public class AllenSafeSimpleList2 implements AllenList {
private AllenSimpleList mainList;
private AllenSimpleList bakList;
private AtomicBoolean main = new AtomicBoolean(false);
private AtomicBoolean bak = new AtomicBoolean(false);
public AllenSafeSimpleList2() {
mainList = new AllenSimpleList();
bakList = new AllenSimpleList();
}
public void addData(int threadIndex, byte[] data) {
if (main.compareAndSet(false, true)) {
mainList.addData(data);
main.set(false);
return;
} else {
while (bak.compareAndSet(false, true)) {
bakList.addData(data);
bak.set(false);
return;
}
}
}
@Override
public void sort() {
if (bakList.getLength() != 0) {
mainList.mergeOtherList(bakList);
}
mainList.sort();
}
@Override
public void write(OutputStream out) throws Exception {
mainList.write(out);
}
}
Allen12_Concurrent_DataWorker_Need_Strategy
桶排。
数据读取和数据入桶线程分开。
一组桶内排序线程按照本身排序工作的进度竞争得到下一个需要排序的桶。
写文件线程和排序线程并发运行。
面向字节处理。
入桶线程变成多线程。
需要一个Strategy来控制程序。Strategy可以控制
是否设置线程的优先级。
使用何种策略进行排序线程和写文件线程的通信,queue还是轮询.
写文件线程是否会Yield。
使用AllenSafeSimpleList还是AllenSafeSimpleList2。
bug fix:
AllenSafeSimpleList2
@Override
public void addData(int threadIndex, byte[] data) {
if (main.compareAndSet(false, true)) {
mainList.addData(data);
main.set(false);
return;
} else {
while (true) {
if (bak.compareAndSet(false, true)) {
bakList.addData(data);
bak.set(false);
return;
}
}
}
}
分享到:
相关推荐
文本文件内容排序功能: 每行是一条记录,每行可以有多列,列间按预定义的分隔符分隔; 可以按单列或多列组合排序,每列的顺序可以设置为反序或者正序; 列的数据类型可以是字符串、整数、浮点数,比较排序时按指定...
1. 建立复数对象,公共方法有加、减、乘、除、求模, 重载toString()输出(重写... 考虑多线程的处理,对链表操作的添加和删除加锁, 设置最大集合数量,如果链表为空,不能删除, 如果复数数量达到最大,不能添加。
- 使用多线程加速下载(9个部分) - 在后台下载文件并在失败后恢复; - 拦截浏览器和剪贴板中的链接; - 提高算法以提高下载速度; - 图像,文件,档案和程序的装载机; - 下载社交网络服务加速器; - 更快的2G,3G...
ZCL_多线程类1.01.ec ZCL_控件类库1.01.ec ZCL_文件读写1.01.ec ZCL_核库函数1.01.ec zip.ec zip压缩.ec 万能注册验证模块.ec 世恒通用安装系统文件压缩模块.ec 个性信息框1.1.ec 个性信息框1.21.ec 个性...
第14章 Visual C++2010 MFC多线程 第14章 程序设计 557 14.1 进程和多线程的概念 557 14.2 线程的创建 558 14.2.1 创建工作者线程 558 14.2.2 创建用户界面线程 559 14.3 线程的终止 560 14.4 设置线程的优先级 562 ...
多线程支持模块 多种对话框模块 1.0 堕之星辰1.2 E 24位转单色位图模块 EDB、高级表格、XLS互换 edb到html-1.0 EDB数据库客户端模块 1.0 edb数据库转Excel模块 1.3 ETimeFly API模块 Excel功能模块 F 发送...
列表文件是一个包括处理的文件名的纯文本文件。第一列应该以文件名开始。可以 在//字符后添加注释。例如,你可以创建包含下列字符串的 backup.lst: c:\work\doc\*.txt //备份文本文档 c:\work\image\*.bmp //...
概述: ...左侧选择“配置属性”->“C/C++”->“代码生成”,右侧窗口中“运行库”一项默认为“多线程调试 DLL (/MDd)”,将该选项修改为“多线程 (/MT)”或“多线程调试 (/MTd)”,重新编译即可。
使用NTKO附件管理控件[多文件上传控件],能够在浏览器中启动原始文件对应的应用程序,对图像文件,OFFICE文件,文本文件,AUTOCAD等任何文件进行编辑,打印,扫描,阅读,并保存到Web服务器。实现文档的方便编辑和统一...
6. 请给出Java代码,实现从一个文本文件中读取数据并排序的过程。 7. 请简述Java中的集合框架,并给出一个实例。 8. 请简述Java中的IO操作,并给出一个实例。 9. 请给出Java代码,实现一个简单的TCP/IP客户端程序。 ...
取文本文件行数(1.0).zip 取易模块信息(1.0).zip 取歌词模块(1.0).zip 取汉字代码(1.0).zip 取汉字全拼音模块(1.1).zip 取汉字笔画(1.0).zip 取汉字笔画模块(1.0).zip 取注册表键句柄(1.0).zip 取焦点窗口句柄(1.0)....
循环创建线程(一个页面,一个线程) 列表集合通过构造方法共享 运行结束后,应该获取到的是一个拥有所有页面的书的集合 根据得分属性和num属性,实现Comparator接口,完成排序 遍历当前这个列表集合,顺序为每个...
ZCL_多线程类1.01.ec ZCL_控件类库1.01.ec ZCL_文件读写 1.01.ec ZCL_核库函数1.01.ec zip.ec Z计算器.ec [神2也教你学E] - 可执行动态载入&输出其他文件模块.ec _仿真shell库.ec √功能键状态√.ec √取功能键状态...
ZCL_多线程类1.01.ec ZCL_控件类库1.01.ec ZCL_文件读写 1.01.ec ZCL_核库函数1.01.ec zip.ec Z计算器.ec [神2也教你学E] - 可执行动态载入&输出其他文件模块.ec _仿真shell库.ec √功能键状态√.ec √取功能键状态...
17.5 在多线程环境中使用SWIG生成的模块 603 17.6 用PySequence_Fast将Python序列转为 C数组 604 17.7 用迭代器逐个访问Python序列的元素 608 17.8 从Python可调用的C函数中返回None 611 17.9 用gdb调试动态载入...
保存为一行一个邮址的文本文件。强大的邮件列表管理功能,可以对邮件列表进行合并、分割、去重、筛选、排序和搅拌,是真正齐全的邮件列表管理工具集合。SMTP/eSMTP中继方式高速邮件群发,内嵌八个并 行发送线程,...
5) 允许用户自定义关键词的挖掘深度(遍历层次),多线程挖掘的时间间隔。因为挖掘的越深,关键词的相关度越小。同时,查询时间间隔的控制,能够防止IP被屏蔽的可能,无需人工干预。 6) 允许用户灵活控制实时查询...
2.重写“线程_启动四参”并改名为“线程_启动多参_文本型” 修改详情请查看新命令 精易模块 V3.59 what’s new:(20140107) 1.删除“系统_启用本地连接”中的垃圾代码,提升速度,感谢 阿蒙 的提醒 2.删除“程序...