Mailing-List: contact user-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@couchdb.apache.org
Received-SPF: pass (nike.apache.org: domain of wmertens@cisco.com designates
 144.254.15.119 as permitted sender)
Message-Id: <6E4DC2A7-6EA0-4826-8462-D313180F5751@cisco.com>
From: Wout Mertens <wmertens@cisco.com>
To: user@couchdb.apache.org
In-Reply-To: <07C64F71-EED4-439C-B08C-8B09EB5621FA@cisco.com>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Apple Message framework v930.3)
Subject: Re: Obtaining unique values from a view
Date: Thu, 5 Mar 2009 17:45:23 +0100
References: <55fad2460903030527r1295a39bl675478e8a9c5266d@mail.gmail.com>
 <3EA1C6DC-6331-4068-A89C-DBC462D0B890@cisco.com>
 <55fad2460903030558r34a2d6b9j5eda578f6002cca4@mail.gmail.com>
 <64BABFD7-8543-4762-B349-688E76ED6DB2@cisco.com>
 <92E0BD49-BD57-4CBD-B0BD-2A8391C00E81@apache.org>
 <DB5E1F44-0422-40E7-A5FB-F5397FD56A52@cisco.com>
 <e282921e0903030900y3c79aafbw5e5f09d60c8c9524@mail.gmail.com>
 <148EE677-9FB0-413C-B0D1-7B84C3BAF811@cisco.com>
 <e282921e0903031828w34db3aeavc3b9ef4ced732ca8@mail.gmail.com>
 <07C64F71-EED4-439C-B08C-8B09EB5621FA@cisco.com>

On Mar 5, 2009, at 4:59 PM, Wout Mertens wrote:

> Actually, I just did some tests around this, and it turns out that  
> if you always query with group=true, CouchDB never runs the final  
> rereduce!

So based on this, I created this reduce function for reducing a maps  
emit(key,value) to unique values per key:

function(k,v,r) {
	function unique_inplace(an_array) {
		var first = 0;
		var last = an_array.length;
		// Find first non-unique pair
		for(var firstb; (firstb = first) < last && ++first < last; ) {
			if(an_array[firstb] == an_array[first]) {
				// Start copying, skipping uniques
				for(; ++first < last; ) {
					if (!(an_array[firstb] == an_array[first])) {
						an_array[++firstb] = an_array[first];
					}
				}
				// firstb is at the last element of the new array
				++firstb;
				an_array.length = firstb;
				return;
			}
		}
	}

	if(r) {
		var arr=[];
		for (var i=0; i<v.length; i++) {
			arr=arr.concat(v[i]);
		}
		arr=arr.sort();
		unique_inplace(arr);
		return(arr);
	} else {
		var arr=v.sort();
		unique_inplace(arr);
		return(arr);
	}
}

It's not optimal yet, ideally the if(r) section should use an n-way  
mergesort+uniq since it receives sorted arrays as values. But this  
also works :).

Thoughts?

Wout.