[译]HAT-trie,缓存敏感字典树

12 Apr 2020 | Trie, Algorithm, Translation |

原文: https://tessil.github.io/2017/06/22/hat-trie.html

字典树 (也被称为前缀树) 是个有趣的怪物. 字典树是一种存储字符串的树形结构,一个节点的所有后代都共享相同的前缀. 这种结构可以进行快速的前缀查找, 例如查找所有以ap为前缀的单次, 并且由于共享前缀的特点,它可以采用紧凑的方式存储字符串.

跟大多数树形数据结构一样,前缀树的主流实现方法都存在缓存不友好的问题.在前缀节点之间遍历的每一步都可能会造成缓存缺失,这不利于进行快速查找。

本文中我们结合了传统字典树和缓存敏感哈希表,提出了缓存敏感的字典树:HAT-trie.

你可以从GitHub中找到 C++ 实现 ,以及一些HAT-trie同其他字典树和关联数据结构的 基准测试 .

接下来的章节, 我们首先更详细的介绍字典树的概念. 然后介绍 burst-trie 以及数组哈希表, 这些是HAT-trie所依赖的中间数据结构. 最后我们讲HAT-trie本身.

Continue Reading →

IRResolver(STL set重叠区间以及异构查询)

01 Mar 2020 | C/CPP, STL, Algorithm |

代码见 https://github.com/jiangzhuti/IRResolver

问题

有一些区间数据:

$ head data.txt 
3640-3610(s, sh)    O-H stretch, free hydroxyl     alcohols, phenols
3500-3200(s,b)      O–H stretch, H–bonded          alcohols, phenols
3400-3250(m)        N–H stretch                    1°, 2° amines, amides
3300-2500(m)        O–H stretch                    carboxylic acids
3330-3270(n, s)     –C≡C–H: C–H stretch            alkynes (terminal)
3100-3000(s)        C–H stretch                    aromatics
3100-3000(m)        =C–H stretch                   alkenes
3000-2850(m)        C–H stretch                    alkanes
2830-2695(m)        H–C=O: C–H stretch             aldehydes
2260-2210(v)        C≡N stretch                    nitriles

要求给出一个数值,输出所有包含该数值的区间信息。

分析

利用STL set构建查询树。需要注意两点:

  1. 支持按区间插入,按值查询(异构查询)
  2. 处理区间重叠

Continue Reading →

图染色(K-Coloring)问题

04 Feb 2020 | C/CPP, SAT-Resolver, Algorithm, graph |

代码见https://github.com/jiangzhuti/K-Coloring

问题

判断一个给定的包含n个顶点m条边的无向图能否用k种颜色给顶点染色,要求相邻两顶点颜色不同

分析

这是一个经典的SAT问题。解法是把问题转化成CNF子句,然后使用通用的SAT Resolver即可解决。

K-Coloring 问题包含以下三个约束条件:

  1. 一个顶点必须染某种颜色
  2. 一个顶点最多染一种颜色
  3. 一条边的两个顶点颜色不相同

Continue Reading →

理解asio中strand的用法

05 Jan 2019 | C/CPP, asio |

设想一个常见的场景,我们设计一个服务器,每当到来一个新的请求时,我们需要读写一个全局的共享对象。在多线程环境下,多个线程同时操作一个共享的对象是不安全的。因此,我们需要对共享对象的操作进行同步。通用做法是用锁来保护,如果对其操作全部在asio的回调函数中进行,那么通常会用一个strand来使回调之间同步执行,方法是调用strand.wrap(handler)或者asio::bind_executor(strand, handler)。这也是strand的常见用法。

要记住的是strand只是保证回调之间的同步。另一种场景下我们需要异步操作 本身 不能被多个线程同时执行。以最常见的为asio::tcp::socket为例,根据文档,socket对象的线程安全类型是:

Thread Safety

Distinct objects: Safe.

Shared objects: Unsafe.

即多个线程共享同一个socket对象时不保证线程安全。不过大部分情况我们不需要考虑线程安全的问题,因为我们通常会这样来使用(以下是简写):

Continue Reading →

关于C函数能否抛出异常的讨论

05 Jan 2019 | C/CPP, 异常 |

C语言在语言层面上没有“异常”的概念,也不提类似C++那样能抛出异常的手段。但是,如果在C++中调用C的函数,不能就此完全忽略异常检查。特别是自从C++11开始,不能钦定一个C函数调用是noexcept。至于为什么,下面说几个蛋疼的案例。

案例1

我们知道,通过extern "C",C++编译器完全可以导出一个C函数接口,尽管函数内部可能包含C++的调用。如果这些C++代码会抛异常,那么最终的C接口运行时也会抛出异常。代码如下:

Continue Reading →

C++奇技淫巧之访问private变量

17 Aug 2018 | C/CPP, 奇技淫巧 |

众所周知,C++中private成员只能在类内部访问,就算是继承也无法直接访问到。想在其他类/函数中访问private成员,几乎只能通过友元(friend)实现。由于友元是侵入性的,当你引用了第三方类库,又不能对其修改时,就没法利用友元了。

然而,C++作为世界上拥有特性最多的语言,特别是指针、模板等怪兽级特性,成为了许多人拿来挑战其中条条框框的武器,private禁咒也被各种形式突破。下面盘点一下访问private成员的各种奇技淫巧。

Continue Reading →

1 2 3