著者
林 達也 中野 浩嗣 オラリウステファン
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告アルゴリズム(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).

言及状況

Twitter (1 users, 1 posts, 0 favorites)

こんな論文どうですか? 仕事・時間量について最適なPRAM上のkマージアルゴリズム(林 達也ほか),1996 https://t.co/bWnzfV89LH

収集済み URL リスト