Potentially sparse? I don't think so...

Post #183,579 by ben_tilly 11/8/04 5:29:51 PM Reply	Potentially sparse? I don't think so... Perhaps in that big gap from 1_000_000_000 up. But there are about 300 million people in the USA, most of whom have a social security number (and others have been handed out), so social security numbers are mostly filled. An optimal solution for the "sparse social security number" problem is going to use far too much memory when you have a mostly filled data space. Heck, 300 million pointers will take 1.2 GB on a 32-bit machine. Scott's solution is an extremely good trade-off that will be hard to beat on any significant criteria, let alone all of them combined. Incidentally one thing to watch for in Scott's solutions, I believe that social security numbers can start with 0. 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)
Post #183,585 by admin 11/8/04 5:42:36 PM Reply	I took the ones that start with 0 into account. 125M is approximately 1,000,000,000 / 8. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #183,587 by ben_tilly 11/8/04 5:49:44 PM Reply	I was referring to the step where you... convert the string to long. Hand-rolled functions will be OK, but some library functions may take a leading 0 to indicate that the number is in octal, which generally won't do what you want it to. 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)
Post #183,597 by admin 11/8/04 6:21:56 PM Reply	Ah, gotcha. Good point. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #183,603 by tuberculosis 11/8/04 6:57:18 PM Reply	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	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)
Post #183,692 by a6l6e6x 11/9/04 2:08:24 AM Reply	Re: social security numbers can start with 0 Yep, mine does! But, there are other non-zero digits as well. :) Alex In politics, what begins in fear usually ends in folly. -- Samuel Taylor Coleridge, poet (1772-1834)

Welcome to IWETHEY!