3 ms·
If you have to seek into the list, of course it's going to suck, that's not a good application for a list. Your test would blow just as bad in C. I'm not sure
by tedunangst 15y ago
If you have to seek into the list, of course it's going to suck, that's not a good application for a list. Your test would blow just as bad in C. I'm not sure that says anything interesting about lists vs arrays in ruby in particular.
I am using the same data structure, I guess it would be a little smaller without the next attr. Still seems fair. Building an array of objects is going to require allocating them. I build hand rolled linked lists by directly linking the objects of interest. Calling the class Link may have been a misnomer, it could have been called AnyClass.
It's easy to insert at the tail of an array (I'm actually inserting at the tail of the list, btw), but popping from the front means having to shift everything down. That's what makes the FIFO case interesting. If we're going to prove that ruby is too slow for linked lists to be viable, we need to be testing a scenario where linked lists generally are viable.
- tptacek 15y agoThe most naive possible C implementation takes 2.5 seconds to run this same test. I just tried it. The point of a list is "insert and delete from the middle", so I don't know how to respond to the idea that actually inserting and deleting from the middle of the list is a bad benchmark. It's difficult to respond to your last point about FIFOs for a different reason. Popping 1000 times from a 1,000,000 Array is so fast that I'd have to write code to benchmark it. And Ruby doesn't even optimize for that case; in real code, I'd use a ring buffer so that pops are just pointer adds. Ruby is, to the best of my knowledge, actually copying every single time. Copies are just way way way faster than you seem to expect them to be.
- barrkel 15y agoThe reason manipulating linked lists in the middle is faster than arrays is so you can save the O(n) work of moving elements. But you lose that if you still do O(n) worth of seeking. There is no big-O difference between inserting and deleting in the middle of an array and a plain linked list, if the linked list is forced to seek. I'm sure this is as obvious to you as it is to me, but perhaps the perspective it comes from explains why people are thinking that your described operations on the list are a dodgy benchmark for judging linked lists vs arrays; absent constant factors, they should perform the same. (And yes, for reasonable input on modern machines, the constant factors will dominate.)
- tptacek 15y agoI'm sure I agree with everything you're saying here, but it carries a whiff of tautology. You lose the benefit of middle-insertion in a list if you have to seek, but part of the point of using an array is not having to seek ever. Anyways the only thing that moved me to comment is the general inferiority of linked list data structures compared to arrays, which are what Ruby (sensibly) uses.
- adam-a 15y agoI'm reading this thread and kind of tearing my hair out. One theoretical case where lists beat arrays is seeking to the middle (once) and inserting 1000000 items in that one spot. If you want to test if lists can ever be useful in Ruby then you want to test the case that they are theoretically useful. Your test is a theoretical dead heat as arrays and lists both perform O(n) in it. All you learn is that arrays are faster in Ruby for the same complexity, which we knew already.
- tptacek 15y ago"We" didn't know that already; there was an implicit argument that there might ever be a point to building a linked list in Ruby, which, no. Like I said, we're way off the rails here.
- adam-a 15y agoI probably shouldn't have replied and dragged it out, and I apologise for my tone but you seem to be almost wilfully missing the point. There are problems where a linked list is theoretically better suited than an array. Your test is a problem where they are theoretically evenly matched. The interesting question is: do the benefits of native code etc, that you get when using an array outweigh the costs that you incur for using a non-optimal data structure for a given problem? To answer this you would need to come up with a situation where a list should be faster if the array and list were both native or both higher level ruby implementations. Then compare the actual running times to see what impact native code vs ruby code has. All your test shows is that in a problem where neither data structure has an advantage in complexity, i.e. they both perform in O(n), the one backed by native code is faster. My assertion is that is a pretty boring thing to discover and "we", or most people, would guess that anyway.
- Retric 15y agoIf your want to insert and delete in the middle use a binary tree. Linked lists are reasonable for queues and that's about it. PS: Slip lists are not bad though.