Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use PySet_Contains for excluded edges #2

Closed
zietzm opened this issue Dec 5, 2018 · 1 comment
Closed

Use PySet_Contains for excluded edges #2

zietzm opened this issue Dec 5, 2018 · 1 comment

Comments

@zietzm
Copy link
Member

zietzm commented Dec 5, 2018

https://docs.python.org/3/c-api/set.html#c.PySet_Contains

In the current implementation, a C integer array is created which is iterated to check membership. This is done to save memory because otherwise a hash table as implemented would have to be created for what is likely a very small set of unchanging edges. If the CPython API is fast enough, this could be an easy way to check membership in the static set.

@zietzm
Copy link
Member Author

zietzm commented Dec 5, 2018

See #1
https://github.com/greenelab/xswap/blob/a00df9d818d3ccf580b0ca6b3dfb764be1925af0/xswap/xswap_backend.cpp#L139-L142

While it would be faster than O(n) lookup, n is the number of excluded edges here. To use the CPython API, a new Python tuple object would have to be created for every new edge. Since few excluded (if any) will be present in most cases, iterating over the excluded edges should be faster.

@zietzm zietzm closed this as completed Dec 5, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant