4 ms·

You only benchmarked the search itself, but in the real world it might also take time to set up the data. You can't really pinpoint a tradeoff point without kno

• deathanatos 7y ago
  That's not a bad point, and perhaps I should test creation times too. (I wanted to ignore that s.t. the test isolated a single thing: searching / wasn't mixing two things together.) Both hashsets and vectors are O(n) in setup, and I'd mostly expect their real-world performance to be very similar: hash tables tend to use contiguous arrays for storage and vectors do by definition, both tend to overallocate (hash tables to prevent collisions, vectors to amortize appends to O(1)), so I'd expect the performance in the real-world to be similar. Vectors tend to insert in-order, though, whereas the insertions in hashsets would bounce around the table, so that might make it more interesting.
  • XelNika 7y ago
    Yes, it's always best to reduce the number of variables in benchmarking, but the setup makes a big difference when we are talking about tiny data sets. I don't know how to test it properly, but I tried looping over both the initialisation and a single search, and the hash sets were much slower, so much so that hash sets trailed lists by microseconds at size 10000. In retrospect, making those data structures unsurprisingly dominated running time and the test kind of lost all meaning. It was clear, however, that it wouldn't take many searches for the hash sets to win, search times for lists were going through the roof.