Skip to content

Instantly share code, notes, and snippets.

@wilkerlucio
Last active June 24, 2024 03:53
Show Gist options
  • Save wilkerlucio/db54dc83a9664124f3febf6356f04509 to your computer and use it in GitHub Desktop.
Save wilkerlucio/db54dc83a9664124f3febf6356f04509 to your computer and use it in GitHub Desktop.
Alphabetical/Natural sorting in Clojure/Clojurescript
(ns util.natural-sorting
(:refer-clojure :exclude [sort sort-by])
(:require [clojure.string]))
(defn parse-int [s]
#?(:clj (Long/parseLong s)
:cljs (js/parseInt s)))
(defn vector-compare [[value1 & rest1] [value2 & rest2]]
(let [result (compare value1 value2)]
(cond
(not (zero? result)) result
(nil? value1) 0
:else (recur rest1 rest2))))
(defn prepare-string [s]
(let [s (or s "")
parts (vec (clojure.string/split s #"\d+"))
numbers (->> (re-seq #"\d+" s)
(map parse-int)
(vec))]
(vec (interleave (conj parts "") (conj numbers -1)))))
(defn natural-compare [a b]
(vector-compare (prepare-string a)
(prepare-string b)))
(defn sort [coll] (clojure.core/sort natural-compare coll))
(defn sort-by [keyfn coll]
(clojure.core/sort-by keyfn natural-compare coll))
@lread
Copy link

lread commented Jun 22, 2024

Ha! That's awesome @wevre! I've no real interest in performance at this point, but maybe @p-himik has an interest?

@p-himik
Copy link

p-himik commented Jun 22, 2024

I am indeed curious enough to profile it myself and also publish some generative tests I have already written for it in my own code. Just don't have enough time at the moment. Will probably get to it some time next week.

@wevre
Copy link

wevre commented Jun 24, 2024

I did some benchmarking (rudimentary) and updated my library to version 0.0.10. Short story is the "lazy" version does outperform implementations based on splitting and parsing, but only for long (for some definition of long) strings, which I think are more rare. At least in situations where I use and where I imagine having a need to use natural sorting, I think they would be rare. Same goes for overflow, it's not a situation I am concerned with. Maybe my situation is an outlier, but so far I've had more control over the types of strings I'm needing to sort.

In this version 0.0.10 of my library I included implementations and tests for my original parse version (which remains the default), my lazy version, a bigint-based version (suggested by Lee), Wilker's original, and Eugene's version. I hope that is okay, I think I have explicit okay from everyone except Eugene but I'm guessing he is okay with including his version.

@p-himik
Copy link

p-himik commented Jun 24, 2024

Sure, I don't mind.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment