Hot answers tagged

16

When seeing a class with a constructor signature like EnglishWordsListGenerator(const std::string &wordFileName) I think it is pretty obvious that this constructor will read the given file (and so need some time), and it should not be to hard to understand that the caller has to care for possible exceptions from this (because file IO can fail). So ...


7

If you are new to C++, it may be desirable to shy away from doing big work in a constructor. Constructors are wedded tightly to the way the language behaves, and you really don't want the constructor getting called unexpectedly (explicit is your friend!). Constructors are also rather unique in that they cannot return a value. This can make error handling ...


5

A hashtable is an array of buckets, where the bucket index corresponds to the hash values of the keys (modulo the array length). As collisions do happen (two different keys mapping to the same bucket), you need a strategy to deal with that. Here are two popular strategies. Using a list: you design a bucket data structure that supports multiple key/value ...


5

It's not a good practice to load an object from a file in the constructor. Beyond the good C++ arguments in the other answers, I'd add a clean code principle: a function should do only one thing. Ok, the constructor is not a normal function, but the principle still applies. I suggest the following: keep the Trie as general as possible to aim at reuse. ...


4

The classic answer would be a trie which stores all rotations of words (in scrabble there is a very similar need and a very similar datastructure called a gaddag). It turns out you can do much better (B-tree of words where the lowest level is delta encoded), but the simplest thing you can do is store a sorted list of all rotations of all words in your ...


4

You're almost certainly overthinking this. Your quest for an ideal data structure is a solution in search of a problem. Look carefully at the example you gave. All three of those dropdowns have a different data source, and they imply a relational structure. Just by looking at the names of your dropdowns, I know that you have three tables: Groups, Events ...


4

A trie is a data structure where: nodes represent strings that are matched, edges represent transitions of one node to the next based on a given additional character, and the root node corresponds to the empty string that is always a matched when no characters are yet processed . Based on this understanding, and from a theoretical point of view: ...


3

Your bitset idea has promise and reminded me of Bloom filters which have gained popularity of late. I think the central problem - as you noted - is this: "How to handle possible duplicates/collisions?" Fortunately this is a problem that has been studied heavily with respect to hash table implementation - see the "Collision Resolution" ...


3

Let w be the amount of words in the trie. Then the boundary O(w*m) is much more useful, since it simply represents the max amount of characters in the trie, which is obviously also it's space boundary. In a way, yes, O(n**m) is a correct boundary too. It's just pretty useless in most cases. For example, w = 200 words with an average length of m = 100 in an ...


3

You want to store strings in compressed form (to save space, I guess), but you want fast lookup, is this right? If I were you, I would go for the speed and use a trie (for the first few characters). It has O(log n) lookup, and it will automatically condense common prefixes. A lot depends on the statistics of the strings, like how many there are, and their ...


3

Use a tree, where each node will be a subdomain. The top level will be the start symbol. Then it would branch into k nodes, where k is the number of top level domains you have. For instance, if your entire database was two entities: foo.bar.example.com and boo.car.ample.net, k will be 2 (net and com). Each of net and com nodes will have one children each: ...


2

Quick Short Answer Pick a regular Tree Structure first, later look for a similar optimized version Long Boring Extended Answer Use a regular Tree Structure first. I read that it seems you try to store the entire path in each node element, and that's one of the reasons your structure may requiere unnecesarily optimization. Note: The following examples ...


2

This is called sharding in MongoDB and partitioning in SQL Server. If the website actually uses “huge amounts of data”, sharding/partitioning is already implemented. You may probably want to rethink what data you actually need to retrieve, how is it used and how do you store it. If you do auto-completion on product names, you probably don't need to retrieve ...


2

Data Stores Have two responsibilities: storing data efficiently performing queries/updates efficiently. Hashmaps do not make for a particularly elegant solution to these two problems. HashMaps become less efficient the more dense they become, so an hashmap optimal for retrieval is more than sub-optimal for storage. Conversely a dense hashmap is also called ...


2

Suppose you have stored prefix in different instances: A-F G-M N-R S T-Z if there are too many records under A-F instance, you can just re-partition and split it to A-D, E-F. if there are too many records in S instance, you can add another load balancer in front of this instance, and split the instance to two, keeping SA-SM in one, and SN-SZ in another. For ...


2

A trie itself is a generic term for a data structure that stores keys implicitly as a path. If you google tries, you will see that there are multiple different implementations for a searching data structure where the keys are stored in this way, and thus, there will be different space complexities for each. One that comes to mind from my personal studies ...


2

A B-Tree is a balanced tree structure that ensures a search in logarithmic time and efficient ordered traversal. Each node has more than two children. This helps to achieve a higher performance than binary trees, because it reduces the number of disk accesses and their storage layout can take advantage of block devices. A trie on the other hand is a ...


1

If you feel like writing your own data structure, use a variant of a Skip List. A standard skip list keeps a list of items in sorted order, giving you O(log n) search complexity as well as O(log n) insertion complexity. But the trick here - and the reason to write your own (and an ordinary skip list isn't really hard, so start with that) is that you'll ...


1

According to my calculation you would need roughly 560mb memory to put everything in memory in one go. 20 000 000 * 20bytes + 8bytes(64 bit for each pointer in the list) = aproximatly 560mb If you double the memory to give som execution space. A program allocating 1.1G will have no problem processing in one go the complete set including filtering out the ...


1

Another way of thinking this is space being O(kN), where k is the count of possible characters (assuming we are using array to store the mapping), N is the number of nodes in trie. Whereas more meaningfully, from the client's perspective, the space complexity is O(mn), where m is the average length of strings inserted, n is the number of words. This ...


1

I don't think I would read a file in the constructor for a couple of reasons: it will significantly slow down object creation and potentially the startup of your program. as you mentioned, there are limited options for error handling. You would have to either put the entire program in a try...catch block or set some sort of flag if something ...


1

You could maintain a separate (or as a part of the NoSQL record) store of hashes of the searchable data. The nature of a hash being non-reversible makes it leak far less information than encrypted strings when you have various amounts of the strings available. Then as queries come in, you just hash the query request information and match on hashes. This ...


Only top voted, non community-wiki answers of a minimum length are eligible