IWETHEY v. 0.3.0 | TODO
1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

IWETHEY Home / IWETHEY Board / Theory and Practice of Programming Forum / For various values of "sparse"
Post #183,603
by tuberculosis
Picture of tuberculosis
11/8/04 6:57:18 PM
Reply
New For various values of "sparse"
its only 1/3 populated and the gaps are uneven. Furthermore, SSN numbers are not issued sequentially. The first three digits have geographic significance.

Furthermore, people die in random order.




"The significant problems we face cannot be solved at the same level of thinking we were at when we created them."     --Albert Einstein

"This is still a dangerous world. It's a world of madmen and uncertainty and potential mental losses."     --George W. Bush
Post #183,612
by ben_tilly
11/8/04 7:45:36 PM
Reply
New Unless you have a lot of knowledge...
that isn't boiling down to anything that gives you a big win. Not when 300 million pointers takes that much space.

The knowledge that it is "gap-y" could provide a space win, but only at some performance cost. You'd have to store the data in carefully compressed form and then decompress before using. For instance you could have a table that maps every 64K block of social security numbers to a block of data, which has Scott's format stored using a standard kind of compression. To lookup a social security number you have to decompress the appropriate block then look up your social security number.

Well filled-in stretches and gaps should both compress well. However now every lookup involves decompressing a block of data rather than just a bitmap. This can only be recommended as a win if the data is seriously uneven and 128 MB of RAM simply can't be done.

Given the cost of RAM, I'd go with Scott's solution.

Cheers,
Ben
I have come to believe that idealism without discipline is a quick road to disaster, while discipline without idealism is pointless. -- Aaron Ward (my brother)
     Finding decent programmers - (tuberculosis) - (56) - Nov. 8, 2004, 01:41:48 PM EST
         well.. - (deSitter) - Nov. 8, 2004, 01:59:47 PM EST
         Not surprising. - (admin) - (35) - Nov. 8, 2004, 02:20:40 PM EST
             Don't agree - (tuberculosis) - (34) - Nov. 8, 2004, 03:15:09 PM EST
                 Hire Jake - (deSitter) - Nov. 8, 2004, 03:18:47 PM EST
                 Re: Don't agree - (admin) - (22) - Nov. 8, 2004, 03:27:22 PM EST
                     Oh yeah - we want one scripting language - (tuberculosis) - (21) - Nov. 8, 2004, 03:46:18 PM EST
                         Please don't ask the one about the manhole covers. :-/ - (Another Scott) - (1) - Nov. 8, 2004, 03:50:34 PM EST
                             Otherwise known as... - (admin) - Nov. 8, 2004, 04:17:49 PM EST
                         Shell scripting isn't the same thing at all. - (admin) - (9) - Nov. 8, 2004, 04:04:34 PM EST
                             I said it was rhetorical - (tuberculosis) - (1) - Nov. 8, 2004, 04:35:33 PM EST
                                 Don't you mean, "rederickal"? - (admin) - Nov. 8, 2004, 04:47:36 PM EST
                             Admin, I'd like a copy of the CD or the ISO. -NT - (folkert) - (6) - Nov. 28, 2006, 12:03:24 AM EST
                                 I'll throw a copy up on my site. - (admin) - (5) - Nov. 28, 2006, 12:24:31 AM EST
                                     I wonder if that CD would be good as a VMWare image - (tonytib) - Nov. 28, 2006, 02:02:23 AM EST
                                     When ever. Its a *NOT* short term thing. -NT - (folkert) - Nov. 28, 2006, 02:08:16 AM EST
                                     Re: I'll throw a copy up on my site. - (admin) - (2) - Nov. 28, 2006, 12:04:29 PM EST
                                         Interesting. - (folkert) - (1) - Nov. 28, 2006, 03:58:54 PM EST
                                             Enjoy. -NT - (admin) - Nov. 28, 2006, 04:51:52 PM EST
                         Potentially sparse? I don't think so... - (ben_tilly) - (6) - Nov. 8, 2004, 05:29:51 PM EST
                             I took the ones that start with 0 into account. - (admin) - (2) - Nov. 8, 2004, 05:42:36 PM EST
                                 I was referring to the step where you... - (ben_tilly) - (1) - Nov. 8, 2004, 05:49:44 PM EST
                                     Ah, gotcha. Good point. -NT - (admin) - Nov. 8, 2004, 06:21:56 PM EST
                             For various values of "sparse" - (tuberculosis) - (1) - Nov. 8, 2004, 06:57:18 PM EST
                                 Unless you have a lot of knowledge... - (ben_tilly) - Nov. 8, 2004, 07:45:36 PM EST
                             Re: social security numbers can start with 0 - (a6l6e6x) - Nov. 9, 2004, 02:08:24 AM EST
                         Re: Oh yeah - we want one scripting language - (ubernostrum) - (1) - Nov. 29, 2006, 12:34:54 AM EST
                             IRLRPD. (new thread) - (Another Scott) - Nov. 29, 2006, 07:50:27 AM EST
                 NEED to be fixed or MAY need to be fixed? - (ben_tilly) - (1) - Nov. 8, 2004, 06:05:13 PM EST
                     MAY - (tuberculosis) - Nov. 8, 2004, 06:54:34 PM EST
                 you dont sell fish anymore, who cares if its fresh? - (daemon) - Nov. 8, 2004, 06:36:54 PM EST
                 Reversing words is trickier than chars - (Arkadiy) - (6) - Nov. 8, 2004, 08:34:57 PM EST
                     read the post above yours :-) - (daemon) - Nov. 8, 2004, 09:00:47 PM EST
                     You're missing an obvious and good solution - (tuberculosis) - (4) - Nov. 8, 2004, 09:26:37 PM EST
                         ohhh - (Arkadiy) - Nov. 8, 2004, 09:31:04 PM EST
                         An obvious but NOT necessarily good solution - (ben_tilly) - (2) - Nov. 8, 2004, 10:31:24 PM EST
                             It gives the results I expect - (tuberculosis) - (1) - Nov. 8, 2004, 11:36:56 PM EST
                                 I was assuming... - (ben_tilly) - Nov. 9, 2004, 11:24:29 AM EST
         Well it helps if you learn to spell it - (ben_tilly) - (10) - Nov. 8, 2004, 02:25:25 PM EST
             I think you'd pass - (tuberculosis) - (9) - Nov. 8, 2004, 03:32:34 PM EST
                 RemoveSpaces - (Arkadiy) - Nov. 8, 2004, 05:24:13 PM EST
                 I might pass at that... - (ben_tilly) - (7) - Nov. 8, 2004, 05:51:54 PM EST
                     Wife's-pathology interviews? >:-) -NT - (Another Scott) - (3) - Nov. 8, 2004, 05:58:05 PM EST
                         Yes, she'll be a pathological expert -NT - (ben_tilly) - (2) - Nov. 8, 2004, 06:56:10 PM EST
                             wow! goatrope her into a trip east - (daemon) - (1) - Nov. 8, 2004, 09:03:34 PM EST
                                 That's up to her - (ben_tilly) - Nov. 8, 2004, 10:32:59 PM EST
                     If you do decide to come here - (tuberculosis) - (2) - Nov. 8, 2004, 06:50:17 PM EST
                         Get yourself enough iwetheyers in your dept... - (FuManChu) - (1) - Nov. 8, 2004, 06:54:20 PM EST
                             Imagine what PARC might have done - (tuberculosis) - Nov. 8, 2004, 06:59:26 PM EST
         I can answer all those questions. - (jake123) - (3) - Nov. 8, 2004, 02:39:43 PM EST
             When can you get here? - (tuberculosis) - (2) - Nov. 8, 2004, 03:47:59 PM EST
                 YEAH! -NT - (deSitter) - Nov. 8, 2004, 03:19:41 PM EST
                 Ooh yeah - IWETHEY-West, here we come! -NT - (inthane-chan) - Nov. 8, 2004, 04:45:35 PM EST
         I could take a stab... - (Arkadiy) - Nov. 8, 2004, 05:22:15 PM EST
         Almost contradictory requests - (tablizer) - (1) - Nov. 9, 2004, 12:03:20 AM EST
             Not true - (broomberg) - Nov. 9, 2004, 12:35:15 AM EST
         There seems to be a problem in CS education - (ubernostrum) - Nov. 29, 2006, 12:16:34 AM EST

Note: this is not exactly the safest place for your hand.
196 ms