#What is the time complexity for cloning a Vec with respect to the number of elements?

43 messages · Page 1 of 1 (latest)

median delta
#

Not sure if this has a very obvious answer or not, to me it would make sense if it's linear but maybe there's some memory trickery being done to make it constant?

delicate raven
#

Definitely not constant

opal brook
#

The actual theoretical time complexity is kind of disconnected from reality. Vecs of 5 and 10 elements might take nearly the same amount of time, while 1 million vs 10 million would probably take >10x if it has to go to ram.

junior yacht
#

There has to be a memcpy at least, which is O(n), I think

delicate raven
#

It's a clone, not a copy, memcpy might never happen

junior yacht
#

Well, that would be the best case scenario for performance, right?

#

Since memcpy is super optimized

delicate raven
#

It calls each element's clone, so it's O(n) if we treat clone as O(1)

median delta
#

ah i see

#

thank you

#

i need a relatively weird data structure for a project and i'm not sure how to do it, should i ask in #981431291683700776 or somewhere else?

opal brook
#

What are your constraints?

median delta
#

essentially i need it to be a tree where

#

from a node you can go up n levels in constant time

#

and preferably constant time for adding a child to a node

#

i dont need to go down the tree or to siblings or anything like that

#

also i should be able to remove nodes too

opal brook
#

How about a vec that's made of (node, Vec<index>) where the nth index is the index of the nth parent in the big vec.

median delta
#

but the problem with that is

#

wait oh

#

i see

#

but when i do that dont i need to

#

if i want to add a child, id need to clone that vector and insert an element at position 0

#

and also if i remove a node i end up with everything shifting

junior yacht
median delta
#

yees slotmap is great

#

i use it a lot

median delta
#

is this data structure even mathematically possible 🥴

delicate raven
#

If you're ok with node removal having arbitrarily garbage performance, it might be

median delta
#

honestly i think thats allright

delicate raven
#

Ok, so, this is an unsafe idea. Slotmap can probably make it safe, but I'm not familiar enough with its API to translate.

You want to write a tree made of Nodes, where a Node is

struct Node<T> {
  data: T,
  parents: Vec<*mut Node<T>>,
}
```To reach the nth parent, you'd dereference the nth pointer in the vector, which is O(1). 

Adding a node is O(depth_of_parent), which with some luck would be a small number (provided you can't place it between a parent and a child (that is, no turning a `A<-B` into `A<-C<-B`)). You'd have to clone the parent's node vector and add one more entry to it. If you're willing to lose the ability to remove elements, you can use something like the `im` crate to store the parents array, which I believe would make adding a node _usually_ O(1), but I haven't checked. (EDIT: you might actually be able to use `im` and keep element removal. Not sure)

Element removal would be sad, since you'd need to traverse all children of this node to make them disappear. You technically _could_ leak them too, I guess. If you go with that, you could keep nodes in an arena, so leaked nodes are still _eventually_ dropped when the arena is.
#

Out of curiosity, what's the intended use case?

median delta
#

i was experimenting with static analysis in langdev and i wanted to try to see if i can make some scope stuff work in constant time

#

in dynamic languages that ive made before if you had something like

var a = 0
if true {
  if true {
    print(a);
  }
}
#

it needed to traverse upwards 2 scopes to find the corresponding a variable

#

so i was thinking now that i can extract info about variable placement before runtime i could optimize it

#

technically i shouldnt even need a tree, the only problem is that im gonna add closures that capture the environment to my lang and im gonna need to keep track of certain scopes

median delta
delicate raven
#

Best you can get for that is probably O(log n)

median delta
#

i see

delicate raven
#

ooo, exactly im's use case 😄

im provides immutable collections, which have the property that to ever add/remove an element, you need to clone them. However, they're clever about it, so they reuse as much memory as possible between clones, meaning that cloning is comparatively fast.

im's hashmap, for example, has

Most operations on this map are O(log_x n) for a suitably high x that it should be nearly O(1) for most maps. Because of this, it’s a great choice for a generic map as long as you don’t mind that keys will need to implement Hash and Eq.

median delta
#

oh interesting

#

ill read up on this thanks