Hot answers tagged data-structures
28
What Should I Know?
Minimum
I think an adept programmer should have at least undergraduate level knowledge in Computer Science. Sure, you can be effective at many jobs with only a small subset of Computer Science because of the rock solid community CS sits upon, and the narrowed focus of most professional positions. Alos, many people will further ...
26
There isn't one; it's a buzzword.
The delineator though is that your data is beyond the capabilities of traditional systems. The data is too large to store on the largest disk, the queries take tons too long without special optimization, the network or disk can't support the incoming traffic flow, a plain old dataview isn't going to handle visualization for ...
21
Most of the time: An anti pattern.
Why? Because it faciliates procedural programming with "Operator" classes and data structures. You separate data and behaviour which isn't exactly good OOP.
Often times: A DTO (Data Transfer Object)
Read only datastructures meant to exchange data, derived from a business/domain object.
Sometimes: Just data structure.
...
20
Nice Question.
Code may be represented by a DAG describing the
inputs and outputs of each of the arithmetic operations performed
within the code; this representation allows the compiler to perform
common subexpression elimination efficiently.
Most Source Control Management Systems implement the revisions as a
DAG.
Several Programming languages describe ...
15
Data Structures are, for the most part:
Memory resident,
Transient,
Limited in size,
Not re-entrant without adding concurrency mechanisms like locks or immutability,
Not ACID compliant,
Fast, if chosen carefully.
Databases are, for the most part:
Disk-bound,
Persistent,
Large,
Safely concurrent,
ACID compliant, with transactional capabilities,
Slower ...
14
It depends on the platform and implementation.
C++ guarantees that the size of char is exactly one byte and at least 8 bits wide. Then, size of a short int is at least 16 bits and not smaller than char. Size of an int is at least as big as size of short int. Size of long int is at least 32 bits and not smaller than int.
sizeof(char) == 1; sizeof(long int) ...
12
When I was learning queues, my professor always used the example of a store. There are 1 or more registers open at any given time, and the Customers enter one queue or another and move through that queue to purchase all of their items.
We actually had to implement a simple program that could move Customers through a RegisterQueue, so if you are actually ...
12
1. If you rarely add and remove data
What about using the same technique as the one used in RDBMS with indexes?
In other words, you'll have the unordered set containing the data, and four ordered sets containing the keys and the pointers to the items in the data set.
Of course, this may cause performance issues if you need to frequently add and remove ...
11
The answer is that it doesn't have much of anything to do with programming. It has to do with problem solving.
Just like linked-lists are data structures used for certain classes of problems, graphs are useful for representing certain relationships. Linked lists, trees, graphs, and other abstract structures only have a connection to programming in that you ...
10
Here's a blog post by the author, where he says
I thought that the basic organization of my dissertation was pretty solid, so mostly I was able to focus on adding and adjusting things to make it work better as a book. For example, I no longer had the constraint from my dissertation of having to focus on original work, so I was free to add data ...
9
You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.
For your queue implementation in ...
8
There are many differences between these two, but in practical terms, there are three main things to consider: speed, interpretability, and accuracy.
Decision Trees
Should be faster once trained (although both algorithms can train slowly depending on exact algorithm and the amount/dimensionality of the data). This is because a decision tree inherently ...
8
It sounds to me like you are attempting to solve the Knapsack Problem if you want a general solution where any denominations would work.
Put in those terms this is an unbounded knapsack problem where all the values are -1 and the weights are the denomination of the chip.
You should be able to find lots about the problem online.
8
I hope you realize that all of this is deeply implementation-defined, both for Java and C++. That being said, Java's object model requires quite a bit of space.
C++ objects do not (generally) need any storage except what the members need. Note that (unlike Java, where everything user-defined is a reference type), client code can use an objects both as value ...
8
The short answer is that cases seem to be few and far between. There are probably a few though.
One would be when you need to store a small number of large objects -- especially, objects that are so large that it's impractical to allocate space for even a few extra of them. There's basically no way to stop a vector or deque from allocating space for extra ...
8
It all has to do with the two things basically:
1) The speed of lookup (where integers for instance fare much better)
2) The size of indexes (where string indexes would explode)
Now it all depends on your needs and the size of the dataset. If a table or a collection has like 10-20 elements in it, the type of the key is irrelevant. It will be very fast ...
8
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 ...
7
Could anyone give an overview of how list structures which are composed of a head and a tail which references the rest of the list i.e linked list are represented in memory of the computer?
In a naive implementation, each node is allocated separately, so the nodes would be spread more or less randomly through the heap memory, wherever the memory ...
7
Whenever you are faced with a question like this and you simply do not have expertise in the problem domain it's good to do a couple things.
First acknowledge that you don't have specific expertise in this problem domain.
Second, explain how you would go about solving the problem.
Although I don't have specific experience when working with ...
7
You're entering the world of Semantics. There are public services that will parse text and pull out the major concepts (a quick search for Semantic API turned up a few) that will parse a free form document and return the major topics encountered including people, places, things, dates, and concepts. Some of the better ones will return in a format known as ...
7
o << endl is equivalent to the following code:
o.put(o.widen('\n'));
o.flush();
In other words, you should only use o << endl when you need to flush the stream. For example:
You're about to perform a time-consuming operating and want to make sure you display a message before doing so.
Another process is waiting on your output.
If more than ...
6
They are probably after an answer mentioning spatial indexing, most likely by selecting a database that provides spatial indexing out of the box, but you might also get a few points by mentioning it can be implemented in the application itself if needed e.g. by implementing an R-Tree (might be handy if the DB selection is fixed for other reasons? but also ...
6
In general, since this seems like a homework question and I don't want to give away the answer, here's the strategy to solving the problem.
Find the largest denomination at or below the value of the pot and divide the pot by that denomination
That's how many of that denomination of chip you require
Take the remainder of the pot, and repeat these steps ...
6
A simple algorithm that gives reasonably good results: Add the squared difference of each color component (red, green, blue) between the color you are looking for and the color in your list of colors and choose the color where the sum of those squared differences is minimal.
For a more accurate result, see the wikipedia article on color difference and ...
6
Generally, the "big arrow" (=>) in Perl is basically a comma, with one difference: everything on its left is treated as if it is quoted. So this:
Foo => Bar
Is the same as:
'Foo', Bar
For more info, see perlop.
6
I'd call it struct or record because it is used for data storage and this is very common to languages like C as you can see there: struct (C programming language). So personally I would prefer use a struct instead of a class that is more suitable and readable:
struct A
{
public string something;
public int a;
}
Usually they are used as DTOs (Data ...
6
Most the answers seem to be ignoring a couple of fairly major points.
First, in an awful lot of Java, you virtually never see a raw int -- nearly all use is of Integer, so the fact that an int could be (about) the same size as an int in C or C++ is almost irrelevant, except for that (in my experience, small) percentage of code that only uses int instead of ...
6
Dijkstra's finds the shortest path between a given node and all other nodes, so I expect it would be more expensive than A*. However, it looks like you're trying to pre-compute the cost & path from any node to any other? Then Dijkstra's is the way to go.
As for a simpler representation, a few things come to mind:
At many intersections, you can come ...
6
Part 1
This is a good design question. You are correct in detecting code smell concerning getters and setters. They generally indicate a design problem exposing the implementation details of your object.
Try to think in terms of what your objects should do - Tell, Don't Ask:
http://pragprog.com/articles/tell-dont-ask
http://c2.com/cgi/wiki?TellDontAsk
...
6
Is there anything special about those datatypes that is necessary for the completeness of the language?
Nope.
Many languages don't have hashes as a fundamental data structure in the language. And indeed, there are examples of languages that don't have arrays or lists either. (BCPL for instance).
And many languages have other fundamental data ...
Only top voted, non community-wiki answers of a minimum length are eligible
