hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。
ラボ/MRU - HSP開発wiki
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS

ラボ

MRU

データ構造

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

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

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

実装例1(片方向リンクリスト)

fileSLinkedListMRU[sp].hsp
Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
|
!
-
|
|
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
!
 
 
 
 
 
 
 
 
 
-
|
|
!
 
 
 
 
 
 
 
-
|
|
!
-
|
!
 
 
-
|
|
!
-
|
!
 
 
 
 
 
/*
################################################################################
#                                                                              #
#      データ構造: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
 
/******************************************************************************
 *                           S A M P L E                           *
 ******************************************************************************/
 
#define LISTSIZE    6
    font "MS ゴシック",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 (火)

実装例2(双方向リンクリスト)

コメント


URL B I U SIZE Black Maroon Green Olive Navy Purple Teal Gray Silver Red Lime Yellow Blue Fuchsia Aqua White

添付ファイル:
fileSLinkedListMRU[sp].hsp
522件 [詳細]
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS
Last-modified: 2008-11-24 (月) 20:05:23 (1839d)