xiaodaigh/sortinglab.jl

Faster sorting algorithms (sort and sortperm) for Julia

sortinglab.jl's Issues

Insertion Sort to Finish Off Radix Sort?

For small arrays, insertion sort is more efficient, so handing off a mostly-sorted array to an insertion sort should give speedups. From what I can see, this isn't implemented yet (although I might have missed it).

Make radix extensible by incorporating a better trait based interface

Error running the examples

I'm using Julia 1.0.2 on Windows 10 x64.

svec_sorted = radixsort(svec);
ERROR: UndefVarError: nthreads not defined
Stacktrace:
 [1] uint_hist(::Array{UInt64,1}, ::Int64, ::UInt16) at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\radixsort_string.jl:27
 [2] sorttwo!(::Array{UInt64,1}, ::Array{String,1}, ::Int64, ::Int64, ::Int64, ::UInt16) at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\radixsort_string.jl:99
 [3] #radixsort!#3(::Int64, ::UInt16, ::Function, ::Array{String,1}, ::Int64, ::Int64, ::Base.Order.ForwardOrdering) at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\radixsort_string.jl:312
 [4] (::getfield(SortingLab, Symbol("#kw##radixsort!")))(::NamedTuple{(:RADIX_SIZE, :RADIX_MASK),Tuple{Int64,UInt16}}, ::typeof(radixsort!), ::Array{String,1}, ::Int64, ::Int64, ::Base.Order.ForwardOrdering) at .\none:0
 [5] radixsort!(::Array{String,1}, ::Bool, ::Tuple{Int64,UInt16}) at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\radixsort_string.jl:340
 [6] radixsort at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\radixsort_string.jl:339 [inlined] (repeats 2 times)
 [7] top-level scope at none:0

julia> fsortperm(svec)
ERROR: MethodError: no method matching Array{Tuple{UInt64,UInt32},1}(::Int64)
Closest candidates are:
  Array{Tuple{UInt64,UInt32},1}() where T at boot.jl:413
  Array{Tuple{UInt64,UInt32},1}(::UndefInitializer, ::Int64) where T at boot.jl:394
  Array{Tuple{UInt64,UInt32},1}(::UndefInitializer, ::Int64...) where {T, N} at boot.jl:400
  ...
Stacktrace:
 [1] fsortperm(::Array{String,1}, ::Type{UInt64}) at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\fsortperm_string.jl:58
 [2] fsortperm(::Array{String,1}) at C:\Users\joe\.julia\packages\SortingLab\b5mnU\src\fsortperm_string.jl:53
 [3] top-level scope at none:0

My computer has defined JULIA_NUM_THREADS = 7 and works for other packages.

Error tagging new release

The tag name "0.2.0" is not of the appropriate SemVer form (vX.Y.Z).
cc: @xiaodaigh

fsortperm still much slower than fsort

julia> @btime fsortperm($x)
  1.210 s (18 allocations: 514.00 MiB)

julia> @btime fsort($x)
  486.066 ms (18 allocations: 256.19 MiB)

Here's what's bizarre -- in R, the pattern is almost exactly reversed. order takes about .651 seconds vs 1.01 for sort.

fsortperm() throws uint_mapping error under Julia-1.9.0-beta2

Hi,
With the latest beta of Julia (1.9.0-beta2), fsortperm() does not work properly with vectors of floats:

julia> fsortperm(rand(4))
ERROR: MethodError: no method matching uint_mapping(::Base.Order.ForwardOrdering, ::Float64)

julia> fsortperm([1, 3, 2, 4])
4-element Vector{Int64}:
 1
 3
 2
 4

Would it (should it) work as-is for this problem?

https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357

investigate this to speed up string sorting

https://arxiv.org/pdf/2003.02391.pdf

https://news.ycombinator.com/item?id=23561101

fsortperm() error for SubString vector input in occasional case

I found fsortperm() got an error when I am sorting a 11511 element SubString vector:

julia> summary(s)
"11511-element Vector{SubString{String}}"

julia> fsortperm(s)
ERROR: MethodError: no method matching uint_mapping(::Base.Order.ForwardOrdering, ::SubString{String})
Closest candidates are:
  uint_mapping(::Base.Order.Lt, ::Any) at ~/.julia/packages/SortingAlgorithms/PEcBU/src/SortingAlgorithms.jl:59                                                                                              
  uint_mapping(::Base.Order.By, ::Any) at ~/.julia/packages/SortingAlgorithms/PEcBU/src/SortingAlgorithms.jl:57                                                                                              
  uint_mapping(::Base.Order.ForwardOrdering, ::Unsigned) at ~/.julia/packages/SortingAlgorithms/PEcBU/src/SortingAlgorithms.jl:46                                                                            
  ...
Stacktrace:
 [1] uint_mapping(x::SubString{String})
   @ SortingLab ~/.julia/packages/SortingLab/lueAf/src/uint_mapping.jl:5
 [2] uint_hist(bits::Vector{SubString{String}}, RADIX_SIZE::Int64, RADIX_MASK::UInt16)
   @ SortingLab ~/.julia/packages/SortingLab/lueAf/src/uint_hist.jl:14
 [3] sorttwo!(vs::Vector{SubString{String}}, index::Vector{Int64}, lo::Int64, hi::Int64, RADIX_SIZE::Int64, RADIX_MASK::UInt16)                                                                              
   @ SortingLab ~/.julia/packages/SortingLab/lueAf/src/sorttwo!.jl:21
 [4] sorttwo!
   @ ~/.julia/packages/SortingLab/lueAf/src/sorttwo!.jl:11 [inlined]
 [5] fsortperm(x::Vector{SubString{String}})
   @ SortingLab ~/.julia/packages/SortingLab/lueAf/src/fsortperm.jl:6
 [6] top-level scope
   @ REPL[65]:1

However, If I transfer it to a String vector, fsortperm() works fine:

julia> issorted(s[fsortperm(String.(s))])
true

If you need this string list for debugging, please let me know.

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

Error tagging new release

The tag name "0.1.0" is not of the appropriate SemVer form (vX.Y.Z).
cc: @xiaodaigh

There is another similar package: SortingAlgorithms.jl

There is another package similar to yours that provides radixsort on Julia.
https://github.com/JuliaCollections/SortingAlgorithms.jl
Maybe you could join forces.

radixsort much slower than buit-in sort (regarding string sorting)

lines = open("f.txt") do file
    readlines(file) #has approx 4.3m lines
end
@time sort(lines)
@time radixsort(lines)

delivers the following output:

2.585242 seconds (9 allocations: 49.539 MiB, 0.42% gc time)
18.793147 seconds (14.83 k allocations: 2.916 GiB, 36.62% gc time)