3 ms·

There's also the classic one-liner: unique_array = list(set(non_unique_array))

by franey 8y ago

KirinDave 8y ago
Which is fine. I'm fairly sure that's n log n, although sometimes those end up being n^2 if they're biased towards memory friendliness.
- nwallin 8y ago
  It's O(n). Python's set has O(1) insertion and lookup. https://wiki.python.org/moin/TimeComplexity#set https://wiki.python.org/moin/TimeComplexity#set
  - KirinDave 8y ago
    The page you link says it's O(n) for lookup.
    - nwallin 8y ago
      It says O(1) for lookup. Average case is the one that matters here. Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/ https://xkcd.com/221/) Python has put significant effort into good default hashes[1] so you won't be vulnerable to attackers feeding in maliciously colliding hashes, nor will you have performance degradation from biased bits in the hashes if you've written an insufficiently uniform hash function.[2] [1] https://python-security.readthedocs.io/vuln/cve-2012-1150_hash_dos.html https://python-security.readthedocs.io/vuln/cve-2012-1150_ha... [2] For instance, pointers are usually aligned to cache line boundaries, and are biased toward page boundaries, and in C++, the hash function of an integer/pointer is the identity function. So in C++, a std::unordered_set of pointers will have ridiculously high collision rates. If you have 1024 pointers in a set of size 2048, you will only have only 32 buckets that have values in them, and each of those buckets will have roughly 32 elements, and the zero bucket will even more. Python doesn't let you shoot yourself in the foot, and whitens your hashes before going to the dictionary. C++ "solves" this problem by providing an API which allows you to override the hash function.
      - KirinDave 8y ago
        > It says O(1) for lookup. Average case is the one that matters here. No, it's actually not. Everyone else and the article were using the worst case asymptotic, so you'reswitching to this vernacular and suggesting, "Oh we mean the asymptotic of the average." Redefining the entire conversation to your notational convenience is not a very fair call, and doesn't speak well of your intentions. And what's more, it's typical to use big-theta notation to discuss average performance anyways. So even if we WERE using that, we'd be using different notation to be more consistent with the literature and less confusing. > Worst case is for people who've intentionally written bad hash functions. No. It's for people who do not know what kind of input they're going to receive or what kind of hardware they're going to execute on.

There's also the classic one-liner: unique_array = list(set(non_unique_array))

by franey 8y ago

There's also the classic one-liner: unique_array = list(set(non_unique_array))

Which is fine. I'm fairly sure that's n log n, although sometimes those end up being n^2 if they're biased towards memory friendliness.

nwallin 8y ago
It's O(n). Python's set has O(1) insertion and lookup. https://wiki.python.org/moin/TimeComplexity#set https://wiki.python.org/moin/TimeComplexity#set
- KirinDave 8y ago
  The page you link says it's O(n) for lookup.
  - nwallin 8y ago
    It says O(1) for lookup. Average case is the one that matters here. Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/ https://xkcd.com/221/) Python has put significant effort into good default hashes[1] so you won't be vulnerable to attackers feeding in maliciously colliding hashes, nor will you have performance degradation from biased bits in the hashes if you've written an insufficiently uniform hash function.[2] [1] https://python-security.readthedocs.io/vuln/cve-2012-1150_hash_dos.html https://python-security.readthedocs.io/vuln/cve-2012-1150_ha... [2] For instance, pointers are usually aligned to cache line boundaries, and are biased toward page boundaries, and in C++, the hash function of an integer/pointer is the identity function. So in C++, a std::unordered_set of pointers will have ridiculously high collision rates. If you have 1024 pointers in a set of size 2048, you will only have only 32 buckets that have values in them, and each of those buckets will have roughly 32 elements, and the zero bucket will even more. Python doesn't let you shoot yourself in the foot, and whitens your hashes before going to the dictionary. C++ "solves" this problem by providing an API which allows you to override the hash function.
    - KirinDave 8y ago
      > It says O(1) for lookup. Average case is the one that matters here. No, it's actually not. Everyone else and the article were using the worst case asymptotic, so you'reswitching to this vernacular and suggesting, "Oh we mean the asymptotic of the average." Redefining the entire conversation to your notational convenience is not a very fair call, and doesn't speak well of your intentions. And what's more, it's typical to use big-theta notation to discuss average performance anyways. So even if we WERE using that, we'd be using different notation to be more consistent with the literature and less confusing. > Worst case is for people who've intentionally written bad hash functions. No. It's for people who do not know what kind of input they're going to receive or what kind of hardware they're going to execute on.