1

I have a giant lists of query searches with cached image results for a few different servers and I want to sync the queries efficiently. I know that one way would be to do it in two steps. First comparing the queries, and second, only syncing non-identical results. Instead though I'd like it to be faster and more efficient by only exchanging a small fixed amount of data and then syncing non-identical results based on that data (it's fine if it happens to sync a small amount of identical results).

What kind of data structure for these queries would be recommended to accomplish this? I've been looking at https://en.wikipedia.org/wiki/List_of_data_structures to try to get a better idea, but I don't have a lot of experience in algorithms so I could really use some direction. I'm planning to do this in C++ if that needs to be taken into consideration. All suggestions appreciated, thanks.

Austin
  • 6,921
  • 12
  • 73
  • 138
  • 1
    Have you considered the HashTable data-structure? – ahoxha Feb 26 '16 at 18:27
  • I started looking into hashes and trees, but don't know very much about them yet. – Austin Feb 26 '16 at 18:44
  • 1
    I strongly suggest you to look more into hashes, as the average case performance is very good. The time complexity for `search, insert` and `delete` is *O(1)* (Average case), although the worst case is *O(n)* (for this reason, especially if you `put` into or `remove` off the `hash`, you should consider *re-hashing* periodically. – ahoxha Feb 26 '16 at 18:57
  • @A2H Ok thanks. I remember reading that search was O(1) but didn't understand why. I'll definitely look into that. – Austin Feb 26 '16 at 19:04
  • It is O(1), if the hash-table is balanced (one bucket contains one entry on average), because all it takes is compute the hash-value of the key and it gives you the exact address to go to in the hash-table; there you just check if the desired entry has been put before or not. – ahoxha Feb 26 '16 at 19:24
  • You can also check out the answer on this [post](http://stackoverflow.com/questions/730620/how-does-a-hash-table-work). It really explains well how a hash-table works. – ahoxha Feb 26 '16 at 19:28
  • Ah it's not actually looking through each that makes sense. Cool thanks for the link. – Austin Feb 26 '16 at 19:29

0 Answers0