多线程字符串排序比赛-后记

作者:野王 代码链接https://github.com/corejava/WordSorter/blob/master/C/sort_word.cpp

节前参加了多线程字符串排序性能比赛 ,觉得挺有意思 , 也学到了一些东东,本文分享一下在参与这次比赛的过程中我对程序优化的心得。

1. 充分利用cpu

一定要充分的把cpu利用起来(多线程), 而且尽可能的不要使用锁, 锁要慎用。我的方法是让每个线程知道自己应该干什么,这样线程之间就不需要用锁来做任务协调了。

2. 排序的优化

影响排序性能的 有几个因素: 比较的效率,排序的集合大小。 排序算法的复杂度。

字符串的比较效率是比较低的。我本来想把字符串比较 转换成 int64 的比较,这样会快很多。因为没有找到合适的 大小端转换方法而作罢, 还是直接采用了 字符串比较。对系统提供 strcmp做了一些修改, 原来的strcmp会判断 大于 等于 还是小于,在我们这里只需要知道 是否小于, 所以简化了 strcmp的代码。其实最好还是转成 int64 比较, 这里要特别注意: 从字符串转int64的耗时是比较高的,所以建议多线程转换, 而且是在 排序之前做预先转换,这样排序的时候 多次的比较 就可以直接用int64进行排序算法的选择,几种成熟的算法大家都知道,就不说了。

排序算法。我当时选了希尔排序因为时间紧 也没有去测试其他的排序算法,排序的集合大小是非常重要的。 因为不管啥算法复杂度,其计算的基础都是集合的大小,集合小了,排的自然更快。我的做法是把大集合切成多个有序的小集合, 每个小的集合 交给每个线程进行排序。在切小集合的时候 ,按照字符串前缀字符 来切分。 这样切开的多个小集合 之间 就是完全有序的。要是内存够 可以一直细切分下去, 一直到最后一个字符, 哈哈 然后就完成排序了。我们切开的多个有序小集合 在输出的时候 ,就不要做merge 操作了。挨个直接输出就可以。 

时间: 2025-01-26 16:37:42

多线程字符串排序比赛-后记的相关文章

Java字符串排序中文+数字

  思路: 在Java中,排序需要复写的是 equals 方法 和 Comparable<T> 接口 的public int compareTo(T o); 方法 步骤: 1. 使用正则表达式来判断数字,多个连续的数字作为一组, 2. 一次检索出数字组合, 3. 检出下一组数字,如果有,则进入步骤4,否则进入步骤6. 4. 如果两组数字出现的位置相等,并且前面部分的字符串相等,则进入第5步.否则break,跳到第6步. 5. 如果前面部分的字符串完全一致.则比较两个数字的大小,如果大小一致,则

c++-C++多线程外部排序的程序报错 bad allocaltion

问题描述 C++多线程外部排序的程序报错 bad allocaltion http://www.cnblogs.com/Jedimaster/archive/2013/11/17/3427761.html 按照这个网页给的方法,写多线程的外部排序算法.我先用第一个产生数据的算法 产生了429496729个int大小的数据.整个文件大概有1.59G这么大.然后分成4个进程,来处理数据.在main函数中,将iNumLocalItems设置为 20 * 1024 * 1024以及更小没有任何错误,但是

字符串指针 内存非法-用指针对字符串排序的问题,内存访问非法(续)

问题描述 用指针对字符串排序的问题,内存访问非法(续) 还是上次类似的问题,求解答. 对字符串进行排序的问题,被指针搞糊涂了. #include<stdio.h> #include<string.h> #include<stdlib.h> int main() { void sort(char p[][5]); char ss[10][5]={"worin","trafi","panda","dala

[华为机试练习题]12.整型字符串排序

题目 给定字符串内有很多正整数,要求对这些正整数进行排序,然后返回排序后指定位置的正整数 排序要求:按照每个正整数的后三位数字组成的整数进行从小到大排序 1)如果不足三位,则按照实际位数组成的整数进行比较 2)如果相等,则按照输入字符串中的原始顺序排序 说明(以下内容考生无须检查,调用者保证): 1) 字符串以'\0'结尾,仅包含数字.空格 2) 字符串内正整数之间以单个空格分隔,字符串首尾没有空格 3) 正整数格式为十进制,大小:1~1000000,正整数的数字非零开始 示例: 如字符串内容

c语言-C语言用指针给字符串排序,错在哪?

问题描述 C语言用指针给字符串排序,错在哪? #include #include void main() { void max(char *x,char *y,char *z); char a[50],b[50],c[50],d,*p,*q,*m; printf("请输入三个字符串 "); gets(a); gets(b); gets(c); p=a; q=b; m=c; printf("排序如下; "); max(p,q,m); puts(p);puts(q);p

mysql-MySQL数据库的字符串排序

问题描述 MySQL数据库的字符串排序 已经知道这种排序是因为字符串排序导致的,请问怎样解决,求大神指教 解决方案 SELECT * from dict_item where did='dict_doctorworktime' ORDER BY cast(code as SIGNED);这样应该就可以了. 解决方案二: 转换一下类型 解决方案三: 既然是数字,那就用数值类型的字段,要么就动态转换成int

C++ 用指向指针的指针的方法对5个字符串排序并输出时遇到的问题

问题描述 C++ 用指向指针的指针的方法对5个字符串排序并输出时遇到的问题 //用指向指针的指针的方法对5个字符串排序并输出 void sort(char **p) { char* temp=new char;//为什么没有长度呢?这么可以没有长度呢?? for(int j=0;j<5;j++) { for(int k=j;k<5;k++) { if(strcmp(p[j],p[k])>0) { temp=p[j]; p[j]=p[k]; p[k]=temp; } } } } int m

字符串排序

字符串排序的算法,将字符串从小到大输出 样例输入 2 2 Hello World 4 I Love C Language! 样例输出 Hello World C I Language! Love code: #include<stdio.h> #include<string.h> int main() {     int t,n;     int k,i,j,m;     char a[101][201],temp[201];     freopen("5.in"

Trie树_字典树(字符串排序)简介及实现_其它综合

1.综述 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie树结构的优点在于:1) 不限制子节点的数量: 2) 自定义的输入序列化,突破了具体语言.应用的限制,成为一个通用的框架: 3) 可以进行最大Tokens序列长度的限制:4) 根据已定阈值输出重复的字符串:5) 提