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

learn more… | top users | synonyms

0
votes
1answer
236 views

Merging Two Binary Search Trees

What time in terms of Big O will it take to merge two BST's in One? Each having no of nodes n and height O(log n) with no common element. Resultant should be also a BST
32
votes
5answers
5k views

Why is deletion usually much harder to implement than insertion in many data structures?

Can you think of any specific reason why deletion is usually significantly harder to implement than insertion for many (most?) data structures? Quick example: linked lists. Insertion is trivial, but ...
1
vote
2answers
74 views

Objects with boolean data type

I have a collection of objects, and for each of them I need to know if a specific condition has been met. That is a ternary condition, it could be not yet tested, tested and failed, or tested and ...
3
votes
3answers
579 views

How can I represent a flowchart, complete with conditional logic using JSON or XML?

One part of a project I'm working on is interactive scripts for call centre staff. Pretty much every possibility I can think of in this case can be represented on paper as a flowchart, which is why I'...
2
votes
3answers
203 views

How does google calculate travel distance/time

I've been working for quite a while now on a service that generates optimal routes for a given set of addresses and vehicles (Vehicle routing problem / traveling salesman problem). Now it's all ...
4
votes
1answer
943 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 ...
3
votes
1answer
134 views

What to do when properties of a HashMap and ArrrayList are neccessary?

I have a data structure that stores various permission groups for a multiplayer game server. There is an instance of a "Rank" class for each permission group. Each rank also has a name. I need to be ...
1
vote
3answers
56 views

Find likely candidates for visited locations along gps track

I'm creating a visualization tool for workout data, specializing on bicycle rides. I'm looking for ways to generate more value from the data that was recorded. Since there usually is a GPS track ...
8
votes
2answers
333 views

How do I store multiple views of data in memory?

I have a bunch of modules. I can break these modules into different categories that are complete and do not overlap. For example, three categories, with ids that can be expressed as Animal, Vegetable, ...
2
votes
3answers
358 views

Which C# data structure should I use to quantify this information?

I am attempting to determine which data structure I should use for the following information: ("Water", 100F, 0F, 0F, 0F, 0F, 0F, 0F, 0F, 0F, 0F, ""); ("Tuna", 60F, 184F, 30F, .01F, ....
3
votes
2answers
74 views

Implementing incremental builds [closed]

I'm working on a toy language. Until now, multiple files have been compiled by merging the ASTs of each file and then running the semantic analysis and code generation phase on the merged AST. Now I'...
2
votes
0answers
29 views

Use dictionary value property as the dictionary key

I am creating an AST, and I am currently introducing the concept of "scope". By implementing a scope, wherever an identifier (variable name) is used, I am able to determine its original declaration. ...
2
votes
2answers
548 views

iOS Core data & NSUserDefaults

I am creating an App where users can search items from an external API. If the users likes an item they can store them into their personal "favourites item list". My question is, is it a good ...
2
votes
1answer
265 views

Does a tree node have an ancestor?

Below is a rooted tree, where any node C except root has one parent P Ancestors of a node C are the nodes on path from C to root, including P,P's parent,P's grandparent, .... till root. My ...
2
votes
1answer
95 views

Database Structure: A product that will only temporarily be available and then slightly change

I'm trying to migrate lagacy data to a new eCommerce system which I'm building myself and I have full control over (so I can modify it however I want). There is a product that came with a free gift ...
0
votes
2answers
3k views

C: How does struct node * next work? [closed]

In C, for creating linked list we write: struct Node{ int data; struct Node* next; }; So, my understanding is "struct Node* next" is a pointer variable of "Node" datatype. But how does it point to ...
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 ...
14
votes
1answer
3k views

PHP: when to use arrays, and when to use objects for mostly-data-storing code constructs?

PHP is a mixed paradigm language, allowing to use and return non-object data types, such as arrays. I pose a question to try to clarify some guidelines for selection of arrays vs objects when deciding ...
1
vote
2answers
758 views

Why do Haskell and Scheme use singly-linked lists?

A doubly linked list has minimal overhead (just another pointer per cell), and allows you to append to both ends and go back and forth and generally have a lot of fun.
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 ...
4
votes
1answer
202 views

Detecting surface faces of a huge 3D mesh/grid

I've written a module in my application that creates a mesh from existing coordinate and face data. The number of vertices in the mesh could easily exceed 10 million and the same goes for the faces. ...
2
votes
1answer
693 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 ...
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. ...
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 ...
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 ...
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 ...
5
votes
1answer
395 views

Efficient data structure to implement fake file system

I want to implement a data structure that will hold the paths of directories, sort of fake file system. Input:- I have a text configuration file containing the paths as follows ... C:/temp1 C:/...
2
votes
1answer
307 views

Combining simple and complex APIs in a web application?

We use C# MVC and Angularjs as the primary tools to develop our web applications. We've recently been discussing best practices, with an eye towards revising our development approaches into something ...
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' ...
8
votes
2answers
310 views

How to handle complex calculated fields in an ORM

In our API we've got a few central datatypes which need to be "decorated" (so to speak) after retrieval from the database with calculated values. The database is accessed through an ORM which follows ...
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 ...
10
votes
1answer
447 views

How does a skip list work?

For a homework assignment, I need to understand how a skip list works. I've been programming for a little over 2 years now (I know that's not that long in reality), and I have never even heard of a ...
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 ...
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) ...
-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 ...
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 ...
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 ...
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, ...
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: ...
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 ...
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 ...