problems with a function

[echo tide]

local function uniqueE(edges)
    local Unique={}
    for i,edge in pairs(edges) do
        local IsUnique = true
        for j,otherEdge in pairs(edges) do
            if compareE(edge,otherEdge) and i~=j then
                IsUnique=false
                break
            end
        end
        if IsUnique then
            table.insert(Unique,edge)
        end
    end
    return Unique
end

the function is currently O(n^2) , which is expensive for the thing im trying to do , is there a way i can make it detect duplicate edges without using a nested loop?

[vestal mist]

nah

"i, edge"

[mellow coral]

dont think u can reduce the time complexity

[echo tide]

aw dang it

well maybe an S4 or something can help

[fervent obsidian]

I don't know how much it'll reduce it, but you could instead run through the list once and fill a table with all of the occurrences of an edge (with like a string key) and then loop through that map, inserting all keys where the value is 1

it may make it more complex, but maybe then it'd be a O(n+n) rather than a O(n^2)?

No idea, just brainstorming

[echo tide]

key strings.... ill try that

[twin tartan]

create a key for edge instead of comparing each like ;

local edgeKey = function(edge)
  local a, b = edge[1], edge[2]
  if a > b then
    a, b = b, a
  end
  
  return `{a}-{b}`
end


local uniquE = function(edges)
  local seen = {}
  local unique = {}

  for _, edge in edges do
    local key = edgeKey(edge)
     if not seen[key] then
        seen[key] = true 
        table.insert(unique, edge)
     end

    end

  return unique
end

now you are at O(n) if i'm not wrong

[twin tartan]

oops I think I gave you the answer u wanted

didn't even see the message from this dude

[echo tide]

can you add comments if possible , im not really profecient in lua

[twin tartan]

which part ?

[echo tide]

edgekey function

it interests me how you did it

 if a > b then
    a, b = b, a
  end

youre comparing element 1 and 2 of each edge , which are of vector 3

you can compare vectors like that?

[twin tartan]

Didn't know it was vector

[echo tide]

oh excuse me for not saying earlier

edges are on the 3d space

[twin tartan]

you use the 3 axis

right

Y X Z

[echo tide]

i insert vector3's but currently use only 2 (x,z)

[twin tartan]

Then just do a function to compare 2 vectors and change a > b by CompareVec(a, b)

if CompareVec(a, b) then

end

and it would work

then return

{a.X},{a.Z}-{b.X},{b.Z}

And it's highly probable you could use buffers to make this way more faster than it is

[echo tide]

man i reallly wanna learn them

i heard alot of good uses about buffers

[twin tartan]

sort of table that are ordered like you want, faster, smaller, in the size you want

Learn them could be useful

[echo tide]

how about i check for both edges

a-b and b-a

if not seen[key1] and not seen[key2]
set both to true

[twin tartan]

work but redundant

[echo tide]

youre saying its useless checking?

[twin tartan]

Mine already normalize

a,b or b,a is the same at the end

one key for two comparaison but it's the same edge

[echo tide]

oh normalizing is better for modulation

[twin tartan]

just better

[twin tartan]

It's like saying I would use two keys for a door, one when i want to go in, one when i want to go out

instead of using one key that work for in and out

[echo tide]

no it makes sense

i get it

thank you

its going to be O(n) probably now

or O(n+n)

[twin tartan]

Yeah, benchmark it should be atleast 2x faster

[echo tide]

Great

[sonic eagle]

O(n+n) is equivalent to O(n)

(they're both linear)