3
$\begingroup$

I have a giant list l1 and some smaller lists l21, l21, ..., l2n. The l1 is the superset and has $\tilde{}10^7$ elements. l2? is subset of l1 (if my other code does correct job). All lists only contain numbers (again, if my code does correct job). I need to take complement of l1 and each of the l2?. The number of subsets (i.e. n) is several hundreds. What's the most memory/time efficient way of doing this? I run this on 4GB machine and usually have 1.* GB of free memory when the program reaches that stage. I'd probably save numbers in file and use some command-line tool like grep to do this. But the original lists are all prepared in a Mathematica program. If there is a good solution in Mathematica then i'd like to avoid going out.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You've tried Complement[] already? $\endgroup$
    – J. M.'s eventual burnout ♦
    Oct 27, 2012 at 2:33
  • 2
    $\begingroup$ If your lists of integers are reasonably dense and entries are non-repeating, you can use arbitrary-length integers interpreted as bit vectors as representation of these lists. These integers can be constructed using repetitive BitSet, complement performed using BitAnd[l1,BitNot[l2?]], and values collected through BitGet. This is elegant, but slow. For a faster kludge, see [mathematica.stackexchange.com/a/13708/3056]. Both methods consume roughly one bit (not byte) per integer (present or not in the list) in list range. (I believe Complement should be sufficient though.) $\endgroup$
    – kirma
    Oct 27, 2012 at 13:45
  • $\begingroup$ Small addition: unless you create the lists in special fashion from the start, you don't really get space benefit over Complement in the large scheme of things. If you had billions of integers, optimization could make sense, but otherwise... $\endgroup$
    – kirma
    Oct 27, 2012 at 13:54

1 Answer 1

Reset to default
4
$\begingroup$

This depends.. How many numbers are in the subsets? In which range are you numbers? What do you want to do with each complement? Can you give a small example using RandomInteger to create sample-data? Generally, you could first try to calculate one complement by using something like this

l1 = RandomInteger[{0, 10^6}, {10^7}];
l21 = RandomInteger[{0, 10^6}, {10^5}];

compl = Complement[l1, l21];

and see whether you memory is sufficient.

To see how much memory is used you can tryMemoryInUse[]. ByteCount[expr] is able to find out how much memory is used by a variable (or expression in general). After the above command, I have wasted

MemoryInUse[]/2^20.

(* Out[9]= 101.952 *)

about 100 MB here.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.