Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>What dou you mean by "fast"?</p> <p>Fast as in complexity, or as an improvement by a constant? You cannot achieve a better complexity with an unsorted array. However, if you change the array very rarely and seach it very often, you can consider sorting it after each change, or better yet, use a different data structure (like a <code>multimap</code> or a <code>set</code>).</p> <p>If you intend to have a better constant in your <code>O(n)</code>, there are some neat tricks which use/abuse the cache of your CPU. If you search for multiple elements, it's genrally faster to search the first few hundred array elements for each of the characters, then the next few hundred, and so on, rather then scan the whole array for each of your search terms. The improvements are not in the complexity, so the effect will usually not be that great. Unless this search happens at your bottleneck repeated deep inside some other algorithm, I would not recommend it. So unless it's inside a rendering algorithm, or a device driver, or for one specific architecture etc. it is most probably not worth it. However, in the rare cases where it might be appropiate, I've seen speed improvements of 3x - 4x or more by using inline assembly and abusing the CPU chache.</p> <p><strong>EDIT:</strong></p> <p>Your comment idicated it might be a good idea to include a short introduction about data structures.</p> <ul> <li>array, vector: fastest accessing, slow searching, slow adding/removing if not appended to the end.</li> <li>list: slow accessing, slow searching, fastest adding/removing</li> <li>trees, hash tables, etc. : <strong>best searching</strong> (some allow <code>O(0)</code> searching!), slow changing (depends on type)</li> </ul> <p>I recommend learning about the different data structures (vector, list, map, multimap, set, multiset, etc.) in C++, so you can use the one which best fits your needs.</p> <p>About the CPU cache: it seems the choosing of a better fitting data structure and code organization is much more important. However, I include this for the sake of completeness. If you search the array in shorter chunks rather than the whole array at once, that part of the array is added to the cache of your CPU, and accessing the cache is much faster than accessing RAM. So you can work on that smaller chunk of your data (for example, search for multiple elements), then switch to the next chunk of data, and so on. This means, for example, </p> <pre><code>search "a" in elements 1..100 search "b" in elements 1..100 search "c" in elements 1..100 search "a" in elements 101..200 search "b" in elements 101..200 search "c" in elements 101..200 ... search "c" in elements 999901 .. 1000000 </code></pre> <p>can be faster than </p> <pre><code>search "a" in elements 1..1000000 search "b" in elements 1..1000000 search "c" in elements 1..1000000 </code></pre> <p>If the number of searched elements (a, b, c, ..) is sufficiently large. Why? Because in case of a cache size of 100, in the first example, data is read 10000 times from the RAM, in the second example, 30000 times.</p> <p>However, the efficiency of this (and your choice of the data chunk size) heavily depends on your architecture, and is only recommended if you are really sure that this is your real bottleneck. Usually it's not.</p>
    singulars
    1. This table or related slice is empty.
    1. POC++ What is the fastest way to scan for certain elements within a unsigned char array and a unsigned char vector?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USvsz
    1. USvsz
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHmm, several good points. And yes it will be searching for multiple elements that are different. Oh and I have a question, what do you mean "abuse the CPU cache"? How do you do that? Sounds very interesting! I never used a multimap, perhaps I should go study a bit on it. Thank you for posting this.
      singulars
      1. PO
      1. USCLearner
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload