Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You can do this check in O(log n) or O(1) time using STL's set or unordered_set respectively. The unordered_set container requires you to write a custom hash function for your coordinates, while the set container only needs you to provide a comparison function. The set implementation is particularly easy, and logarithmic time should be fast enough:</p> <pre><code>#include &lt;iostream&gt; #include &lt;set&gt; #include &lt;vector&gt; #include &lt;cassert&gt; class Position { public: Position(const std::vector&lt;long int&gt; &amp;c) : m_coords(c) { } size_t dim() const { return m_coords.size(); } bool operator &lt;(const Position &amp;b) const { assert(b.dim() == dim()); for (size_t i = 0; i &lt; dim(); ++i) { if (m_coords[i] &lt; b.m_coords[i]) return true; if (m_coords[i] &gt; b.m_coords[i]) return false; } return false; } private: std::vector&lt;long int&gt; m_coords; }; int main(int argc, const char *argv[]) { std::set&lt;Position&gt; visited; std::vector&lt;long int&gt; coords(3, 0); visited.insert(Position(coords)); while (true) { std::cout &lt;&lt; "x, y, z: "; std::cin &gt;&gt; coords[0] &gt;&gt; coords[1] &gt;&gt; coords[2]; Position candidate(coords); if (visited.find(candidate) != visited.end()) std::cout &lt;&lt; "Aready visited!" &lt;&lt; std::endl; else visited.insert(candidate); } return 0; } </code></pre> <p>Of course, as iavr mentions, any of these approaches will require O(n) storage.</p> <p>Edit: The basic idea here is very simple. The goal is to store all the visited locations in a way that allows you to quickly check if a particular location has been visited. Your solution had to scan through all the visited locations to do this check, which makes it O(n), where n is the number of visited locations. To do this faster, you need a way to rule out most of the visited locations so you don't have to compare against them at all.</p> <p>You can understand my set-based solution by thinking of a binary search on a sorted array. First you come up with a way to compare (sort) the D-dimensional locations. That's what the Position class' &lt; operator is doing. As iavr pointed out in the comments, this is basically just a lexicographic comparison. Then, when all the visited locations are sorted in this order, you can run a binary search to check if the candidate point has been visited: you recursively check if the candidate would be found in the upper or lower half of the list, eliminating half of the remaining list from comparison at each step. This halving of the search domain at each step gives you logarithmic complexity, O(log n).</p> <p>The STL set container is just a nice data structure that keeps your elements in sorted order as you insert and remove them, ensuring insertion, removal, and queries are all fast. In case you're curious, the STL implementation I use uses a red-black tree to implement this data structure, but from your perspective this is irrelevant; all that matters is that, once you give it a way to compare elements (the &lt; operator), inserting elements into the collection (set::insert) and asking if an element is in the collection (set::find) are O(log n). I check against the origin by just adding it to the visited set--no reason to treat it specially.</p> <p>The unordered_set is a hash table, an asymptotically more efficient data structure (O(1)), but a harder one to use because you must write a good hash function. Also, for your application, going from O(n) to O(log n) should be plenty good enough.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow to verify if a vector has a value at a certain index
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJulian Panetta
    1. USJulian Panetta
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow to verify if a vector has a value at a certain index
      singulars
      1. PTQuestion
    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. VTAcceptedByOriginator
    1. CONice. I guess your comparison operator could use `std::lexicographical_compare`.
      singulars
      1. PO
      1. USiavr
    2. COOh, yes, that would have worked. Although, it wouldn't have caught the case where different-dimensioned coordinates were compared.
      singulars
      1. PO
      1. USJulian Panetta
    3. CO@JulianPanetta I'm not a proficient enough programmer to fully understand this solution, I'm going to read some references and see if I can implement this myself.
      singulars
      1. PO
      1. USNictraSavios
 

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