5 ms·
My first guess would be that a FIFO queue is more efficient as a list than an array, but maybe there's something weird about ruby that makes that untrue. I'd l
by tedunangst 15y ago
My first guess would be that a FIFO queue is more efficient as a list than an array, but maybe there's something weird about ruby that makes that untrue. I'd love to hear why.
- tptacek 15y agoUnless you have an extraordinarily clever implementation of "linked list in Ruby" (in which case this is still a terrible interview question), no. Arrays are more efficient for every reasonable access pattern. If the links of your list are references to Ruby objects (which every online "linked list in ruby" page uses), they're not so much "more efficient" as they are "tractable" compared to linked-list's "intractable".
- tedunangst 15y agoLooks like you're right, interpreter time dominates unless I use rbx, and it's still not a big win for linked lists. But the meaning of your last sentence escapes. Linked lists are tractable compared to intractable linked lists? Antecedent mismatch?
- tptacek 15y agoProbably. All I meant to say is that on MRI, you might as well give up on reference-based linked lists; they just don't work at scale. In rbx, you're saying 1000.times { list.insert(500000, 666) } actually beats 1000.times { array.insert(500000, 666) } I really should be taking rbx way more seriously.
- tedunangst 15y agoSomething like that. rbx takes about 0.5 secs to start up, but after that it generally runs in the neighborhood of 10x faster, assuming you're spending enough time in actual ruby code to make that possible.
- tptacek 15y agoCan you show me your list implementation? I just installed rbx and tried this; the Array implementation ran in single-digit seconds, but I gave up and CTR-C'd the list one (which works fine for smaller lists).
- tedunangst 15y agoWhy do I get the sinking feeling I'm about to embarrass myself by implementing a linked list wrong? Anyway, here's the test case I used, where I'm emulating a FIFO. class Link attr_accessor :next, :v end i = 2000 j = 10000 k = 100 if true p "linked list" j.times { head = Link.new tail = head i.times { n = Link.new n.v = 12 tail.next = n tail = n } (i-k).times { n = head head = head.next } } else p "array" j.times { arr = [] i.times { n = Link.new n.v = 13 arr << n } (i-k).times { n = arr.pop } } end
- tptacek 15y agoMy test was: 1. Make a 1,000,000 node linked list of integers (I used doubly linked lists but I don't think it matters). 2. 1,000 times, insert into the middle of the list; I wrote a trivial O(n) stateless insert and called it with an offset of 500,000 1,000 times. 3. Make a 1,000,000 element Array of integers --- I just did "1000000.times.map". 4. 1,000 times call "insert" with an index of 500,000. Step (2) takes so long I kill the process. Step (4) takes a barely perceptible amount of time. (Both in Rubinius). It looks to me like: * You're using much smaller data structures than I am * Your "Array" case is still building Link objects, so still incurs the object management overhead * You're inserting at the head of the list every time, which doesn't incur seek time. But inserts at the head or tail of a contiguous array don't need to seek or reallocate either.
- tedunangst 15y agoIf 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.
- petercooper 15y agoAll I meant to say is that on MRI, you might as well give up on reference-based linked lists; they just don't work at scale. I think that, sadly, this is true of almost any well engineered data structure. MRI's overhead is so vast that even if you perform an operation at, say, O(n) with the logical solution, using a naive built-in or iterative technique with retrieval of O(n * n) will be faster up until the often rather distant point where the lines cross.
- tptacek 15y agoIt's just as bad on Rubinius and just as bad on JRuby. I think this has more to do with tree-walking (and using a data structure that intensively requires that) than simply MRI overhead.