c - Fast algorithm mapping int to monotonically increasing int subset -


i have encountered variations of problem multiple times, , became bottleneck in arithmetic coder implementation. given n (<= 256) segments of known non-negative size si laid out in order starting origin, , given x, want find n such

s0 + s1 + ... + sn-1 <= x < s0 + s1 + ... + sn

the catch lookups , updates done @ same frequency, , every update in form of increasing size of segment 1. also, bigger segment, higher probability looked or updated again.

obviously sort of tree seems obvious approach, have been unable come tree implementation satisfactorily takes advantage of known domain specific details.

given relatively small size of n, tried linear approaches, turned out considerably slower naive binary tree (even after optimization, starting of list numbers above half total)

similarly, tested introducing intermediate step remaps values in such way keep segments ordered size, make access faster used, added overhead exceeded gains.

sorry unclear title -- despite being basic problem, not aware of specific names it.

i suppose bst do... may try add new numeric member (int or long) each node keep sum of values of left descendants. you'll seek each item in approximately logarithmic time, , once item added, removed or modified you'll have update ancestors on returning path recursion. may apply self-organizing tree structure, example avl keep worst-case search optimal or splay tree optimize searches used items. take care update left-subtree-sums during rebalancing or splaying.


Comments

Post a Comment

Popular posts from this blog

angularjs - ADAL JS Angular- WebAPI add a new role claim to the token -

i have created angular spa webapi backend using adal js authentication.as there no roles in ad, need manually add role claims in order give users access different api controllers. the roles stored in database. expecting inject claim through call webapi after authentication ad. webapi code might this. identity.addclaim(new claim("role", "user")); var ticket = new authenticationticket(identity, props); var accesstoken = startup.oauthbeareroptions.accesstokenformat.protect(ticket); is possible replace adal idtoken new token? is viable solution or there other better way handle this? as initial token generated azuread, possible edit token add new claim? appreciated. graph api supporting group claims. see here: http://justazure.com/azure-active-directory-part-4-group-claims/ if @ examples on page, users assigned groups , app can check group in claims. in current version of portal, need app manifest , modify it.
Read more

php - CakePHP HttpSockets send array of paramms -

i problem when make request (i can request). $link = 'http://uri/path/?param1=1&sid=2&sid=3&sid=4' $http = $httpsocket = new httpsocket(); $res = $httpsocket->get($link); if check request pr($http); i see : [line] => /url/path/?param1=1&sid%5b0%5d=2&sid%5b1%5d=3&sid%5b2%5d=4 http/1.1 and i'm getting empty response because server doesn't know parameters sid%5b0%5d=2 when try send parameters array : $data = array('param1' => '1', 'sid' => array('2','3', '4')); i see same changes %5b0%5d - additional indexes. how fix it? unfortunately , can not change server side, if send request in browser, i'll normal response in json format. when make request, can parameters this: $param1 = $_get['param1']; $sid= $_get['sid']; tip: use diferente names parameters. have multiples sid. use sid1, sid2, sid3... update: can parameters this:
Read more

node.js - Using Node without global install -

i'm working on few node & electron (atom shell) projects , i'm curious how them work without user having install node globally. i've seen few applications including node directory in project contains node.exe binary. how go setting node project use binary? edit: thought should add, i've searched everywhere answer this, unrelated results.
Read more