C# Array vs List

[Guest]

I'm working on a Unity C# script (NO UNITY KNOWLEDGE REQUIRED)

and I'm deciding between using an Array, vs a list. 

 

I'm going to be working with a collection of Strings, and a collection of WWW (I don't know if WWW is a Unity thing, or C# thing for remembering addresses like file location, and websites. It is a variable type as int, float, double, char, and string are.)

 

There will be 2 separate arrays, or lists. 1 for the string, and 1 for the WWW. I don't know how many elements will be in the arrays as that is defined in run-time by the user. 

 

Based on this link Arrays are 7% faster, and use less memory. Because this is a game, I am leaning towards speed and less memory for optimization. However with data manipulation I don't know if it would be better to use a list.

 

What I will be needing from these collections is:

1. Be able to have the size set during run-time, or dynamically change size as elements are added/removed

2. Be able to read the value of 1 collection, and find the corresponding element in the other list.

(To save on memory, I am taking 1 string value, and 1 WWW value from one script and putting them into a collection in the second script; They need to be at the same index so I can find the WWW based on the contents of the String.)

3. Be expandable to be able to take .txt text document text and place the information in an index; This way the user doesn't have to enter the information every time they start the game.

(Obviously with appropriate coding saying for instance every space is the end of a variable's contents.)

4. Be able to be read, and have the contents of the collection sent to a .txt text document and saved so the user may load these preferences/entries at a later date. (Sorta connects with requirement #3.)

 

What would you recommend I use?

There's pros to Lists having a million functions that can interface with the data. Cons like using more data.

Array pros like being faster, and cons with significantly more work to be done to use them equivalently.

(Presumption about more work.)

 

I need to brush up on my array knowledge in C# for adding, and resizing arrays.

In .net LINQ I can use:

listName.Add(foo);

 

TL;DR

Should I use an Array, or List. I need to recall a collection of data. Should I go for speed in arrays or a wide variety of functions with Lists? I only need it to do the 4 things from the requirements numbering above. 

[unknownmiscreant]

If you need to change the array size on the fly, you definitely need to use a list. Arrays are fixed size. To get the functaionality you need from an array, you will basically be rewiritng the code for a list.

 

However be aware, that adding/removing items from the list is a very slow process. if you could do something to mean the number of lines in the file was known, a fixed size a array could be made, and the contents of the file loaded into that.

 

I would recomned using a list and possibly creating a object to store both strings. As then you will not need to cross-reference between 2 lists, you will just be able to write:

listOfStrings.str1

listOfStrings.str2

[Guest]

13 minutes ago, unknownmiscreant said:

If you need to change the array size on the fly, you definitely need to use a list. Arrays are fixed size. To get the functaionality you need from an array, you will basically be rewiritng the code for a list.

1. The array will be created immediately.

2. Then in a settings like menu, the player will set how many elements the arrays will be.

3. Then when the player has chosen all the settings, the program is to set the values the user set to the array. 

13 minutes ago, unknownmiscreant said:

However be aware, that adding/removing items from the list is a very slow process. if you could do something to mean the number of lines in the file was known, a fixed size a array could be made, and the contents of the file loaded into that.

This process only needs to be done once, but it could be a large sum of items that need to be loaded into the list at a time. (I'm anticipating 100 or more in some cases.)

 

13 minutes ago, unknownmiscreant said:

I would recomned using a list and possibly creating a object to store both strings. As then you will not need to cross-reference between 2 lists, you will just be able to write:

I would love to use an object, however I'm not sure that it will work in Unity 3D. unity uses C# as a scripting language more so than a programming language. Each time a different level loads, all the game objects are destroyed, and scripts cannot exist unless attached to a game-object. 

 

I understand the concept as I have done that exact thing in Java before with a deck of cards shuffling thing but I'm unsure of its possibility. I'll investigate this second suggestion.

 

Do you have any further comments on my original plan with the new information I gave you? 

[unknownmiscreant]

4 minutes ago, fpo said:

1. The array will be created immediately.

2. Then in a settings like menu, the player will set how many elements the arrays will be.

3. Then when the player has chosen all the settings, the program is to set the values the user set to the array. 

If you know the final size of the number of items you need in the list, use an array. Otherwise use a list.

 

5 minutes ago, fpo said:

This process only needs to be done once, but it could be a large sum of items that need to be loaded into the list at a time. (I'm anticipating 100 or more in some cases.)

If the items only need to be loaded once, probably just use a list, it will be easier.

 

7 minutes ago, fpo said:

I would love to use an object, however I'm not sure that it will work in Unity 3D. unity uses C# as a scripting language more so than a programming language. Each time a different level loads, all the game objects are destroyed, and scripts cannot exist unless attached to a game-object. 

Okay, take a look, I was talking more from the point of WPF.

[Guest]

14 minutes ago, unknownmiscreant said:

If you know the final size of the number of items you need in the list, use an array. Otherwise use a list.

I don't know the size before the array is created. The array can also change sized, but once it's final, the array won't change its size anymore.

14 minutes ago, unknownmiscreant said:

If the items only need to be loaded once, probably just use a list, it will be easier.

Do you think that's the better option? In favor opposed to an array.

14 minutes ago, unknownmiscreant said:

Okay, take a look, I was talking more from the point of WPF.

Um... I don't think you mean this:

Quote

Windows Presentation Foundation (or WPF) is a graphical subsystem by Microsoft for rendering user interfaces in Windows-based applications. WPF, previously known as "Avalon", was initially released as part of .NET Framework 3.0 in 2006. Rather than relying on the older GDI subsystem, WPF uses DirectX

I don't need the graphics programming to be done at all. The unity 3d game engine has that all figured out. 

[unknownmiscreant]

4 minutes ago, fpo said:

Do you think that's the better option? In favor opposed to an array.

Based off the information you have given, I would use a list.

2 minutes ago, fpo said:

Um... I don't think you mean this:

I personally use WPF (yes we are talking about the same thing) for all of the software I write in C#. I write software to interface to embedded systems, so WPF works well for me. I understand it does not apply to you, however was telling you so you realized why my understanding of how objects worked did not apply to your case situation.

[Guest]

3 minutes ago, unknownmiscreant said:

Based off the information you have given, I would use a list.

Okay, I was leaning that way as I was writing the OP, however I will await a few other people's opinions to see if anyone else has anything to bring to the table. It's also too late at night for me to finish writing that script right now. 

3 minutes ago, unknownmiscreant said:

I personally use WPF (yes we are talking about the same thing) for all of the software I write in C#. I write software to interface to embedded systems, so WPF works well for me. I understand it does not apply to you, however was telling you so you realized why my understanding of how objects worked did not apply to your case situation.

Ahh, okay. I did some more reading into it on wikipedia. I don't quite understand all the concepts as of now, but perhaps in time I may work my way into it. 

[Sebivor]

I suppose PATRICIA tries and ternary search trees could be referred to as lists when they're ordered for suboptimal retrieval...

To be clear, all memory in modern-day computers is mapped as though it's like an array (i.e. it's addressable by index), and not like a list. Things used to be different in the past, when we used tapes as storage, as then the `->next` and `->previous` or `->forward` and `->reverse`, or whatever you want to call those links, would correlate to the tape seeking back and forth. Even hard disks are mapped as a table (in the broader sense, an "array") which has indexes for sectors, tracks, etc.

Nonetheless, if your question is "Which is faster: a linked list implemented on top of an array, or an array implemented on top of a linked list?"... I don't know! Not enough information is provided, but it sounds like you're referring to a tree either way. A memory mapped file containing a tree (or better yet, a graph)? Who cares about space!

[Sebivor]

That's basically the description for a database, by the way, and they've had the ability easily accomplish all of those tasks for many years now. Seems fast enough for most businesses, eh...

Here's why you should absolutely NOT use an actual linked list for ANYTHING nowadays: They're extremely cache unfriendly... I mean, there's no guarantee that any cache memory exists in C, but in most systems we have this thing called "cache prediction" which can be as simple as "the user wants next byte from hard disk, while we're there, let's fetch the next 512KB and cache it in case they want that too" or as complex as the moon... Suffice to say, there exists at this time many more simpler caching algorithms that are compatible with arrays than lists. Common cache lines don't just go one way like a linked list; they don't just go two ways like a doubly linked list, and I suspect they've gone beyond four way caching in post-2012 computers, from my brief spot of research.

TLDR: Don't use either. Use some other type of associative array such as a hashtable or, if you're desperate for space, PATRICIA or TST (they both have similar overheads but different usecases; TSTs are better when a single key might have multiple values associated), or if you're super desperate. All but the last of those on an SSD will most certainly make you a happy camper with mannny gigabytes of fast-to-insert and fast-to-retrieve-by-key storage. Even the last might not be so bad for collections that are less than 512KB.

I say the overhead is three integers as they are indexes into the array or the key value. Three integers, 64 bits each... 192 bits of overhead per item might seem like a lot for very small items, but what's a few hundred on a disk that has over 2,000,000,000,000,000?
 

12 hours ago, unknownmiscreant said:

If you need to change the array size on the fly, you definitely need to use a list. Arrays are fixed size. To get the functaionality you need from an array, you will basically be rewiritng the code for a list.

This seemingly legit MSDN documentation has me wondering whether that's actually a concern...

 

12 hours ago, fpo said:

(I'm anticipating 100 or more in some cases.)

 

I understand the concept as I have done that exact thing in Java before with a deck of cards shuffling thing but I'm unsure of its possibility. I'll investigate this second suggestion.

 

Do you have any further comments on my original plan with the new information I gave you? 

Oh, lord! That huge number? LOL! At this point all I have to ask is "have you tried something, yet?" and all I have to say regarding your original plan is "try something..."

[Yamoto42]

12 hours ago, fpo said:

or dynamically change size as elements are added/removed

 

12 hours ago, fpo said:

Be expandable

 

11 hours ago, fpo said:

The array can also change sized

Why are you even considering an array?  List<T> is implemented as an array...so you still get the constant time access...and potentially quadratic expansion time.

 

But mainly: don't declare it as an array or a List<T>.  Use an IList<T>.  In c#, arrays actually implement this interface as well, so (since you say you aren't altering ti after initialization) the majority of your code it doesn't particularly matter what you use.
  

[Sebivor]

59 minutes ago, Yamoto42 said:

But mainly: don't declare it as an array or a List<T>.  Use an IList<T>.  In c#, arrays actually implement this interface as well, so (since you say you aren't altering ti after initialization) the majority of your code it doesn't particularly matter what you use.
  

Such memeing! I like you!

You can not instantiate an interface; they're like virtual classes... they don't contain constructors or any logic. All they specify is what members/methods a class that uses them shall have.

There is a reason why neither array nor list should be used, and it comes from the OPs message:

 

Quote

1. Be able to have the size set during run-time, or dynamically change size as elements are added/removed

2. Be able to read the value of 1 collection, and find the corresponding element in the other list.

(To save on memory, I am taking 1 string value, and 1 WWW value from one script and putting them into a collection in the second script; They need to be at the same index so I can find the WWW based on the contents of the String.)

3. Be expandable to be able to take .txt text document text and place the information in an index; This way the user doesn't have to enter the information every time they start the game.

(Obviously with appropriate coding saying for instance every space is the end of a variable's contents.)

4. Be able to be read, and have the contents of the collection sent to a .txt text document and saved so the user may load these preferences/entries at a later date. (Sorta connects with requirement #3.)

The bracketed part at the end of point two implies a list can't be used, The collection should be as small as possible, thus an array is the only alternative until you start talking about data compression (and even then...).

This implies any of the classes with the IDictionary interfaces would be most suitable, so that you could look up items by some meaningful identifier (that is, the corresponding element in the other list, according to the OP).

This includes the (predictably) `Dictionary` class, the `SortedDictionary` class (of relevance here, as it'll likely be a sorted array that uses binary search to search and qsort to sort), the `SortedList` class (hopefully a form of tree) and a few others which aren't likely too common/likely to perform well.

In any case, OP expects up to 100 items, so there shouldn't be any problem with any of these solutions, providing they're done competently.

[Yamoto42]

21 minutes ago, Sebivor said:

You can not instantiate an interface; they're like virtual classes...

Exactly what I was getting it:  designing around abstractions so he can easily change his mind later...or even based on different situations.  I used the word "declare" specifically to differentiate it from instantiation.  He obviously still has to use a concrete implementation...but beyond the constructor "ideally" that shouldn't be referenced again unless he absolutely requires it...but if that were the case this question would likely be moot from the start.

The same thing stands for IDictionary.

 

The only thing here I don't quite understand is what hes trying to accomplish with #2...he says "They need to be at the same index so I can find the WWW based on the contents of the String."...if they are at the same index what sort of searching does he need to do?   I think i understand what he's trying to do (create a pointer to another collection)...but I don't understand why it's necessary, or what searching has to do with it.

[Sebivor]

I agree; it's vague, but the way I read it is that he wants to be able to map key to value easily

[Guest]

8 hours ago, Sebivor said:

I suppose PATRICIA tries and ternary search trees could be referred to as lists when they're ordered for suboptimal retrieval...

To be clear, all memory in modern-day computers is mapped as though it's like an array (i.e. it's addressable by index), and not like a list. Things used to be different in the past, when we used tapes as storage, as then the `->next` and `->previous` or `->forward` and `->reverse`, or whatever you want to call those links, would correlate to the tape seeking back and forth. Even hard disks are mapped as a table (in the broader sense, an "array") which has indexes for sectors, tracks, etc.

Nonetheless, if your question is "Which is faster: a linked list implemented on top of an array, or an array implemented on top of a linked list?"... I don't know! Not enough information is provided, but it sounds like you're referring to a tree either way. A memory mapped file containing a tree (or better yet, a graph)? Who cares about space!

From what I gathered about PATRICIA it seems to be a sorting algorithm that searches by going to the mid point, and seeing if the value you're looking for is higher or lower than that mid point repeating till it finds the item searched for. 

 

I'm not sure if a list, or an array would be better.

7 hours ago, Sebivor said:

in most systems we have this thing called "cache prediction" 

This seemingly legit MSDN documentation has me wondering whether that's actually a concern...

Oh, lord! That huge number? LOL! At this point all I have to ask is "have you tried something, yet?" and all I have to say regarding your original plan is "try something..."

As for Patricia (presuming I got what it was) I hadn't planned on sorting, however I could sort everything alphabetically as once everything is in its memory slot, it will remain unchanging. 

With the CPU predicting what to cache next, it may be beneficial. 

 

I don't know how much space it'll have to compete with, so I was curious if there was a better way than what I had though up of. 

The MSDN link is pretty helpful, and informative.

100 is kinda a lot to me! I never worked with more than like 20 unknown values of variables before, and C# isn't SQL haha. 

7 hours ago, Yamoto42 said:

Why are you even considering an array?  List<T> is implemented as an array...so you still get the constant time access...and potentially quadratic expansion time.

 

But mainly: don't declare it as an array or a List<T>.  Use an IList<T>.  In c#, arrays actually implement this interface as well, so (since you say you aren't altering ti after initialization) the majority of your code it doesn't particularly matter what you use.

I don't know .Net that well. I'm learning C# from a background of C, basic C++ and elementary Java. 

How does IList [eye list] differ from just List in C# .Net? 

I don't know much about how C# uses Lists & arrays on the binary level. I only understand Arrays with C++ in memory because the textbook I have for it has a diagram showing how it's ordered in RAM. (Or storage. I don't know for sure which, but believe it to be RAM.)

6 hours ago, Sebivor said:

You can not instantiate an interface; they're like virtual classes... they don't contain constructors or any logic. All they specify is what members/methods a class that uses them shall have.

The bracketed part at the end of point two implies a list can't be used, The collection should be as small as possible, thus an array is the only alternative until you start talking about data compression (and even then...).

This implies any of the classes with the IDictionary interfaces would be most suitable, so that you could look up items by some meaningful identifier (that is, the corresponding element in the other list, according to the OP).

This includes the (predictably) `Dictionary` class, the `SortedDictionary` class (of relevance here, as it'll likely be a sorted array that uses binary search to search and qsort to sort), the `SortedList` class (hopefully a form of tree) and a few others which aren't likely too common/likely to perform well.

In any case, OP expects up to 100 items, so there shouldn't be any problem with any of these solutions, providing they're done competently.

I don't understand what you mean by instantiating an interface. Unity is handling all the GUI and interface for me. 

 

About the indexing, I meant in how I would access it. Let me explain how I am organizing these 2 collections.

1. The string is the name of the setting. When the program needs to find something it will search it by string name.

2. When it finds the name (pretending it's an array) it'll be at index i within the array.

3. Look for the WWW variable in index i of the WWW array because i is the index of the name. 

 

If you have a better idea for how to keep the corresponding data together as this, please share as I don't have much experience in data collections. I was considering using objects, but it seemed to me that all the objects would be "destroyed" when the player loaded the first level as Unity destroys all objects not set to "Don't Destroy." I would keep the settings window intact with don't destroy but there is a lot of data that'd be stored in memory that doesn't need to be used anymore once they leave that settings screen. 

If I sort the array using the standard sorting algorythm (if element i +1 > i, switch them) I'd expand it to include the other collection (i + 1 switch with i) as I noted after the second post I quoted in this reply. (Obviously there'd be more with the sorting, but you understand my concept.)

 

I hope my code is competent haha. 

6 hours ago, Yamoto42 said:

Exactly what I was getting it:  designing around abstractions so he can easily change his mind later...or even based on different situations.  I used the word "declare" specifically to differentiate it from instantiation.  He obviously still has to use a concrete implementation...but beyond the constructor "ideally" that shouldn't be referenced again unless he absolutely requires it...but if that were the case this question would likely be moot from the start.

The same thing stands for IDictionary.

 

The only thing here I don't quite understand is what hes trying to accomplish with #2...he says "They need to be at the same index so I can find the WWW based on the contents of the String."...if they are at the same index what sort of searching does he need to do?   I think i understand what he's trying to do (create a pointer to another collection)...but I don't understand why it's necessary, or what searching has to do with it.

My question may be moot. I will fill the array once. (The user may mess up and re arrange settings a few times) but then once they're done fiddling with settings, the writing is done. However the computer may need to read from these collections many times a second. I didn't mathematically calculate it as this is a user based situation on how many settings they'd like to add. 

 

I explained my #2 in better detail above. 

It's not necessary, just the solution I came up with. Because WWW and String are 2 different data types I cannot use a 2D array, and I don't think lists can contain multiple data types, nor be 2D or have a similar aspect to them. 

5 hours ago, Sebivor said:

I agree; it's vague, but the way I read it is that he wants to be able to map key to value easily

yes, basically that.

If string foo is in string array index 5

then foo's WWW value is in WWW array index 5. 

[unknownmiscreant]

9 hours ago, Sebivor said:

This seemingly legit MSDN documentation has me wondering whether that's actually a concern...

Thanks for telling me about that. Didn't know you could resize arrays on the fly. 

 

I may be totally wrong, but I always thought that to change the size of an array required copying all of its elements into a new array. Hence my reservations about lists.

[Sebivor]

For your usecase I would definitely use a sorted array. With 100 elements, you'll find your match by inspecting at most 6 or 7 items. It's a minute problem in the grand scheme.

PATRICIA builds a graph which allows you to locate elements by inspecting only the bits which differ between them. It's no more a "sorting algorithm" than any other trie algorithm or ternary search tree. To be clear, it's not just a set of algorithms but also the data structure the algorithms build. If you don't get it, start with a ternary search trie. A ternary search trie has nodes like a doubly-linked list, except instead of going to next and previous, they go to less than, equal to or greater than.

So to insert a setting by name of setting_name into the tree, the computer starts at the top-most node, which could be any existing setting, and compares setting_name to the name of that node. If setting_name is less than the name of that node, it takes the less than path down the graph, for example.

As a result of the three directions such a tree can have, it's easy to contain duplicate values. That's useful when you want duplicate values, otherwise PATRICIA is the more appropriate algorithm/data structure. PATRICIA got rid of one-way branching; that is, it doesn't just branch "down" the tree any more, it can loop back up to previous nodes, and such loops tell you where a search ends.

Nodes in a PATRICIA tree tell you which bit to inspect, so starting at the root, you obtain the index of the bit to test from the node, then check that index in the text, a 0 tells you to take the left branch and a 1 the right... Eventually you get to a point where the "bit index" is less than or equal to the previous, so you perform a full text comparison of the node you've landed on to determine, either you found a match or not.

So, when searching "hello", root might tell you to test the 3rd bit from the left, which is inside the letter 'h'. 'h' is 01101000 in ASCII, so the 3rd bit is the 1 I have highlighted red... So you take the right branch from the tree and it might tell you to inspect bit 4 next, which is a 0... and 0 takes you left, but that causes the index to go back to 3... The search has terminated here, and the node key needs to be compared to "hello" a final time to determine whether or not the search was successful.

The algorithm you described is binary search, which is an operation upon sorted arrays, one of the alternatives for this post. There's not really any data structure to build, for that, though... I mean sure, you have to sort an array... but neither PATRICIA nor TST require that you "sort" data, per se... you compare the data, and decide where to insert it into a tree so you can retrieve it again, thus avoiding a complete resort upon insertion.

[Yamoto42]

In object oriented programming, there is a concept of abstract and concrete types.

Concrete types are what you are likely familiar with.  They consist of data, methods, etc.

Abstract classes are similar to concrete classes, except they may have data or methods that are DECLARED, but not DEFINED.

As an example:

public class Concrete {

	public Int32 GetAnInt() {
		return 42;
	}

	public Int64 GetALong() {
		return 1234567890;
	}

}


public abstract class Abstract {

	public Int32 GetAnInt() {
		return 64;
	}

	public abstract Int64 GetALong();
}

Now, because the definition of Abstract is incomplete, you cannot call its constructor...but don't worry about that for now.

We have a special case for classes where NOTHING is defined.  We call them interfaces.

// By convention in C# we start them with an uppercase I
public interface INumberMaker {
  
  In32 GetAnInt();
  
}

public class Spam : INumberMaker {
  
  public In32 GetAnInt() {
    return 42;
  }
  

}

public class Eggs : INumberMaker {
  
  public In32 GetAnInt() {
    return 64;
  }
  
  public In64 GetALong() {
    return 42;
  }
}


Now for teh code
...
  INumberMaker myNum = new Spam();
 
  System.out.println(myNum.GetAnInt());  // Will print 42

  myNum = new Eggs();
 
  System.out.println(myNum.GetAnInt());  // Will print 64

  System.out.println(myNum.GetALong());  // Will not compile
...

What we have effectively done is said "I don't care what myNum is, as long as it has a method called GetAnInt() that returns an Int32."  The second time we assign it, it may have a method called GetALong...but we don't care.  By DECLARING it of type INumberMaker, even though we INSTANTIATED eggs, we have explicitly said INumberMaker and its GetanInt() method is all we care about.

That's what interfaces are used for.  We declare what matters, for example IList<T> defines what MAKES a list, but not how it is implemented.  It says what does a list do?  It stores items an a specific order, allows retrial based on their order, etc...  It doesn't say how they are stored, only that they exist and what method names will be used to access them.  (this is called an API)

 

List<T> then says "lets store it as an array" and LinkedList<T> says "Lets store it as a path of nodes".  But they both implement IList<T>.

 

...and in this case your code should care about how it's ACCESSED, not how its STORED.  That decision only has to be made once...and it may often change.  If your code needs to know how its stored, you've probably put too much responsibility on a single area.  Let the initialization worry about how its stored, let the accessor only worry about how its accessed.
 

[Sebivor]

1 minute ago, unknownmiscreant said:

Thanks for telling me about that. Didn't know you could resize arrays on the fly. 

 

I may be totally wrong, but I always thought that to change the size of an array required copying all of its elements into a new array. Hence my reservations about lists.

That may be the case at times, however often enough the size of the existing object can merely be extended because nothing is occupying that space.

Nonetheless, we're talking about such a small number of items here. 100 is far too small to notice a significant difference between any of the data structures and algorithms mentioned here.

[unknownmiscreant]

28 minutes ago, Sebivor said:

That may be the case at times, however often enough the size of the existing object can merely be extended because nothing is occupying that space.

Nonetheless, we're talking about such a small number of items here. 100 is far too small to notice a significant difference between any of the data structures and algorithms mentioned here.

Yes that is true. its probably best for OP to just choose the data structure that has the most methods he wishes to use.