《编程珠玑》习题-如何用位逻辑实现位向量

《编程珠玑》第一章提到了一个排序问题,具体需求抄在下面:

输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出:按升序排列的输入整数的列表。

约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化了。

整个解题的思路是通过位向量来进行排序,使用107个位来代表从0~107的数,如果文件中包含数n,则将第n位置为1, 输出的时候按序遍历每一位,如果该位为1就输出该位的序号,即可得到最后的排序序列。

书中实现位向量是通过整数数组来实现的,或许是因为c语言中没有位向量这个数据结构, c++中的标准模板库已经提供了bitset这个数据结构。 实现的原理如下:

由于一个整型是32位,所以只需定义一个长度为107/32的整型数组即可提供所需的二进制位,整数数组记为A。 从输入文件中读入一个整数,将这个整数整除32,得到的结果即是表示该数存在的二进制位记录在数组的哪个下标的整数中, 比如111,用111整除32得3,即代表该数存在的二进制位在数组下标为3的数,即A[3]中。 将读入的数模32,得到的数即为代表该数的标志位在A[3]中的位置,比如111模32结果为15, 则将A[3]的第15位置为1,即A[3]现在为00000000000000000100000000000000,即为32768 如此即可使用整型数组模拟位集合,比如读入的第二个数为127,127整除32为3,模32为31,则A[3]为10000000000000000100000000000000 代码如下:

//一个整型有32位
#define BITSPERWORD 32
//定义移位的长度,2的5次方为32
#define SHIFT 5
//定义取模的掩码
#define MASK 0x1F
//输入文件中整数的最大范围
#define N 10000000
//定义存储的数组
int a[1 + N/BITSPERWORD];
/*
 *根据参数i,设置对应的标志位的值
 *i>>SHIFT,i右移5位,相当于i/32
 *i & MASK,i和11111做与运算,得到i%32
 *1<<(i & MASK),1左移(i%32)位,将结果与a[i>>SHIFT]做或运算
 *即可设置整数i对应的标志位为1
 */
void set(int i)
{
	a[i>>SHIFT] |= (1<<(i & MASK));
}
/*
 *根据参数i,设置对应的标志位为0
 */
void clr(int i)
{
	a[i>>SHIFT] &= ~(1<<(i & MASK));
}
/*
 *根据参数i,判断对应的标志位是否为1
 */
int test(int i)
{
	return a[i>>SHIFT] & (1<<(i & MASK));
}

100个常用的vim命令中文版

这篇文章被标题党冠以《程序员应该知道的100个vim命令》在网上流传,其实这些命令对速成有些帮助, 在加深对vim的理解方面没有太大用处。想用好查找替换功能就必须能熟练写正则表达式, 想方便的操作文件就必须对shell命令有了解,想写程序方便就要装插件模拟IDE的功能, 有些功能可能还要自己动手写shell脚本或者插件在vim中进行调用

从我自己的经验看来,想用好vim,就必须理解vim命令的设计风格,看几遍vim帮助文档,经常使用, 学习vimscript,没有任何可以速成的方法

这个文章作为tips也不合格,完全不如这篇 Best of VIM Tips, gVIM's Key Features zzapper。 作者说自己是一个有15年vi经验和7年vim经验并且还在继续学习的人

翻译到一半觉得这篇文章完全没有翻译的价值,不过还是继续翻译完了,地址: 常用的vim命令


vim中添加快速单词查询功能

本文内容转载整理自网上的文章,Vim - 闲耘™.Wiki > 其它技巧 > 翻译取词,原始作者不详

从github上下载的一些开源项目提供的文档是英文的,在vim里面看文档遇到不认识的单词还得用鼠标取词去查询, 特别不方便。于是去网上找给vim添加便捷单词查询功能的方法,整理在下面

首先需要安装一个shell下运行的词典工具stardict,可以使用下面的命令来安装

sudo apt-get install sdcv stardict stardict-tools 

安装完成后可以在shell里面使用sdcv命令来查询单词,stardict并没有自带字典文件,需要自己去下载字典文件, 可以用搜索引擎搜索stardict-langdao-ec-gb-2.4.2.tar.bz2来寻找字典数据包的下载地址, 将下载下来的包解压后放入/usr/share/stardict/dic中,这里可能会碰到权限问题,可以用命令来完成。 现在使用sdcv命令查询单词就能出现内容了

ubuntu:~1 sdcv terminal
Found 1 items, similar to terminal.
-->朗道英汉字典5.0
-->terminal
['tә:minәl]
n. 终端机, 终点, 末端, 极限, 终点站
a. 终点的, 定期的, 致死的, 结尾的, 末端的, 晚期的
【计】 终端; 终端设备
【化】 接线端
【医】 终末的, 末端, 端
【经】 终站, 终点, 定期
  

下面就是给vim添加命令,让vim调用shell命令去查询单词,把结果显示到vim中,在vimrc中添加下面的函数, 需要查词的时候把光标移动到要查的词内,默认使用<leader>f进行查询,在左侧会打开一个窗口,显示查询结果。 快捷键和窗口的设置都可以通过修改下面的函数来进行自定义。网上提供的函数代码,打开查询结果的窗口后光标也会跟随到新窗口去, 还需要再通过命令跳转回文本窗口,不是很方便。我在函数后面加了一行命令 "wincmd p",来跳转回刚才的窗口,这样查词就方便多了

function! Mydict()
"执行sdcv命令查询单词的含义,返回的值保存在expl变量中
let expl=system('sdcv -n ' . expand("<cword>"))
"在每个窗口中执行命令,判断窗口中的文件名是否是dict-tmp,如果是,强制关闭
windo if expand("%")=="dict-tmp" |q!|endif	
"纵向分割窗口,宽度为25,新窗口的内容为dict-tmp文件的内容
25vsp dict-tmp
"设置查询结果窗口的属性,不缓存,不保留交换文件
setlocal buftype=nofile bufhidden=hide noswapfile
"将expl的内容显示到查询结果窗口
1s/^/\=expl/
"跳转回文本窗口
wincmd p
endfunction
"按键绑定,将调用函数并执行
nmap <leader>f :call Mydict()<CR>

JQuery DataTables插件中文文档

下面内容翻译自官网: DataTables (table plug-in for jQuery) 是一个jQuery的表格插件。 是以渐进增强理念为基础构建的一个高度灵活的工具,可以在任何HTML表格上实现高级交互控制。 抽时间将帮助文档翻译成了中文版,地址: JQuery-DataTables插件中文文档

主要特点:

  1. 可变长度分页
  2. 即时表格数据过滤
  3. 与数据类型自动检测相结合的多列排序
  4. 智能处理列宽
  5. 可以从几乎任何数据源加载数据(DOM,Javascript array,Ajax file and server-side processing)
  6. 表单视图的滚动配置
  7. 完全国际化
  8. jQuery UI ThemeRoller支持
  9. 健壮性,背后是2900项单元测试
  10. 丰富的插件
  11. 免费
  12. 表格状态保持
  13. 隐藏列
  14. 动态创建表格
  15. Ajax自动加载数据
  16. 自定义DOM元素的位置
  17. 单列过滤
  18. 自定义的分页类型
  19. 非侵入式的DOM交互
  20. 高亮排序的列
  21. 先进的数据源控制
  22. 提供商业支持
  23. 提供屏幕阅读器和键盘支持
  24. 压缩后70K,gzip压缩后20k
  25. 多种扩展插件支持
  26. 丰富的文档
  27. 130多个样例

—  原创作品许可 — 署名-非商业性使用-禁止演绎 3.0 未本地化版本 — CC BY-NC-ND 3.0   —