1

I'm writing a program that evaluates tons of positions in a board game (i.e. othello). My board representation is an std::vector. Since the same position can occure more times in processing, I use an std::set<std::vector> to store examined positions.

In term of performances I don't know if it is preferable to use std::set (that works natively because std::vector implements all the operators required) or std::unordered_set with a good hashing function (i.e. boost::hash_range(...)).

In alternative are there other good solutions to achieve the same goal? (Maybe different board representations [bitboards for sure when available] or different data structures?)

EDIT ************************************** EDIT

This is the pseudo code to fetch boards:

enqueue initial board
while queue not empty:
    dequeue a board
    if board is already examined: //std::set search
        continue
    put board in examined boards
    if board is solved:
        print solution
    else:
        for each possible board that can arise out of this one:
            add board to end of queue
c.bear
  • 1,197
  • 8
  • 21
  • 1
    Why not a vector of vectors? – NathanOliver Jul 21 '15 at 15:24
  • 1
    If you are talking about performance, you need to measure what is fast for your problem. And `std::vector` always should be the candidate to compare with if possible. – Baum mit Augen Jul 21 '15 at 15:30
  • @NathanOliver with a vector checking if is a position is already examined requires O(n). With set O(logn) and with unsorted_set O(1). When n is extremly big vector is a bottleneck – c.bear Jul 21 '15 at 15:31
  • I think you need a little more explanation/example in your question then as I am unclear what you are trying to do. – NathanOliver Jul 21 '15 at 15:32
  • @NathanOliver I improved the question with the pseudo code :) – c.bear Jul 21 '15 at 15:37
  • First I'd create something that works, and only after this I'd check if optimization is needed. – Jepessen Jul 21 '15 at 15:47
  • @kuket15 If you want performance, then profile. Asking questions before profiling is useless. Also, your reliance on O(whatever) notation is obsolete since 1980th, or at least it requires real-world verification. In 2015 we are living in the world of optimizing compilers, cache hierarchies, branch predictors, out-of-order execution etc. Naive theoretical reasoning about what your code algorithmic complexity is just doesn't work anymore. P.S. Use `vector` by default. – Ivan Aksamentov - Drop Jul 21 '15 at 16:04
  • @Drop As many suggest I'll benchmark all different conditions. Obviously it's the best thing to do. But I really doubt `vector` is even comparable with `set` for my purposes. Anyway i think *Try it yourself* is the best answer to my post. – c.bear Jul 21 '15 at 16:20
  • I don't think I would recommend using `vector>` here - the original poster seems to want uniqueness, after all. – celticminstrel Jul 21 '15 at 16:23

1 Answers1

1

see

Why on earth would anyone use set instead of unordered_set?

what is the difference between set and unordered_set in C++?

Basically: unless you're concerned about the order of the values you should probably go with unordered_set.

But as for all other performance problems: When in doubt --> start measuring. Implement both "less" and "hash", then try it with both classes and check which is performing better (Note: in this case you don't have almost the same API anyway. So it shouldn't take you long to switch classes for a test)

Community
  • 1
  • 1
Daniel
  • 1,041
  • 7
  • 13