1

I have a class like this,

public class Cube
{
    private int[,] data;

    public Cube()
    {
        data[,] = new int[3,3];
        data[0,0] = 1;
        data[1,0] = 2;
        // etc
    }

    public void RotateFrontOfCube()
    {
        // code
    }

    public void RotateBackOfCube()
    {
        // code
    }

If I have a dictionary and add instances of this class to the dictionary, how much memory will be used?

Does the instance of the class somehow represent just the data required for the class? Or the data plus the methods?

If I add more code to the class does the memory usage increase against instances of this class?

I am building a tree of this data in an attempt to analyse rubiks cube solutions, but it uses a lot of memory.

By the way, my class above has been simplified, and doesn't represent a full rubiks cube data.

peter
  • 13,009
  • 22
  • 82
  • 142
  • The algorithm used probably is one that requires a large working set.. this is not a problem with the class so much as the algorithm design. – user2864740 Apr 26 '18 at 01:03
  • 1
    I am building a tree, each parent has 12 children, and I get down to about level 6 or 7 before the app dies using 2 GB of memory. – peter Apr 26 '18 at 01:04
  • 1
    12*12*12*12*12.. see? It doesn't matter if the program can get to step 8 or 9 (or 12, etc.) - if the problem still can't be solved by then it'll still run out of memory. In fact, if each object was reduced to 1/12th the current memory usage, that would only allow *one* more step.. – user2864740 Apr 26 '18 at 01:05
  • 1
    A cube can be solved in 21 moves at minimum, so this turns out to be a difficult problem to solve. – peter Apr 26 '18 at 01:08
  • You make a good point. Memory reduction will only get you so far. I started with 1 optimisation, which means that if you get to a state on the cube you already have gone to you don't go further on that leaf. But I need to somehow reduce memory (as you suggest will only have limited success), or work out which tree items not to continue with. Or else store a lot less about each tree item. Once I am finished with the cube state I can just store the move name for each tree item. – peter Apr 26 '18 at 01:15
  • you need to throw away branches as you finish with them. This will save a massive amount of memory and allow you to go very deep – Keith Nicholas Apr 26 '18 at 01:15
  • Throw away branches. That is easier said than done, however you are right. Thanks. – peter Apr 26 '18 at 01:19
  • 1
    as a reference, there are ~43 quintillion states of a cube. – Keith Nicholas Apr 26 '18 at 01:19
  • 1
    This is an algorithm issue not a class size issue. No matter how much you optimize you won’t fit the whole tree in memory. I’d suggest a different algorithm - perhaps one that only stores the current state and 1 previous state. – Brian Driscoll Apr 26 '18 at 01:19
  • You mean I can't fit 43 quintillion instances of a class in memory at a time? Quite right, or perhaps I just need a new computer. – peter Apr 26 '18 at 01:21
  • you don't even have 48 quintillion bits, let alone bytes :) not even if you cached everything to your hard drive :) – Keith Nicholas Apr 26 '18 at 01:23
  • You have opened my eyes. I was thinking about the hard drive. But no. – peter Apr 26 '18 at 01:24
  • if you can convince 5.4 million other people use 1 terabyte on their computers you'd have just enough space to have 1 bit represent 1 combination.......which sadlly wouldn't tell you anything. You'd likely need around a billion computers :) – Keith Nicholas Apr 26 '18 at 01:26
  • But then you'd be running the algorithm for days to copy all that data. Then you discover a bug and have to start over. Haha. – peter Apr 26 '18 at 02:00
  • Interestingly enough I was thinking that I should just have 1 cube object, apply a move at a time to it using recursion, then when finished investigating the child possibilities in any particular part of the tree undo the move. Why store anything else other than the moves we go through to get to the current state. It will be slow, but memory shouldn't be a problem. – peter Apr 26 '18 at 02:26
  • @peter wouldn’t that have the exact same memory problem? You would still be storing the history of all your moves somehow right? – maccettura Apr 26 '18 at 04:20
  • I tried it last night, and memory is no problem anymore. 1 cube object, applying each move to the cube changing the state of the cube inside a recursive method then when you return you undo the last move. No need to keep history as the recursive method will keep track of where we are up to. The cube can also keep track of the current set of moves required to get to this state. However this isn't going to work. Memory is small, but the time taken to run through all moves is going to be approximately 8000 years based on my current timings. Even if my calculations are out it still looks bad. – peter Apr 27 '18 at 01:48
  • @maccettura I would only store the current set of moves and if a solution is obtained then copy that set of moves out to somewhere else. I'm going to have to program some kind of algorithm to reduce the moves it investigates. – peter Apr 27 '18 at 01:50

1 Answers1

0

If I have a dictionary and add instances of this class to the dictionary, how much memory will be used?

This is implementation defined of course, though in .NET Framework & Core internally, Dictionary has some overhead that's linear with respect to its element count - that's going to be ballpark 4 + (8 + the size of storing TKey (or a reference to it) + the size of storing TValue (or a reference to it)).

See: https://referencesource.microsoft.com/mscorlib/System/collections/generic/dictionary.cs.html

In your case, TValue would be a reference type, so see How big is an object reference in .NET?

Does the instance of the class somehow represent just the data required for the class? Or the data plus the methods?

Just the data of the instance itself. (Though once again, I presume this is implementation-defined).

If I add more code to the class does the memory usage increase against instances of this class?

No. See Where are methods stored in memory?... (Though once again, I presume this is implementation-defined).

Warty
  • 7,237
  • 1
  • 31
  • 49
  • Is there a term that concisely encompasses `notReallySizeof(T)` where `notReallySizeof == sizeof(pointer) if reference type else sizeof(T)`? Someone do tell. – Warty Apr 26 '18 at 01:06