ラボ/MRU

MRU †

[編集]

↑

データ構造 †

[編集]

MRUとはMost Recently Used（一番最近使った）の意味で頻繁にアクセスするデータに次回から素早くアクセスするためのデータ構造で最近話題（私だけか）のコモンダイアログのLastVisitedMRUのMRUなどです。
LastVisitedMRUキー内のMRUListには最近開いた各アプリケーション毎に保持されている最後に開いたディレクトリを管理しています。
MRUListを検索するのに最近アクセスしたアプリケーションを優先するために直前にアクセスしたアプリケーションに対応する管理コードをリスト先頭に移動させ、次回以降同じアプリケーションがMRUListを参照する際に素早く検索するためです。
（同じこと繰り返していないか？）

LastVisitedMRUのMRUListの動作エミュレートに関してはHSPWikiのNote:HSPのTips集を参照してみてください。
（実はMRUを保存しないようなレジストリ設定もありますが、参照先では実装していなかったりします。）

前置きが長引きましたが、MRUとはそういうデータ構造です。
MRUの対となるデータ構造にLRUがあります。

↑

実装例１（片方向リンクリスト） †

[編集]

SLinkedListMRU[sp].hsp

/*
################################################################################
#                                                                              #
#      データ構造：MRU(Most Recently Used)                                     #
#      リスト構造の一種で頻繁にアクセスするデータに次回から素早くアクセス      #
#      できるようにしたデータ構造                                              #
#                                                                              #
################################################################################
*/
 
#module "SLinkedListMRU"
    /*--------------------------------------------------------------------*
     *                     片方向リンクリストの初期化                     *
     *--------------------------------------------------------------------*/
    #deffunc SLink_init int i
        mref res , 64
        if i < 1 : res = -1 : goto *@f
 
        n = i
 
        dim _value  , n+2
        dim _next   , n+2
 
        repeat n+1
            _next(cnt) = cnt+1
        loop
        _next(n+1)  = -1
 
        head        = 0
        tail        = head
        new         = _next(tail)
 
        res         = n
*@
        return
 
    /*--------------------------------------------------------------------*
     *                    リンクリストに要素を挿入する                    *
     *--------------------------------------------------------------------*/
    #deffunc SLink_addmru int i
 
        ; リストがいっぱい、もしくは無効なリスト
        if n = 0 : res = -1 : goto *@f
 
        ; 挿入位置を求める
        q = head
        p = _next(head)
 
        repeat
            if (p = new) | (i = _value(p)) : break
            q = p
            p = _next(p)
        loop
 
        if _next(p) = -1 : res = -1 : goto *@f
 
        _value(p)   = i     ; ダミー
 
        _next(q)    = _next(p)
        _next(p)    = _next(head)
        _next(head) = p
 
        if p = tail : tail = q
        if tail = head : tail = p
 
        new = _next(tail)
 
        ; 挿入した直前の要素のインデックス（無意味）
        res = q
*@
        return
 
    /*--------------------------------------------------------------------*
     *                    リンクリストの要素を削除する                    *
     *--------------------------------------------------------------------*/
    #deffunc SLink_del int i
        ; 空のリスト
        if head = tail : res = -1 : goto *@f
 
        ; 削除位置を求める
        q = head
        p = _next(head)
 
        repeat
            if (p = new) | (_value(p) = i) : break
            q = p
            p = _next(p)
        loop
 
        if p = new : res = -1 : goto *@f
 
        ; 末尾処理
        if p = tail{
            tail    = q
            new     = p
        }
        else{
            _next(q)    = _next(p)
            _next(p)    = _next(tail)
            _next(tail) = p
            new         = _next(tail)
        }
 
        ; 削除した要素のインデックス（無意味）
        res = p
*@
        return
 
    /*--------------------------------------------------------------------*
     *                    リンクリストの要素を表示する                    *
     *--------------------------------------------------------------------*/
    #deffunc SLink_disp
 
        p = _next(head)
        s = "[ "
        repeat
            if p = new : res = cnt : break
            s += "" + _value(p) + " "
            p = _next(p)
        loop
        s += "]" + ":" + res + "/" + n
        mes s
        return 
#global
 
/******************************************************************************
 *                           Ｓ　Ａ　Ｍ　Ｐ　Ｌ　Ｅ                           *
 ******************************************************************************/
 
#define LISTSIZE    6
    font "ＭＳ ゴシック",12
    randomize
    cmd = ""
    input cmd,,,3
    SLink_init LISTSIZE
    if stat = -1{
        dialog "リストの初期化に失敗しました．",1,"終了確認" : end
    }
 
    onkey gosub *enter
    stop
 
*enter
    if iparam ! 13 : goto *@f
 
    ; 入力ボックスチェック
    getstr num,cmd,1
    if num = ""{
        cmd = "" : objprm 0,cmd
        goto *@f
    }
 
    num = int(num)
 
    c = peek(cmd,0)
 
    switch c
        case '+' :  SLink_addmru num
                    if stat ! -1{
                        title " "+num+" を挿入しました．"
                        SLink_disp
                    }
                    else{
                        title "リストがいっぱいです．"
                    }
                    swbreak
        case '-' :  SLink_del num
                    if stat ! -1{
                        title " "+num+" を削除しました．"
                        SLink_disp
                    }
                    else{
                        title "リストが空です．"
                    }
                    swbreak
    swend
    cmd = "" : objprm 0,cmd
*@
    return

↑

コメント †

[編集]

知らないなりに想像してみた…例えば本棚から取った本を直すときは、どこから取り出しても常に一番右端に収納する。
すると、よく使う本は右側に片寄ってくる。
日々使用している本（辞書とか参考書とか）を探すときは右側から探せば見たい本がすぐに見付かるようになる。
ただし、使用頻度の高い本の割合が多く、まったく使わない本が少ないとあまり効率はよくない。（全体的な順番の入れ替わりが発生するため）
昨日使った本がもう左端に行っちゃってるよ、とか。
…こういうイメージの解釈でいいのかな？- GENKI
そんな感じというかそういう事です。
あと「全体的な順番の入れ替え」というのは"入れ替え"の事ですか？目的の本を探す"探索"の事かな？
データ構造をリンクリストで実装すれば要素の入れ替えは対象要素と先頭要素とのポインタの貼り替えだけなのでO(1)でできると予想。
「昨日使った本がもう左端に」という例のように目的の要素を探索するのにリニアサーチを使った場合は要素数に比例するのでO(N)といった計算量と予想。
このデータ構造はある要素に対して連続してアクセスするようなデータに対して効果がある、と思う。
例えばファイル選択ダイアログ。毎回異なるアプリケーションに切り替えて万遍なく使用するということは少なく、大抵はそのソフトを立ち上げたまま作業ファイルを開くといった感じだと思う。ここでファイル選択ダイアログでのMRUの要素とはファイル選択ダイアログを使用した（アクセスした）アプリケーションです。
ともかくMRUは最近使った要素に素早く"アクセス"するためのデータ構造なので、目的の要素を素早く"探索"するにはその要素の名前をキーとするリストを常にソート状態にしておき、クイックソートで探し当てる…といった事が考えられるかもしれない。
もちろんMRU要素とソート済みリストとの要素の繋がりもリンクさせておいて。 -- kz3 2005-08-25 04:37:10 (木)
はい、MRUできました＾＾見ての通り、SLinkedListAry?とほとんど変わりません。変わるのは要素の挿入操作だけです。
今回のは要素の重複を許しません。挿入操作を要素へのアクセスと捕らえ、新規要素、既存要素にアクセスすると最も最近アクセスされた要素としてリスト先頭に移動されます。しかしこの時、リストを構成する配列上のインデックスは変わりません。ポインタをつなぎかえるだけで要素の順番を変えることができます。
この要素の並びを入れ替えることなく要素をつなぐポインタをつなぎかえるだけで済む容易さが単純リストにはないリンクリストの強みです。 -- kz3 2005-09-04 11:58:35 (日)
文字列操作の指定インデックスの文字を先頭に移動(v2.61)?は文字列で指定インデックスを先頭に移していますが、これもMRUと捕らえることができます。またこれを文字列ではなくリンクリストで表現することも可能です。興味のある人は挑戦してみてね＾＾ -- kz3 2005-09-04 12:02:14 (日)
リンクリストがいっぱいの時に既存要素にアクセスできなかったのを直しました。ファイル名は同じです。 -- kz3 2005-09-06 09:50:27 (火)