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

learn more… | top users | synonyms

2
votes
1answer
82 views

Time complexity of update and lookup in binary random access list

I'm trying to get through one of the exercises in Okasaki's "Purely Functional Data Structures," where he presents a zeroless binary numbers as a structure for random-access list, and asks to 9.6 ...
1
vote
2answers
154 views

Lots of independent data structures into one big one

I have 10 independent data structures that contain unsigned bytes and bit fields from different data sources. I am using C++, and was looking for a way to combine all these data structures into one ...
10
votes
2answers
609 views

Is there a design pattern for managing deep many-to-many relationships?

I'm having trouble defining this data pattern I've come across working on several applications. It consists of: An object type which is composed of many objects itself A second object type, where ...
1
vote
0answers
108 views

Storing a many-to-many relationship between aggregate roots in a document store

Intro I'm currently facing a rather difficult problem. An application that we need to expand and partially overhaul, uses RavenDB as its storage backend (a NoSQL document store). The two most ...
2
votes
4answers
148 views

Clean Abstract Syntax Tree

I'm writing a toy compiler for fun. Basically, my problem is that I don't want to clutter the AST with stuff like debug information (symbol tokens, locations of tokens, etc) as well as data that the ...
2
votes
1answer
692 views

What is an efficient data structure for syntax highlighting in text editors?

I'm creating a very small text editor in C++ with the ncurses library. So far, it works great. I have implemented the Gap Buffer data structure to make the editing more efficient than a line-based ...
4
votes
2answers
165 views

Mutable AST vs. different immutable ASTs

I am writing a toy compiler. During the semantic passes, I want to add information to the AST. Which of the following is the best approach? Define 1 mutable AST type whose fields are updated with ...
8
votes
2answers
5k views

Why does Python use hash table to implement dict, but not Red-Black Tree? [closed]

Why does Python use hash table to implement dict, but not Red-Black Tree? What is the key? Performance?
4
votes
1answer
134 views

What method should I use to populate a tree as I'm consuming data that is contained within the tree?

I have a tree that consists of 5 types of nodes - V, W, X, Y, and Z. V represents the root node, and a given tree has exactly one element of type V. A V contains one or more Ws, a W contains one or ...
-6
votes
3answers
627 views

How can the containsKey() method of a Java Hash Table be O(1)? [duplicate]

I had a very large ArrayList in Java, and I often need to check if it contains a particular value. This has proven very slow. Then I discovered that you can use a data structure based on a Hash. ...
0
votes
0answers
126 views

Enterprise Mashups. A good approach for .net

I'm in the middle of trying to talk our management into letting us do a portal that sits across the many, many systems that we use. I believe in using the best tool for the job so we have a good ERP, ...
2
votes
4answers
2k views

Is it possible to efficiently store all possible phone numbers in memory?

Given the standard North American phone number format: (Area Code) Exchange - Subscriber, the set of possible numbers is about 6 billion. However, efficiently breaking down the nodes into the sections ...
1
vote
1answer
42 views

How to represent alternative and sequential tasks?

I am experimenting with hierarchical task planning (in python) and I would like to have functions which return lists of tasks. I need to differentiate between alternative paths and sequential tasks. ...
1
vote
0answers
101 views

Search algorithm on sequential data model

For sequential data models like LinkedList, search algorithms like linear-search and binary-search are well known. Are their any other search algorithms apart from these two, that work on sequential ...
5
votes
4answers
524 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 ...
4
votes
2answers
386 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs (...
4
votes
2answers
340 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 ...
0
votes
2answers
200 views

Is there a name for this data structure pattern consisting of a list of dictionaries each with one entry, consisting of an object? [closed]

There is a data structure idiom that looks something like this: [ { obj_1_id: { key1: value1_1, key2: value2_1 } }, { obj_2_id: { key1: ...
2
votes
2answers
43 views

How to manage ongoing data migrations?

I work in a SaaS project in which each user can have a representation of some common data at a given point in time. For the sake of example, let's consider that each user's data is metadata about them ...
6
votes
3answers
457 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) | ...
5
votes
1answer
495 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 ...
7
votes
1answer
646 views

Algorithm/data structure to answer “what recipes can I make with this set of ingredients?”

Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ...
19
votes
3answers
39k views

Abstract Data Type and Data Structure

It's quite difficult for me to understand these terms. I searched on google and read a little on Wikipedia but I'm still not sure. I've determined so far that: Abstract Data Type is a definition of ...
11
votes
3answers
529 views

Do binary trees serve a specific purpose in storing hierarchical data? What is their canonical use?

I understand the structure of binary trees and how to traverse them. However, I am struggling to realize their actual uses, purposes in programs and programming. When I think about 'real life' ...
12
votes
2answers
4k views

What is the relationship between data structures and algorithms? [closed]

I have been searching for a good online course in data structures but have found that Google also returns results for algorithms courses, which say stuff like: In this course you will learn ...
11
votes
2answers
5k views

Using a stream manipulator (endl) or a newline escape character (\n)?

I don't have a specific context in which I'm asking the question, but while I was reading a beginner book on C++ I noticed the use of both an endl stream manipulator and a newline escape character ...
3
votes
1answer
157 views

Providing views to an std::container

I want to maintain a buffer of 5 seconds of sensor data. The sensor data consists, among other things, of accelerometer readings in x,y,z dimensions, gyroscope readings in x,y,z dimension and ...
106
votes
15answers
83k views

Why are data structures so important in interviews? [closed]

I must confess that I was not so strong in data structures when I graduated out of college. Throughout the campus placements during my graduation, I've witnessed that most of the biggie tech companies ...
1
vote
1answer
101 views

Best practices for tracking multiple pieces of data in a program

I have a project in C (don't ask why but it needs to be in C), where I need to track multiple pieces of data and commands for different modules. Some actions that the program will take depend on the ...
2
votes
5answers
522 views

std::vector Non-Array Implementation?

I've seen some posts on the StackExchange family of sites talking about std::vector implementations. They all seem to indicate that std::vector is implemented strictly as an array (in practice), and ...
1
vote
3answers
2k views

Does the Head(start) pointer of Doubly Linked list points previously to the tail(last) node

I have one question in my mind that in case of circular doubly linked list the head pointer of the doubly linked list also logically point to the next pointer of the tail node of the linked list and ...
-3
votes
1answer
660 views

Dictionary representation of an object

As python memory model is dictionaries of dictionaries, looks like any object in JavaScript has similar representation. Below code, > foo = {} makes foo as an empty dictionary {}. fine. If ...
3
votes
2answers
1k views

Name of data structure that's tree-like with multiple root nodes

I'm attempting to implement a data structure, and using a more traditional tree data structure, but I'm not using the root node as it holds no real value in the context I'm using it in. Ideally, I ...
4
votes
1answer
399 views

How to store data that is recorded with different frequency?

I'm writing a metallurgical web application, that must store data (electrical parameters) recorded at different frequencies. For example: six parameters recorded with frequency of one measure per ...
1
vote
2answers
162 views

Efficient datastructure to create size-limited dictionary

I need a class that acts like a dictionary but will constrain the total number of key/value pairs it contains. For instance, let's say the maximum number of entries is 1000 and the class already ...
20
votes
3answers
2k views

How do purely functional programming languages deal with fast changing data?

What data structures can you use so you can get O(1) removal and replacement? Or how can you avoid situations when you need said structures?
0
votes
1answer
977 views

I need a data structure for a card game

I am programming a card game in java, and unsure what data structure I should use for the player's hand. I considered using an array, with one integer to traverse the array and another integer to ...
1
vote
2answers
538 views

Complex data structure in python: just dict, etc, or some classes?

Consider a web service API that returns a complex Json object. Using the stock Python tools for the job, this will read in from the web service as a dict which contains, in turn, a mixture of arrays, ...
8
votes
2answers
693 views

How do personal assistants typically generate sentences?

This is sort of a follow up to this question about NLG research directions in the linguistics field. How do personal assistant tools such as Siri, Google Now, or Cortana perform Natural Language ...
3
votes
4answers
2k views

What do you call an iterator that returns the current, previous and next siblings of each node of a list? [closed]

What do you call an iterator that given a list [a, b, c], returns an object of the form { prev, curr, next } for each iteration? e.g, (? === undefined) { prev: ?, curr: a, next: b } { prev: a, curr: ...
9
votes
13answers
22k views

What are some good, simple examples for queues? [closed]

I'm teaching CS2 (Java and data structures), and am having some difficulty coming up with good examples to use when teaching queues. The two major applications I use them for are multithreaded message ...
8
votes
2answers
392 views

What data structure would you use to represent an organic compound?

Are there any good data structures out there that can be used to represent a molecule? I was thinking maybe I represent it as a Graph by making every atom a vertex, however, it's common for organic ...
50
votes
11answers
14k views

How to represent a Rubik's Cube in a data structure

If I am attempting to simulate a Rubik's Cube, how would you create a data structure to store the cube's state in memory, with X number of tiles per side? Things to consider: the cube can be of any ...
5
votes
2answers
1k views

Is it possible to speed up a hash table by using binary search trees for separate chaining?

I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and ...
3
votes
2answers
207 views

MaxHeap-like data structure supporting max AND min, also decrease-key (yes decrease-key)

For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations: load from array ...
0
votes
5answers
1k views

Fastest way to determine if a value is in a list?

I'm aware there may not be a good solution to this problem. I'm looking for a fast algorithm that determines whether or not a value (let's say an integer) exists in a set of values, however I need the ...
0
votes
0answers
152 views

scrabble solving with maximum score

I was asked a question You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word ...
0
votes
0answers
151 views

How to model dynamic table schema in .Net code

I am preparing to do an upgrade of a fairly large program that is currently written entirely in MS Access, both GUI and data (code and data in separate files). One of the key features of the product ...
16
votes
8answers
7k views

Is having trouble with data structures common for beginners? [closed]

I'm taking my second course on Java. We are getting into data structures. I have done an assignment on a linked list, and now a stack. I had a hard time with the linked list. The stack gave me a ...
1
vote
2answers
90 views

Passing context around AST nodes

I have various objects inside my AST, such as IfBlock, FunctionBlock, LogicExpression, etc. All of those objects share a context, which is basically a hashmap with some variables. It's a very simple ...