search

hetio / xswap

Python library (C++ backend) for degree-preserving network randomization
https://hetio.github.io/xswap/
BSD 2-Clause "Simplified" License
12 stars 3 forks source link

Compare std::vector<bool> as hash table #5

Closed zietzm closed 5 years ago

zietzm commented 5 years ago

std::vector<bool> could be a good way to create the hash table in a space efficient way that is also very simple to use.

https://en.cppreference.com/w/cpp/container/vector_bool

zietzm commented 5 years ago

Unfortunately, it appears that while this implementation is as space efficient as the current, it is FAR slower. Therefore closing this PR and sticking with the current implementation.

dhimmel commented 5 years ago

it is FAR slower

Out of curiosity what's the rough difference?

zietzm commented 5 years ago

The performance I'm finding is very odd. So strange, in fact, that I was very convinced there must be some kind of bug in my code that was making the runtime so excessive. Basically, for a small number of edges, the performance is about three times as slow. This is, unfortunately, the best case scenario. For large numbers of edges, it seems that the runtime is even slower than the Python XSwap implementation. In fact, its so slow that I haven't even completed a full GiG permutation, because I worry that it might simply continue indefinitely.

Just as an example, permuting GiG with multiplier=0.001, I found the following:

This was with the most simple implementation of std::vector<bool> I could manage. I can only imagine this may have something to do with the fact that this is not a standard container.