ocaml - Data structure for occurrence counting in long tail distribution -

-

i have big list of elements (tens of millions). trying count number of occurrence of several subset of these elements. occurrence distribution long-tailed.

the data structure looks (in ocaml-ish flavor):

type element_key type element_aggr_key  type raw_data = element_key list  type element_stat = {      occurrence : (element_key, int) hashtbl.t; }  type stat = {     element_stat_hashtable : (element_aggr_key, element_stat) hashtbl.t; }

element_stat use hashtable key each elements , value integer. however, inefficient because when many elements have single occurrence, occurrence hashtable resized many times. cannot avoid resizing occurrence hashtable setting big initial size because there many element_stat instances (the size of hashtable in stat big).

i know if there more efficient (memory-wise and/or insertion-wise) data structure use-case. found lot of existing data structure trie, radix tree, judy array. have trouble understanding differences , whether fit problem.

what have here table mapping element_aggr_key tables in turn map element_key int. practical purposes, equivalent single table maps element_aggr_key * element_key int, do:

type stat = (element_aggr_key * element_key, int) hashtbl.t

then have single hash table, , can give huge initial size.


Comments

Post a Comment

Popular posts from this blog

python - Subclassed QStyledItemDelegate ignores Stylesheet -

-
i'm trying subclass qstyleditemdelegate remove focus rectangle in qcombobox . even though i'm calling base implementation of paint function , nothing else, result different. looks if parts of style-sheet influence bounding box of item taken consideration. class pstyleditemdelegate(qstyleditemdelegate): def __init__(self, *args, **kwds): super(pstyleditemdelegate, self).__init__(*args, **kwds) def paint(self, *args, **kwargs): qstyleditemdelegate.paint(*args, **kwargs) what have paint unmodified qstyleditemdelegate ? as suggested tried replacing pyside pyqt4 , works, appears bug. update pyside 1.1.2 1.2.1 result same. unfortunately switch breaks other parts of code, if there no other suggestions i'm going accept answer. edit bug tracked here
Read more

java - HttpClient 3.1 Connection pooling vs HttpClient 4.3.2 -

-
i have used httpclient3.1(java) connection pooling below : import org.apache.commons.httpclient.httpclient; import org.apache.commons.httpclient.multithreadedhttpconnectionmanager; import org.apache.commons.httpclient.params.httpclientparams; import org.apache.commons.httpclient.params.httpmethodparams; import org.apache.log4j.logger; public class httpclientmanager { private static logger logger = logger.getlogger(httpclientmanager.class); private static multithreadedhttpconnectionmanager connectionmanager = new multithreadedhttpconnectionmanager(); private static httpclientparams clientparams = new httpclientparams(); static { try { clientparams.makelenient(); clientparams.setauthenticationpreemptive(false); clientparams.setparameter(httpmethodparams.so_timeout, new integer(30000)); // set so_timeout clientparams.setparameter(httpmethodparams.head_body_check_timeout, new integer(3000)); // head responses ...
Read more

node.js - StackOverflow API not returning JSON -

-
i using node.js script gather data stackoverflow. know responses gzipped, put code in should take care of that. script follows: var request = require('request'); var zlib = require('zlib'); function getstackoverflowresponse(url, callback){ request(url, {encoding: null}, function(err, response, body){ if(response.headers['content-encoding'] == 'gzip'){ zlib.gunzip(body, function(err, dezipped) { callback(dezipped); }); } else { callback(body); } }); } var url = "https://api.stackexchange.com/docs/questions#pagesize=2&order=desc&min=2014-01-04&max=2014-02-02&sort=activity&tagged=apigee&filter=default&site=stackoverflow&run=true"; getstackoverflowresponse(url, function(questions) { console.log(questions); }); instead of getting json output, i'm getting following response: buffer 0d 0a 0d 0a 0d 0a 0d 0a 3c 21 44 4f 43 54 59 50 45 20 48...
Read more