Create big Two-Dimensional Array

Question

simple question:

How can I use a huge two-dimensional array in C#? What I want to do is the following:

int[] Nodes = new int[1146445];

int[,] Relations = new int[Nodes.Lenght,Nodes.Lenght];

It just figures that I got an out of memory error.

Is there a chance to work with such big data in-memory? (4gb RAM and a 6 core CPU)^^

The integers I want to save in the two-dimensional array are small. I guess from 0 to 1000.

Update: I tried to save the Relations using Dictionary<KeyValuePair<int, int>, int>. It works for some adding loops. Here is the class wich should create the graph. The instance of CreateGraph get's its data from a xml streamreader.

Main (C# backgroundWorker_DoWork)

ReadXML Reader = new ReadXML(tBOpenFile.Text);
CreateGraph Creater = new CreateGraph();

int WordsCount = (int)nUDLimit.Value;
if (nUDLimit.Value == 0) WordsCount = Reader.CountWords();

// word loop
for (int Position = 0; Position < WordsCount; Position++)
{
    // reading and parsing
    Reader.ReadNextWord();

    // add to graph builder
    Creater.AddWord(Reader.CurrentWord, Reader.GetRelations(Reader.CurrentText));
}

string[] Words = Creater.GetWords();
Dictionary<KeyValuePair<int, int>, int> Relations = Creater.GetRelations();

ReadXML

class ReadXML
{
    private string Path;
    private XmlReader Reader;
    protected int Word;
    public string CurrentWord;
    public string CurrentText;

    public ReadXML(string FilePath)
    {
        Path = FilePath;
        LoadFile();
        Word = 0;
    }

    public int CountWords()
    {
        // caching
        if(Path.Contains("filename") == true) return 1000;

        int Words = 0;
        while (Reader.Read())
        {
            if (Reader.NodeType == XmlNodeType.Element & Reader.Name == "word")
            {
                Words++;
            }
        }

        LoadFile();

        return Words;
    }

    public void ReadNextWord()
    {
        while(Reader.Read())
        {
            if(Reader.NodeType == XmlNodeType.Element & Reader.Name == "word")
            {
                while (Reader.Read())
                {
                    if (Reader.NodeType == XmlNodeType.Element & Reader.Name == "name")
                    {
                        XElement Title = XElement.ReadFrom(Reader) as XElement;
                        CurrentWord = Title.Value;

                        break;
                    }
                }
                while(Reader.Read())
                {
                    if (Reader.NodeType == XmlNodeType.Element & Reader.Name == "rels")
                    {
                        XElement Text = XElement.ReadFrom(Reader) as XElement;
                        CurrentText = Text.Value;

                        break;
                    }
                }
                break;
            }
        }
    }

    public Dictionary<string, int> GetRelations(string Text)
    {
        Dictionary<string, int> Relations = new Dictionary<string,int>();

        string[] RelationStrings = Text.Split(';');

        foreach (string RelationString in RelationStrings)
        {
            string[] SplitString = RelationString.Split(':');

            if (SplitString.Length == 2)
            {
                string RelationName = SplitString[0];
                int RelationWeight = Convert.ToInt32(SplitString[1]);

                Relations.Add(RelationName, RelationWeight);
            }
        }

        return Relations;
    }

    private void LoadFile()
    {
        Reader = XmlReader.Create(Path);
        Reader.MoveToContent();
    }
}

CreateGraph

class CreateGraph
{
    private Dictionary<string, int> CollectedWords = new Dictionary<string, int>();
    private Dictionary<KeyValuePair<int, int>, int> CollectedRelations = new Dictionary<KeyValuePair<int, int>, int>();

    public void AddWord(string Word, Dictionary<string, int> Relations)
    {
        int SourceNode = GetIdCreate(Word);
        foreach (KeyValuePair<string, int> Relation in Relations)
        {
            int TargetNode = GetIdCreate(Relation.Key);
            CollectedRelations.Add(new KeyValuePair<int,int>(SourceNode, TargetNode), Relation.Value);  // here is the error located
        }
    }

    public string[] GetWords()
    {
        string[] Words = new string[CollectedWords.Count];

        foreach (KeyValuePair<string, int> CollectedWord in CollectedWords)
        {
            Words[CollectedWord.Value] = CollectedWord.Key;
        }

        return Words;
    }

    public Dictionary<KeyValuePair<int,int>,int> GetRelations()
    {
        return CollectedRelations;
    }

    private int WordsIndex = 0;
    private int GetIdCreate(string Word)
    {
        if (!CollectedWords.ContainsKey(Word))
        {
            CollectedWords.Add(Word, WordsIndex);
            WordsIndex++;
        }
        return CollectedWords[Word];
    }

}

Now I get another error: An element with the same key already exists. (At the Add in the CreateGraph class.)

Answer 1

You'll have a better chance when you set Relations up as a jagged array (array of array) :

//int[,] Relations = new int[Nodes.Length,Nodes.Length];
int[][] Relations = new int[Nodes.length] [];
for (int i = 0; i < Relations.Length; i++)
    Relations[i] = new int[Nodes.Length];

And then you still need 10k * 10k * sizeof(int) = 400M

Which should be possible, even when running in 32 bits .

Update:

With the new number, it's 1M * 1M * 4 = 4 TB, that' not going to work.
And using short to replace int will only bring it down to 2 TB

---

Since you seem to need to assign weights to (sparse) connections between nodes, you should see if something like this could work:

struct WeightedRelation 
{ 
   public readonly int node1;
   public readonly int node2;
   public readonly int weight;
}

int[] Nodes = new int[1146445];

List<WeightedRelation> Relations = new List<WeightedRelation>();
Relations.Add(1, 2, 10);
...

This just the basic idea, you may need a double dictionary to do fast lookups. But your memory size would be proportional to the number of actual (non 0) relations.

Answer 2

Okay, now we know what you're really trying to do...

int[] Nodes = new int[1146445];

int[,] Relations = new int[Nodes.Length ,Nodes.Length];

You're trying to allocate a single object which has 1,314,336,138,025 elements, each of size 4 bytes. That's over 5,000 GB. How exactly did you expect that to work?

Whatever you do, you're obviously going to run out of physical memory for that many elements... even if the CLR let you allocate a single object of that size.

Let's take a small exampler of 50,000, where you end up with ~9GB of requires space. I can't remember what the current limit is (which depends on CLR version number and whether you're using the 32 or 64-bit CLR) but I don't think any of them will support that.

You can break your array up into "rows" as shown in Henk's answer - that will take up more memory in total, but each array will be small enough to cope with on its own in the CLR. It's not going to help you fit the whole thing into memory though - at best you'll end up swapping to oblivion.

Can you use sparse arrays instead, where you only allocate space for elements you really need to access (or some approximation of that)? Or map the data to disk? If you give us more context, we may be able to come up with a solution.

Answer 3

Jon and Henk have alluded to sparse arrays; this would be useful if many of your nodes are unrelated to each other. Even if all nodes are related to all others, you may not need an n by n array.

For example, perhaps nodes cannot be related to themselves. Perhaps, given nodes x and y, "x is related to y" is the same as "y is related to x". If both of those are true, then for 4 nodes, you only have 6 relations, not 16:

a <-> b
a <-> c
a <-> d
b <-> c
b <-> d
c <-> d

In this case, an n-by-n array is wasting somewhat more than half of its space. If large numbers of nodes are unrelated to each other, you're wasting that much more than half of the space.

One quick way to implement this would be as a Dictionary<KeyType, RelationType>, where the key uniquely identifies the two nodes being related. Depending on your exact needs, this could take one of several different forms. Here's an example based on the nodes and relations defined above:

Dictionary<KeyType, Relation> x = new Dictionary<KeyType, RelationType>();
x.Add(new KeyType(a, b), new RelationType(a, b));
x.Add(new KeyType(a, c), new RelationType(a, c));
... etc.

If relations are reflexive, then KeyType should ensure that new KeyType(b, a) creates an object that is equivalent to the one created by new KeyType(a, b).