3 ms·
Possibly the most critical code in my application: #Non-destructive. Returns the input array/list in randomized order. Uses approximately O(n) time and O(n
by patio11 15y ago
Possibly the most critical code in my application:
#Non-destructive. Returns the input array/list in randomized order. Uses approximately O(n) time and O(n) space.
def self.shuffle_array(array)
shallow_copy = array.map {|a| a}
shallow_copy.size.downto(1) {|n| shallow_copy.push(shallow_copy.delete_at(rand(n)))
shallow_copy
end
- rue 15y agoHopefully you've since migrated to Array#shuffle.
- patio11 15y ago"If it ain't broke..."
- ssp 15y agoDoesn't that run in quadratic time - or can delete_at() somehow avoid copying all the tail elements in the array?
- T-hawk 15y agoI know nothing about Ruby, but it's possible if a language implements an array as a linked list so the tail elements don't actually move. (At any rate, I hardly think we're worried about a modern computer workload of at most 25^2 string operations.)
- ssp 15y agoIn that case, it couldn't find the element to delete in constant time.
- klochner 15y agoYour function isn't close to linear. Here are my benchmarks for 10 iterations of sorting: patio11: 100000 -- 120.469834 10000 -- 1.218803 1000 -- 0.019961 100 -- 0.000958 Array.shuffle: 100000 -- 0.054125 10000 -- 0.002993 1000 -- 0.000302 100 -- 4.1e-05