algorithm - what is the most memory efficient datastructure for maintaining a sordted <5k list of integers? -


i have many lists of sorted integers, of them less 3600 items each. i'd keep them in memory as possible, i'm looking space efficient datastructure.

most common operations inserts, membership testing , range queries.

the integers in 1 through 10 billion-range, though in theory there corner cases integers lower.

i've been looking @ skiplists, quite nice, feel there might more efficient structures out there.

this depends on access pattern , proportion of lookups respect modifications. when lookups more common modifications (in case, inserts apparently), quite common, can away sorted arrays give optimal memory efficiency.

if inserts more common, sorted arrays won't do, , have resort more complicated data structures. b-trees sound possible candidate given pack many nodes together, , not suffer linkage overhead as avls, skip-lists or red-black trees.

i think interesting investigate radix trees, if there happens lot of successive integers in lists, because such ranges "compressed" radix tree.

it worth noting bloom filter can further optimize membership queries. are, in way, space-efficient data structures membership queries, being probabilistic, can use them in combination other deterministic data structure, unless of course allowed return incorrect answers :-).


Comments

Post a Comment

Popular posts from this blog

assembly - 8086 TASM: Illegal Indexing Mode -

this question has answer here: illegal use of register in indirect addressing 1 answer i writing 8086 assembly program needs compile through tasm v3.1. running error can not seem fix. my data segment has following set purposes of keyboard input: parao label byte maxo db 5 acto db ? datao db 5 dup('$') what trying first character entered, first byte of datao: lea dx, datao mov bl, [dx] however, when attempt compile, error: **error** h5.asm(152) illegal indexing mode line 152 "mov bl, [dx]" any appreciated. if matters, running tasm through dosbox (my laptop running 64-bit win7) google hasn't come helpful answers. can post entirety of code if necessary. pretty sure reason can't use dx register pointer. try instead using [si], [di] or [bx]: lea bx, data0 mov al, [bx]
Read more

Java, LWJGL, OpenGL 1.1, decoding BufferedImage to Bytebuffer and binding to OpenGL across classes -

i've been attempting solve problem without luck. have 4 classes, main class, object class, sprite class , image loader class. i'm attempting load png using image loader , using method found here: http://www.java-gaming.org/topics/bufferedimage-to-lwjgl-texture/25516/msg/220280/view.html#msg220280 convert bytebuffer, , bind opengl. the image in it's own seperate resource folder. should being drawn this: ( http://i.imgur.com/j8gbu4c.png ) (32x32), i'm seeing white box has dimensions of image, not actual texture. if has idea of go fix i'd appreciate it. i'm new opengl , looking avoid using external library in order learn how actual code works. thanks. updated! to following, implemented suggestion provided vallentin, quad taking color of first pixel in image. i've attempted implementing image loader provided c.s here . i'm receiving error: javax.imageio.iioexception: error reading png image data @ com.sun.imageio.plugins.png.pngimagereader.r...
Read more

javascript - addthis share facebook and google+ url -

i attempting use addthis create simple url shares whichever current page user on when click share button. of right now, have twitter working. when user clicks, able see url populated in tweet box. when user clicks facebook or google+, url doesn't seem show in share box. <ul class="addthis_toolbox addthis_default_style "> <li><a class="addthis_button_facebook"><img src="/img/facebook-social.png" width="20" height="20" border="0" alt="share" /></a></li> <li><a class="addthis_button_twitter"><img src="/img/twitter-social.png" width="20" height="20" border="0" alt="share" /></a></li> <li><a class="addthis_button_google_plusone_share"><img src="/img/google-social.png" width="20" height="20" border="0" alt="s...
Read more