The intention is not to replace the table itself with this; but rather use it as a supplement–a “blacklist” table that efficiently records the values that have already been stored in tableOfSizes.
2 Likes
It’s not faster, table.sort() is the meta for sorting on roblox
local tableTest : Array<number> = {}
local randomNumber : number
--Filling the table with 100 random numbers to sort
for i = 1, 100 do
randomNumber = math.random(1, 1000)
table.insert(tableTest, randomNumber)
end
print(tableTest) --Unsorted table
table.sort(tableTest, function(a : number, b : number)
return a > b
end)
print(tableTest) --Sorted table
2 Likes
In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.
Reminder that table.sort uses a linear sorting algorithm which is one of the least efficient way to sort an array.
2 Likes
Datasigh is right, table.sort() is implemented using C and a lot faster than any sorting algorithm you might try to implement yourself
3 Likes
Benchmark it, I’m right.
2 Likes
local array, hash = {}, {}
for i = 1, 1e3 do
table.insert(array, i)
hash[i] = true
end
return {
ParameterGenerator = function()
return
end;
Functions = {
["array"] = function(Profiler)
for i = 1, 1e3 do
if table.find(array, i) then
local a = i
end
end
end;
["hash"] = function(Profiler)
for i = 1, 1e3 do
if hash[i] then
local a = i
end
end
end;
};
}
4 Likes
The original question was about sorting, not a lookup question.
On a google search, table.sort uses quicksort, which has on average O(n log n) complexity, the best complexity you can have in a sorting algorithm. There’s also probably a quicksort/mergesort/heapsort implementation in Lua somewhere online.
Not to mention, OP is using two nested for loops and table.find, which I think averages out to O(n^3) complexity. It could at least be simplified to selection sort, which is O(n^2).
Edit: I double-checked the Luau source code, and it uses the quicksort algorithm as well as vanilla Lua.
1 Like
Read the title. “Suggestions on how to make this sorting code faster”. I am making a suggestion on making his code faster. He is using table.find to which I am suggesting a faster alternative.
1 Like
1 Like
Yes, I was wrong, I remember reading from some source a while back that said table.sort used a linear sorting algorithm 
And just a clarification, a hash map has nothing to do with sorting, it’s about his code itself where he used table.find as part of his sorting algorithm
2 Likes
im just wondering, you made a earlier post where you were able to monitor the speed/efficiency of the code or something, what did you use for that?
Can you explain a little more about what you need this array for?
I am not sure that building and sorting an array like this is your best option for solving the problem.
2 Likes
local function swap(arr, i, j)
local temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
end
local function partition(arr, left, right)
local pivot = arr[right]
local i = left - 1
for j = left, right - 1 do
if arr[j] < pivot then
i += 1
swap(arr, i, j)
end
end
swap(arr, i + 1, right)
return i + 1
end
local function quickSort(arr, left, right)
if left >= right then
return
else
local pivot = partition(arr, left, right)
quickSort(arr, left, pivot - 1)
quickSort(arr, pivot + 1, right)
end
end
return {
ParameterGenerator = function()
local tableTest : Array<number> = {}
local randomNumber : number
--Filling the table with 100 random numbers to sort
for _ = 1, 100 do
randomNumber = math.random(1, 1000)
table.insert(tableTest, randomNumber)
end
return tableTest
end,
Functions = {
["table.sort"] = function(Profiler, tableTest : Array<number>)
table.sort(tableTest, function(a, b)
return a > b
end)
end,
["Insertion Sort"] = function(Profiler, tableTest : Array<number>)
for start = 2, #tableTest do
local temp = tableTest[start]
local index = start
while index > 1 and temp < tableTest[index - 1] do
tableTest[index] = tableTest[index - 1]
index = index - 1
end
tableTest[index] = temp
end
end,
["Quick Sort"] = function(Profiler, tableTest : Array<number>)
quickSort(tableTest, 1, 2)
end,
}
}
local tableOfSizes = {}
for _, v in ipairs(folder:GetChildren()) do
table.insert(tableOfSizes, {instance = v, size = v.Size})
end
table.sort(tableOfSizes, function(a,b)
return a.size > b.size -- or a.size < b.size (whichever order you need)
end)
for _, sortedItem in ipairs(tableOfSizes) do
warn(sortedItem.instance, sortedItem.size)
--sortedItem would be of type: {instance: any, size: number}
end
When it comes to sorting you’re probably not going to be able to implement an algorithm that is faster than the default table.sort(). The more interesting question is why are you sorting? Can you just keep the result and use that for subsequent lookups? Can you sort once and keep the order when elements are added? Can you instead use a hash table? Can you reduce the amount of elements that need sorting? Can you scrap sorting altogether and process each thing in an arbitrary order? Is it fine if it takes a while and you yield during the sort?
All of these depend on the problem sorting is solving. But when it comes to sorting itself, you’re probably not going to see a massively better algorithm than table.sort()
numerical loops runs about 30% faster than next loop and pairs loop according to this website
i saw you using next loop so i had to mention it because the first thing that came to my mind is that you used a next loop because its faster than a pairs loop but it might be a wrong assumption that came out of the blue
i have a better suggestion than my last one. the last one was kind of basic
basically to make this piece of code run faster, the problem is that what this code is doing is
note: randomNumbersTable being folder:GetChildren() in this case
1: take a random number from the randomNumbersTable
2: compare the random number to every number in the randomNumbersTable
3: index into tableOfSizes once complete
4: repeat
do you not see the problem?
the question is that, do you REALLY have to compare one number to every number to achieve this?
is it really that necessary?
and the answer is that there is a better way to go about it compared to how you went about it then to make this code run faster, you’ll have to change the approach and get rid of the thought of comparing one number to every other number.
note: orderedTable is tableOfSizes
i suggest you try this method i came up with:
take a random number from the randomNumbersTable.
blindly index into orderedTable.
ask the computer “is the random number indexed smaller than the random number indexed before it”.
if the random number indexed IS smaller than the random number indexed before it then keep swapping the index of the most recent random number indexed with the index before it until the index before it has a number smaller than it.
repeat.
--also i scripted it for you
local callsMade = 0
local random = Random.new()
local randomNumbers = {}
for i = 1, 250 do
randomNumbers[i] = random:NextInteger(1, 41019238712983712)
end
local numbersMinToMax = {}
numbersMinToMax[0] = -math.huge
local function sort(i, randomNumber)
callsMade += 1
numbersMinToMax[i] = randomNumber
if randomNumber < numbersMinToMax[i - 1] then
numbersMinToMax[i] = numbersMinToMax[i - 1]
sort(i - 1, randomNumber)
end
end
local theTimeWhenThisVarWasMade = os.clock()
for i = 1, #randomNumbers do
callsMade += 1
sort(i, randomNumbers[i])
end
local speedPerformance = os.clock() - theTimeWhenThisVarWasMade
print(numbersMinToMax)
print(callsMade)
print(speedPerformance)
note: this method can be made theoretically faster if it has a guessing mechanical that makes a better guess out of a bad one and keep repeating it until it reaches the correct index but you should just use table.sort. The point of this was to prove that there is a better way to go about “compare the random number to all numbers in the table”
summary of suggestion: just dont repeat “compare the random number to all numbers in the table” because this is the MAIN reason why your code is slow
Roblox uses Luau, not native Lua and there’s a lot of internal changes. I would advise you to do all the benchmarking yourself if you want a clear answer
The screenshot below is from a benchmark back in 2021
