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

learn more… | top users | synonyms

3
votes
2answers
99 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 ...
18
votes
2answers
13k views

Sets Data Structure in Golang

I really like google golang but could some one explain what the rationale is for the implementors having left out a basic data structure such as sets from the standard library?
2
votes
3answers
63 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
0answers
44 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, ...
1
vote
1answer
87 views

Non-fixed-size Fenwick Tree implementation

I'm planning to implement a non-fixed-size Fenwick tree. That is, a Fenwick tree that allows interleaving range queries with adding/removing elements. All implementations and samples I've seen so far ...
0
votes
5answers
474 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
46 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
27 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
5k 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
55 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 ...
3
votes
1answer
94 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 ...
2
votes
0answers
63 views

Can't figure out class scheduling issue? [closed]

"You are a college advisor trying to help students plan their academic careers. You have the list of courses in each major and their prerequisites. Students often want to take their major courses as ...
1
vote
2answers
121 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 ...
3
votes
3answers
332 views

Is it worthwhile to try to write foolproof data structures?

The problem We need to store data in a table-like way, but we have very strict space constraints (~1Mb per table of 10k+ rows). We store data like this: ID | reviews | factor | score | interval | ...
2
votes
1answer
96 views

Best data structure to store data sorted alphanumerically AND by weight

What is the best data structure to store data sorted alphanumerically AND by weight (where weight is the first sorting criterion) with very low access time probably Olog(n) or better Application: A ...
7
votes
1answer
377 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 ...
45
votes
4answers
8k views

Which algorithms/data structures should I “recognize” and know by name? [closed]

I'd like to consider myself a fairly experienced programmer. I've been programming for over 5 years now. My weak point though is terminology. I'm self-taught, so while I know how to program, I don't ...
2
votes
0answers
23 views

IRLBot Paper DRUM Implementation - Why keep key, value and auxiliary buckets seperate?

Repost from here as I think it may be more suited to this exchange. I'm trying to implement DRUM (Disk Repository with Update Management) as per the IRLBot paper (relevant pages start at 4) but as ...
0
votes
1answer
56 views

What are the advantages of linear probing over separate chaining or vice-versa when implementing hash tables?

I've been brushing up on algorithms and reviewed these two methods of implementing hash tables. It seems like they largely have similar performance characteristics and memory requirements. I can ...
-3
votes
2answers
135 views

How to visualise this data model?

I have learnt different variants of list data model like Dlist, SList and recursivenodetype-list. But I could not understand/visualise this datamodel as mentioned below in C++ syntax, with an ...
8
votes
2answers
510 views

Is there any better approach to shortest path finding within a (vehicular) traffic network?

Dear fellow programmers, We're developing software which simulates vehicular traffic. Part of the process called "assignment" is concerned with assigning vehicles to their routes and has to use some ...
0
votes
1answer
53 views

Any good data structure to perform efficient lookup and modification operations about what are the shapes containing the current cursor position

I think I'm facing a pretty common issue but cannot remember which solution is the most suitable one. Let's put it that way: I can, in a, certain, given, language get some events anytime the user is ...
2
votes
1answer
196 views

When designing a data structure, should I implement very inefficient operations for convenience?

(I've added the .NET tags because the data structures are for .NET, and this question should be considered in the context of the conventions for that platform.) I'm writing a library of immutable and ...
2
votes
1answer
69 views

Is storing data directly in a list node better than storing a pointer to data?

Suppose we have two different doubly-linked list structures: One has content of the node embedded directly in the node: struct Content { // some stuff }; struct Node { struct Node *next; ...
0
votes
1answer
174 views

Is a linked list an actual data structure?

I hear conflicting sides from this topic. I was under the impression that a linked list was a way to implement a data structure (stack, queue), not actually a data structure.
1
vote
1answer
124 views

C# Structs, 16 byte rec. - Are getters and setters included in that?

I was reading into the nitty-gritty of structs in C# here: "C Fundamentals, The differences between struct and class." and at the very bottom it mentions keeping a struct below 16 bytes. I looked ...
0
votes
1answer
94 views

What's the algorithm should I use for seeing how well 2 strings match?

Suppose I have 2 strings: string1 = "home/lisa/Music/some_files/01.05 - Garden Ground.mp3" string2 = "Music/Jim Smith/Unknown/(Deluxe Version/Garden Ground).mp3" string4 = "Music/Jim Smith/Unknown/00 ...
4
votes
4answers
266 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 ...
0
votes
2answers
307 views

Storing and retrieving simple data within a framework

I'm determined to get a decent answer to this, because while I have my own approach (constants) I'm not convinced I'm doing it as efficiently as I could be. So I'm editing the entire question, to ...
0
votes
1answer
158 views

Injectable, Poppable Stack

Background A project involves converting a relational expression map (rxm) to an XML/SQL statement. The map resembles: root > people, # "root" keyword starts the document ...
0
votes
1answer
44 views

Boundary traversal in binary tree

How to perform boundary traversal in binary tree using only single traversal of the tree? I am doing it in this way (not a single traversal): void printBoundary (struct node* root) { if (root) ...
0
votes
1answer
154 views

Best Data structure for implementation of dependent drop-downs

I want to implement dependent drop-down feature on a web page in my website containing the following drop-downs: User's group name Group events (dependent drop-down) Locations (dependent drop-down) ...
3
votes
3answers
208 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 ...
1
vote
1answer
50 views

Difficulty in deciding correct data structure

Two objects are interacting (Object Alpha, Object Beta) Each contain a point (x,y) which will be used to make comparisons, among other things. Object Alpha's point (x,y) attribute is dynamic and ...
1
vote
1answer
93 views

Data structure for traversing hierarchical hostnames

So, quite often I'll come across a situation where I'd like to process hostnames in a hierarchical manner. For example, given a hostname "foo.bar.baz.example.com", I might want to compare it against ...
1
vote
5answers
240 views

What would an anti-tree look like?

I am wondering if the Tree data structure has a dual. Something that 'starts at the leaves and converge on the root'. If so, what's it called? Maybe I'm missing something completely obvious. I could ...
2
votes
1answer
60 views

How Javascript Engines access/lookup property names?

How Javascript Engines access/lookup property names? what kind of associative array (data structure or search/lookup algorithm) did they use? (for V8, TraceMonkey, JSC, and Rhino) For example, in C++ ...
1
vote
0answers
111 views

Optimal data structure for binary data/Java

I have several input formats mostly restricted to geotiff and some proprietary binary formats. I import them into my program and then need to export them into various other data formats (also binary) ...
0
votes
2answers
55 views

Approaches to get stats like average latency in last N seconds

I am receiving messages with latency information (LI, {date, latency}). For statistical reasons: (I am open to approx. approaches, stats monitor will be updated in 6-60 seconds) I want to monitor ...
0
votes
3answers
264 views

How to save complex data to file/disk?

I am working on a side project for a small business owner (my father) and part of the requirements for the application include saving customer and job related data in a way that it can easily be ...
2
votes
1answer
44 views

Multitenancy and nested set trees

The application I work on utilizes nested sets1 to represent tree structures within our database. We need to expand a particular area of access control to support multiple clients who should not be ...
0
votes
2answers
31 views

Making sure loaden (non default) config is valid

I'm writing a device Software in which the device must handle much data. Therefore it has a database, either on NV-Ram (Non-volatile memory) or a SD-Card. Due there's a DB which I can use, I also use ...
1
vote
4answers
133 views

What do polynomial algorithms entail?

From here, I know it is that an algorithm that... ...is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k) for some ...
11
votes
7answers
18k views

What is the point of using lists over vectors, in C++?

I've run 3 different experiments involving C++ lists and vectors. Those with vectors proved more efficient, even when a lot of insertions in the middle were involved. Hence the question: in which ...
0
votes
1answer
69 views

Application with really dynamic data structure [closed]

Well, I'm on the verge of this project that really puzzled me. The situation is, in our office, we have a department that collect data about the corporate performance indicators from all across the ...
5
votes
1answer
1k 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 ...
1
vote
2answers
73 views

Structuring data to represent a tree with squirrels

What I want to represent Let's assume I have several schemas of the following kind: It is a tree on which positions of squirrels are represented by a blue dot. The number of bifurcations differ ...
0
votes
1answer
292 views

How to remove a middle element from queue?

I had a question, about how to remove an element from middle of the queue , without disturbing the order of other elements. E.g. Queue before operation:- <| a b c d e |< Queue after ...
4
votes
2answers
98 views

Is it a good idea to have a database row that represents an unknown value within a system [closed]

We have two systems, System A imports a list of sports events from system B, it only wants to import the events we will be providing live data for, the filter used to hide events that we are not ...
-1
votes
2answers
105 views

Efficiently save big data structures [closed]

I need to save big data structure (Tree with specific nodes) into file efficiently. Data is always changing, so I need to rewrite whole data structure very often, so simple serialization is not good ...