Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If "abc" and "xyz" are fixed values, you can maintain three counters with your collection indicating the number of strings:</p> <ul> <li>starting with "abc" but not ending with "xyz".</li> <li>not starting with "abc" but ending with "xyz".</li> <li>starting with "abc" and ending with "xyz".</li> </ul> <p>That gives you an O(1) time complexity for searching at the cost of extra calculation when inserting into, or deleting from, the collection.</p> <p>If the "abc" and "xyz" are arbitrary strings, it's O(n) for <em>all</em> operations, including the "abc..." one. You only have to consider what happens when your collections consists of items that all start with "abc" to see this. That's not bounded by O(logN) at all since you have to process all items in the tree (both branches of every non-leaf node).</p> <p>I think your ideal solution is to maintain the two ordered trees, one for the normal strings and one for the reversed strings. But don't worry about trying to do an intersection between the two. All you need to do is minimize the search space as much as practicable.</p> <ul> <li>To find "abc...", use the normal tree to find the strings starting with that value.</li> <li>To find "...xyz", use the reverse tree to find the strings ending with the reverse of that that value (zyx...).</li> <li>To find "abc...xyz", use the normal tree to find the strings starting with that value and then filter out those that don't end in "xyz".</li> </ul> <p>That way you don't have to worry about intersecting values between the two trees and you still get a performance improvement over the simplistic linear search.</p>
    singulars
    1. This table or related slice is empty.
    1. POSearch for strings matching the pattern "abc:*:xyz" in less than O(n)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpaxdiablo
    1. USpaxdiablo
    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. This table or related slice is empty.
    1. CO"abc" and "xyz" are arbitrary of course. Ok you're right about it not being O(log N). I should have stayed away from mentioning anything in Big-O. But in most cases you can definitely prune away certain branches of the tree.
      singulars
      1. PO
      1. USHarish
 

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