Archives

帖子来自 邓辉 RSS

邓辉

2011 英特尔® 线程挑战赛 —Parallelized Parser and Formula Interpreter

作者： 邓辉 (9 篇文章) 日期： 八月 9, 2011 在 2:43 下午
评论 (0)

  2011 英特尔® 线程挑战赛— 并行语法分析器与公式解释器 邓辉   denghui0815@hotmail.com 由于时间关系，文档写的不是太仔细，抱歉!  源码下载 问题描述 公式语法分析器和解释器分析连续的输入文字流，检查语法是否正确，根据输入内容分析出其数据结构并解析公式。公式的结果可以存储在变量中，将来的公式可以使用所有未作为公式的某个值从内存中除去的变量。最新多核硬件中的并行处理功能可用于增加语法分析器和解释器的吞吐量。许多热门 Web 浏览器的 JavaScript 引擎中的最新增强功能都需要提高与网络相关的语法分析器的处理速度。 问题描述： 编写一段多线程代码，解释、执行输入语句并生成输出结果。发送到输出结果的文字顺序应与程序输入语句中的顺序一致。您可以并行执行多个语句以增加吞吐量。 注意：关键字和变量区分大小写。行结束符为分号 (;) 下面的示例定义了两行： var ...

继续 ›

分类: 博客征文专栏, 并行计算, 开放源代码
标签：, ,

2011 英特尔® 线程挑战赛—Tiling Rectangles

作者： 邓辉 (9 篇文章) 日期： 六月 17, 2011 在 9:46 上午
评论 (0)

2011 英特尔® 线程挑战赛—Tiling Rectangles   邓辉   denghui0815@hotmail.com    源码下载 问题描述 给定一个整数尺寸的矩形区域，此区域可以再细分为多个方格，同样也是整数尺寸。此过程称为拼贴矩形。 对于这种用方格拼成的矩形，我们可以使用一系列分组的整数对拼贴进行编码。 从给定矩形水平方向的上方开始，从左向右、从上向下“读取”方格。 用括号将处于相同水平（位于拼贴矩形顶部）的方格的侧面长度组合到一起，然后按从左向右的顺序列出   例如，4x7 矩形将按以下方式拼贴…  _ _ ...

继续 ›

分类: 并行计算, 开放源代码
标签：, ,

2009 英特尔® 线程挑战赛参赛随笔系列 - 第六题 线段求交

作者： 邓辉 (9 篇文章) 日期： 七月 8, 2009 在 11:33 上午
评论 (0)

  问题描述 问题：写一段多线程代码，用来查找在三维空间内相交的线段对。线段的输入文件和输出结果文件将在命令行上指定。 输入格式：输入文件是一个文本文件，它的第一行将包含一个整数 N，表示文件内包含的线段数。后面的 N 行将包含线段的 4 个（可打印）字符名称和用来表示线段两个 (x,y,z) 端点的 6 个整数。其中的前 ...

继续 ›

分类: 博客征文专栏
标签：

2009 英特尔® 线程挑战赛参赛随笔系列 - 第五题: 背包问题

作者： 邓辉 (9 篇文章) 日期： 七月 1, 2009 在 10:48 上午
评论 (3)

  问题描述 在你为旅行准备行李时，重要的是你要注意不要在行李箱里放过多的东西，否则你可能会为因行李过重而付出额外的代价。这可能是来自航空公司的额外行李费用，或由于携带背包引起的肌肉酸痛。而且，当你装包时，控制总重量并不是你的唯一标准，你需要为你的旅行放入更有价值的物品。比如当你到澳大利亚度假时，如果你在包里塞满了羽毛，这不会有任何意义。背包问题的目的是要找到物品的最优选择，从而使这些物品的总价值最大，同时使总重量控制在限制范围内。 问题：写一个线程代码来找到能够形成最大总价值的物品清单，同时这些物品的总重量能够满足一个背包（容器）的限定容量。每个物品将有一个相关属性，包括容量（用重量表示）和价值（价格）。背包容量和要使用的物品清单会包含在命令行指定的输入文件内。装入的物品清单，装入的物品数量，总重量以及最终总价值将打印到一个输出文件：packinglist.out。 输入格式：第一行的文本文件将包含三个数：一个实数和两个整数。实数表示背包的容量，第一个整数表示每个可用物品的最大数目，这就是说，即使每个物品会在文件中列出一次，可能会有多个相同物品用来装包。第二个整数表示文件中物品的数目。随后的每一行由三项数据组成：表示物品名的唯一的13个字符长的字符串;表示物品重量的一个实数;以及表示物品价值的一个实数。在输入中不存在重量和价值相同的两个物品。 输出格式：使用易懂的一些格式。列出装入包中的每个物品以及这些物品的数量。同时需要包括所有装入包中物品的总重量和总价值。 有关本问题的详细情况，请进入本次线程挑战赛，获取更多信息。   对背包问题的分析和求解 有关此问题的参赛源代码，请点击这里下载。 串行算法 本题属于多重背包问题，多重背包可以转化为01背包进行求解。将物品分组1, 2, 4, 8..... 2^(k - 1), nCount - 2^(k ...

继续 ›

分类: 博客征文专栏
标签：

2009 英特尔® 线程挑战赛参赛随笔系列 - 第四题: 字符串匹配

作者： 邓辉 (9 篇文章) 日期： 六月 10, 2009 在 11:59 上午
评论 (0)

  问题描述 问题描述：写一个线程程序来搜索用字符串表示的 DNA 序列的数据库，来找到可以匹配的其他 DNA 序列。数据库和查询字符串由四个字符组成：'A', 'C', 'G'. 和 'T' 。对于每个输入的搜索查询字符串，输出必须报告任何输入 ...

继续 ›

分类: 博客征文专栏
标签：

2009 英特尔® 线程挑战赛参赛随笔系列 - 第三题：查找

作者： 邓辉 (9 篇文章) 日期： 五月 27, 2009 在 11:48 上午
评论 (1)

  问题描述 问题描述：写一个线程程序在一个线性存储且有序的唯一关键字集合中搜索给定关键字集合的所在位置。关键字是由15个字符组成的字符串，第一个输入文本文件包含有序关键字集合。第二个输入文本文件包含不定数量的关键字，这些关键字将在第一个文件中的关键字集合里进行查询。对于第二个输入文件中的每一个关键字在输出文件中都应该有对应的单行输出，输出信息包括关键字以及其在第一个文件中的下标，下标从0开始。如果待搜索关键字不在第一个文件中，那么将在输出文件中打印没有找到的信息。程序所涉及到的文件名（包括关键字集合文件，待搜索关键字集合文件，输出文件）将在命令行中给出。 文件格式：第一个输入文件的第一行是一个整数，代表文件中有序关键字集合的关键字数量（这里用N表示）。接下来存储的就是N行有序的关键字，每个关键字是15个字符的字符串。第二个文件包括待查询的不定数量的关键字集合，关键字同样是15字符的字符串，每行存储一个关键字。 输出文件应当与第二个输入文件有相同的输出行数。对于第二个文件中列出的每个关键字，在输出文件中都有对应的一行输出信息表明待搜索关键字以及在第一个文件中的下标或者未找到的信息。 有关本问题的详细情况，请进入本次线程挑战赛，获取更多信息。   对查找问题的分析和求解 串行算法 本题为查找算法题，可选的查找算法很多，有顺序查找、二分查找、HashMap等等。 顺序查找算法是将待查找的值依次与数组中每一个值比较，相等即查找成功，否则查找失败，顺序查找是O(N)的算法，不需要额外的空间。 二分查找算法只能在已排序的数据中查找，所以首先是将数据排序，然后取中间的值与待查找值进行比较，相等即查找成功。否则根据比较的结果在一半的数据中递归查找。二分查找是O(logN)的算法，不需要额外的空间。 HashMap查找算法通过Hash函数计算Hash值将数据分散到桶中，每个桶里的数据Hash值相同。不同值有相同Hash值我们称为冲突，冲突会导致桶中的数据增加。查找时利用Hash函数得到待查找值的Hash值，在这个Hash值限定桶中进行顺序查找，理论上该算法是O（1）的。如果数据集增大或者Hash函数不够好，冲突会增加，导致桶内数据增加，效率也会随之降低。如果所有数据的Hash值相同，则退化为顺序查找。 由于本题的输入是已经排序的字符串，所以首选当然是二分查找，但它是O(logN)的，理论上不及HashMap查找，但HashMap需要构建时间，性能与数据量也有关系。所以使用什么算法是需要根据数据量来调整的。 每个关键字为15字节，可以放入到__m128i中，于是定义XSearchItem结构表示关键字 // 关键字数据 typedef struct tagXSearchItem {      union      {          char cVal[16];          uint16   nVal16[8];          ...

继续 ›

分类: 博客征文专栏
标签：

2009 英特尔® 线程挑战赛参赛随笔系列 - 第二题: 3SAT

作者： 邓辉 (9 篇文章) 日期： 五月 20, 2009 在 2:17 下午
评论 (2)

  问题描述 可满足性问题研究的是取值为布尔值的析取子式的合取范式组成的表达式是否为TRUE的问题。要解决这个问题，也就是使得整个表达式为TRUE，你必须首先确定一组取值为TRUE或者FALSE的布尔变量是否存在。三元可满足性（3SAT）是可满足性问题的一种，它限制了析取子式只能有3个变量。以下是3SAT表达式的一个例子： (X_1 | !X_2 | X_3) & (X_3 | X_2 | ...

继续 ›

分类: 博客征文专栏

2009 英特尔® 线程挑战赛参赛随笔系列 - 第一题: 基数排序

作者： 邓辉 (9 篇文章) 日期： 五月 7, 2009 在 9:18 上午
评论 (2)

  问题描述 给出一组含有关键字的未排序字符串，这些关键字可视为整数的二进制表示，关键字内的各个位可以用来对这组字符串进行排序。这种排序方法被称为基数排序。 请编写一个用多线程实现基数排序算法的程序：对从输入文件读取的关键字进行排序，然后将排序后的关键字输出到另一个文件。输入文件名和输出文件名应为执行程序命令行的第一和第二个参数。 输入文件中的第一行是要排序的关键字总个数 (N)；后面紧跟 N 个关键字，每行一个；关键字是由 7 个可打印字符组成的字符串，不含空格 (ASCII 0x20)。文件中关键字的个数小于 2^31 – 1。排序后的输出结果必须保存在文本文件中，每行一个关键字； 计时：如果您在程序中加入计时代码来计算排序过程所用的时间并报告已用的时间，将用这个时间来计分；如果不加入计时代码，将使用整个执行时间（包括输入时间和输出时间）来计分。 有关本问题的详细情况，请进入本次线程挑战赛获取更多信息。   对基数排序的分析和求解 串行算法 “基数排序法”（radix ...

继续 ›

分类: 博客征文专栏
标签：

英特尔® 线程挑战赛系列文章—2008 第五题：数独解决方案

作者： 邓辉 (9 篇文章) 日期： 五月 4, 2009 在 8:50 上午
评论 (0)

数独(Sudoku)是一种逻辑谜题游戏,解答方法是将数字放到栅格里,但同行同列或者同一个子块里不能有相同的数字。通常栅格一般取 9x9。这样的话，每一行每一列以及这9 个 3x3 的不重叠子块的每一个，都会包括整数 1-9 的一个具体实例。除了 9x9 的栅格外，也有可能会用 16x16 ...

继续 ›

分类: 博客征文专栏