I iterate through a process, each time generating a new number between 1 and a very large number (10^15 or larger). I am waiting for any number to repeat.

Clearly a 1D Boolean array (starting out all as false) is too large (for any memory that I have access to). However, I am hoping that a compressed version of the array might do the trick, if enough consecutive subsequences are generated. Please note that the array will likely not remain sparse.

This hinges on the ability to update a value (to true), without uncompressing.

Any ideas?

I thought of combinations of Compress, SparseArray, PackedArray, but nothing comes to mind.

Thanx for the thinx.

  • $\begingroup$ I would suggest to just try a simple SparseArray, see e.g. this question $\endgroup$
    – Lukas Lang
    Nov 19, 2022 at 19:33
  • $\begingroup$ What about using a HashTable? $\endgroup$
    – Victor K.
    Nov 19, 2022 at 20:38
  • $\begingroup$ Unless I'm missing something, I'm very skeptical of this approach. Even if you use a bit array, you would need UnitConvert[Quantity[10^15, "Bits"], "Terabytes"] = 125 TB of memory to store it. $\endgroup$
    – Victor K.
    Nov 19, 2022 at 20:45
  • $\begingroup$ Thank you for your answers. However, as I stated, since the array may likely not stay sparse, I wanted compression, which can take advantage of: from element m1 to n1, they are all false, from m2 to n2, they are all true, etc. $\endgroup$ Nov 20, 2022 at 13:20


Your Answer

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

Browse other questions tagged or ask your own question.