Questions regarding efficient storing and representing data within a software application.

learn more… | top users | synonyms

6
votes
4answers
570 views

Understanding the Macro Aspects of Data Structures

I am studying data structures right now, but I still need to find a teacher/site/book with a clear explanation of the macro aspects of this topic. What I mean is: most lessons/text books mix ...
6
votes
3answers
2k views

How do you choose a programming/data structure/algorithm book? [closed]

I really should not be mentioning the name of the book, but the first time I read it (during my under-grad days) I almost concluded that data structure was a bad course to pick. Which brings me to ...
6
votes
3answers
1k views

Is a tree with nodes that have reference to parent still a tree?

If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore? Wikipedia definition is: In computer science, a tree is a widely used abstract data ...
6
votes
3answers
1k views

Faster reads, on an infinite grid plane, than using a hash table?

In the past, I've had alot of success just using a .NET Dictionary, with a TKey consisting of the X,Y coordinates merged together. However its read performance, despite being amortized constant time, ...
6
votes
2answers
4k views

Nested Enum type in C++ or C#?

I've come across a recurring issue in a few of my recent projects in which I find myself using enums to represent state, or type, or something else, and I need to check against a few conditions. Some ...
6
votes
3answers
6k views

What is the best way to store a table in C++

I'm programming a decision tree in C++ using a slightly modified version of the C4.5 algorithm. Each node represents an attribute or a column of your data set and it has a children per possible value ...
6
votes
1answer
3k views

What is the usage of Splay Trees in the real world?

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: ...
6
votes
2answers
1k views

What data structure could I use for modeling a network of nodes and edges?

My application needs to model of and perform operations on a network with 40 - 50 nodes and typically less than 6 edges per node. Both nodes and edges are objects with around 1K data each. During ...
6
votes
3answers
427 views

Hashing growth strategy

What is a good growth strategy for hash tables? If the number of elements exceeds the number of buckets, I increase the number of buckets with the following formula: n = int(n * 1.618033988749895) | ...
6
votes
2answers
1k views

How do scalable bloom filters work?

I was reading up on scalable bloom filters and could not understand how each time a constituent bloom filters fills up, a new bloom filter with larger size is added. The elements that contributed to ...
6
votes
1answer
173 views

Unit testing a text index

Consider a text index such as a suffix tree or a suffix array supporting Count queries (number of occurrences of a pattern) and Locate queries (the positions of all the occurrences of a pattern) over ...
6
votes
1answer
316 views

How to design data structures for sharding?

When designing data structures for an application, what are some best practices to make sure it can be sharded? In particular, which of the following is better: Creating relationships in databases ...
6
votes
1answer
536 views

Min cost concatenation alignment [closed]

I am doing a project on data mining. I have a very large string of size, say n and many small strings, l_1,l_2.. each of size at most m. I want to find the sequence of small strings such that their ...
5
votes
2answers
893 views

Overriding GetHashCode in a mutable struct - What NOT to do?

I am using the XNA Framework to make a learning project. It has a Point struct which exposes an X and Y value; for the purpose of optimization, it breaks the rules for proper struct design, since its ...
5
votes
1answer
382 views

Can anyone explain to me what problem Core Data solves? [closed]

Core Data seems to add a needless layer of complexity. If you want to save data created natively by the user in an app why not just use an object and then write the data all to SQLite or back to a ...
5
votes
2answers
853 views

Do you get the benefits of a B-Tree in a managed language?

My understanding is that one of the key features of a B-Tree (and a B+Tree) is that it is designed such that the size of its nodes are some multiple of the block size of whatever media the data is ...
5
votes
6answers
1k views

What's the difference between a stream and a queue?

What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of ...
5
votes
3answers
130 views

How to create “constructors” for structures in C

The problem I have this structure that I want to create a "constructor" for it. struct example { int x, y, z; /* various members */ struct another *another; /* pointer to another structure ...
5
votes
2answers
327 views

Why Do B+ Trees Have a Minimum Occupancy of 50%?

As far as I can tell, the basic operations (add, delete, search) on a B+ Tree would function the same if minimum occupancy was 1, or 1/3, or any other function on node size. All the sources available ...
5
votes
2answers
494 views

Is it safe in Haskell to save a data structure to a file using “show”, and retrieve it using “read”?

Say I have the following types: type EndsTup = (Int,Int) -- (0-based index from start or end, Frequency) type FreqTup = (Char, [EndsTup], [EndsTup]) -- (Character, Freqs from start, Freqs ...
5
votes
1answer
144 views

Is it possible to have these characteristics in a data structure?

I was tutoring a student that came up with this assignment. It basically requires a data structure with the following characteristics: it holds a set of integers in {1, 2, ..., n} n is power of 2 ...
5
votes
2answers
5k views

Optimal way to store 18 billion key, value pairs [closed]

I have around 200 million new objects coming in, and a 90 day retention policy, so that leaves me with 18 billion records to be stored in the form of key-value pairs. Key and value both will be a ...
5
votes
2answers
374 views

How can a true Vector be implemented in Haskell?

How could a true Vector type be implemented in Haskell? In order for something to be a Vector, it has to be stored sequentially in memory, with O(1) random access. But Haskell hides its memory ...
5
votes
7answers
2k views

Priority list of tasks stored in a database

I am trying to think of the best way to do the following: I have a list of tasks stored in the database. A task has a priority assigned to it. You can change the priority of a task to reorder the ...
5
votes
4answers
390 views

Quadtree with duplicates

I'm implementing a quadtree. For those who don't know this data strucutre, I am including the following small description: A Quadtree is a data structure and is in the Euclidean plane what an ...
5
votes
2answers
2k views

Creating huge decision tree

I'm to write an event correlator. A fundamental part of the system will be a decision tree that recognizes the origin of the fault basing on recorded states and log files. Often many accidents will ...
5
votes
4answers
275 views

Is there a pattern that will help with this data structure

I'm doing a java project. My main structure contains 2 lists with elements of type A the other type B. B itself contains a list of objects which may contain elements of A. It must be that when an ...
5
votes
1answer
441 views

How to store satellite data in C data structures

I've been reading through Introduction To Algorithms 3rd Ed, and I am having difficulty in implementing some practical situations. It's not the theory, or implementing the internals of the data ...
5
votes
1answer
4k views

Homogeneous vs. heterogeneous AST representation

What are the reasons to choose a homogeneous vs. a heterogeneous AST representation for implementing a complex domain-specific programming language? Just to be very clear about what I'm asking, here ...
5
votes
2answers
574 views

Fast set indexing data structure for superset retrieval

I am given a set of sets: {{a,b}, {a,b,c}, {a,c}, {a,c,f}} I would like to have a data structure to index those sets such that the following "lookup" is executed fast: find all supersets of a given ...
5
votes
2answers
2k views

Data structure for pattern matching

Let's say you have an input file with many entries like these: date, ticker, open, high, low, close, <and some other values> And you want to execute a pattern matching routine on the ...
5
votes
2answers
343 views

Data structures for storing finger/stylus movements in drawing application?

I have a general question about creating a drawing application, the language could be C++ or ObjectiveC with OpenGL. I would like to hear what are the best methods and practices for storing strokes ...
5
votes
3answers
170 views

Maintaining a list of nodes with challenging requirements

This is a question regarding the design of a collection of ordered nodes which have some requirements that I am struggling to satisfy. In the problem area that I am dealing with we have routes which ...
5
votes
1answer
179 views

Bloom filters or similar, but with no false positive

To improve some lookups, I am considering the use of Bloom Filters. But in my use-case, the most probable outcome is that the element do exists in the target set. Bloom filters can have false ...
5
votes
2answers
999 views

Efficient Data Structure for holding a graph

Problem Link - http://opc.iarcs.org.in/index.php/problems/NUMTRIPLE In my opinion, the problem can be solved by a data structure, that shows how each number is connected to another, and via recursion ...
5
votes
1answer
2k views

Building a Graph Editor - How to create a data driven graph

I am developing a graph-editor that uses drag and drop to build hierarchical graphs (containing nodes and links). Each node in the graph should be linked to a table in our database (SQL Server). I did ...
5
votes
3answers
399 views

Generating Deep Arrays: Shallow to Deep, Deep to Shallow or Bad idea?

I'm working on an array structure that will be used as the data source for a report template in a web app. The data comes from relatively complex SQL queries that return one or many rows as one ...
5
votes
4answers
292 views

Users creating instances from a template - is there a software pattern that corresponds to this use case?

I am looking into designing a system where users build a template item and then create many instances based on this template.They then need to be able customise each instance but I also need for them ...
4
votes
5answers
687 views

Is my understanding of abstract datatypes correct?

After reading lots of pages on various sites, I came to the conclusion that abstract datatype helps to separate the use of datastructure from its implementation. We can easily map the data into a ...
4
votes
10answers
965 views

Standardized Data Structure Interface

I want to work with a variety of data structures (arrays, singly/doubly linked lists, sorted structures, etc.) on a plug-and-play basis. For example, I want to be able to easily swap in and out the ...
4
votes
2answers
474 views

Is there any particular reason for the use of lists over queues in functional programming languages?

Most functional programming languages such as Scheme and Haskell use lists as their main data structure. Queues are identical to lists, except for the fact appending to the end - not to the begin - ...
4
votes
2answers
3k views

Is there a way to handle nested Collections more elegantly?

My question is rather a design question. In my program I got to a data structure that looks something like this: private ConcurrentHashMap<A, ConcurrentHashMap<B, ConcurrentHashMap<Integer, ...
4
votes
2answers
1k views

Same constructor signature with different semantics?

Occasionally, I'm confronted with the problem that I have to provide some constructors in order to initialize objects with different sets of data. These sets can be mathematically transformed into ...
4
votes
2answers
6k views

What is the advantage of using map datastructure?

I am a member of some online coding website and today when I submitted a solution in C++, I saw there were much better answers in C++ itself which took considerably less time. The solutions were open ...
4
votes
1answer
770 views

Why is there not a basic SortedList<T>?

As far as I know, there is no way to get a List<T> with the capacity to sort itself. If I add a element, I want the data-structure to insert it in the right position (based on the associated ...
4
votes
4answers
329 views

Why use an enum to determine node type in a parse tree?

The Sun Compiler Tree API uses an interface called Tree as the parent of all the different kinds of parse tree nodes (assignments, if-statements, class declarations, etc.). A part of this interface is ...
4
votes
3answers
8k views

How can I practice implementing data structures and algorithms? [duplicate]

I just finished learning the basics on data structures and algorithms using Python and C, completing some of the exercises from the book I read. I feel that it is necessary to implement some of these ...
4
votes
2answers
328 views

Is this data model a list or tree?

Using python syntax with below environment diagram, teacher taught us that there are 11 trees(orange boundary) in this diagram, including leaf. It has been taught here, lists are represented as a ...
4
votes
4answers
457 views

Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...
4
votes
2answers
1k views

Which design better when use foreign key instead of a string to store a list of id

I'm building online examination system. I have designed to table, Question and GeneralExam. The table GeneralExam contains info about the exam like name, description, duration,... Now I would like to ...