Commons.Collections.SquareList
1.0.6
See the version list below for details.
dotnet add package Commons.Collections.SquareList --version 1.0.6
NuGet\Install-Package Commons.Collections.SquareList -Version 1.0.6
<PackageReference Include="Commons.Collections.SquareList" Version="1.0.6" />
paket add Commons.Collections.SquareList --version 1.0.6
#r "nuget: Commons.Collections.SquareList, 1.0.6"
// Install Commons.Collections.SquareList as a Cake Addin #addin nuget:?package=Commons.Collections.SquareList&version=1.0.6 // Install Commons.Collections.SquareList as a Cake Tool #tool nuget:?package=Commons.Collections.SquareList&version=1.0.6
Commons.Collections.SquareList
Managed Commons library containing the SquareList specialized collection.
Now requires .NET 6.0/C# 10 to build
Loosely based on an article published in the May 2013 issue of Dr Dobb's Journal, by Mark Sams. His implementation in C used circular doubly-linked lists of doubly-linked lists, I've reimplemented using a List of Dynamic Slices backed a single Big Array, It uses a lot less memory than linked lists, but inserts in crammed sets can have ripple effects with worst case O(n).
This implementation allows for multiple instances of the same value to be inserted, and then deleted one-at-a-time or wholesale.
Thinking about performance, search for counting/existence is done bidirectionally, but removal scans only in the forward direction, to have a stable behavior (remove the first found) when duplicates exist.
The SquareList is a structure that is particularly useful in applications that frequently require the current minimum and maximum values, as they both can be found in constant time, even accounting for deletions. This implementation performs insert/delete/find operations within a worst-case running time of O(sqrt(n)) [In truth O(n) for inserts]. Values are always kept in ascending order, so traversing it in that order is natural and performant.
Commons.Collections.SquareList 1.0.6 is available at Nuget: Commons.Collections.SquareList.
Targets in the package
Release | .NET Standard 1.0 | .NET Standard 2.1 | .NET 6.0 |
---|---|---|---|
1.0.0 | ✔ | ||
1.0.2 | ✔ | ||
1.0.3 | ✔ | ✔ | |
1.0.4 | ✔ | ✔ | ✔ |
1.0.5 | ✔ | ✔ | ✔ |
1.0.6 | ✔ | ✔ | ✔ |
Performance
Some performance testing, all times in ms (updated and now using release version of nuget, on .NET 6.0):
SortedList (all times in ms) [.NET 6.0]
Initial Size | Creation | Deletes | Inserts | Searchs | Min | Max |
---|---|---|---|---|---|---|
1000 | 1 | 1 | 0 | 0 | 16 | 19 |
1779 | 0 | 0 | 0 | 0 | 15 | 19 |
3163 | 0 | 0 | 0 | 0 | 16 | 19 |
5624 | 0 | 0 | 0 | 0 | 15 | 13 |
10000 | 0 | 1 | 1 | 0 | 6 | 3 |
17783 | 1 | 1 | 2 | 0 | 3 | 3 |
31623 | 1 | 2 | 3 | 0 | 3 | 3 |
56235 | 2 | 4 | 5 | 0 | 3 | 3 |
100000 | 4 | 9 | 10 | 0 | 3 | 4 |
177828 | 7 | 16 | 19 | 0 | 3 | 4 |
316228 | 17 | 39 | 38 | 0 | 3 | 3 |
562342 | 26 | 188 | 115 | 0 | 3 | 3 |
1000000 | 47 | 363 | 127 | 0 | 2 | 3 |
1778280 | 77 | 575 | 302 | 0 | 3 | 3 |
3162278 | 144 | 1050 | 809 | 0 | 3 | 3 |
5623414 | 261 | 1893 | 1528 | 0 | 3 | 3 |
10000000 | 484 | 3421 | 2930 | 0 | 3 | 2 |
17782795 | 874 | 6045 | 5311 | 0 | 3 | 3 |
31622777 | 1598 | 10743 | 9482 | 1 | 3 | 3 |
SquareList
Initial Size | Creation | Deletes | Inserts | Reinserts | Searchs | Min | Max | CutInHalf | Shrink |
---|---|---|---|---|---|---|---|---|---|
1000 | 2 | 3 | 2 | 3 | 0 | 0 | 0 | 1 | 1 |
1779 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
3163 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
5624 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
10000 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
17783 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
31623 | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 |
56235 | 1 | 1 | 1 | 3 | 0 | 0 | 0 | 0 | 0 |
100000 | 1 | 2 | 1 | 5 | 0 | 0 | 0 | 0 | 1 |
177828 | 2 | 3 | 2 | 10 | 0 | 0 | 0 | 0 | 1 |
316228 | 6 | 3 | 3 | 19 | 0 | 0 | 0 | 0 | 2 |
562342 | 11 | 4 | 4 | 31 | 0 | 0 | 0 | 1 | 5 |
1000000 | 15 | 2 | 1 | 51 | 0 | 0 | 0 | 0 | 6 |
1778280 | 27 | 6 | 5 | 83 | 0 | 0 | 0 | 2 | 10 |
3162278 | 45 | 8 | 8 | 159 | 1 | 0 | 0 | 3 | 18 |
5623414 | 72 | 9 | 8 | 287 | 1 | 0 | 0 | 4 | 34 |
10000000 | 129 | 12 | 10 | 500 | 1 | 0 | 0 | 9 | 60 |
17782795 | 237 | 17 | 14 | 890 | 1 | 0 | 0 | 14 | 108 |
31622777 | 412 | 21 | 18 | 1584 | 1 | 0 | 0 | 24 | 189 |
License: MIT
See LICENSE
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net5.0 was computed. net5.0-windows was computed. net6.0 is compatible. net6.0-android was computed. net6.0-ios was computed. net6.0-maccatalyst was computed. net6.0-macos was computed. net6.0-tvos was computed. net6.0-windows was computed. net7.0 was computed. net7.0-android was computed. net7.0-ios was computed. net7.0-maccatalyst was computed. net7.0-macos was computed. net7.0-tvos was computed. net7.0-windows was computed. net8.0 was computed. net8.0-android was computed. net8.0-browser was computed. net8.0-ios was computed. net8.0-maccatalyst was computed. net8.0-macos was computed. net8.0-tvos was computed. net8.0-windows was computed. |
.NET Core | netcoreapp1.0 was computed. netcoreapp1.1 was computed. netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 was computed. netcoreapp3.1 was computed. |
.NET Standard | netstandard1.0 is compatible. netstandard1.1 was computed. netstandard1.2 was computed. netstandard1.3 was computed. netstandard1.4 was computed. netstandard1.5 was computed. netstandard1.6 was computed. netstandard2.0 was computed. netstandard2.1 is compatible. |
.NET Framework | net45 was computed. net451 was computed. net452 was computed. net46 was computed. net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 was computed. net472 was computed. net48 was computed. net481 was computed. |
MonoAndroid | monoandroid was computed. |
MonoMac | monomac was computed. |
MonoTouch | monotouch was computed. |
Tizen | tizen30 was computed. tizen40 was computed. tizen60 was computed. |
Universal Windows Platform | uap was computed. uap10.0 was computed. |
Windows Phone | wp8 was computed. wp81 was computed. wpa81 was computed. |
Windows Store | netcore was computed. netcore45 was computed. netcore451 was computed. |
Xamarin.iOS | xamarinios was computed. |
Xamarin.Mac | xamarinmac was computed. |
Xamarin.TVOS | xamarintvos was computed. |
Xamarin.WatchOS | xamarinwatchos was computed. |
-
.NETStandard 1.0
- NETStandard.Library (>= 1.6.1)
-
.NETStandard 2.1
- No dependencies.
-
net6.0
- No dependencies.
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.
Packaging for netstandard1.0;netstandard2.1;net6.0