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

learn more… | top users | synonyms

1
vote
2answers
2k views

2D linked list vs. multidimensional array/vector

I hope that programmers is the correct stack exchange for this, as it is quite a concept based question. I'm working on a data structure in C++ that is a represents data in 3D space. The x-y plane is ...
9
votes
2answers
635 views

In-memory datastore in Haskell

I want to implement an in-memory datastore for a web service in Haskell. I want to run transactions in the STM monad. When I google hash table steam Haskell I only get this: Data. BTree. HashTable. ...
2
votes
1answer
51 views

I have an unordered list of rectangles and their neighbors on four sides with no origin. How can I efficiently convert this into a grid?

I am writing a GtkGrid-like container for my GUI library for Go, and I'm trying to write the actual layout part of the code. Basically, I have an unordered list of controls. Each control is a ...
3
votes
2answers
4k views

Difference between a heap and a priority queue

I always thought that heaps and priority queues were synonyms - an abstract data structure that supports the insert, findMin and deleteMin operations. Some literature seems to agree with me - Chris ...
2
votes
1answer
322 views

What is the “best practice” for converting an external API's data structure?

When an API's data structure does not fit well with an angular app, I am trying to determine the best-practice in my specific design and implementation for converting it to a usable structure. I was ...
2
votes
1answer
201 views

Tokenizing Text Held in a Rope Data Structure

I am building a text editor which makes use of a Ragel based tokenizer to support syntax highlighting. I am considering the use of a rope data structure to support efficient modifications and ...
5
votes
3answers
3k views

How exactly is an Abstract Syntax Tree created?

I think I understand the goal of an AST, and I've built a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice ...
0
votes
1answer
110 views

How to make the members of my Data Access Layer object aware of their siblings

My team currently has a project with a data access object composed like so: public abstract class DataProvider { public CustomerRepository CustomerRepo { get; private set; } public ...
7
votes
1answer
213 views

Are “skip deltas” unique to svn?

The good folks who created the SVN version control system use a structure they refer to as "skip deltas" to store the revision history of files internally. A revision is stored as a delta against an ...
10
votes
2answers
751 views

How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear

I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage. In my scenario, a number of users who are hostile to each other are all trying to ...
3
votes
2answers
199 views

Should I use nested matrices or dictionaries?

As per Should I ask my question about which data structure to use here? I'm asking this here. Hopefully this isn't too implementation specific. I'm currently developing a program that will represent ...
3
votes
2answers
77 views

1 class model or 3 class models? 1 for each - UI, Hardware API Library, and Database

I've always used one class model in all 3 area's of my projects. User Interface, Hardware API (for data collection), Database (entity database context). Every new project only seems to grow in size, ...
0
votes
1answer
65 views

How to chain together points in an array

I have a series of points with lengths and rotations like this: I need to create separate chains from points whose lines overlap but I’m having real trouble doing this efficiently. I have an array ...
4
votes
2answers
398 views

Are bloom filters actually faster than hashes, even taking in account cache?

Bloom filters look really great when you consider you can determine if an Int is in a set with 99% certainty in constant time. But so can hashes, with the only difference that, in a hash, most of the ...
14
votes
8answers
34k views

Dictionary vs List

So I ran into a Dictionary<int, int> today at work. This just seemed weird to me because I would have probably just used a List<int> instead. Is there a difference and would there be a use ...
0
votes
3answers
265 views

Why is the complexity of fetching a value from an array be O(1)?

How come the complexity of fetching a value from an array by it's index is O(1)? I thought the algorithm has to go through all the indexes, find the correct index, and then know what value to return. ...
0
votes
2answers
266 views

boolean operations in C using bitfields

I am trying to implement boolean data type in C. Basically, I am working with sets. The following code can be used to access each bit but I am unsure whether I can represent sets using this method. ...
1
vote
3answers
501 views

Tournament bracket method to put distance between teammates

I am using a proper binary tree to simulate a tournament bracket. It's preferred any competitors in the bracket that are teammates don't meet each other until the later rounds. What is an efficient ...
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
4answers
1k views

Writing a new programming language - when and how to bootstrap datastructures?

I'm in the process of writing my own programming language which, thus far, has been going great in terms of what I set out to accomplish. However, now, I'd like to bootstrap some pre-existing data ...
2
votes
1answer
242 views

How should data transfer between a client and a web API for normalized data be designed?

I want to design an API backed by some database (doesn't really matter which, but to make the discussion more interesting, let's say it's Mongo - explanation below) which sends data to a client. The ...
4
votes
2answers
271 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 ...
0
votes
3answers
2k views

Nested maps vs. combined keys

in the project I am currently working on we had three different types of prices depending on the age of the user (adult, child, etc...). So we had on the DB a table looking like this: PRICES type ...
5
votes
2answers
384 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 ...
1
vote
2answers
1k views

What is the underlying mechanism behind va_list and where is it defined?

http://www.cplusplus.com/reference/cstdarg/va_list/ According to the above link, va_list is an argument or parameter used in some macros - va_start, va_arg, va_end. These macros are present in the ...
4
votes
3answers
3k views

Data Oriented Design - impractical with more than 1-2 structure “members”?

The usual example of Data Oriented Design is with the Ball structure: struct Ball { float Radius; float XYZ[3]; }; and then they make some algorithm that iterates a std::vector<Ball> ...
2
votes
2answers
530 views

Best way of storing a small number of user credentials

I'm working on a messaging application, based on a server/client architecture. Now I am thinking about the way how to store the user credentials. It's not a huge number, just about 20 entries with ...
0
votes
2answers
244 views

High-level strategy for distinguishing a regular string from invalid JSON (ie. JSON-like string detection)

Disclaimer On Absence of Code: I have no code to post because I haven't started writing; was looking for more theoretical guidance as I doubt I'll have trouble coding it but am pretty befuddled on ...
19
votes
4answers
9k views

EAV - is it really bad in all scenarios?

I'm thinking to use EAV for some of the stuff in one of the projects, but all questions about it in stackoverflow end up to answers calling EAV an anti pattern. But I'm wondering, if is it that wrong ...
5
votes
2answers
742 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 ...
0
votes
1answer
473 views

What data structure is suitable for implementing dynamic huffman encoding and decoding on a piece of text?

Some pseudo code or resources will be appreciated.I was thinking if implementing it in form of a BST stored in an array. However,not all operations can be performed easily using this approach. I am ...
22
votes
2answers
849 views

Is there a data structure for this type of list/map?

Perhaps there's a name for what I want, but I'm not aware of it. I need something similar to a LinkedHashMap in Java, but where it returns the 'previous' value if there's no value at the specified ...
1
vote
4answers
771 views

Data structure for file search

I've asked this question before and I got a few answers/idea, but I'm not sure how to implement them. I'm building a telecom messaging solution. Currently, I'm using a database to save my ...
3
votes
2answers
546 views

Data structure for grid with negative indeces

Sorry if this is an insultingly obvious concept, but it's something I haven't done before and I've been unable to find any material discussing the best way to approach it. I'm wondering what's the ...
2
votes
1answer
404 views

Where to implement thread-safety logic for my queue data structure?

I will immediately confess that I do very little multithreading, so questions of style and organization in this domain a little fresh to me. I've written a data structure (in Python, if that matters) ...
10
votes
2answers
946 views

Ideal data structure for storing map data?

I was asked this in an interview test. I did okay on the test but didn't know enough to answer this question. I am curious to know what data structures I can use to query the data quickly. Basically ...
1
vote
1answer
42 views

Benefits of caching the count of items in a data structure versus on-demand calculation?

Given a data structure, I want to provide an API method Size which returns the number of items. I am vacillating between 2 approaches: Maintain a count and increment/decrement it in response to ...
6
votes
1answer
506 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 ...
1
vote
3answers
390 views

Choice between 1-dimensional and 2-dimensional array

I'm implementing the Chessboard class to represent the chessboard. I've to implement the transformations (reflections and rotations) on the chess board possible. The possible transformations includes ...
-1
votes
1answer
398 views

Does implementing algorithms improve your programming skills? [duplicate]

I have been self studying algorithms and data structures for some time now and currently enjoying it. Whenever I understand an algorithm, I usually try to code them from scratch for fun and I always ...
0
votes
1answer
391 views

How does Google store its PageRank matrix?

I'm curious to know how Google stores the matrix that's used in the PageRank algorithm; and am looking for a data-structure for storing a very-large (not fitting in memory of any one computer) sparse ...
1
vote
2answers
2k views

Equivalent of #map in ruby in golang

I'm playing with Go and run into something I'm unable to find in Google, although there is certainly something that exists: I'm using the following struct: type Syntax struct { name string ...
3
votes
6answers
2k views

How did programmers implement Linked list ideas before the object oriented paradigm?

Linked lists, as far as I have seen, are largely implemented using object-oriented ideas. (having an object that holds some information and the address of the next link). How were Linked-lists ...
1
vote
3answers
368 views

what is the javascript internal data structure?

Consider a basic js object: var obj={x:1,y:'2'}; Is this stored internally as a hashtable or does js use a different mechanism for key value pairs? If they are hash tables does anyone know how they ...
0
votes
1answer
875 views

What happens to equal elements when inserting into a binary search tree?

Most BST examples show a sample of a BST with unique values; mainly to demonstrate the order of values. e.g. values in the left subtree are smaller than the root, and values in the right subtree are ...
6
votes
6answers
6k views

Why is the usage of string keys generally considered to be a bad idea?

This has been bugging me for a while. Most of the time, when it comes to storing data in structures such as hashtables, programmers, books and articles insist that indexing elements in said structures ...
24
votes
7answers
4k views

Should I keep investing into data structures and algorithms? [closed]

These days, I'm investing heavily in data structures and algorithms and trying to solve some programming puzzles. I'm trying to code and solve with Java and Clojure. Am I wasting my time? should I ...
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 ...
2
votes
5answers
587 views

how to design a stack without using java library or using list [closed]

I have a question how to design a stack without using list or array? This is one question that I want to think about as I want to better understand stack.
8
votes
8answers
17k views

What is the difference between an Array and a Stack?

According to Wikipedia, a stack: is a last in, first out (LIFO) abstract data type and linear data structure. While an array: is a data structure consisting of a collection of elements ...