Hot answers tagged

106

Frankly, I don't see the need for inheritance here. It doesn't make sense; Node is an ArrayList of Node? If this is just a recursive data structure, you would simply write something like: public class Node { public String item; public List<Node> children; } Which does make sense; node has a list of children or descendant nodes.


99

Keep in mind that Any doesn't operate on a List; it operates on an IEnumerable, which represents a concrete type that may or may not have a Count property. It's true that it's not necessarily the best thing to use on a List, but it definitely comes in handy at the end of a LINQ query. And even more useful than the standalone version is the override that ...


73

I'll expand my comment: ... if you're adding or removing elements, you want a list (or other flexible data structure). Arrays are only really good when you know exactly how many elements you need at the start. A Quick Breakdown Arrays are good when you have a fixed number of elements that is unlikely to change, and you wish to access it in a non-...


68

I already answered a similar question lately and it's very important to realize that += can have different meanings: If the data type implements in-place addition (i.e. has a correctly working __iadd__ function) then the data that i refers to is updated (doesn't matter if it's in a list or somewhere else). If the data type doesn't implement an __iadd__ ...


57

The “horrible for memory” argument is entirely wrong, but it is an objectively “bad practice”. When you inherit from a class, you don't just inherit the fields and methods you are interested in. Instead, you inherit everything. Every method that it declares, even if it isn't useful for you. And most importantly, you also inherit all its contracts and ...


56

There is a run time difference Count() can be O(n) where Any() is O(1).


29

Assuming that you mean "integer" when you say "number", you can use a bitvector of size 2^n, where n is the number of elements (say your range includes integers between 1 and 256, then you can use an 256-bit, or 32 byte, bitvector). When you come across an integer in position n of your range, set the nth bit. When you're done enumerating the collection of ...


24

I'll expand my comment a bit. The List[T] data structure, from scala.collection.immutable is optimized to work the way an immutable list in a more purely functional programming language works. It has very fast prepend times, and it is assumed that you will be working on the head for almost all of your access. Immutable lists get to have very fast prepend ...


23

The most important factor is that you can prepend to an immutable singly linked list in O(1) time, which allows you to recursively build up n-element lists in O(n) time like this: // Build a list containing the numbers 1 to n: foo(0) = [] foo(n) = cons(n, foo(n-1)) If you did this using immutable arrays, the runtime would be quadratic because each cons ...


21

Yes, there are such languages. Many of them. In fact, this feature is pretty much the definition of an array language or vector language. Examples of array and vector languages include, but are not limited to, the APL family of languages with its successors, derivatives and cousins (E.g. APL, J, K) and pretty much all mathematical and statistical languages ...


19

Clarification - terminology Python does not distinguish between the concepts of reference and pointer. They usually just use the term reference, but if you compare with languages like C++ that do have that distinction - it's much closer to a pointer. Since the asker clearly comes from C++ background, and since that distinction - which is required for the ...


17

Extending a container in as of itself is usually accepted to be bad practice. There's really very little reason to extend a container instead of just having one. Extending a container of yourself just makes it extra strange.


16

Even more, C++ have such functions, take a look to algorithm (or with C++11 additions) header: std::transform std::for_each std::remove_copy_if They can be easily used with any container. For example your code can be expressed like this (with C++11 lambdas for easy coding): std::vector<int> x = {1, 2, 3, 4, 5}; std::vector<int> y; std::...


16

While there can be exactly one max value in a collection, there can be more than item representing that value. E.g {1, 9, 2, 9, 0} has max value of 9, represented by both elements [1] and [3]. Note that not all collections support index access; e.g. a Set<Integer> can have a meaningful maximum but accessing an element by index makes no sense in it. ...


14

Adding to what has been said, there is a somewhat Java-specific reason to avoid this kind of structures. The contract of the equals method for lists requires a list to be considered equal to another object if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. ...


13

How do you propose the head be reached in this reversed list? If not using mutable structures the reversed list would only be performant if you made the head linear time and tail constant. But now you've got the exact same structure as before except you're calling the head the tail and vice versa. the structure is the way it is because regardless of which ...


11

None of the answers here give you any code to work with to really illustrate why this happens in Python land. And this is fun to look at in a more deep approach so here goes. The primary reason that this doesn't work as you expect is because in Python, when you write: i += 1 it is not doing what you think it's doing. Integers are immutable. This can be ...


10

A generic queue or array is generally not, by itself, thread safe, just like many other data types. Thread safety is usually accomplished in two ways: Using mutex locks - each thread that wants to modify a value has to wait. Delegation - only the owning thread can modify the value. Mutex locks are fairly straight forward - nobody owns the value, but only ...


10

If by "best" you actually mean "fastest", then by far the fastest way (although not nearly the most efficient way) is to choose a multiplier that makes all of the weights integers, at least to whatever precision you care about, and then store that many copies of each in one large array. For example, if you assign "score multiplier" a weight of 80%, and "...


10

I want to answer a small part of your question, that is nonetheless very interesting: Is it possible to use a fold (also known as reduce) operation for this? Yes, it is. In fact, it is always possible to use a fold for anything! Fold is a general operation for iteration, anything you can do with iteration, you can do with fold! The Wikipedia page for ...


9

There is no such datatype, probably because this is a very special requirement which can be easily solved by utilizing a dictionary and adding simply both pairs theDictionary.Add("foo", "bar"); theDictionary.Add("bar", "foo"); Obviously, you can put this into a generic function like void MyDictAdd(Dictionary<T,T> dict, T key1, T key2) { dict....


9

Actually, keep in mind that there is the List.Count property, and then there is the Enumerable.Count method. In your example, you are using the Enumerable.Count() method, which has to iterate through every single item of the enumeration to return a result. That is clearly slower than calling Any() which only needs to iterate over the first item, if it ...


9

This is odd to me. Why should an empty collection be treated any differently? Forcing the programmer to check if the collection is empty before doing things to it would be a widespread, problematic sort of burden. Worse, an empty collection is in no way exceptional. Personally, I would rather have the occasional bug where a no-op happened because I forgot ...


9

Generally speaking DTOs (Data Transfer Objects) need to be serialized in order to be transferred, for example to JSON. Types like IList and IEnumerable can easily be serialized but are not so easy to deserialize because the serializer has to pick a concrete type. In my experience the best balance between convenience, functionality and efficiency is List<...


8

Because you still need a way to search the associative array. The hash table is your search mechanism; it gives you O(1) performance for any given key search, by computing an index into the bucket containing your item. What is your underlying search mechanism, if it's not a hash table? A Binary Search Tree? That's good for very large tables, but it's ...


8

It's a bounded queue (a first-in-first-out queue with a fixed capacity). This particular queue always allows addition of elements and silently remove head element for newly added element (when full). In Java there is the CircularFifoQueue that works exactly that way (see also Size-limited queue that holds last N elements in Java). For .NET you'd take a ...


8

This heavily depends on definition of list and tree. Mathematically list doesn't mean anything and tree is just special subset of a graph. Inferring from your question, your teacher's definition of tree is nested lists. In which case, list of nesting depth of 0 is still a tree. So abc = [1, 2, 3, 4] Is a tree. In this case, the list is subset of tree. ...


8

A List is general and flexible. Generalized structures are ideal for return values in business, web, and desktop applications. It's not optimal to return a Deque or an Array if your consumers will be converting to List in most cases anyway. It's potentially less efficient. And, it clutters your consumers' codebases with boilerplate conversions and/or ...


7

Python actually supports insertion of arbitrary sub-lists, as a part of list slice assignment. You just assign to an empty slice before the element where you want to insert a new list: list1 = [1, 2, 3] list1[1:1] = [10, 20, 30] # insert 3 elements at index 1 print list1 # prints [1, 10, 20, 30, 2, 3] Many languages view lists as primarily sequential ...


7

Typically, people remove things from lists already knowing what those things are, as that knowledge is why they want to remove the item in the first place. By contrast, people don't usually want to remove specific known items from a stack/queue, but rather retrieve the first/last element. Probably relevant factors: Consistency with List<T>.Remove(T)....


Only top voted, non community-wiki answers of a minimum length are eligible