search

Kotlin / kotlinx.collections.immutable

Immutable persistent collections for Kotlin
Apache License 2.0
1.18k stars 62 forks source link

Improve performance scaling #2

Closed FranciscoE-Hudl closed 5 years ago

FranciscoE-Hudl commented 8 years ago

The choice of internal representation for some PCollections scales on O(log2 n), where other implementations like Clojure's scale on O(log32 n)*

PCollections is a friendly implementation of persistent collections that's available today with little friction, but other options could be considered.

*Sources:

The Joy Of Clojure 2nd Ed Section 5.1.3

When learning about Clojure’s persistent data structures, you’re likely to hear the term O(log32 n) for those based on the persistent hash trie and O(log2 n) for the sorted structures. Accessing an element in a Clojure persistent structure by index is O(log n), or logarithmic.

https://github.com/GlenKPeterson/UncleJim/wiki/UncleJim%20vs.%20PCollections

FranciscoE-Hudl commented 8 years ago

It's a nitpick given that you're asking for feedback on Twitter.

andrewoma commented 8 years ago

My dexx collections are a port of Scala's collections having the O(log32 n)* performance characteristics if you're interested: https://github.com/andrewoma/dexx

jjl commented 7 years ago

I found paguro (formerly UncleJim), which are based on clojure's collections but made typesafe.

Clojure's collections are arguably the best on the JVM, bar the way everything gets turned into object and Paguro seems to be well-built.

ilya-g commented 5 years ago

In 0.2 collections use trie structures with scaling factor of 32, see the changelog https://github.com/Kotlin/kotlinx.collections.immutable/releases/tag/v0.2