|
索引统计与 Python 字典
最近折腾索引引擎以及数据统计方面的工作比较多, 与 Python 字典频繁打交道, 至此整理一份此方面 API 的用法与坑法备案. 索引引擎的基本工作原理便是倒排索引, 即将一个文档所包含的文字反过来映射至文档; 这方面算法并没有太多花样可言, 为了增加效率, 索引数据尽可往内存里面搬, 此法可效王献之习书法之势, 只要把十八台机器内存全部塞满, 那么基本也就功成名就了. 而基本思路举个简单例子, 现在有以下文档 (分词已经完成) 以及其包含的关键词 - doc_a: [word_w, word_x, word_y]
- doc_b: [word_x, word_z]
- doc_c: [word_y]
将其变换为 - word_w -> [doc_a]
- word_x -> [doc_a, doc_b]
- word_y -> [doc_a, doc_c]
- word_z -> [doc_b]
写成 Python 代码, 便是 doc_a = {'id': 'a', 'words': ['word_w', 'word_x', 'word_y']}
doc_b = {'id': 'b', 'words': ['word_x', 'word_z']}
doc_c = {'id': 'c', 'words': ['word_y']}
docs = [doc_a, doc_b, doc_c]
indices = dict()
for doc in docs:
for word in doc['words']:
if word not in indices:
indices[word] = []
indices[word].append(doc['id'])
print indices
不过这里有个小技巧, 就是对于判断当前词是否已经在索引字典里的分支 if word not in indices:
indices[word] = []
可以被 dict 的 setdefault(key, default=None) 接口替换. 此接口的作用是, 如果 key 在字典里, 那么好说, 拿出对应的值来; 否则, 新建此 key, 且设置默认对应值为 default. 但从设计上来说, 我不明白为何 default 有个默认值 None, 看起来并无多大意义, 如果确要使用此接口, 大体都会自带默认值吧, 如下 for doc in docs:
for word in doc['words']:
indices.setdefault(word, []).append(doc['id'])
这样就省掉分支了, 代码看起来少很多. 不过在某些情况下, setdefault 用起来并不顺手: 当 default 值构造很复杂时, 或产生 default 值有副作用时, 以及一个之后会说到的情况; 前两种情况一言以蔽之, 就是 setdefault 不适用于 default 需要惰性求值的场景. 换言之, 为了兼顾这种需求, setdefault 可能会设计成 def setdefault(self, key, default_factory):
if key not in self:
self[key] = default_factory()
return self[key]
倘若真如此, 那么上面的代码应改成 for doc in docs:
for word in doc['words']:
indices.setdefault(word, list).append(doc['id'])
Posted at Jan 01 2014 - 05:16:40
Permanent Link:
/p/517
Load full text
|
Post tags:
Data Structure
Python
|
|
万能巧械 - 二叉检索树 [壹]
二叉检索树的查询与检索操作看这里 从二叉检索树中删除一个元素分多个步骤: 找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1. 下面是这一部分的实现 void remove_by(key_type const& key)
{
remove_by_from(key, &root);
}
void remove_at(int position)
{
remove_at_from(position, &root);
}
static void remove_by_from(key_type const& key, node** parent)
{
--((*parent)->load);
if (key < (*parent)->t.key()) {
remove_by_from(key, &((*parent)->left));
return;
}
if ((*parent)->t.key() < key) {
remove_by_from(key, &((*parent)->right));
return;
}
remove(parent);
}
static void remove_at_from(int position, node** parent)
{
--((*parent)->load);
int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
if (position < left_load) {
remove_at_from(position, &((*parent)->left));
return;
}
if (left_load < position) {
position = position - left_load - 1;
remove_at_from(position, &((*parent)->right));
return;
}
remove(parent);
}
static void remove(node** n);
这些函数都是 class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改. 找到了节点之后将会有下面 3 种情况 前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)
Posted at Jan 24 2012 - 05:42:01
Permanent Link:
/p/481
Load full text
|
Post tags:
Algorithm
Generic Programming
Order Statistic
B-tree
Data Structure
Template
C++
Binary Search Tree
|
|
万能巧械 - 二叉检索树 [零]
堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短 - 按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
- 随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
- 多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构
前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据 结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述. 较之堆更加全能的索引数据结构非 二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况. 首先还是把二叉树的架子给搭出来 template <typename T>
class binary_search_tree {
struct node {
T t;
node* left;
node* right;
int load;
explicit node(T const& rhs)
: t(rhs)
, left(NULL)
, right(NULL)
, load(1)
{}
};
node* root;
typedef typename T::key_type key_type;
public:
binary_search_tree()
: root(NULL)
{}
public:
void insert(T const& e);
void remove_by(typename T::key_type const& key);
void remove_at(int position);
T& element_by(typename T::key_type const& key);
T& element_at(int position);
};
Posted at Jan 23 2012 - 05:04:23
Permanent Link:
/p/479
Load full text
|
Post tags:
C++
Generic Programming
Data Structure
Binary Search Tree
Algorithm
Order Statistic
Template
|
|
单链表 给我翻过来
下面是一个简单的单链表节点结构 struct node {
int value;
struct node* next;
};
那么如何将这个链表反转过来呢? void reverse(struct node* head);下面采用递归的方式实现, 废话少说, 直接上代码 struct node** _reverse(struct node* n)
{
if (NULL != n->next)
*_reverse(n->next) = n;
return &(n->next);
}
void reverse(struct node* head)
{
*_reverse(head) = NULL;
}
上面的实现假定传入的 head 不会是空节点. 如果要检测, 可以加入一个判断 void reverse(struct node* head)
{
if (NULL != head)
*_reverse(head) = NULL;
}
下面来验证一下吧 #include <stdio.h>
struct node {
int value;
struct node* next;
};
void reverse(struct node* head);
void print_list(struct node const* head);
int main(void)
{
struct node a = { 0, NULL },
b = { 1, &a },
c = { 2, &b }; // c(2) -> b(1) -> a(0) -> NULL
print_list(&c);
reverse(&c); // changed to a(0) -> b(1) -> c(2) -> NULL
print_list(&a);
return 0;
}
void print_list(struct node const* head)
{
printf("[");
for (; NULL != head; head = head->next) {
printf(" %d", head->value);
}
printf(" ]\n");
}
struct node** _reverse(struct node* n)
{
if (NULL != n->next)
*_reverse(n->next) = n;
return &(n->next);
}
void reverse(struct node* head)
{
*_reverse(head) = NULL;
}
Posted at Dec 21 2011 - 04:59:53
Permanent Link:
/p/475
Load full text
|
Post tags:
C
Algorithm
Data Structure
|
|
日常的数据结构 - 堆的实现与第 K 最小堆
在 前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式. 从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如 +---+
| 4 |
+---+
/ \
+---+ +---+
| 5 | | 9 |
+---+ +---+
/ \
+---+ +---+
| 8 | | 5 |
+---+ +---+
这样一棵完全二叉树可以被转换成 .----.
/--. \
+---+---+---+---+---+---+-----
| - | 4 | 5 | 9 | 8 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是 .----.
/--. \
+---+---+---+---+---+---+-----
| 0 | 1 | 2 | 3 | 4 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如 .----.
/--. \
+---+---+---+---+---+---+-----
| - | 0 | 1 | 2 | 3 | 4 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升). 既然堆的逻辑结构是数组, 那么可以采用 std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架 template <typename _T, typename _Less>
class heap {
std::vector<_T> array;
_Less const less;
typedef typename std::vector<_T>::size_type size_type;
public:
heap()
: array(1) /* insert a placeholder, array[0] */
, less(_Less())
{}
void push(_T const& value);
_T pop();
};
Posted at Oct 07 2011 - 09:23:13
Permanent Link:
/p/441
Load full text
|
Post tags:
C++
Algorithm
Template
Heap
Order Statistic
Generic Programming
Data Structure
|
|
日常的数据结构 - 动态最值统计与堆
如果设计一个顺序统计系统, 需要动态向集合内添加元素, 又可以随时从集合中取得并 丢弃最小值. 由于集合中有集合会被移除, 因此接下来再次取最小值时如果重新扫一次集合, 时间开销会相当大. 在一般情形中, 若为了均衡时间开销, 需要考虑维护一个更复杂的数据结构. 这个数据结构建立在 满二叉树 (full binary tree)和 完全二叉树 (complete binary tree)的概念上. "满" 这个字眼提示在树的每一层都摆满了节点, 而这恰好又是个充要条件, 即如果一棵二叉树每一层都堆满了节点, 那么它就是满二叉树. 满二叉树的定义干脆就按节点个数来: 一棵二叉树如果深度为 K, 而拥有 2 K-1 个节点, 那么它就是一棵满二叉树. 如下面是 2 层和 3 层满二叉树, 分别拥有 3 个和 7 个节点 +---+
| a |
+---+ +---+
| a | .---' `---.
+---+ +---+ +---+
/ \ | b | | c |
+---+ +---+ +---+ +---+
| b | | c | / \ / \
+---+ +---+ +---+ +---+ +---+ +---+
| d | | e | | f | | g |
+---+ +---+ +---+ +---+
而如果一棵二叉树满足 - 除了最后一层, 其余层构成一棵满二叉树
- 最后一层从右起缺少 0 个或多个连续的节点
那么它就是一棵完全二叉树. 更直观一些, 将一个满二叉树的节点按照广度优先 (即逐层向下) 遍历的方式顺序编号, 编号从 1 开始 (而不是从 0 开始), 如
Posted at Oct 03 2011 - 13:01:06
Permanent Link:
/p/434
Load full text
|
Post tags:
Data Structure
Heap
Algorithm
Order Statistic
|
