Questions tagged [data-structures]
Questions regarding efficient storage and representation of data within a software application.
1
vote
0answers
36 views
How to use lock-free FIFOs in multi-threading?
Computer-science wisdom says that a lock-free FIFO (queue) is the right way to synchronize shared data between two threads in a lock-free manner. I know what a queue is and how the lock-free property ...
0
votes
0answers
26 views
Data Structure for Sorted Ranking of Classes (Scoreboard)
Let's say I am designing a scoreboard where I need to access and update player scores as fast as possible. The score of some players change often so I need to find that player and reorder the list. ...
0
votes
1answer
42 views
Subdomain matching
I am working on a small plugin for a DNS server. I have a static list of domain (sometimes subdomains too) names:
gaming.xyz.com
facebook.com
mail.example.com
blog.example.com
I want to check if a ...
0
votes
0answers
30 views
Should I use the same class for the configuration and the runtime object representing the same entity?
I am building an reporting application.
The database already exists, is populated by an other system, and contains an 'cuurent balance' table, with columns CustomerId and CurrentBalance
In the ...
2
votes
2answers
100 views
How to model JSON data so it can be easily de-serialized in to simple Java classes?
Context
Currently I'm struggling with correctly modeling a small instruction set I want to send as JSON to an Android application to generate a list of UI parts. Right now it's layered as pretty much ...
0
votes
0answers
13 views
Design of a schema parser in order to validate files according to that schema?
I am trying to parse files written in the EXPRESS data modeling language.
These files are used to define data structures of files used for the exchange of product manufacturing data. In my case, this ...
2
votes
1answer
70 views
trie iteration should include root?
I'm working on a trie data structure. My simple, initial understanding: trie data structures require a fixed root node. This node cannot be deleted.
When iterating through all nodes in a trie (in ...
2
votes
3answers
148 views
How should I implement custom database fields?
I'm building an app where end users can add custom fields to database tables. Think of it like a CRM app, where sometime you just need to add an extra field to your customer table. Pretty much all ...
0
votes
1answer
84 views
How fuzzy search is implemented for file paths
Say I have file paths like this:
my/long/directory/structure/index.js
my/long/directory/structure2/index.js
my/long/directory/structure3/index.js
my/long/directory/structure.../index.js
my/long/...
1
vote
1answer
45 views
Which datastructure to use for temporary storage of intermittent and asynchronous sensor data?
Here an outline of the setup:
Input data:
I have several sources for sensor input data (GPS, and a bunch of other sensor data from different sources).
All of those individual inputs consist of a ...
0
votes
1answer
95 views
Express unique recursive task system
I would like to express a task as either itself or a container for other tasks (recursively). The problem is that each task has to be one of two fundamental types: a goal or a routine. And, children ...
58
votes
16answers
10k views
How should I store “unknown” and “missing” values in a variable, while still retaining the difference between “unknown” and “missing”?
Consider this an "academic" question. I have been wondering about about avoiding NULLs from time to time and this is an example where I can't come up with a satisfactory solution.
Let's assume I ...
0
votes
1answer
124 views
How would you design a “multithreaded” LRU cache using C++ (unordered_map and Linkedlist)?
Please note that this is about a thread-safe LRU cache (not simply a LRU cache as specified in https://leetcode.com/problems/lru-cache/description/). It isn't a duplicate of LRU cache design question ...
1
vote
1answer
118 views
Find a string in list of strings
Background:
I am writing an application for a small embedded device. There is a static list of strings: currently about 500 strings and string length is 12 characters on average. The list might ...
0
votes
3answers
158 views
how can i return the median of a threaded binary search tree in constant time?
I'm having a trouble with understanding how to implement and find the median of a threaded binary search tree in constant time.
The tree consists of a worker's id and name.
The given details are ...
17
votes
9answers
2k views
How is polymorphism used in the real world? [closed]
I am trying to understand how Polymorphism is used in a real life project, but I can only find the classical example (or something similar to it) of having an Animal parent class with a methodspeak(), ...
2
votes
1answer
87 views
Data Structure for “Intuitive” Text Matching
I've noticed that text editors and such have a more-than-prefix/suffix-based pattern matching algorithm going on behind the scenes. And StackOverflow's tag matching algorithm does more than just ...
0
votes
1answer
50 views
Limitations of Tries in Comparison to B-Trees for a Database
I am wondering about how range queries work, and the standard solution is to use B+trees. However, I am a fan of tries as a general data structure and would like to know if they (or variations of them)...
45
votes
8answers
12k views
Before OOP, were data structure members left public?
When a data structure (for example, a queue) is implemented using an OOP language, some members of the data structure need to be private (for example, the number of items in the queue).
A queue can ...
1
vote
2answers
67 views
Should static and historical data be split in the API? To what extend?
The project is a read-only interface for a company database.
In the database, there is some 'static' data about departments, in a Departments table.
The value of these fields don't change with time (...
2
votes
1answer
70 views
Multiple data structures containing the same references
I was wondering what the best practice is for creating multiple different data structure which can all contain references to the same objects. As an example, consider a video game with many entities.
...
0
votes
0answers
37 views
implementing data structure that consists of pair-diff(s,d)
i am having trouble and would really appreciate your help, especially with pair-diff(S,d)
i am trying to implement a data structure S in given times:
Insert(S,k) - inserting k into S O(logn)
Delete(...
1
vote
1answer
57 views
Parnas' Paper on Modularization and Workflow Engines
In a Software Engineering class, we had an assignment to read Parnas' seminal paper on modularization [0]. In this paper, two approaches of dividing a software into modules are discussed:
Traditional ...
0
votes
0answers
28 views
JSON-based Audit Log best practice
Not quite sure if this is the community to ask this question, but I was wondering what the best structure would be for a JSON-based audit logger.
We currently run Microsoft SQL Server but some of the ...
1
vote
1answer
97 views
How to fetch data based on id from isolated code cleanest way?
I'm working on client-server application. Client architecture (class hierarchy) looks like this:
System (name is of course different, more descriptive) - represents whole system
Module A - a class ...
-1
votes
1answer
111 views
Is Tree the right data structure?
I must create a basic calendar of one year. I thought to use a generic Tree with the year like root, months as children of root, days as children of months etc...
Is it the right way?
I receive data ...
-3
votes
1answer
84 views
Determining MPG over a range of time using Dictionary and Class Objects
A group of friends are tracking the miles per gallon for each of their cars. Each time one of them fills up their gas tank, they record the following in a file:
His or her name, The type of car they ...
1
vote
2answers
710 views
Advantages of using an array over a hash table?
I am wondering about the following question. To simulate an array via a hash table, one can simply set the keys of the hash table to be the indices of the array, and set the value of each key to be ...
1
vote
1answer
41 views
Flexable Table, or multiple tables?
In my application, I have many things that use images in different ways. For example, a product may have a logo and many screenshots, a user can have a profile image, and a company can have a logo.
I ...
1
vote
2answers
197 views
Large matrix manipulation in multithreaded environment
I have:
matrix 20*40000 of floats M - std::vector<std::vector<float>>;
1000 values X;
~2000000 POD structures S.
A typical situation is: for each value from X I take several structs from ...
2
votes
1answer
136 views
Optimal way of storing sorted tree in memory
Wondering what the general structure is for storing a tree in memory most efficiently (for access operation, and space).
For the access operation, it should take advantage of contiguous memory (...
10
votes
4answers
620 views
Good code style to introduce data checks everywhere?
I have a project that is sufficiently large in size that I can't keep every aspect in my head any more. I'm dealing with a number of classes and functions in it, and I'm passing data around.
With ...
0
votes
1answer
48 views
Question about memory handling of trees and certain sorts on large data sets.
If data structures such as trees and certain sorts(quick sort, merge sort) work using recursive algorithms and recursive algorithms take up a lot of memory space in the stack and can only work on a ...
7
votes
2answers
282 views
FIFO Min-Max-Heap for Rolling Median
I'm working on a system with hard real-time constraints in c++ and I need a very fast way to calculate the rolling/moving/streaming median of a set of numbers of size N=100 to 300. Normally this size ...
0
votes
0answers
87 views
What is a good data-structure to store intermediary results of map-reduce pipeline?
I also think about this question as about storing a symmetry group. A quick loose reminder of what symmetry group is: a set of "things" (say, rotations of triangle), and a binary operation (say, ...
1
vote
1answer
63 views
What is the most efficient way to represent resizable adjacecny matrix
I'm building a simple app that represents some matrix, where nodes are added quite often. Currently I have following code for adding a new node:
let mut new_edges = Array2::default((position + 1, ...
1
vote
2answers
168 views
How is a quadtree stored in a file?
I'm trying to understand how a 2d or 3d map would be saved, and I'm trying to figure out quad trees. So like is each node represented by characters in a file and inside of that is the next one?
What ...
-2
votes
1answer
85 views
Is Clojure a wrong choice for implementing Data Structures?
I am planning to improve my knowledge of Clojure and algorithms at the same time by implementing some known data structures in Clojure (e.g. linked lists, skip lists, bloom filter, etc.). However, I ...
0
votes
2answers
810 views
Storing a temporary data outside of DbContext in Entity Framework
I have a performance issue with a few methods in my Service Layer. Methods that are causing me troubles have some logic, but it's db connection that takes over 95% exec time. The problem is ...
3
votes
4answers
235 views
Web Applications REST API: Should the data be structured to meet the UI's requirements on the client or on the server?
For a web app I am working on I have a pretty basic relational database. I access this database through a RESTful API and generate the markup in React once the data is retrieved.
If I find myself ...
0
votes
5answers
186 views
What is a good format to store a table of data
This is for one of my personal projects. I want to store a table of data in a BLOB/TEXT column in the database. I don't want to store the data in its own database table because the schema of this data ...
-3
votes
2answers
214 views
Why we use top== -1 for implementation of stack using simple array?
I am a newbie at data structures.
I have read an implementation of a stack using a simple array. The algorithm for this implementation is presented below.
Stack implementation in terms of an array
...
0
votes
2answers
114 views
Version checking when reading deeply nested structures
I need to open a game save file, read it, maybe modify it and then save it.
The structure of the save is quite simple: it is an object with some members, some of which are data, while others are ...
1
vote
0answers
68 views
Best practice to handle input and output with several csv-like files
I am currently writing an application with the following structure:
input: the equivalent of an excel workbook, i.e. a few tables with different headers and a few scalar values. They represent ...
0
votes
1answer
35 views
Journal Entries vs Entities - what should be the source of truth?
So, this is going to sound like an accounting question, and on top of that might be a little too opinion or discussion-based for Stack Exchange. But we've been going back and forth on this a little ...
5
votes
2answers
185 views
How should I name the fields in a class representing 2D and 3D sizes?
I'm working on a display library which in most cases works on a 2D plane but it has some components which display 2D projections of a 3D space.
This domain has the notion of Position, Size, ...
0
votes
1answer
73 views
Server load/capacity based on data structure
Using PHP, I created a chatbox, and I used an unorthodox way of storing chat messages in MySQL.
The tbl_chat_messages has the following columns:
id | sender_id | receiver_id | message | date
The ...
2
votes
2answers
129 views
Receive data in random order, send in order
I am facing an issue where I have a data stream that sends unordered data. I'm trying to find a way to receive the data in random order, but send it in order.
As an example, I'll receive object4 and ...
10
votes
3answers
2k views
Is it good practice to wrap a related set of properties into its own struct/class?
Writing a User object in Swift, though my question relates to any strongly typed language. A User can have a bunch of links (FacebookProfile, InstagramProfile, etc). A few questions around this.
Is ...
0
votes
0answers
30 views
Correct way-data structure for advertising peers in a p2p network
Underlying problem
In a case of a peer-to-peer discovery protocol,suppose we need to advertise peers in a manner that the network graph will grow such that we avoid cases of both too dense areas (e.g ...
