Index Array Storage Memory

Question

Is there a use case for storing index ranges when talking about a potentially huge list.

Let's say with a list of millions of records. These will be analysed and a sublist of indexes will be reported to the user. Rather than listing out a massive list of indexes it would be obviously more legible to present;

Identified Rows: 10, 21, 10000-30000, 700000... etc to the user.

Now I can obviously create this string from the array of indexes but I'm wondering if it would also be more memory efficient to create the list in this format (and not creating a massive list of indexes in memory). Or is it not worth the processing overhead?

List intList = new List{1,2,3,4,5,6,7...};

vs

List strList = new List{"1-3000","3002","4000-5000"...};

To apply this I would imagine creating a List and when adding an item update/add to the list as necessary. Would require quite a bit of converting strings to int and vice-versa I think which is where this process may not be worth it.

Let me know if this isn't clear enough and I can potentially explain further.

UPDATE

I quite like Patrick Hofman's solution below using a list of ranges. What would be really cool would be to extend this so that .add(int) would modify the list of ranges correctly. I think this would be quite complicated though, correct?

Of course it is more memory efficient if you have a List<string>{"1-9999999"} than one which contains all these numbers — Tim Schmelter
– Tim Schmelter, Commented Apr 12, 2018 at 15:33
What you're describing is called a sparse matrix and has long been used where most items in a collection are the same. If your matrix contains integers it would be even better to store integers that constantly converting to and from strings. — Dour High Arch
– Dour High Arch, Commented Apr 12, 2018 at 15:39
You could use a Dictionary, or just KVP, with a start index and end index as integers. Then there are no conversions, only reading the pairs and pushing the values into your display strings. Then you will just need some validation logic to ensure your ranges don't overlap if you wish to avoid that. — user7396598
– user7396598, Commented Apr 12, 2018 at 16:01

Patrick Hofman · Accepted Answer · 2018-04-12 15:38:56Z

4

I would opt to create a list of ranges. Depending on the number of singles in it, it might be more or less efficient:

public struct Range
{
    public Range(int from, int to)
    {
        this.From = from;
        this.To = to;
    }

    public int From { get; }
    public int To { get; }

    public static implicit operator Range(int v)
    {
        return new Range(v, v);
    }
}

You can use it like this:

List<Range> l = new List<Range>{ 1, 2, 3, new Range(5, 3000) };

answered Apr 12, 2018 at 15:38

Patrick Hofman

158k23 gold badges270 silver badges343 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

windowsgm Over a year ago

Thanks for that. It would be cool to extend this so that .add(7) would modify the list as such to create a range in place of an int if required.

Collectives™ on Stack Overflow

Index Array Storage Memory

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related