Queue/Definition: Difference between revisions
Content added Content deleted
(→{{header|Groovy}}: new solution) |
(CoffeeScript) |
||
| Line 708: | Line 708: | ||
The implementation is thread-safe if there is at most one reader thread, i.e. only one thread ever calls <code>dequeue</code> on a given queue. |
The implementation is thread-safe if there is at most one reader thread, i.e. only one thread ever calls <code>dequeue</code> on a given queue. |
||
=={{header|CoffeeScript}}== |
|||
<lang coffeescript> |
|||
# Implement a fifo as an array of arrays, to |
|||
# greatly amortize dequeue costs, at some expense of |
|||
# memory overhead and insertion time. The speedup |
|||
# depends on the underlying JS implementation, but |
|||
# it's significant on node.js. |
|||
Fifo = -> |
|||
max_chunk = 512 |
|||
arr = [] # array of arrays |
|||
count = 0 |
|||
self = |
|||
enqueue: (elem) -> |
|||
if count == 0 or arr[arr.length-1].length >= max_chunk |
|||
arr.push [] |
|||
count += 1 |
|||
arr[arr.length-1].push elem |
|||
dequeue: (elem) -> |
|||
throw Error("queue is empty") if count == 0 |
|||
val = arr[0].shift() |
|||
count -= 1 |
|||
if arr[0].length == 0 |
|||
arr.shift() |
|||
val |
|||
is_empty: (elem) -> |
|||
count == 0 |
|||
# test |
|||
do -> |
|||
max = 5000000 |
|||
q = Fifo() |
|||
for i in [1..max] |
|||
q.enqueue |
|||
number: i |
|||
console.log q.dequeue() |
|||
while !q.is_empty() |
|||
v = q.dequeue() |
|||
console.log v |
|||
</lang> |
|||
output |
|||
<lang> |
|||
> time coffee fifo.coffee |
|||
{ number: 1 } |
|||
{ number: 5000000 } |
|||
real 0m2.394s |
|||
user 0m2.089s |
|||
sys 0m0.265s |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||