Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It would be interesting to know why you think the linked-list based implementation is slow. This is the classic implementation of a queue. Insert and delete are about as fast as I can imagine (updating one or two reference fields). Note that I haven't looked at the code you're talking about.</p> <p>You can implement a ring buffer with an array. It might be faster for some things (like traversing all elements, say), but would have a maximum size (for the most straightforward implementation). There are also complications in initializing the array.</p> <p>Generally speaking, functional (immutable) implementations of data structures are a bit slower than the corresponding imperative (mutable) versions. There's a very nice functional queue implementation that has great performance. The basic trick is to keep half the queue in forward order (for fast removal) and half in reversed order (for fast insertion). The extra pass for reversal introduces a small penalty, like I was saying.</p> <p>If you're looking at memory (allocation and GC), the immutable approach will allocate the most, the classic method a medium amount, and the ring buffer will allocate very little. But a good FP implementation (like OCaml) makes it very fast to allocate memory, and it's not too slow to reclaim it either if the objects are short-lived.</p> <p><strong>Edit:</strong> For what it's worth, I just ran an exceptionally crude timing test on my laptop (3.06 GHz Intel Core 2 Duo), and I can enqueue and dequeue a million values using the standard OCaml Queue module in 70 millisec. So then that's about .7 msec to do 10,000 (if I got that right). It doesn't seem fast enough to do what you want if your CPU is no faster than mine.</p> <p><strong>Edit 2:</strong> I just hand wrote some code that assumes there's a pre-existing reference field in your values that can be used to queue them up. This avoids doing any allocations in the queueing code, but is otherwise similar to the standard Queue module (though far less elegant). On the same laptop as above, a million queues and dequeues takes around 48 millisec. So it's a little faster.</p> <p><strong>Edit 3:</strong> Very likely you've got your answer by now, but I just ran a crude timing test using the pure queue implementation I outlined above, and I see around 18 millisec to do a million queues and dequeues. So it's quite a bit faster. This is plausible, as OCaml is tuned for pure computation. Here is my code; you can check for any errors.</p> <pre><code>type q = { head: int list; tail: int list; } let q_add q i = { q with tail = i :: q.tail } let q_take q = match q.head with | [] -&gt; begin match List.rev q.tail with | [] -&gt; raise Not_found | h :: t -&gt; (h, { head = t; tail = [] }) end | h :: t -&gt; (h, { head = t; tail = q.tail }) let main () = let q = q_add { head = []; tail = [] } 0 in let now = Unix.gettimeofday () in let rec go q i = if i &gt; 1_000_000 then q else let (_, q') = q_take (q_add q i) in go q' (i + 1) in let _ = go q 1 in let duration = Unix.gettimeofday () -. now in Printf.printf "%f\n" duration let () = main () </code></pre> <p>Like I said, this is a crude test. The queue just alternates between 1 and 2 elements in length. I'm not sure the results would hold up in your environment. But it's interesting.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow can I build a faster implementation of Queue?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJeffrey Scofield
    1. USJeffrey Scofield
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow can I build a faster implementation of Queue?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COwhat do you think of janestreet's [DeQueue](http://www.janestreet.com/ocaml/doc/core/Dequeue.html) solution ?
      singulars
      1. PO
      1. UScodablank1
    2. COI haven't looked at their code either, but generally speaking a double-ended queue is going to be harder to implement effectively than a single-ended one because it can do more. Have you done some timing tests? A simple solution might work better than you think. A millisecond is a long time.
      singulars
      1. PO
      1. USJeffrey Scofield
    3. COI just tested it but the problem I needed to test q_add and q_take separately with iterative calls to simulate random enqueue and dequeue : `let test f init max = let t1 = Unix.gettimeofday() in for i = init to max do f i; done; let t2 = Unix.gettimeofday() in printf "time in milliseconds : %f" ((t2 -. t1) *. 1000.); print_newline();; let q = ref { head = []; tail = [] };; test (fun i -> q:=q_add !q i) 0 40000;; test (fun i -> q_take !q) 0 40000;;` I get something like ~2.0 millisec and ~15000.0 millisec ! Is my test just not adequate ?
      singulars
      1. PO
      1. UScodablank1
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload