Can i make my code faster??? | Together C & C++ | Page 1

bitter salmon Oct 25, 2022, 1:48 PM

#

on that big input???

#

lol

stone juniper Oct 25, 2022, 1:49 PM

#

yeah

#

before it ran like 1m30s

bitter salmon Oct 25, 2022, 1:49 PM

#

hmm what have u actually done...

#

hash

stone juniper Oct 25, 2022, 1:49 PM

#

made is_part significantly faster :P

bitter salmon Oct 25, 2022, 1:49 PM

#

oh

#

ok

#

oh so operator== is for .find

stone juniper Oct 25, 2022, 1:53 PM

#

well not quite, how it works with these kind of containers it seperates it on hash, but you can have hash collision so you need a way to compare coords

#

so you need both for unordered_set

bitter salmon Oct 25, 2022, 1:54 PM

#

umm is partsSet.insert working as push_front??

#

it should push value at front

stone juniper Oct 25, 2022, 1:55 PM

#

no, not quite

#

the order in partSet is completly "random"

#

however it's just used to check if a coord matches any of the parts

bitter salmon Oct 25, 2022, 1:56 PM

#

oh

#

it makes sense

stone juniper Oct 25, 2022, 1:56 PM

#

though I didn't test it just saying

#

just ran it

#

but I think it should be fine

#

as you don't modify values anywhere, and im mirroring pops and pushes in the set

bitter salmon Oct 25, 2022, 1:59 PM

#

where is actually this hash used?

#

ide shows me

#

Struct 'hash<Coord>' is never used

stone juniper Oct 25, 2022, 2:02 PM

#

bitter salmon Struct 'hash<Coord>' is never used

it's used by the internals of std::unordered_set

#

it's not called directly

bitter salmon Oct 25, 2022, 2:02 PM

#

oh ok

#

its working very fast

#

thank you very much

stone juniper Oct 25, 2022, 2:04 PM

#

do check if this is actually correct

bitter salmon Oct 25, 2022, 2:04 PM

#

ok

stone juniper Oct 25, 2022, 2:05 PM

#

I did not verify the output

bitter salmon Oct 25, 2022, 2:06 PM

#

why i didnt heard about std::unordered_set

#

is it like faster than array but unordered???

stone juniper Oct 25, 2022, 2:08 PM

#

no it's quite distinct

#

unordered_set is essentially a hased value set where everything is unique

#

there is also a regular set what is sorted

bitter salmon Oct 25, 2022, 2:09 PM

#

can unordered_set or set be faster than array???

#

faster in iteration

#

when i dont need to know order

#

what will be better

#

because if its unordered

#

then it dont need to order it

#

so it can be faster

stone juniper Oct 25, 2022, 2:12 PM

#

well it's most likely gona be slower to itterate

#

or well to do a full itteration, but the neat thing is with this you don't have a linear itteration

#

on average isPart is constant time at worst linear

#

before it was always linear

bitter salmon Oct 25, 2022, 2:19 PM

#

ok

#

also what type of container u will recommend for fruits??

#

look what fruits does

#

it only temporarily saves data

stone juniper Oct 25, 2022, 2:20 PM

#

honestly tthat seems fine

bitter salmon Oct 25, 2022, 2:20 PM

#

deque??

stone juniper Oct 25, 2022, 2:20 PM

#

nah never

bitter salmon Oct 25, 2022, 2:20 PM

#

std::deque<Fruit>

#

im using deque currently

#

which is not good

stone juniper Oct 25, 2022, 2:21 PM

#

imho that list never was an issue

bitter salmon Oct 25, 2022, 2:21 PM

#

yes but it will be good if i will know for the future

stone juniper Oct 25, 2022, 2:21 PM

#

look at the timing here

bitter salmon Oct 25, 2022, 2:21 PM

#

yes

stone juniper Oct 25, 2022, 2:21 PM

#

the only 2 big things, where isPart and timing

#

the rest is irrelevant

bitter salmon Oct 25, 2022, 2:22 PM

#

yes but it will be good if i will know for the future what is faster container type for this

stone juniper Oct 25, 2022, 2:22 PM

#

std::vector generally

bitter salmon Oct 25, 2022, 2:22 PM

#

for just holding elements and iterating once

bitter salmon Oct 25, 2022, 2:22 PM

#

stone juniper std::vector generally

hmm ok

#

isnt array faster than vector??

stone juniper Oct 25, 2022, 2:22 PM

#

it doesn't make sense for the board to be a dequeue either

#

not realy

bitter salmon Oct 25, 2022, 2:22 PM

#

ok

stone juniper Oct 25, 2022, 2:22 PM

#

the difference is constraints, arrays need to be compile time constant

#

vectors are dynamic sized

#

what well comes at a cost, but itterating speed should be basically the same

bitter salmon Oct 25, 2022, 2:23 PM

#

yes but in this case im sure what will be size of fruits

#

so vector is unnecessary

#

array can handle that better

#

there is also std::array

#

hmm

#

also i can delete new allocated array in good place

leaden cragBOT Oct 25, 2022, 2:34 PM

#

@bitter salmon Has your question been resolved? If so, run !solved :)

bitter salmon Oct 25, 2022, 2:35 PM

#

thanks for your help

#

!solved

leaden cragBOT Oct 25, 2022, 2:35 PM

#

Thank you and let us know if you have any more questions!

bitter salmon Oct 25, 2022, 4:43 PM

#

!unsolved

#

@stone juniper i have found bug

#

its not finding coord

#

actually partsSet

#

is not adding everything

#

thats because there is moment when there are 2 same coords

#

when snake is going into its own tail but is not actually like killing itself

#

everything works except this

#

wait i know why... when it happens i cant remove element

#

because its already not adding to this unordered_set

#

!solved

leaden cragBOT Oct 25, 2022, 4:54 PM

#

Thank you and let us know if you have any more questions!

distant gorge Oct 29, 2022, 8:00 AM

#

weird how much conversation happened after literally giving the superset of the solution thonk

#Can i make my code faster???