stl的容器库非常强大,但是为了要兼容各种元素类型,采用了模板进行泛化,这样的好处就是使用非常的方便,但是编译器会对使用到的每种类型都进行一遍实例化,用的类型太多的话不仅影响编译速度而且生成的可执行文件也很冗余。
因此,TBOX在设计容器架构的时候,引入tb_item_func_t
类型,来设置容器使用的成员类型,这样在实现容器通用性的同时,也不会产生过的冗余,而且容器接口操作上,同样相当的便利。
可以先看个简单使用哈希的例子:
/* 初始化hash, 哈希桶大小8
* 键:大小写敏感字符串
* 值:long整型
*/
tb_hash_map_ref_t hash = tb_hash_map_init(8, tb_item_func_str(tb_true), tb_item_func_long());
if (hash)
{
// 设置键值对:"key" => 123
tb_hash_map_set(hash, "key", (tb_pointer_t)123);
// 获取值
tb_long_t value = (tb_long_t)tb_hash_map_get(hash, "key");
// 退出hash
tb_hash_map_exit(hash);
}
/* 初始化hash, 哈希桶大小: TB_hash_map_BULK_SIZE_MICRO
* 键:tb_struct_xxxx_t 结构体类型,内存数据由hash内部自己维护, 后面两个参数设置成员的释放回调函数
* 值:true类型,永远是tb_true, 这种hash相当于stl的set<tb_struct_xxxx_t>,内部会去优化掉value占用的内存
*/
tb_hash_map_ref_t hash = tb_hash_map_init(TB_hash_map_BULK_SIZE_MICRO, tb_item_func_mem(sizeof(tb_struct_xxxx_t), tb_null, tb_null), tb_item_func_true());
if (hash)
{
// 初始化tb_struct_xxxx_t
tb_struct_xxxx_t xxxx = {0};
// 设置键值对:xxxx => tb_true
tb_hash_map_set(hash, &xxxx, (tb_pointer_t)tb_true);
// 判断键是否存在
if (tb_hash_map_get(hash, &xxxx))
{
// ...
}
// 退出hash
tb_hash_map_exit(hash);
}
/* 初始化hash, 哈希桶大小使用默认大小: 0
* 键:大小写不敏感字符串
* 值:uint8整型
*/
tb_hash_map_ref_t hash = tb_hash_map_init(0, tb_item_func_str(tb_false), tb_item_func_uint8());
if (hash)
{
// 设置键值对:"key" => 123
tb_hash_map_set(hash, "key", (tb_pointer_t)123);
// 获取u位整型键值
tb_uint8_t value = (tb_uint8_t)tb_hash_map_get(hash, "key");
// 退出hash
tb_hash_map_exit(hash);
}
TBOX提供了各种常用算法,对容器中的元素进行各种操作,这里主要介绍下排序和查找算法。
排序算法目前支持如下几种:
tb_quick_sort
tb_heap_sort
tb_insert_sort
tb_bubble_sort
并且提供通用的tb_sort
接口,对各种排序算法进行自动适配,使得任何情况下,性能都是最优的。
例如:
xmake的工程描述文件,摈弃了makefile的繁琐复杂,借鉴了premake的简洁明了,原生支持lua脚本,使得更加的灵活、方便扩展。
工程默认描述文件名为xmake.lua,支持多级目录嵌套,也可以通过以下命令,指定其他文件作为工程描述文件:
xmake -f /tmp/xxx.lua
xmake --file=xxx.lua
下面先来看一个最简单的例子:
-- 添加一个名为demo的目标到工程
target("demo")
-- 设置目标程序类型为二进制可执行程序,一般为console的终端命令行程序
set_kind("binary")
-- 添加src目录下的所有c文件
add_files("src/*.c")
怎么样简单吧,这样就已经完成了一个最简单的工程描述。。
Bloom Filter是由Bloom在1970年提出的一种快速查找算法,通过多个hash算法来共同判断某个元素是否在某个集合内。可以用于网络爬虫的url重复过滤、垃圾邮件的过滤等等。
它相比hash容器的一个优势就是,不需要存储元素的实际数据到容器中去来一个个的比较是否存在。 只需要对应的位段来标记是否存在就行了,所以想当节省内存,特别适合海量的数据处理。并且由于省去了存储元素和比较操作,所以性能也比基于hash容器的高了很多。
但是由于bloom filter没有去比较元素,只通过多个hash来判断唯一性,所以存在一定的hash冲突导致误判。误判率的大小由hash函数的个数、hash函数优劣、以及存储的位空间大小共同决定。
并且删除也比较困难,解决办法是使用其变种,带计数的bloom filter,这个这里就不多说了。
对于bloom filter算法的实现,相当简单: 首先分配一块固定的连续空间,大小是m个比特位(m/8+1个字节),然后再提供k个不同hash函数,同时对每个元素进行计算位索引。如果每个位索引对应的位都为1,则存在该元素,否则就是不存在。
可以看出,如果判断为不存在,那么肯定是不存在的,只有在判断为存在的时候,才会存在误判。
bloom filter主要的难点其实在于估算: 保证指定误判率的情况下,到底需要多少个hash函数,多少的存储空间。