Heart.X.Raid
- 浏览: 888109 次
- 性别:
- 来自: 武汉
-
最新评论
-
小宇宙_WZY：
膜拜一下大神，解决了我一个大问题，非常感谢 orz
【解惑】深入jar包：从jar包中读取资源文件 -
JKL852qaz：
感谢，遇到相同的问题！
【解惑】深入jar包：从jar包中读取资源文件 -
lgh1992314：
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991：
说的都有道理，protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991：
...
【总结】String in Java
文章列表
普通的方法很简单，首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为O(L+L/2)=O(3L/2)。
能否再优化一下这个时间复杂度呢？有一个很巧妙的方法：设置两个指针* fast、*slow都指向单链表的头节点。其中* fast的移动速度是* slow的2倍。当* fast指向末尾节点的时候，slow正好就在中间了。
C源代码如下：
void locate(LinkedList *head){
LinkedList *fast, *slow;
fast=slow=head;
...
Lucene使用文件扩展名标识不同的索引文件。如.fnm文件存储域Fields名称及其属性，.fdt存储文档各项域数据，.fdx存储文档在fdt中的偏移位置即其索引文件，.frq存储文档中term位置数
据，.tii文件存储term字典，.tis文件存储term频率数据，.prx存储term接近度数据，.nrm存储调节因子数据，另外
segments_X文件存储当前最新索引片段的信息，其中X为其最新修改版本，segments.gen存储当前版本即X值。
本系列文章将详细介绍的这些文件的数据存储细节。下面的图描述了一个典型的lucene索引文件列表：
它们的关系图则如下所示：
...
注意，本专题内容参见《http://lucene.apache.org/java/3_0_1/fileformats.html
》
深入了解Lucene的磁盘索引文件，可以使我们对IR系统底层数据存储结构有一个深刻的认识。在《索引文件格式》这一专题中，我们将详细探讨
Lucene 3.0索引数据在磁盘上的存储格式，并通过一个实例进一步理解这些格式。但首先，我们必须准备点Lucene 索引文件格式的基础知识。
★ Lucene 自定义的基本数据类型
【Byte】
由8 bits组成的基本数据类型。所有其他的数据类型都是一个byte ...
★ .frq
词语频率数据
文件 .prx 词语位置数据文件
1、frq 保存了
词语所在文档的文档列表(docID)和该词语出现在文档中的频率信息。
FreqFile (.frq) -->
<TermFreqs, SkipData>
...
Terms数据
磁盘文件存储细节
从这篇开始，已经涉及到倒排索引表的信息存储问题了。我们都知道倒排索引表中的Dictionary有许多不同的terms组成，Lucene关于这些terms数据的存储，就放在磁盘的.tii和.tis文件中。
★ .tii
词典
索引文件 .tis 词典数据文件
1、tii 保存了tis中每
隔
IndexInterval个词的位置信息，这是为了加快对词典文件tii中词的查找速度
具体结构如下：
TermInfoIndex (.tii)--> TIVersion, I ...
数据规模分析
不考虑操作系统的区别，通常将C++中的一个整型变量认为4bytes。那么1亿整型需要400M左右的内存空间。当然，就现代PC机而言，连续开辟400M的内存空间还是可行的。因此，下面的讨论只考虑在内存中的情况。为了讨论方便，假设M=1亿，N=1万。
用大拇指想想
略微考虑一下，使用选择排序。循环1万次，每次选择最大的元素。源代码如下：
//解决方案1，简单选择排序
//BigArr[]存放1亿的总数据、ResArr[]存放1万的总数据
void solution_1(int BigArr[], int ResArr[] ){
...
1、经典最长平台算法
已知一个已经从小到大排序的数组，这个数组中的一个平台(Plateau)就是连续的一串值相同的元素
，并且这一串元素不能再延伸。例如，在
1,2,2,3,3,3,4,5,5,6中[1]、[2,2]、[3,3,3]、[4]、[5,5]、[6]都是平台。是编写一个程序，接受一个数组，把这个数组中最长的平台找出
来。在上面的例子中3,3,3就是该数组中最长的平台。
【说明】
这个程序十分简单，但是要编写好却不容易，因此在编写程序时应该考虑下面
几点：
(1) 使用的变量越少越好；
(2) 把数组的元素每一个都只查一次就得到结果；
(3) 程序语 ...
GCC介绍
在为Linux开发应用程序时，绝大多数情况下使用的都是C语言，因此几乎每一 位Linux程序员面临的首要问题都是如何灵活运用C编译器。目前Linux下最常用的C语言编译器是GCC（GNU Compiler Collection），它是GNU项目中符合ANSI C标准的编译系统，能够编译用C、C++和Object C等语言编写的程序。GCC不仅功能非常强大，结构也异常灵活。最值得称道的一点就是它可以通过不同的前端模块来支持各种语言，如Java、 Fortran、Pascal、Modula-3和Ada等。
开放、自由和灵活是Linux的魅力所在，而这一点在GCC上的体 ...
注意：以下文章是参见http://lucene.apache.org/java/3_0_1/fileformats.html#Fields
和实践中读取文件内容概括总结出来的。
Fields数据磁盘文件存储细节
Lucene 的数据域在内存中组织成Document和Field数据结构。每次建立索引的Docume ...
1.5 IndexWriter的关闭细节
IndexWriter索引器创建内存索引的整体流程在前几篇文章中已经详细阐述了，当我们利用IndexWriter创建完内存索引表之后，剩下的工作就只剩下关闭IndexWriter了。IndexWriter在关闭的时候除了清理内存中的对象之外，还有一个非常重要的工作，就是把内存要存储的信息(需要保存的Fields信息，倒排索引表等)写入Lucene的磁盘索引文件。
关于Lucene的每个磁盘索引文件我们会用一个专题来系列阐述，这里只是了解一下写文件的流程。
◆ IndexWriter. optimize()
在《索 ...
题目：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为
2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。
分析：
既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法
（请见《桶排序
》）：
思想：将整形的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。
第一步:把10G整数每2G读入一次内存，然后一次遍历这536 ...
《桶排序
》中我们能够看到，数据值的范围越大，可能需要桶的个数也就越多，空间代价也就越高。对于上亿单位的关键字，桶排序是很不实用的。基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。
多关键字排序问题(类似于字典序)：
我们先看看扑克牌的例子。一张牌有两个关键字组成：花色(桃<心<梅<方)+面值(2<3<4<...<A)。假如一张牌的大小首先被花色决定，同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。
(1) 首先按照花色对所有牌进行稳定排序，这样就可以将 ...
从《基于比较的排序结构总结 》中我们知道：全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*logN)。但确实存在更快的算法。这些算法并不是不用“比较”操作，也不是想办法将比较操作的次数减少到 logN。而是利用对待排数据的某些限定性假设 ，来避免绝大多数的“比较”操作。桶排序就是这样的原理。
桶排序的基本思想
假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M ...
★ 基于“比较”操作的内部排序性能大PK
我们首先总结一下《排序结构专题1-4》中的十种方法的性能((N个关键字的待排序列))：
排序方法
平均时间
最坏时间
辅助存储空间
稳定性
直接插入排序
O(N^2)
O(N^2)
O(1)
√
折半插入排序
O(N^2)
O(N^2)
O(1)
√
希尔排序
...
归并排序 O(N*logN) 是另一种效率很高的排序方法。"归并"的含义就是将两个或两个以上的有序表组合成一个有序表。加入两个有序表的长度分别为m、n，则一次归并的时间复杂度为O(m+n)。
我们可以用"归并"的思想来实现排序。假如待排序列含有n个关键字，则可看成是n个有序的子序列，每个序列长度为1，然后两两归并，得到[n/2]个长度为2或1的子序列，在两两归并....，知道得到一个长度为n的有序序列为止。这就是2-路归并算法。
下图就是2-路归并排序的一个例子：
我们可以用分治的思想解决归并排序，给定一个有N个关键字的有序序列 ...