著者

林 達也 中野 浩嗣 オラリウステファン

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.89, pp.23-30, 1996-09-13

参考文献数

19

---

要素数が合計がnのソートされたk個の列をマージして新しいソート列を求める問題をkマージ問題と呼ぶ。本論文では、単純で仕事・時間量が最適な3つのPRAM上のkマージ問題を解くアルゴリズムを示す。まず、EREW?PRAM上で、O(og )時間で仕事量がO( log )のkマージアルゴリズムと、CREW?PRAMとCRCW?PRAM上でO(oglog n+log )時間で仕事量がO( log )のkマージアルゴリズムを示す。また、これらのアルゴリズムが仕事量がO( log )である限り、高速化はできないことを示す。The k-merge problem, given a collection of k,(2〓k〓n), sorted sequences of total length n, asks to merge them into a new sorted sequence. The main contribution of this work is to propose simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models. Our k-merge algorithms runs in O(log n) time and performs O(n log k) work on the EREW-PRAM. and in O(loglog n+log k) time and O(n log k) work both on the CREW-PRAM and on the CRCW-PRAM. We also prove that the computing time of these algorithms cannot be improved provided that the amount of work is bounded by O(n log k).