Lucene 如何实现高性能 GroupBy <二>

逃离我推掉我的手 2022-02-26 16:24 135阅读 0赞

转载：[http://www.cnblogs.com/zengen/archive/2010/11/30/1892241.html][http_www.cnblogs.com_zengen_archive_2010_11_30_1892241.html]

紧接上一篇 [Lucene 如何实现高性能GroupBy <一>][Lucene _GroupBy] 的讲：Lucene--Util--PriorityQueue.cs

先给大家看一段代码，来源于PriorityQueue类

protected internal void  Initialize(int maxSize)
            {
                size = 0;
                int heapSize;
                if (0 == maxSize)
                // We allocate 1 extra to avoid if statement in top()
                    heapSize = 2;
                else
                    heapSize = maxSize + 1;
                heap = new System.Object[heapSize];
                this.maxSize = maxSize;
                
                // If sentinel objects are supported, populate the queue with them
                System.Object sentinel = GetSentinelObject();
                if (sentinel != null)
                {
                    heap[1] = sentinel;
                    for (int i = 2; i < heap.Length; i++)
                    {
                        heap[i] = GetSentinelObject();
                    }
                    size = maxSize;
                }
            }

这个方法做的最主要的一件事情就是初始化了一个名为heap的东东，这是个什么东东呢？它的作用何在？

e.g. protected internal System.Object\[\] heap;

看到这句大家应该清楚了heap是什么东东，它就是一个Object数组

我们再看看Initialize方法，此方法带了个参数，“int maxSize”，这个maxSize = pageSize\*pageIndex，现在大家应该明白了，heap = ScoreDoc\[\]，它是用来保存分数最大的maxSize条搜索结果，在Initialize方法中，我们给heap每一项的赋值为负无穷大值。

好，我们再来结合Collect方法的最后一句代码

e.g.

pqTop = (ScoreDoc)pq.UpdateTop();

pq是什么？pq = PriorityQueue，pq为PriorityQueue类对象，由此得知，在Collect方法中调用了PriorityQueue的UpdateTop方法，那我们就来看看PriorityQueue中的UpdateTop方法做了什么事情？

int i = 1;
                System.Object node = heap[i]; // save top node
                int j = i << 1; // find smaller child
                int k = j + 1;
                if (k <= size && LessThan(heap[k], heap[j]))
                {
                    j = k;
                }
                while (j <= size && LessThan(heap[j], node))
                {
                    heap[i] = heap[j]; // shift up child
                    i = j;
                    j = i << 1;
                    k = j + 1;
                    if (k <= size && LessThan(heap[k], heap[j]))
                    {
                        j = k;
                    }
                }
                heap[i] = node; // install saved node
    
                return heap[1];

这个方法主要作用就是比较每个DocID对应的Score的大小，将最大的前pageSize\*pageIndex个ScoreDoc保存在heap中，并返回最小的ScoreDoc。此处返回最小的ScoreDoc的作用是什么呢？请看如下代码：

if (score < pqTop.score || (score == pqTop.score && doc > pqTop.doc))
    {
    　　return;
    }

这段代码来自于Collect方法，当DocID对应的Score比heap中最小的Score还小的时候，不再进行分数大小比较，直接淘汰掉了，从而减少了分数大小比较操作，优化了性能，此句属于题外话。

好，讲到这里，我们已经对搜索结果集如何按照得分高低选取出前pageIndex\*pageSize条记录有了一定的了解，我们再回过头来看看，怎么保证每个公司对应的产品是该公司得分最高的产品？

首先，我来讲讲思路：

在Collect方法中，我们有个判断，如果某个公司的产品出现过，就把这个公司的ID缓存起来，下次再有产品对应的公司ID在缓存中存在，就不再往下走了，仅记录出现在次数，但是这样却保证不了某个公司得分最高的产品出现，所以现在我们这样来做，Collect方法中的判断不去掉，用来记录出现的次数，但是当某个产品对应的公司ID在缓存中存在，我们就不能在此处进行Return了，而是继续进入到PriorityQueue类中进行Score的比较，不过这时对于Score的比较与原本Score的比较又有些不同，怎么不同呢？

原本的Score比较是分数低的一律被排挤掉，仅保留分数高的，现在的Score比较是同一公司分数低的被同一公司分数高的替换掉，然后再进行高低分排序，说到这里，关键点来了，如何知道某个公司对应的ScoreDoc在heap中的位置，为什么要知道位置，刚刚前面说了，我们需要把同一公司分数低的Doc用该公司分数高的Doc替换，相当把heap\[i\]位置的值更新一下，所以我们需要记录某个公司对应的ScoreDoc在heap中的位置，这里我们就需要更改heap对象了，代码如下：

protected class GroupQueueElement
            {
                public string groupValue;
                public object queueValue;
    
                public GroupQueueElement(string gValue, object qValue)
                {
                    groupValue = gValue;
                    queueValue = qValue;
                }
            }
            protected GroupQueueElement[] heap;

由上述代码可知：heap = GroupQueueElement\[\]; GroupQueueElement为CompanyID（分组字段值）与ScoreDoc对应关系对象。

讲到这里，差不多就已经可以实现GroupBy了，最后一个关键点：高低分排序算法

private void  DownHeap()
            {
                int i = 1;
                System.Object node = heap[i]; // save top node
                int j = i << 1; // find smaller child
                int k = j + 1;
                if (k <= size && LessThan(heap[k], heap[j]))
                {
                    j = k;
                }
                while (j <= size && LessThan(heap[j], node))
                {
                    heap[i] = heap[j]; // shift up child
                    i = j;
                    j = i << 1;
                    k = j + 1;
                    if (k <= size && LessThan(heap[k], heap[j]))
                    {
                        j = k;
                    }
                }
                heap[i] = node; // install saved node
            }

这里用到了移位运算，用以快速的将heap中的分数进行排列，每一次的排列都会将分数最小的值放在heap\[1\]位置，用以返回，在Collect方法如果发现Doc对应的Score比heap中最小的分数还小时，就不再进行高低分排序。

我们前面说到，同一公司分数低的被同一公司分数高的替换掉再进行高低分排序时我们要注意了，移位起始值就不再是1了，而是被替换值在heap中的位置，所以我们还需要重载一下DownHeap方法，这些都很简单了，都是一些具体的实现方式了，原本想把实际的代码公布出来，但是考虑到里面有很多是根据具体需求来写的，懒得改代码了，这里也就不再公开具体代码，即然明白了原理，而且公布了一些比较关键地方的代码，我想实现起来应该没有什么大问题了，如果有其它疑问，可以以评论的方式来出现，欢迎大家来拍砖。

[http_www.cnblogs.com_zengen_archive_2010_11_30_1892241.html]: http://www.cnblogs.com/zengen/archive/2010/11/30/1892241.html
[Lucene _GroupBy]: http://www.cnblogs.com/zengen/archive/2010/11/24/1886244.html