4 ms·
> Why would you want to use a non-intrusive doubly-linked list? Or you have a list of objects with many references to parts inside the list and you want to rea
by Jensson 5y ago
> Why would you want to use a non-intrusive doubly-linked list?
Or you have a list of objects with many references to parts inside the list and you want to rearrange those parts from those references at O(1) speed.
Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. Lets say I put integers in these so the data is embedded in the list. You have many other places referring to elements inside the list and you want those references to track the objects position.
How would you solve this using a Rust compatible data structure?
> The question is fair.
No it is not. Experienced people almost surely knows their use case better than you do.
> there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting.
Are you kidding me? Seriously, I don't see how you could believe this unless you never tried to use ref counting to replace other code and compare the performance difference.
- volta83 5y ago> Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. You can do this with a vector of pointers as well, at lower space complexity cost (1 pointer per element instead of two), and a lower runtime cost (1 swap of two pointers instead of swapping 4 pointers). Such a data-structure has also other advantages, like higher cache efficiency, etc.
- Jensson 5y agoYou can't move an element in a vector in O(1) time. Swapping isn't the same as moving, you'd have to move n elements to make room for the new one.
- volta83 5y agoYou mentioned changing the order of two elements in a list, such that one comes after the other. With a vector of pointers to the elements (C++ std::vector<T*>) this can be easily done in O(1) as I explained above. If now that I've proven you wrong, you want to change the problem to something else, feel free to state your new problem, and I'll proceed to prove you wrong again.
- Jensson 5y ago> You mentioned changing the order of two elements in a list, such that one comes after the other. Putting B after A is not swapping them, it is putting the element B so it is right after A. You could technically interpret it as you did, but only a contrarian would do that. If you want more people to support rust then you should stop being a contrarian. If you want me and others to assume that the Rust community is full of hard to work with people then please continue, but that wont make people more likely to pick up rust. If instead of behaving like you do here people would just say "Sure thing, in order to get that performance in rust you just do X and Y!" I bet people would be way more supportive of rust. But if working in the language means that people like you will come and argue like this then why not just write a C library, and then someone will write a Rust wrapper and people are happy? While if they'd write it in unsafe Rust people would come and complain like hell.
- volta83 5y ago> You could technically interpret it as you did, but only a contrarian would do that. Or you could have been more clearer. I didn't intend any animosity, but you clearly do. > If you want more people to support rust I don't care whether more people support Rust or not. I am just fighting the spectacular amount of disinformation in this thread by malicious actors that have never used Rust. > Putting B after A is not swapping them, it is putting the element B so it is right after A. Then you should have written that instead. Take the pointer in the vector right after A, and swap it with B. That way, A is now right before B, and B is now right after A.
- Jensson 5y ago> Take the pointer in the vector right after A, and swap it with B. That way, A is now right before B, and B is now right after A. This is a joke, right? I don't see how it can't be. But in case it isn't, in almost all problems like this it is assumed that you don't want to change the order of the other elements. For example, if you wrote a function MoveToDirectlyAfter(a, b), and it did move elements other than a or b people would say that your function contains bugs or that it doesn't do what it says.