Archive for 算法-编程

最近又心血来潮研究图形学去了,啃3d开发去了。n年前研究过,那时候心性不行,感觉太难了,搞了一半就放弃了。现在又准备重新研究了,目标定位到OpenGL es上了。 主要OpenGL ES支持手机平台,而且属于opengl的子集,没有历史包袱。虽然可能很多高级特效之类的不支持,但是应该也用不到,可能我学习的速度还赶不上硬件和opengl发展速度,考虑这些就考虑多了。从网上介绍来说es是可以在桌面上用的,但是网上搜了一下都需要模拟器。而我看的书是《opengl es 3.0 编程指南》这个书只是说libglesv2的lib版本,这个我就很疑惑。而且还推荐了很多桌面上的模拟器,用来跑示例,我这还想着桌面的也用es写,但感觉模拟器应该也能一起编译打包。 然后我搜了一下lib,发现libgles2已经安装了,搜的libgles,好多包安装过了。然后我看了一下头文件,GLES3/gl3.h也有。libegl也有安装。我就直接cmake了示例代码,然后运行成功了。 所以具体是这个包起作用,还是还有别的包,我也不太清楚,也懒得验证了。然后我就通过包信息里的官方网址,发现还是NVIDIA的github。里边头文件确实有gles3的,看了readme也没说支持3.0的es。大概率是支持了。 具体windows可能是需要模拟器了吧,或许也有显卡公司写的lib。

Continue

临时看个问题,对matplotlib没有了解,基本纯网上搜了搜。暂时先记录一下。 是使用 pandas读了一个excel表,然后加了index字段,是个日期,数据保存在变量df里,可以直接调用df.plot()进行画图,我是有点震惊的。这是因为这几个库联用的多嘛。画出来的图横坐标日期不能全显示,然后想全显示出来。 第一反应就是日期太长了,然后找可以调整角度的函数,用xticks修改角度,不好用。然后发现xticks可以指定横坐标显示位置,显示映射啥的。 x=np.arange(0,12,1)生成一个选择的映射,label传入全部十二个日期。然后就显示全面了。plt.xticks(x, mon, rotation=90) xticks参数还可以指定Text类型的参数,进行文本样式的设置。 最近让搞R语言,在看R语言画图的功能。因为看我对python的matplotlib,numpy,pandas这些库都没经验,领导之前会用R,就让我直接写R了。感觉搞这些工具,但不会统计的东西,搞起来总感觉是在隔靴子挠痒。

Continue

看网上教程,最后选择了这种rpc调用的方式,这种方式可以提前启动R虚拟机,R程序造成的崩溃不会影响到java程序。另一种方式是JRI,全名是Java/R Interface 第一步R安装Rserve,这里有点问题就是最好root权限安装,我看文档这种方式需要源码安装,并且有$R_HOME/bin权限。所以直接root启动r然后安装了,install.packages("Rserve")。这里试了一下R INSTALL 好像只能安装本地的包。最后决定安装官网的最新版本,目前还没在CRAN中。install.packages("Rserve",,"http://rforge.net") 第二步启动R server,命令行执行 R CMD Rserve,这个就是上边说的daemon模式,文档说只支持unix系统,windows还不行。默认启动端口6311.看参数好像只能指定端口,不支持指定IP。看文档只能通过配置文件去指定是否允许远程访问。写一行remote enable就行了,我没在默认/etc/Rserv.conf 改,直接参数指定的文件。 第三步java客户端连接,这里需要两个jar包,官方网站能下载,看版本有点老,安装包也带。目录在 /home/xx/R/x86_64-pc-linux-gnu-library/4.0/Rserve/java/ 包的安装目录下。然后javac -classpath ./REngine.jar:./Rserve.jar:. test.java,测试运行一下没啥问题。数据类型的转换问题还需要详细研究一下。

Continue

代码基本网上搜的,没啥贴的,写一下思路,有需要的自己网上搜就行了。主要是自己看的电子书是扫描版的pdf,里边全是图片,超级大,好几百M。之前找了一圈,靠谱软件需要收费,不靠谱个人软件只能windwos下用。于是自己搞吧,发现也不太难。 第一步是把pdf提取图片 用到pymupdf库,这个是封装的c的接口,感觉写个pdf软件也不难啊,都有开源库,不知道为啥他们还收费。我提取图片发现,好多水印图片是直接用pdf编辑软件加上的,导致水印可以直接从提取的图片里边删掉,这个挺好。 第二步,把图片二值化 这里用到opencv,用到cv2.threshold。这个阈值不太好设置,可以使用cv2.THRESH_OTSU,提取一个分析值,但是这个不是最优的,有的书是半彩页的,书边会有浅色的背景之类,或者重点颜色等。这个有分析建议值之后,还需要自己试一下哪个值比较好。 第三部,把图片生成新pdf 这个还是用pymupdf库,基本都差不多。 没想到的是压缩率还挺低,一百多MB的pdf能压缩成十多兆。可能也是之前的pdf质量比较高吧。但是我看了一下压缩后的,清晰度一点不减少。有背景色的地方,选择阈值合适,背景色也都过滤掉了,文字不受影响。

Continue

libpmem有一个初始化操作在函数pmem_init里, 里边有初始化的一系列操作,东西太多,主要就是查架构,定下以后使用的函数等。我这里根据当前CPU架构,只看了需要用到的内容. 首先通过pmem2_arch_init(&info);初始化info。在libpmem2/x86_64/init.c里,pmem_cpuinfo_to_funcs(info, &impl);这个函数是判断flush支持的指令,从最低级开始判断,如果高级的支持,就直接替换。这个我看过cpuinfo是支持clwb,所以info->flush = flush_clwb; info->flush_has_builtin_fence = 0; info->fence = memory_barrier;。这里边很多环境变量的获取判断,都是调试或者制定模式的,这里先不管这些。SIMD支持avx512f,所以也直接看这个了,初步看着这个好像是为了MOVNT准备的就是ntstore,主要就定义一个memmove_nodrain。然后这里info就初始化完了。 flush_clwb,为flush_clwb_nolog(addr, len);在libpmem2/x86_64/flush.h里定义的: static force_inline void flush_clwb_nolog(const void *addr, size_t len) { uintptr_t uptr; /* * Loop through cache-line-size (typically 64B) aligned chunks * covering the given range. */ for (uptr = (uintptr_t)addr & ~(FLUSH_ALIGN - 1); uptr < (uintptr_t)addr + len; uptr += FLUSH_ALIGN) { pmem_clwb((char *)uptr); } } FLUSH_ALIGN为64,所以其实数据结构能对齐64B应该是好的,但是想了想应该没办法对齐。所以还是得计算对齐地址,但是小数据可以不需要for了,这个可以定制。pmem_clwb为CLWB void _mm_clwb(void const *p);这个gcc应该是支持的,等查一查,官方为了兼容,直接汇编实现的。memory_barrier为_mm_sfence();这个clwb是必须的。 回到pmem_init,初始化了Funcs系列函数,这些跟info里的一样的,不在写具体逻辑到这里了。最后pmem_os_init(&Is_pmem);这个就是第二篇里边的判断函数的初始化,暂时不细看了。 pmem_flush就是调用的flush_clwb,pmem_drain就是调用的memory_barrier,pmem_persist就是先flush后pmem_drain,pmem_memcpy就是先memmove_nodrain,然后drain,这里的特殊env控制就不管了。pmem_memcpy_nodrain就是只是少了pmem_drain这一步。pmem_memcpy_persist这个是不管env的肯定drain. flush_empty这个不干事,只是通知pmemcheck。 还剩最后一块memmove_nodrain = memmove_nodrain_avx512f_clwb。这个我之前看的时候,搜代码都搜不到,还好统看了一下代码文件,发现是个模板搞的。MEMCPY_TEMPLATE(avx512f, clwb, /* */)。 pmem_memcpy_nodrain调用的时候,flag传了一个0,所以没有flag的,调用的是memmove_movnt_avx512f_clwb。长度小于256单位应该是Byte吧,因为是传过来的len,使用memmove_mov_avx512f_clwb,其他情况是通过flag来决定的,这个可以通过pmem_memcpy可以传参数,属于最灵活的调用方式了,也可以指定是否pmem_drain。 memmove_mov_avx512f_clwb在libpmem2/x86_64/memcpy/memcpy_t_avx512f.c里,先通过if ((uintptr_t)dest - (uintptr_t)src >= len)来判断两块内存是否相交,然后选择不同方法。这里可以优化,想了想我要写的代码没有重叠内存,所以可以优化。看memmove_mov_avx512f_fw里主要就是不同长度选择使用不同函数就复制数据。我查看小数据的复制,是用的转成uint来进行赋值拷贝的。也用了循环展开优化数据复制。这里边的持久化用的pmem_clwb,这个是为已经对齐的地址准备的,看来我能想到的官方肯定都想到了啊。mov的指令都是使用的avx指令load和store. memmove_movnt_avx512f_clwb在memcpy_nt_avx512f.c里,这里也判断了数据重叠问题,但是没看懂的是这里需要flush,但是不需要barrier.我觉得不应该正好反过来吗。。这里用的是load和stream指令来移动数据,移动完跟想的一样是没有flush的,flush是为的开头结尾的小数据准备的。 两种移动数据都不需要barrier,可能是为了集中控制,把是否barrier的权限放到接口里决定。 现在具体看看也没有多少可以优化的,一个是flush的for循环,一个是memcpy的判断内存重叠的问题。不过每次减少两个判断,收益也不少了。再一个确认一下初始化是否算时间,把初始化的时间也优化了。 后期移植的时候又发现一个,在avx实现的拷贝过程中,是按2kb的数据块进行的ntstore。比赛最高1kb,所以这里可以去掉,从1kb开始判断就行了。

Continue

libpmem主要通过pmem_map_file封装来进行mmap的映射,首先通过util_file_get_type获取文件类型,主要区分文件是否存在,DAX设备文件。比赛用的fsdax,这个主要通过mmap来实现的寻址操作,挂载路径为/dev/pmem/。还有devdax,这个好像是给虚拟机分配的时候用这个模式,挂载路径为/dev/dax/。还有sector和raw模式。 文件支持的flag有(PMEM_FILE_CREATE|PMEM_FILE_EXCL|PMEM_FILE_SPARSE|PMEM_FILE_TMPFILE),dax设备支持的flag有(PMEM_FILE_CREATE|PMEM_FILE_SPARSE). 然后判断是dax后,判断len必须是0或者文件大小。open_flags默认有O_RDWR,如果flag有PMEM_FILE_CREATE则open_flags添加O_CREAT。后边判断传了len必须有PMEM_FILE_CREATE,len为0必须没有PMEM_FILE_CREATE.PMEM_FILE_TMPFILE必须有PMEM_FILE_CREATE.之后os_open(path, open_flags, mode)打开文件。如果flag带有PMEM_FILE_CREATE,则os_ftruncate文件,没有PMEM_FILE_SPARSE,则os_posix_fallocate(fd, 0, (os_off_t)len))文件。这里看不太懂,看手册这俩函数基本是等价的。如果没有PMEM_FILE_CREATE,则获取真是文件大小,重新复制len。 然后pmem_map_register,在pmem_posix.c里,调用util_map,传了MAP_SHARED。在common/mmap.c里 肯定有PROT_READ|PROT_WRITE,然后调用util_map_hint,这个主要就是确定mmap地址的,调试有参数可以固定虚地址的,这个看书看过。基本用不上。好像是通过mmap MAP_PRIVATE找一个mmap对齐的地址。 req_align为零,align = GIGABYTE。#define GIGABYTE ((uintptr_t)1 << 30)。这里脑袋有点浆糊了,不具体看就是找个一个对齐地址,然后后边用来mmap pmem文件使用,先这样吧。然后util_map_sync,地址是刚返回的地址,在这里mmap了。 然后复制len和is_pmemp。关闭fd,就结束了。pmem_is_pmem里边东西还挺多,有调试相关,乱七八糟一堆,主要是在初始化指定默认判断函数,然后在这里如果有env或者其他情况进行函数转换,然后掉函数看结果,不细看了,因为比赛肯定为pmem。 其实总结一下流程很简单,先打开文件,设置文件大小。然后mmap寻找一个对齐地址,最后真正mmap,返回。

Continue

参加了个阿里的kv数据库比赛,接触到持久化内存的概率,到现在对这里理解的也不是太深入,只管总结一下。看了官方的书,还有一些代码和官方视频,但是为了参加比赛,还是觉得研究一下代码。初步看了看发现能在比赛上优化的地方还挺多的,所以决定慢慢总结和移植一下。 持久化内存(Persistent Memory)我看网上好像概念已经老早就有了,我是第一次知道,也记不住讲不清。总的来说就是可以掉电不丢数据的内存,是嫌ssd慢了,又出来一个算是ssd和内存的中间层。还有两种模式,可以当普通内存用,相当于扩展普通内存的容量。或者当持久内存用,可以保证掉电不丢数据和快速的读写速度。 libpmem是intel开发的持久化内存开发组件(Persistent Memory Development Kit)里的一个库,属于底层库,libpmemobj等库都是在这基础上开发的。比赛用到,基本不考虑libpmemobj这库,集成太厉害了,libpmem我大体看了代码发现也可以修改移植,能优化不少。而且因为我c语言经验不多,看了源码后发现能学很多东西。所以决定阅读总结加移植代码。 大体的使用思路就是,基于系统调用mmap进行pmem的进程空间地址的映射,这里是内核原生支持了。所以这玩意应该出了很久了,才刚听说,感觉阿里应该属于用的比较早的。之后就跟正常使用内存一样了,而这些操作都是在用户空间,所以效率理论上还有优势,虽然本身速度赶不上内存。持久化操作需要将cpu cache里的数据踢出到内存(evict),刷新到持久内存上。 基本情况就这样,下边看几个基础文件。学到很多代码 core/util.h util.c 这俩都是常用函数集合 #define force_inline __attribute__((always_inline)) inline #define NORETURN __attribute__((noreturn)) #define barrier() asm volatile("" ::: "memory") 第一个从名字就看出来是强制函数inline,第二个是有时候写的分支没有返回时编译器会有报错,这个可以告诉编译器不要报错。第三个是内存栅栏。 typedef uint64_t ua_uint64_t __attribute__((aligned(1))); 能够指定最少字节对齐数,受连接器限制,不会超过连接器大小。感觉没啥用,但是也可能以后用上,学到东西了。 util_setbit, util_clrbit这个是位操作,这个是会的 util_is_pow2, return v && !(v & (v - 1)); 判断是否是2的幂 __builtin_ctz,__builtin_clz,这个是判断一个数,从开头或者从结尾有多少个零的,厉害了。 其他的就没啥了,看看util.c util_is_zeroed检查内存为0,应该用不到,记录下。util_checksum_compute,这是是计算一块内存的checksum,已移植,不知道会不会比hash快,这个应该比hash准确,但是比赛还是讲究速度,到时候试试。算法好像是Fletcher64。 valgrind好像能模拟cpu环境,调试程序的,好像书里有写,没太看内容,先记录。 Mmap_align好像用来分配对齐的,这里不知道干啥的,先跳过记录。linux下直接分配的Pagesize = (unsigned long) sysconf(_SC_PAGESIZE) util_concat_str连接字符串,没用记录.util_localtime获取时间,没用记录 其他的基本用不上了,主要看书看到原理的地方,发现checksum相关内容,有用到,就搜了一下源码,看到这些代码。

Continue

devtools包能够方便在开发R语言包时,测试,文档生成,安装包等操作。 testthat包是单元测试的包,这里要写单元测试了。 devtools的安装需要提前安装一些依赖,不然安装会报错,我的是ubuntu系统,需要安装一下依赖 apt install libxml2-dev libcurl4-openssl-dev 安装完这俩软件,再安装就可以了,具体是否依赖其他软件就不清楚了,我这里是少这俩,官方文档也不太友好。 我是先创建的package在安装的devtools,发现现在没有好的方法添加test文件了,我是使用的testthis包进行创建的,这个三个包都是一个公司出的,testthis包的内容没看全,看起来是devtools所有相关功能都是在这里实现的。 use_test() 可以安装目录文件创建tests文件及内容,还有NAMESPACE文件依赖的修改等 可以使用use_test('hello.R')生成制定文件的test文件,我看文件命名规则基本生成test-hello.R,context为hello。 test_that("multiplication works", { expect_equal(2 * 2, 4) }) 执行test()或者使用RStudio里的build菜单执行单元测试

Continue

网上最常用的R语言连接数据库的包是RMySQL,但是我看RMySQL推荐使用RMariaDB,RMySQL以后会不在维护。所以使用RMariaDB了,这个使用上应该没啥区别,因为他们都使用了DBI包,规范了数据库接口的定义。 结合上一篇讲全局变量的问题,我存在了options里代码如下 db_config <- getOption("db_config") con <- dbConnect(RMariaDB::MariaDB(), dbname=db_config$db, username=db_config$user, password=db_config$password, host=db_config$host) print(con) print(dbListTables(con)) dbDisconnect(con)

Continue

包初始化创建我是用的rstudio,创建的r package项目。 然后可以build菜单选择build source package,右侧的build窗口可以check,install,非常快的点击就完成了 也可以用命令做 R CMD build tpk R CMD CHECK R CMD INSTALL tpk 这里我傻了吧唧,命令行操作的时候, install 后面跟了个tar包全名,导致后边用install.package时候也是用的全名,导致查错误也每个结果。搞了半天发现名字不对。

Continue