`
datamachine
  • 浏览: 163429 次
社区版块
存档分类
最新评论

用集算器来处理大文件集合运算

阅读更多

在进行文本处理时,经常会遇到对大文件进行集合运算的情况,比如找出两个文件不同的行数据。用命令行的grep\cat命令处理此类问题时,写法很简单,但效率太低,用高级语言处理此类问题虽然可以获得较高的运行效率,但代码编写复杂度确相当高。

    用集算器来进行大文件的集合运算和多线程并行计算,不仅代码简洁,而且性能优异。

文件file1.txtfile2.txt存储着大量的字符串,找出两者共同的行数据(交集)。部分数据如下:

 


两个大文件

两个文件都超出内存时,可以使用集算器的游标归并来实现交集运算,代码如下:



 

A1B1:以游标的形式打开文件。函数cursor并不会将数据全部读入内存,而是以游标(流)的方式打开文件,因此不会占据内存空间。函数cursor使用了默认参数,即:以tab为列分割符读入全部的字段,自动命名为_1_2_3…_n。对于本案例来说,只有一个字段_1

 

A2=[A1.sortx(_1),B1.sortx(_1)].merge@xi(_1)

使用归并算法找出两者共同的行数据,也就是求交集。归并算法要求数据有序,因此要先用sortx函数对游标进行排序,即A1.sortx(_1)A2.sortx(_1),这里的_1是文件默认字段名。函数merge表示对多组数据进行归并(本案例是两组),没有参数选项时,可以对内存中的集合进行归并,使用参数选项@x表示对游标进行归并,使用参数选项@i表示归并的结果是交集。

注意,A2的运算结果仍然是游标,仍然不会占据内存空间。只有遇到export/fetch/groups等函数时,集算器引擎才会分配合适的内存缓冲区,并将前面的游标计算自动转化为内存计算。

 

A3=file("E:\\result.txt").export(A2)

将游标A2写入文件。函数export既支持将内存数据写入文件,也支持将游标写入文件。这里使用了默认参数,即:无列名,列分割符为Tab,覆盖文件而不是追加,写成文本文件而不是二进制。打开result.txt,可以看到部分数据如下:



 

值得注意的是,前面的集算器代码是分步计算,事实上可以将它们合为一句:A1=file("e:\\result.txt").export([file("E:\\file1.txt").cursor().sortx(_1),file("E:\\file2.txt").cursor().sortx(_1)].merge@xi(_1)).

 

另外,本案例只实现了交集,其实还有并集、合集、差集,只需要修改单元格A2中函数merge的选项即可。比如,将file1.txtfile2.txt合并,并去除两者重复的成员(并集)。求并集应当使用函数选线@u,代码是:[A1.sortx(_1),B1.sortx(_1)].merge@xu(_1),并集的结果如下:


 

如果不去除重复成员(和集),则代码是:[A1.sortx(_1),B1.sortx(_1)].merge@x(_1),这也是归并的本意,计算结果如下:


如果想找到在file1.txt,但不在file2.txt中的数据(差集),则应当使用函数选项@d,代码是[A1.sortx(_1),B1.sortx(_1)].merge@xd(_1),计算结果如下:



注意:差集不满足交换律,所以想获得在file2.txt,但不在file1.txt的数据时,应当使用代码[B1.sortx(_1),A1.sortx(_1)].merge@xd(_1),计算结果如下:

 

 

 

文件一大一小

如果只有一个文件超出内存,那就可以将小文件读入内存,再用Hash查找的方法来进行集合运算,这样可以显著提高效率。集算器代码如下:



 

A1:用游标的方式打开文件。

 

A2=file("e:\\file2.txt").import()这句代码直接将小文件file2.txt读入内存。函数importcursor类似,默认的字段名也是_1_2。在IDE中点击B1可以看到当前格的计算结果:



 B2>B1.primary(_1).index()

上述代码用来给B1设置主键,并建立Hash索引,这样可以大大提高查询速度。B1B2可以合为一句:B1=file("E:\\ file2.txt").import().primary(_1).index().

 

A3=A1.select(B1.find(~._1))

这句代码用来查询出游标A1B1相同的数据,即求交集。函数select用来执行查询,符合条件的数据将被取出。函数select内可以使用~来代表当前记录。

查询条件是B1.find(~._1),这表示从B1中找到A1中当前记录的_1字段。

注意,这句代码的计算结果仍然是游标。

 

A4=file("E:\\result.txt").export(A3),这句代码将最终计算结果写入文件。

 

计算差集时,可以将A3单元格中的代码改成A1.select(!B1.find(~._1)),也就是从A1中找出不在B1里的那些行数据。

 

计算file1file2的并集时,可以先计算出file1file2的差集,再和file2做合并。



A4格的表达式[A3,B1.cursor()].conj@x(),函数conj可以进行多个集合的合并(合集),比如[[1,2,3],[2,3],[]]=[1,2,3,2,3]。函数选项@x可以合并多个游标里的数据。由于B1不是游标,因此要用函数cursorB1变换为游标,即B1.cursor(),这要比从文件里再读一遍来得快。

 

一大一小文件并行计算

前面的算法是串行,改成并行可以进一步提高性能,具体做法是用多个线程并行读取文件,每个线程都用游标访问文件的一部分,并同时进行集合计算,最后再将每个游标的结果合并。

在相同的硬件环境下对2.77G大文件和39.93M的小文件进行测试,串行时平均耗时85秒,并行时平均耗时47秒,性能提高接近一倍。由于集合运算的复杂度较小,瓶颈会产生在硬盘读取上,如果进一步加大运算的复杂度,性能提升的幅度将会更大。

集算器并行计算的代码如下:



B1:将小文件读入内存,设置主键并创建索引。

A2=4A2是分段数量,即将文件分成4段。分段数量不宜过多,一般不能超过CPU的核数,否则会排队等待,而没有实质提速效果。具体的最大并行数可以在环境选项中配置。

 

A3=A2.(file("e:\\file1.txt").cursor@z(;, ~:A2))

上面的代码按照分段数量生成4个游标。其中A2.(express)表示按照括号内的表达式依次计算A2的成员,括号内可用“~”来表示当前成员。A2一般是集合,比如["file1", " file2"][2,3]A2如果是从1开始的连续数字,比如[1,2,3,4],则可以简写成4.( express),案例中的代码就是这种情况。

括号内的表达式是file("e:\\file1.txt").cursor@z(;, ~:A2),其中函数cursor使用了选项@z,这表示将文件分段,用游标取其中的某一段。~:A2,这表示文件会被大致分为4(A2=4),“~”是A2的当前成员,因此每个游标依次对应第1、第2、第3、第4段文件。

另外,之所以是“大致分”,是因为精确分会出现半行数据的情况,而集算器会去头补位,自动取出整行数据。JAVA要实现这种处理要麻烦得多。

 

A4=A3.(~.select(B1.find(~._1)))这句代码针对A3中的每个游标计算交集,计算结果是游标的集合。

A5=A4.conj@xm()A4中的多个游标进行并行合并。

A6=file("e:\\result.txt”).export(A5),将计算结果输出到文件中。到此为止,交集已经计算完成,差集和并集的计算可以参考之前的案例。

 

集算器可以独立使用,也可以和JAVA集成。下面通过JDBC将集算器脚本集成在JAVA里。JAVA代码如下:

         //建立esProc jdbc连接

         Class.forName("com.esproc.jdbc.InternalDriver");

         con= DriverManager.getConnection("jdbc:esproc:local://");

         //调用esProc,其中test.dfx是脚本文件名

         st =(com.esproc.jdbc.InternalCStatement)con.prepareCall("call test()");

         st.execute();//执行esProc存储过程,也可以传入参数并传出计算结果。

 

         对于第一个案例中的简单脚本,可以嵌入JAVA代码中直接执行,而不必编写脚本文件(text.dfx)。相应的JAVA代码如下:

         ResultSet set=st.executeQuery("file(\"e:\\result.txt\").export([file(\"E:\\file1.txt\").cursor().sortx(_1),file(\"E:\\file2.txt\").cursor().sortx(_1)].merge@xi(_1))");

 

 

 

  • 大小: 85.7 KB
  • 大小: 21.5 KB
  • 大小: 25.8 KB
  • 大小: 35.3 KB
  • 大小: 46.3 KB
  • 大小: 10.8 KB
  • 大小: 10.8 KB
  • 大小: 23.9 KB
  • 大小: 20.9 KB
  • 大小: 27.6 KB
  • 大小: 31.7 KB
0
0
分享到:
评论

相关推荐

    集合交并运算处理

    在编程领域,集合交并运算处理是常见的数据操作任务,特别是在使用C++这样的高级编程语言时。本示例中,我们关注的是如何高效且灵活地处理集合,包括执行交集、并集以及相等比较等操作。对于任意元素个数和任意元素...

    集合的运算:交、并、补

    根据给定的文件标题“集合的运算:交、并、补”及其描述,本文将详细介绍如何在编程语言C++中实现集合的基本运算——...通过这些代码,读者不仅可以理解集合运算的基本概念,还可以了解如何在实际编程中应用这些概念。

    集合运算.zip

    在蓝桥杯这样的竞赛中,集合运算是解决某些类型问题的关键,比如图论中的顶点集合、数学问题中的解集,甚至是处理数据集的筛选和分组。选手需要熟练掌握集合操作,以便快速有效地解决问题。通过分析这些输入文件,...

    集合交并差运算

    - 并查集是一种高级集合操作,用于处理不相交集合的合并与查询。它包含“Find”(查找元素所属集合)和“Union”(合并两个集合)操作。C语言中可以通过路径压缩或按秩合并等优化策略提高效率。 在实际编程中,...

    运算12集合的基本.pdf

    8. 使用文氏图理解集合运算:文件中多次出现“Venn”,表明可以通过文氏图来直观表示集合的交集、并集等情况。 9. 集合的运算规则:例如,若A={x|x, B={x|x>0}, C={x|x,那么根据集合运算的规则,AB表示A和B的交集...

    jihe.rar_集合运算

    在编程领域,集合运算是一种常见的数据处理操作,尤其在C++这样的编程语言中,它提供了对集合进行高效处理的能力。本项目"jihe.rar_集合运算"主要关注的是集合的和、差、交集等基本运算,这些都是在处理数据时非常...

    sss.zip_C++_集合的运算_面向对象

    在C++编程中,集合(Set)是一种容器,它...在提供的`sss.cpp`文件中,可能包含了实现上述功能的代码,包括链表结构的定义、集合运算的函数以及面向对象的类设计。具体实现细节可以通过阅读源码来进一步学习和理解。

    linux使用select 编写简单的计算器运算程序

    编写这样的程序,你需要理解`select`的工作原理,以及如何正确处理文件描述符集和用户输入。此外,还需要掌握基本的C语言编程技能,包括输入/输出操作、字符串处理以及基本的数学运算。最后,为了提高用户体验,你...

    python源码集合处理技术

    根据给定文件的信息,我们将重点讲解Python源码的集合处理技术。在深入之前,需要澄清的是,描述中提及的“百度网盘分享地址”并不是一个技术知识点,而是指向了Python源码集合的下载途径。这通常意味着有关Python...

    实现集合交并差

    4. **执行流程**:用户启动exe文件后,程序会提示用户选择进行哪种操作,然后根据用户输入的数据执行相应的集合运算,并显示结果。由于程序提供exe文件,这意味着它已经被编译为可执行程序,可以直接在支持C++环境的...

    位运算求子集

    根据给定的文件信息,我们可以了解到这是一段C++代码,主要通过位运算来求解一个集合的所有子集。接下来,我们将对这段代码所涉及的关键概念进行深入解析,并结合位运算的基本原理以及如何利用位运算求解子集等问题...

    C语言C++结课大作业——交并补运算+Gui界面(含GUI).zip

    3. **数据结构**:实现集合运算通常需要使用适当的数据结构,如数组或链表。数组可以提供快速访问,但大小固定;链表则允许动态添加和删除元素,但访问速度较慢。在C++中,可以使用`std::set`或`std::unordered_set`...

    C常用算法程序集数值计算矩阵运算

    如果需要处理大规模的矩阵问题或者希望获得更为专业和优化的算法,可以使用专门的数值计算库,如LAPACK(Linear Algebra Package)。LAPACK是专为解决复数和实数的线性代数问题而设计的,它提供了大量用于矩阵运算的...

    高一国庆大礼包集合与逻辑1-3全解全析.pdf

    根据提供的文件内容,该文档主要涵盖了集合与逻辑的数学知识点,特别是与命题逻辑、集合运算、以及它们在解题中的应用相关。下面是一些从文件内容中提炼出的知识点: 一、集合的基本概念 1. 集合表示具有某种特定...

    图像处理基础算法源代码MATLAB集合

    这个名为"图像处理基础算法源代码MATLAB集合"的资源包,显然是为初学者提供了一个宝贵的自学平台,让我们来深入探讨其中可能包含的知识点。 1. **MATLAB基础**:首先,你需要熟悉MATLAB的基本语法,包括矩阵操作、...

    Gdal的dll文件集合

    在您提到的“Gdal的dll文件集合”中,包含了8个与GDAL相关的C#接口DLL文件,这些文件对于在.NET环境中使用GDAL至关重要。 1. **gdal_csharp.dll**:这是GDAL的主要C#接口,提供了对GDAL核心功能的访问,包括打开、...

    python集合常见运算案例解析

    在Python中,集合运算可以通过各种方法实现,比如使用“|”运算符进行并集运算,使用“&”运算符进行交集运算,使用“-”运算符进行差集运算,以及使用“^”运算符进行对称差集运算。还可以用方法调用的形式,例如...

    初学Android练习用,20以内加减法运算练习(代码经调试通过,GridView-动态数组-wav)

    在Android中处理音频文件,可以使用MediaPlayer类,加载.wav文件并播放。首先需要在项目的res/raw目录下存放.wav文件,然后通过MediaPlayer的setDataSource()方法指定音频资源,prepare()进行准备,最后调用start()...

    用java实现画曼德勃罗集(Mandelbrot Set)及朱莉亚集(Julia Set)

    总之,用Java实现曼德勃罗集和朱莉亚集的绘制,不仅涉及到复数运算和迭代算法,还涵盖了图像处理和性能优化,是一项结合数学、编程和艺术的挑战。通过这个过程,你可以更好地理解和欣赏分形之美,同时提升自己的编程...

    集合论基础 PDF 高清完整带目录版

    根据提供的文件信息,这里主要涉及的是“集合论基础”这一数学领域的知识点。虽然部分内容并未给出具体章节或细节,但基于标题、描述以及标签中的信息,我们可以推断出这份文档大概会涵盖集合论的基础概念与原理。...

Global site tag (gtag.js) - Google Analytics