I have this sorting function for LinkedLists, and it removes half of the LinkedList:
local function split(head: Link)
local fast = head
local slow = head
while fast and fast.next do
fast = fast.next.next
if fast then
slow = slow.next
end
end
local temp = slow.next
slow.next = false
return temp
end
local function merge(first: Link, second: Link, comp: Comparator)
if not first then
return second
end
if not second then
return first
end
if comp(first.value, second.value) then
first.next = merge(first.next, second, comp)
return first
else
second.next = merge(first, second.next, comp)
return second
end
end
local function mergeSort(head: Link, comp: Comparator)
if not head or not head.next then
return head
end
local second = split(head)
head = mergeSort(head, comp)
second = mergeSort(second, comp)
return merge(head, second, comp)
end
-- Similar to table.sort but for LinkedLists.
-- Uses the Merge Sort algorithm to efficiently sort linked lists.
function ListUtility.sortLinks(linkedList: LinkedList, comp: Comparator)
local sorted = mergeSort(linkedList.head, comp)
linkedList.head = sorted
end
The reason is because Luau treats variables set to tables as references instead of copies. Given that deep copying these links multiple times is resource intensive at best, how would I fix this?
I’m not entirely sure how sorting for Linked Lists are implemented, but copying the table yourself through a custom function would be essentially the same in performance as if it were copied under-the-hood, at least algorithmically.
I’ve tried to run your code, but I can’t seem to reproduce this “removes half of the LinkedList”, can you check if I’m using your code correctly?
local ListUtility = {}
type Link = {next: Link, value: any}
type LinkedList = {head: Link, amount: number}
local function newLink(value: any): Link
return {next = false, value = value}
end
-- Returns an empty LinkedList.
function ListUtility.getLinkedList(): LinkedList
return {head = false, amount = 0}
end
-- Adds a value as a Link to a LinkedList.
function ListUtility.addLink(linkedList: LinkedList, value: any)
local link = newLink(value)
if linkedList.head then
link.next = linkedList.head
linkedList.head = link
else
linkedList.head = link
end
end
-- Removes a Link from a LinkedList.
function ListUtility.removeLink(linkedList: LinkedList, link: Link)
if linkedList.head == link then
linkedList.head = link.next
else
local prev = linkedList.head
while prev and prev.next~=link do
prev = prev.next
end
if prev then
prev.next = link.next
end
end
end
-- Similar to ipairs() but for LinkedLists.
-- Iterate forwards through a chain of Links
function ListUtility.links(linkedList: LinkedList)
local current = linkedList.head
return function()
local link = current
current = current.next
return link.value
end
end
local function split(head: Link)
local fast = head
local slow = head
while fast and fast.next do
fast = fast.next.next
if fast then
slow = slow.next
end
end
local temp = slow.next
slow.next = false
return temp
end
local function merge(first: Link, second: Link, comp: Comparator)
if not first then
return second
end
if not second then
return first
end
if comp(first.value, second.value) then
first.next = merge(first.next, second, comp)
return first
else
second.next = merge(first, second.next, comp)
return second
end
end
local function mergeSort(head: Link, comp: Comparator)
if not head or not head.next then
return head
end
local second = split(head)
head = mergeSort(head, comp)
second = mergeSort(second, comp)
return merge(head, second, comp)
end
-- Similar to table.sort but for LinkedLists.
-- Uses the Merge Sort algorithm to efficiently sort linked lists.
function ListUtility.sortLinks(linkedList: LinkedList, comp: Comparator)
local sorted = mergeSort(linkedList.head, comp)
linkedList.head = sorted
end
return ListUtility
And the test script that led me to conclude it deleted half the links:
local linkedList = ListUtility.getLinkedList()
for i = 0, 1000 do
ListUtility.addLink(linkedList, i)
end
ListUtility.sortLinks(linkedList, function(a, b)
return a<b
end
for value in ListUtility.links(linkedList) do
print(value) -- prints 501 to 1000 but not the other half
end
The way I am adding links is by shifting the top links, while the way you’re doing it is by adding it to the tail. I don’t really know if this would be a problem, but it’s the only thing I can see from your Demo that’s different from my code.
local ListUtility = require(script.LinkedList)
local linkedList = ListUtility.getLinkedList()
for i = 0, 1000 do
ListUtility.addLink(linkedList, i)
end
ListUtility.sortLinks(linkedList, function(a, b)
return a < b
end)
for value in ListUtility.links(linkedList) do
print(value) -- prints 501 to 1000 but not the other half
end
, then the order of the output of numbers is reversed (but the error still occurs):
, and, both times, all numbers from 0 to 1000 are printed.
This is more of a matter of opinion, but I would think that a function like .addLink(v) is like table.insert(t, v), appending to the end instead of shifting the beginning. Personally, it seems simpler to implement and would likely be more of what someone is expecting to happen when they use code like this (if you publish this as a Module, but even if you revisit the code later, you might mix-up how the links are added. Again, just my opinion on what is more obvious with the name of the function).
I think it’s important to note that the version of the module I sent was rewritten out of memory, I deleted the original one (out of frustration ) But if it does seem to work, the problem may actually have just been something i overlooked in the original module? Either way, aside from that boolean error (which is probably easily fixable), I think the problem has actually been… solved? (somehow), I’m gonna mark your last post as a solution. Thank you!
) But if it does seem to work, the problem may actually have just been something i overlooked in the original module? Either way, aside from that boolean error (which is probably easily fixable), I think the problem has actually been… solved? (somehow), I’m gonna mark your last post as a solution. Thank you!
