Hot answers tagged

56

This is easy. Almost nothing matters more than clarity to the reader. The first variant I found incredibly simple and clear. The second 'improved' version, I had to read several times and make sure all the edge conditions were right. There is ZERO DOUBT which is better coding style (the first is much better). Now - what is CLEAR to people may vary from ...


29

Assuming that you mean "integer" when you say "number", you can use a bitvector of size 2^n, where n is the number of elements (say your range includes integers between 1 and 256, then you can use an 256-bit, or 32 byte, bitvector). When you come across an integer in position n of your range, set the nth bit. When you're done enumerating the collection of ...


29

Basically, because an index is ordered, and when searching through an ordered data set, you don't have to search every item to find the element you're looking for; there are faster ways. Discussing database indexing in detail can become very arcane very quickly, but the simplest way to answer this is that you can use techniques such as a binary search to ...


20

A search feature can be modelled as a separate service with separate responsibility from the two services you mention. So, the approach here could be to create a new service ('search') and have it store a copy of the data from both services in a form which is easy to index and search, possibly also denormalized in order to quickly give results in the desired ...


19

I think for simple loops, such as these, the standard first syntax is much clearer. Some people consider multiple returns confusing or a code smell, but for a piece of code this small, I do not believe this is a real issue. It gets a bit more debatable for more complex loops. If the loop's contents cannot fit on your screen and has several returns in the ...


15

(1) What all features should I extract? First, realize that you're not classifying documents. You're classifying (document, query) pairs, so you should extract features that express how well they match. The standard approach in learning to rank is to run the query against various search engine setups (e.g. tf-idf, BM-25, etc.) and then train a model on the ...


12

1. If you rarely add and remove data What about using the same technique as the one used in RDBMS with indexes? In other words, you'll have the unordered set containing the data, and four ordered sets containing the keys and the pointers to the items in the data set. Of course, this may cause performance issues if you need to frequently add and remove ...


11

It is not that the computer knows what the result is without reading the table. It actually does quite a lot of work to find the result, but it is very fast, so it appears instantaneous to you. But yes, certainly, it does not read the entire table. The way it works is implementation dependent, but a popular simple algorithm which serves for illustration ...


10

This is a usability question (for UX.SE). Ideally, you would first produce the most relevant results (the ones with the exact phrase entered), then the results with search keywords (and their inflections) adjacent to each other, then the results for the AND operation on search by individual keywords/their inflections (i.e. anywhere in the document), and ...


9

Microsoft Access was based on a database engine called Jet which offered * and ? as wildcards for LIKE. These were never a part of the SQL standard. At some point, Microsoft incorporated a SQL-92 mode which offered the standard characters. The use of % and _ goes back a very long way. My copy of An Introduction to Database Systems by C.J. Date (4th ...


9

int i = 0; while (i < array.length && array[i] != value) i++; return i < array.length; […] everything is more obvious and more in a structured-programming way. Not quite. The variable i exists outside the while loop here and is thus part of the outer scope, while (pun intended) x of the for-loop exists only within the scope of the ...


8

What you are looking for is called a spatial index and the problem you are trying to solve is collision detection. More specifically I would use a quadtree data structure, which subdivides your space into four subspaces each time you descend one level in the tree. This is in 2D, if you are trying to solve the problem in 3D the appropriate structure would be ...


8

SQL dates back to the early 1970s. It's about the same age as UNIX. UNIX-style file name matching wildcards didn't become ubiquitous until much later. * was already a reserved character in SQL, as in SELECT * FROM Customer. Having it also be a wildcard would probably have been confusing. And standardization -- of wildcard characters or anything else -- ...


8

The "index" of a book is not a great metaphor, IMO. A better metaphor is trying to look up a word in a dictionary. Imagine that you want to look up a word in the Oxford English Dictionary (OED), which is a massive dictionary that comprises multiple volumes. The words in the OED are sorted alphabetically, of course, to make it easy to look up a word. But ...


7

Python has a great natural language toolkit, the NLTK. It supports word tokenisation out of the box: >>> import nltk >>> input = 'We have some great burritos!' >>> tokens = nltk.word_tokenize(input) >>> tokens ['We', 'have', 'some', 'great', 'burritos', '!'] >>> nltk.pos_tag(tokens) [('We', 'PRP'), ('have', 'VBP')...


7

The fastest way is just to compare hash code of files having same size. This is the idea of of this answer on SO (see the second command line and its explanations). There is no security issue while detecting duplicated files, therefore I would recommend a fast hashing code. For instance the project ccache uses MD4: ccache uses MD4, a very fast ...


7

This is actually a very modest number of files for a doc management system. 5200 files x 52 weeks x 10 years is less than 3 million. Even at your own calculation, its only 1.5 TB of data over 10 years. That will easily fit on a hard drive. For this volume of files, I would recommend keeping the files in the file system, not the database. It will give you ...


7

Not every list is sorted, yet sometimes there are things we'd like to find. Also quicksort is O(n log n), which means it takes longer than O(n).


6

For a start you will need a full text search engine like Apache Solr or Sphinx (there are more and some databases have full text features too, but I know those two and they are free and work great). If it has facet search (like Solr) this will help a lot (for certain types of queries). This will cover the largest part of indexing and performance issues. ...


6

The problem you have here in general is called the Scheduling Problem and in its general form is NP-complete. In other words, it is a well-known problem for which there exists no efficient algorithm (yet, or maybe never). The linked page (already mentioned in a comment before) refers to one specific variant called job shop scheduling. There are many ...


6

Sorting the arrays will not work. By changing the order you will not be able to determine which element matches first. The intersect solution will also not work. To use it you'd have to copy both arrays to a set class, which by definition does not preserve order. Your answer is correct. I would consider using hashsets to reduce search time.


6

checking if a list is sorted defeats the purpose of the binary search (using less comparisons for a O(log n) running time instead of a O(n)) you are better of doing a linear search if you can't be sure the list is already sorted


6

Keep in mind that from a theoretical perspective it's impossible to let sorting and finding be quicker than finding. To sort, you need to look at every element at least once to determine its place. To find, in the worst case scenario, you need to look at every element once (provided they are not sorted). Only when you're doing repeated searches, it may make ...


6

I have chosen a singleton pattern because: I want the singleton to hold nested classes; one class for each pattern. This doesn't require a singleton, or a static class. You could have public class Patterns // non-static { public class PatternA : IPattern { } public class PatternB : IPattern { } } and you'd be able to use it as a bag ...


6

Without knowing the full details of what you need, you probably want to do one of the following: Use an existing search tool, like Sphinx or Lucene Perform n-gram approximate matching I don't fully know what's involved installing and configuration sphinx; but, I'm under the impression you can point it at a database, tell it which fields to index, how to ...


5

Donald Knuth wrote a lot about string matching pattern theory. A lot of algorithms are very efficient in time and hidden constant. You can found some good algorithms here: http://delab.csd.auth.gr/~dimitris/courses/cpp_fall05/books/SIAM_JNL_Comp_77_KMP_string_matching.pdf


5

sort the lines by the X of the leftmost point then for each line look at the next lines and check each of them until the x of their leftmost point is further right than the current line's rightmost point this will be n*log n best case (for the sorting) but will degenerate into the naive n^2 in bad data sets


5

You're going through each item in one collection for each item in another, that's O(N * M) where n and m are the sizes of each collection. The short circuiting doesn't affect the big O representation, as it is measuring the worst case, in which you never exit early. And even in the average case, the short circuiting cuts the time in half. O(N * M / 2) is ...


5

Am I right that there are many possible answers to this question? And is my trace of the DPS correct? Yes, there is no 'natural' ordering of the nodes of a graph. So there is also no 'natural' ordering in the result of the DFS of a graph. Of course, in the example above, you could sort the nodes alphabetically as you have labels on them. If you assume ...


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