Storing list of lists efficiently (sieving)

Question

Question

I'm looking for a data structure for a project in C to store a list of lists. I need to be able to access the n-th list given just n (the terms will be accessed out of order). The individual lists will contain between 1 and M integers (say M = 25 for concreteness); the outer list contains N of these. The individual lists are closer to 1 than M on average: in my example, only 20% have between 5 and 25 elements.

The obvious implementation is an array of length N*M. But this is space-inefficient: for performance reasons, it's important that the structure not take up too much memory. What is a good way to do this?

Context

I'm writing a factorization sieve. The outer array represents numbers from Sb + 1 to S(b+1), and each of the arrays store the prime factors of one number in that range. The smaller the structure gets the larger S can be chosen, reducing the number of (expensive) divisions.

This also gives another avenue for optimization: store only primes greater than or equal to L. The benefit is that instead of needing floor(log_2(x = largest number in range)) elements in each list, you need only floor(log_L(x)). (The example above corresponds to x = 10^12, L = 3.) The downside is that to reconstruct the factorization one needs to do trial division for primes below L.

In my application each factorization is reconstructed once, so increasing L to the next prime costs (somewhat more than) 10^12 additional divisions in my example; as an order of magnitude, this is 24-87 ops each or 2-8 hours in total on a 3 GHz K10. The more efficient the memory structure, the fewer 2 to 8 hour chinks I'll need to spend. (On the flip side, memory structures that take too much CPU work aren't worth it unless they provide a better tradeoff.)

Answer 1

One data structure which comes to mind is a two-dimensional array where the 'inner' array is a fair bit smaller than floor(log_L(x)). If there are prime factors left over then store a pointer in the last element, which goes to a secondary overflow array. You can also reduce the storage needed by leaving off the last prime factor, which can be determined by dividing out the others.

I don't know if this is much better than the naive approach. The upside is that memory usage is much smaller -- maybe 5 elements instead of 25, letting you pack in 4 to 5 times as many numbers in the same space. The downside is that it's more work to reconstruct the numbers and memory locality might be slightly worse.

But there's another trick which may help. As long as L > 2, all of the numbers in the list will be odd, so the last bit is unused. You could use this to store the exponent in the number itself: store p * 2^(e-1) instead of p. So "3" represents 3, "6" represents 3^2, "12" represents 3^3, and so on. If you use 64-bit numbers you can represent 3^63 as 3*2^62 which is less than 2^64. (Larger bases are easier: 5^62 is 18 trillion times larger than 3^63 but can be represented in this format with 64 bits.) 32 bits limits you to 3^31, but you already can't represent the prime 2^32 + 15, which makes the limit somewhat more than 2^64.

Actually, I think this is good enough that the secondary array can be skipped entirely. Here's a list showing how many factors you need to store

Using 1 uint32_t lets you store factored numbers less than 3*5*7 = 105 (7 bits).

Using 2 uint32_ts lets you store factored numbers less than 3*5*7*11 = 1155 (11 bits).

Using 3 uint32_ts lets you store factored numbers less than 3*5*7*11*13 = 15015 (14 bits).

Using 4 uint32_ts lets you store factored numbers less than 3*...*17 = 255255 (18 bits).

Using 5 uint32_ts lets you store factored numbers less than 3*...*19 (23 bits).

Using 6 uint32_ts lets you store factored numbers less than 3*...*23 (27 bits).

Using 7 uint32_ts lets you store factored numbers less than 3*...*29 (32 bits).

Using 8 uint32_ts lets you store factored numbers less than 3*...*31 (37 bits).

Using 9 uint32_ts lets you store factored numbers less than 3*...*37 (42 bits).

Using 10 uint32_ts lets you store factored numbers less than 3*...*41 (48 bits).

Using 11 uint32_ts lets you store factored numbers less than 3*...*43 (53 bits).

Using 12 uint32_ts lets you store factored numbers less than 3*...*47 (59 bits).

Using 13 uint32_ts lets you store factored numbers less than 3*...*53 (64 bits).

Using 14 uint32_ts lets you store factored numbers less than (2^32 + 15)^2 (64 bits).

To go beyond this you'd probably want to use the alternate data structure I mentioned (where the secondary array uses uint64_t) so you don't need to convert the main array to uint64_t. But this is only of concern for segmented sieving; it's infeasible to sieve all the numbers up to 2^64 -- it would take hundreds of years.