[RFC FS-1113] Additions to collection functions by uxsoft · Pull Request #11888...
source link: https://github.com/dotnet/fsharp/pull/11888
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Conversation
Suggestion approved in principle: fsharp/fslang-suggestions#1047
RFC FS-1113 https://github.com/fsharp/fslang-design/blob/main/preview/FS-1113-insert-remove-update-functions.md
- Map.Keys, Map.Values, Map.keys implementation
- Array removeAt, removeManyAt, updateAt, insertAt, insertManyAt implementation
- List removeAt, removeManyAt, updateAt, insertAt, insertManyAt implementation
- Seq removeAt, removeManyAt, updateAt, insertAt, insertManyAt implementation
- Map tests
- Array tests
- List tests
- Seq tests
- Map benchmark
- Array benchmark
- List benchmark
- Seq benchmark
- Map xml docs
- Array xml docs
- List xml docs
- Seq xml docs
All CLA requirements met.
@dsyme I found out that the Map.Values implementation collides with internal Map.Values extension in illib.fs - MapAutoOpens module which returns a list instead of seq. This is the reason the solution right now doesn't build.
Since it's not part of the spec you provided I'll remove it from this PR. That said I see it's something that IS used, so let me know if you'd like me to take a look at it in a separate PR.
This is looking good.
Based on the suggestion discussion and looknig at the implementation I think we should at least drop updateManyAt
across the board. It is just too corner-case.
I'll discuss on the suggestion further
Benchmarks:
In the case of Seq, this includes Seq.iter to execute the enumerator. Happy to hear suggestions on how to improve the benchmarks.
Method Length Mean Error StdDev Gen 0 Gen 1 Gen 2 Allocated ListRemoveAtBeginning 1000 5.189 ns 0.1772 ns 0.0274 ns - - - - ListRemoveAtEnd 1000 5,480.353 ns 386.7945 ns 59.8569 ns 0.3967 0.0076 - 31968 B ListRemoveManyAtBeginning 1000 15.646 ns 2.2214 ns 0.3438 ns - - - - ListRemoveManyAtEnd 1000 5,708.041 ns 329.0971 ns 50.9281 ns 0.3891 0.0076 - 31648 B ListInsertAtBeginning 1000 11.304 ns 0.4238 ns 0.0656 ns 0.0004 - - 32 B ListInsertAtEnd 1000 5,288.309 ns 197.7985 ns 30.6095 ns 0.3967 0.0076 - 32000 B ListInsertManyAtBeginning 1000 192.468 ns 16.3248 ns 2.5263 ns 0.0091 - - 720 B ListInsertManyAtEnd 1000 5,519.864 ns 289.2547 ns 44.7625 ns 0.4044 0.0076 - 32368 B ListUpdateAtBeginning 1000 13.254 ns 2.1878 ns 0.3386 ns 0.0004 - - 32 B ListUpdateEnd 1000 5,376.328 ns 662.6034 ns 102.5386 ns 0.3967 - - 32000 B ArrayRemoveAtBeginning 1000 290.669 ns 49.1012 ns 7.5985 ns 0.0505 - - 4024 B ArrayRemoveAtEnd 1000 294.764 ns 33.7929 ns 5.2295 ns 0.0501 - - 4024 B ArrayRemoveManyAtBeginning 1000 299.750 ns 69.9924 ns 10.8314 ns 0.0501 - - 3984 B ArrayRemoveManyAtEnd 1000 308.453 ns 14.0719 ns 2.1776 ns 0.0501 - - 3984 B ArrayInsertAtBeginning 1000 308.234 ns 65.4868 ns 10.1342 ns 0.0505 - - 4032 B ArrayInsertAtEnd 1000 309.545 ns 55.3982 ns 8.5729 ns 0.0505 - - 4032 B ArrayInsertManyAtBeginning 1000 469.130 ns 181.3617 ns 28.0659 ns 0.0567 - - 4528 B ArrayInsertManyAtEnd 1000 472.598 ns 13.5101 ns 2.0907 ns 0.0567 - - 4528 B ArrayUpdateAtBeginning 1000 285.476 ns 60.8502 ns 9.4166 ns 0.0505 - - 4024 B ArrayUpdateEnd 1000 289.100 ns 14.6357 ns 2.2649 ns 0.0505 - - 4024 B SeqBaseline 1000 4,778.660 ns 64.5020 ns 9.9818 ns 0.3967 - - 32000 B SeqRemoveAtBeginning 1000 17,688.588 ns 814.1713 ns 125.9939 ns 0.3967 - - 32176 B SeqRemoveAtEnd 1000 17,908.279 ns 3,491.8980 ns 540.3751 ns 0.3967 - - 32176 B SeqRemoveManyAtBeginning 1000 17,933.747 ns 7,319.8466 ns 1,132.7544 ns 0.3967 - - 31888 B SeqRemoveManyAtEnd 1000 13,838.434 ns 1,616.7749 ns 250.1977 ns - - - 208 B SeqInsertAtBeginning 1000 13,728.032 ns 1,717.2646 ns 265.7486 ns - - - 224 B SeqInsertAtEnd 1000 14,017.171 ns 615.6242 ns 95.2685 ns - - - 224 B SeqInsertManyAtBeginning 1000 14,958.334 ns 2,903.5820 ns 449.3325 ns - - - 696 B SeqInsertManyAtEnd 1000 14,842.622 ns 2,283.4617 ns 353.3682 ns - - - 696 B SeqUpdateAtBeginning 1000 14,025.052 ns 622.5198 ns 96.3356 ns - - - 208 B SeqUpdateEnd 1000 14,426.805 ns 2,623.2662 ns 405.9534 ns - - - 208 B ListRemoveAtBeginning 10000 5.233 ns 0.7114 ns 0.1101 ns - - - - ListRemoveAtEnd 10000 54,311.147 ns 3,251.2917 ns 503.1410 ns 3.9673 1.3428 - 319968 B ListRemoveManyAtBeginning 10000 15.787 ns 2.0573 ns 0.3184 ns - - - - ListRemoveManyAtEnd 10000 57,615.459 ns 4,463.5608 ns 690.7410 ns 3.9673 1.6479 - 319648 B ListInsertAtBeginning 10000 11.160 ns 0.1968 ns 0.0305 ns 0.0004 - - 32 B ListInsertAtEnd 10000 51,662.888 ns 3,395.7760 ns 525.5001 ns 3.9673 1.3428 - 320000 B ListInsertManyAtBeginning 10000 191.575 ns 6.1768 ns 0.9559 ns 0.0088 - - 720 B ListInsertManyAtEnd 10000 53,400.577 ns 1,470.3110 ns 227.5323 ns 3.9673 1.3428 - 320368 B ListUpdateAtBeginning 10000 12.887 ns 1.3595 ns 0.2104 ns 0.0004 - - 32 B ListUpdateEnd 10000 51,021.072 ns 1,251.5245 ns 193.6748 ns 3.9673 1.2207 - 320000 B ArrayRemoveAtBeginning 10000 2,783.078 ns 84.5712 ns 13.0875 ns 0.5074 - - 40024 B ArrayRemoveAtEnd 10000 2,801.524 ns 258.2577 ns 39.9657 ns 0.5074 - - 40024 B ArrayRemoveManyAtBeginning 10000 2,840.637 ns 112.6929 ns 17.4393 ns 0.5074 - - 39984 B ArrayRemoveManyAtEnd 10000 2,805.009 ns 375.3281 ns 58.0824 ns 0.5074 - - 39984 B ArrayInsertAtBeginning 10000 2,855.498 ns 113.3414 ns 17.5397 ns 0.5074 - - 40032 B ArrayInsertAtEnd 10000 2,759.410 ns 113.8738 ns 17.6221 ns 0.5074 - - 40032 B ArrayInsertManyAtBeginning 10000 2,987.276 ns 26.2617 ns 4.0640 ns 0.5417 - - 40528 B ArrayInsertManyAtEnd 10000 2,990.363 ns 119.8012 ns 18.5394 ns 0.5417 - - 40528 B ArrayUpdateAtBeginning 10000 2,749.533 ns 109.0117 ns 16.8697 ns 0.5074 - - 40024 B ArrayUpdateEnd 10000 2,751.861 ns 171.5464 ns 26.5470 ns 0.5074 - - 40024 B SeqBaseline 10000 48,700.400 ns 15,827.2521 ns 2,449.2848 ns 3.9673 0.6104 - 320000 B SeqRemoveAtBeginning 10000 181,764.728 ns 26,840.3927 ns 4,153.5805 ns 3.9063 1.2207 - 320176 B SeqRemoveAtEnd 10000 171,426.703 ns 5,435.0195 ns 841.0753 ns 3.9063 1.2207 - 320176 B SeqRemoveManyAtBeginning 10000 173,260.168 ns 5,517.7923 ns 853.8845 ns 3.9063 0.9766 - 319888 B SeqRemoveManyAtEnd 10000 137,210.248 ns 6,283.5974 ns 972.3936 ns - - - 208 B SeqInsertAtBeginning 10000 136,211.487 ns 1,914.6332 ns 296.2916 ns - - - 224 B SeqInsertAtEnd 10000 135,684.692 ns 1,913.7171 ns 296.1498 ns - - - 224 B SeqInsertManyAtBeginning 10000 143,877.527 ns 3,522.7392 ns 545.1478 ns - - - 696 B SeqInsertManyAtEnd 10000 144,109.247 ns 8,476.2822 ns 1,311.7140 ns - - - 696 B SeqUpdateAtBeginning 10000 137,175.562 ns 15,831.5443 ns 2,449.9490 ns - - - 208 B SeqUpdateEnd 10000 136,017.792 ns 5,653.3475 ns 874.8618 ns - - - 208 B
changed the title WIP additions to immutable collections
Additions to immutable collections
This is looking great, just a few comments on the benchmarking
changed the title Additions to immutable collections
[RFC FS-1113] Additions to immutable collections
changed the title [RFC FS-1113] Additions to immutable collections
[RFC FS-1113] Additions to collection functions
@uxsoft I updated to
- Add Map.values
- Remove Map.Empty (in favour of existing Map.empty)
@uxsoft Thank you for this contribution!
Thank you for your guidance!
Nice work, now I can get rid of some of my 'extensions' in the near future :)
I am not sure if this is the right place to ask this, as this is already merged.
However, I see that at the toSeq
function the summary states that The sequence will be ordered by the keys of the map.
. This is also the case for Map.keys
and Map.values
, so I think it is an interesting property to note within the summary of those.
Also the tests should verify this if this is added.
This is also the case for Map.keys and Map.values, so I think it is an interesting property to note within the summary of those.
Yes, I agree. It's also interesting to think whether things like "get me the middle key in the ordering of keys" will run efficiently or not
let midKey =
let keys = map.Keys
keys.[keys.Length/2]
I haven't checked. Probably not
I can open a new PR with these small changes if you'd like
It's also interesting to think whether things like "get me the middle key in the ordering of keys" will run efficiently or not.
Correct me if I'm wrong but I think that is not even possible, directly, as ICollection
does not implement Item
:
So to get the middle one would have to MoveNext()
through the sequence.
No one assigned
None yet
No milestone
Successfully merging this pull request may close these issues.
None yet
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK