abcsumits's blog

Please add sortedContainers module in python environment.
By abcsumits, history, 22 months ago, In English

python doesn't have any library for ordered map and ordered set. We can install sortedContainers module in our pc for that. Please include this module. It would be very helpful for all who code in python.

MikeMirzayanov

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

"Just use C++" virgin vs sortedContainers chad

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    vs Gods who know how to write their own Treap/RB Tree/2-3 Tree/AVL Tree/Scapegoat Tree/Skip List/Any BBST-like data structure

    → Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

you can also use your own template of sortedlist .. etc

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    still, the sortedlist template runs in n^(1/3) which is more than the sortedcontainers's sortedlist which runs in nlogn

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just copy the sortedcontainers SortedList source code lol

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        can you use it directly though? If you could I would think pyrival would already directly copy it without rewriting the whole thing with a higher time complexity

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          PyRival has a shortened version here. However this version changes .add() to .insert(), .bisect_left() to .lower_bound(), and .bisect_right() to .upper_bound(). I use an older version that retains .add(), .bisect_left(), .upper_bound() and also has the Fenwick tree within the same class, which you may refer here.

          → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks;) huikang

        → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The docs are somewhat confusing in this regard. They say approximate nlogn but then the theoretical bounds are different:

      https://grantjenks.com/docs/sortedcontainers/performance-scale.html

      → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That is bullshit. Sortedcontainer's sortedlist runs in O(n^(1/3)) as they explain here.

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It doesn't come with the default of any Python implementation, so maybe not.

→ Reply