9. キュー
著者:梅谷 武
各言語においてキューの基本動作を確認し、比較する。
作成:2024-09-17
更新:2024-09-21
更新:2024-09-21
キューとはデータを先入れ先出し(FIFO: First In, First Out)で管理するデータ構造である。Racketで簡単な例を示す。標準可変(mutable)キュー:data/queueを用いる。
- 空キュー生成: (make-queue)
- enqueue: (enqueue! que value)
- 先頭挿入: (enqueue-front! que value)
- dequeue: (dequeue! que)
- リスト変換: (queue->list que)
- 空キュー?: (queue-empty? que)
- キュー長: (queue-length que)
> (require data/queue)
> (define que (make-queue))
> (enqueue! que 0)
> (enqueue! que 1)
> (enqueue! que 2)
> (queue-length que)
3
> (queue->list que)
'(0 1 2)
> (dequeue! que)
0
> (dequeue! que)
1
> (dequeue! que)
2
> (queue-length que)
0
> (queue->list que)
'()
同じことをOCamlでやってみる。標準ライブラリのQueueモジュールはmutableなキューを提供する。キューをリストに変換する機能はない。
- 空キュー生成: Queue.create
- 先頭要素取得: Queue.peek que
- enqueue: Queue.add value que
- dequeue: Queue.take que
- 空キュー?: Queue.is_empty que
- キュー長: Queue.length que
# let que = Queue.create ();;
val que : '_weak1 Queue.t =
# Queue.add 0 que;;
- : unit = ()
# Queue.add 1 que;;
- : unit = ()
# Queue.add 2 que;;
- : unit = ()
# Queue.length que;;
- : int = 3
# Queue.peek que;;
- : int = 0
Queue.take que;;
- : int = 0
# Queue.take que;;
- : int = 1
# Queue.take que;;
- : int = 2
# Queue.length que;;
- : int = 0
# Queue.is_empty que;;
- : bool = true
std::queueを用いる。
Module Queueを用いる。
data/queueを用いる。
繰り返す回数nを与える。
- 空キュー:queを作る。
- enqueueをn回繰り返し、queの長さを見る。
- dequeueをn回繰り返し、queが空になったことを見る。
queue.cpp:
#include <chrono>
#include <print>
#include <queue>
#include <stdexcept>
void test(long n) {
// push
auto start = std::chrono::high_resolution_clock::now();
std::queue<long> que;
for (long i = 0l; i < n; ++i)
que.push(i);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end - start;
std::println("length = {}", que.size());
std::println("push time: {:9.6f} [sec]", duration.count());
// pop
start = std::chrono::high_resolution_clock::now();
while (!que.empty())
que.pop();
end = std::chrono::high_resolution_clock::now();
duration = end - start;
std::println("length = {}", que.size());
std::println("pop time: {:9.6f} [sec]", duration.count());
}
int main(int argc, char *argv[]) {
try {
if (argc != 2) {
throw std::invalid_argument(
"Usage: queue <positive integer>");
}
long n = std::stol(argv[1]);
if (n <= 0l) {
throw std::invalid_argument(
"The argument must be a positive integer.");
}
test(n);
} catch (const std::logic_error &e) {
std::println(stderr, "Logic error: {}", e.what());
} catch (const std::runtime_error &e) {
std::println(stderr, "Runtime error: {}", e.what());
} catch (const std::exception &e) {
std::println(stderr, "Another std::exception: {}", e.what());
} catch (...) {
std::println(stderr, "Unknown exception.");
}
return 0;
}
makefile:
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = queue.cpp
EXES = queue_g queue_l
all: $(EXES)
queue_g: $(SRC)
$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
queue_l: $(SRC)
$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
clean:
rm -f $(EXES)
n = 10000000で測定する。
$ measure ./queue_g 10000000
length = 10000000
push time: 0.064587 [sec]
length = 0
pop time: 0.017294 [sec]
======================================
Process exited with status: 0
total time: 0.089741 [sec]
mem size: 84956 [KB]
code size: 128 [KB]
$ measure ./queue_l 10000000
length = 10000000
push time: 0.079857 [sec]
length = 0
pop time: 0.019460 [sec]
======================================
Process exited with status: 0
total time: 0.107054 [sec]
mem size: 85620 [KB]
code size: 101 [KB]
queue.ml:
open Printf
let test n =
(* push *)
let start = Unix.gettimeofday () in
let que = Queue.create () in
for i = 0 to n - 1 do
Queue.push i que
done;
let end_ = Unix.gettimeofday () in
printf "length = %d\n" (Queue.length que);
printf "push time: %9.6f [sec]\n" (end_ -. start);
(* pop *)
let start = Unix.gettimeofday () in
while not (Queue.is_empty que) do
ignore (Queue.pop que)
done;
let end_ = Unix.gettimeofday () in
printf "length = %d\n" (Queue.length que);
printf "pop time: %9.6f [sec]\n" (end_ -. start)
let () =
try
if Array.length Sys.argv <> 2 then
raise (Invalid_argument
"Usage: queue <positive integer>")
else
let n = int_of_string Sys.argv.(1) in
if n <= 0 then
raise (Invalid_argument
"The argument must be a positive integer.")
else
test n
with
| Invalid_argument msg ->
eprintf "Logic error: %s\n" msg
| Failure msg ->
eprintf "Runtime error: %s\n" msg
| exn ->
eprintf "Another exception: %s\n" (Printexc.to_string exn)
makefile:
OCAMLOPT = ocamlopt
OCAMLFLAGS = -O2
LIBPATH = -I +unix
LIBS = unix.cmxa
SRC = queue.ml
EXES = queue
all: $(EXES)
queue: $(SRC)
$(OCAMLOPT) $(OCAMLFLAGS) $(LIBPATH) -o $@ $(LIBS) $(SRC)
clean:
rm -f $(EXES) *.o *.cmx *.cmi
n = 10000000で測定する。
e$ measure ./queue 10000000
length = 10000000
push time: 0.688266 [sec]
length = 0
pop time: 0.599199 [sec]
======================================
Process exited with status: 0
total time: 1.307432 [sec]
mem size: 288552 [KB]
code size: 3300 [KB]
queue.rkt:
#lang racket
(require iso-printf)
(require data/queue)
(define (test n)
; push
(define start (current-inexact-milliseconds))
(define que (make-queue))
(for ([i (in-range n)])
(enqueue! que i))
(define end (current-inexact-milliseconds))
(printf "length = %d\n" (queue-length que))
(printf "push time: %9.6f [sec]\n" (/ (- end start) 1000.0))
; pop
(set! start (current-inexact-milliseconds))
(let loop ()
(unless (queue-empty? que)
(dequeue! que)
(loop)))
(set! end (current-inexact-milliseconds))
(printf "length = %d\n" (queue-length que))
(printf "pop time: %9.6f [sec]\n" (/ (- end start) 1000.0)))
(define (main args)
(with-handlers
([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
[exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
(cond
[(not (= (vector-length args) 1))
(error "Usage: queue <positive integer>")]
[else
(let ([n (string->number (vector-ref args 0))])
(cond
[(not (integer? n))
(error "The argument must be an integer.")]
[(<= n 0)
(error "The argument must be a positive integer.")]
[else
(test n)]))])))
(main (current-command-line-arguments))
n = 10000000で測定する。
$ raco exe queue.rkt
$ measure ./queue 10000000
length = 10000000
push time: 1.347604 [sec]
length = 0
pop time: 1.258418 [sec]
======================================
Process exited with status: 0
total time: 3.128601 [sec]
mem size: 666752 [KB]
code size: 12564 [KB]
測定結果を表にまとめる。単位は秒[sec]。
測定項目 | GCC | Clang | OCaml | Racket |
---|---|---|---|---|
push | 0.065 | 0.080 | 0.688 | 1.348 |
pop | 0.017 | 0.019 | 0.599 | 1.258 |
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani