New answers tagged data-structures
The Fenwick Tree is a space-efficient data structure because it foregoes the original data and instead only stored some "encoded" version. As you have noticed, however, this encoding means that you cannot add or remove an element (except at the tail) without a lot of churn. If your add/remove operations are infrequent enough than rebuilding the whole ...
It's hard to say, given what you've put into your question (no mention of language or performance requirements). An array will work. As you noted, you can remove finished effects then add logic to handle the holes. If it's an array of objects, just setting that element to NULL should suffice. You can also have a field isFinished inside an object if you ...
Your representation is simply a way to store a graph. You can use a WITH RECURSIVE clause to follow links between nodes. PostgreSQL documentation (actually first answer to "with recursive sql" by google) show a few examples.
In general, trees should not know about their parents. As you traverse the tree, you can see all children (and their children, and so on) to know if you need to do some work. Deciding once you get to the children that you need to go back is sloppy, and makes many algorithms more difficult/complex. And by keeping the knowledge in one direction, you reduce ...
Your immediate problem can be solved by not storing types of expressions as AST nodes. Create a separate type for types. This can be immutable and without parent references so you never have to clone it. There should be no reason to want to navigate from a type to its parent type. It also avoids having your expression types carry around information like ...
I think this has to do with golang focus on simplicity. sets become really useful with difference, intersection, union, issubset, and so on.. methods. Perhaps golang team felt that that is too much for one data structure. But otherwise a "dumb set" that only case add, contains and remove can be easily replicated with map as explained by @jozefg.
When you are designing a programming language, you generally want the core of the language to be as simple as possible but as general as possible and as expressive as possible, while still fulfilling its core design objectives. When you add a feature to a language, you have to consider how it fits with the overall design and philosophy of the language. ...
Inserting everything takes no comparisons, sorting it afterwards is in O(n*log(n)) so inserting and then sorting is in O(n * log(n)) Inserting one element into a sorted list so as to maintain a sorted list is logarithmic in the size of the list, so inserting n elements into that list is in O(n * log(n)) since the size of the list grows as you keep inserting ...
Insertion sort works best when you are inserting a new value into something that is already sorted. So what I would do is use Quicksort to sort the original dataset that you have, then when additional log entries come in, add them one by one into the already sorted set. With Quicksort being O(n*logn) and Insertion Sort being O(n) when used with an already ...
It sounds like you need a thread pool of workers to which you can pass selection criteria (for the database call) and a reference to the chart area. Then you can have each worker query the database for a subset of the data, and have it plot its portion of the graph. You may have to mediate access to the graph area (I have no idea how QT is structured), but ...
Have a look at the Batch Iterator (or Chunky Iterator) Pattern from POSA5. There is also a book if you want more detail. Assuming you understand the Iterator pattern, the batch iterator does the chunking based on the size of the data structure it uses (the iterator's client is unaware of how chunking occurs).
This might be too general for what you're looking for, but it sounds like a kind of directed graph.
Linked lists are very commonly persistent and immutable. In fact, in functional programming languages, this usage is ubiquitous. Tail pointers break both of those properties. However, if you don't care about immutability or persistence, there is very little downside to including a tail pointer.
You are correct, a tail pointer never hurts and can only help. However, there is a situation where one does not need a tail pointer at all. If one is using a linked list to implement a stack, there is no need for a tail pointer because one can guarantee that all accesses, insertions, and removals occur at the head. That being said one might use a ...
Typically I would use some embedded relational store for that. Some kind of Prolog in Lisp might do. A self-written data structure could be like this: a CLOS class for the triple: meaning, form, score a hash-table mapping from a meaning to a list of triples a hash-table mapping from a form to a list of triples The lists of triples could be sorted by ...
The StackOverflow post @manlio pointed out is an exact duplicate. Basically, yes, the algorithm can improved to O(n+m); the approach is to flatten the trees to sorted lists, merge them, and recreate a BST. This page also has some example code that may be of interest as well.
Top 50 recent answers are included