1. Aを使用→Aを登録→(A=1)
2. Bを使用→Bを登録→(B=1,A=2)
3. Cを使用→Cを登録→(C=1,B=2,A=3)
4. Dを使用→Dを登録→(D=1,C=2,B=3,A=4)
5. Bを使用→順序のみ更新→(B=1,D=2,C=3,A=4)
6. 一番古いのを削除 →Aを削除→(B=1,D=2,C=3)
上記のような1000個のデータ(A,B…)を使用したら、使用履歴に登録していくプログラムを作るとして
高速に検索するには、どうすればよろしいでしょうか。
検索したいのは以下の2つです。
・一番古いデータの検索(削除するため)
・データが登録有無の検索
汎用的な手法があればその名称をお教え願えないでしょうか。ちなみに二分木はちょっと違うような気がしました。
No.4
- 回答日時:
No.3 です。
[ ... 高速に検索するためには、最も最近登録された ...] は、[... 高速に登録、削除するためには、...] の間違いです。検索は、配列 i を直接参照すればよいので、No.2 の方が書かれたハッシュテーブルと(ほぼ)同じ効率です。
No.3
- 回答日時:
データの種類が1000個と前もって分かっているのであれば 、サイズが1000の配列を利用するのが最も速いのではないでしょうか。
配列の i 番目には、データ i (0<=i<=999) の登録有無を記録するとし、例えば、データ i が登録無(未登録、削除済)の場合、配列要素 i に 1000 を、登録有の場合、データ i が最も最近登録されたデータであれば -1 を、それ以外の場合は、データ i の次に登録されたデータのデータ番号を配列 i に記録しておけばよいと思います。高速に検索するためには、最も最近登録されたデータのデータ番号と、最も初めに登録された(一番古い)データのデータ番号の 2 数も記録する必要があります。
各配列要素、また、最も最近登録されたデータのデータ番号、最も初めに登録された(一番古い)データのデータ番号を初め 1000 に初期化し、あとは、登録、削除に応じて、しかるべく配列要素とこの 2 数の情報を更新すればよいと思います。
No.2
- 回答日時:
高速に検索がしたいならハッシュテーブルはどうですか?
ハッシュ値が同じものを双方向リストで管理すれば、mtsedさんのしたいことはどちらも満たせると思います。
参考URL:http://ja.wikipedia.org/wiki/ハッシュテーブル
No.1
- 回答日時:
双方向リストなどはどうでしょうか?
双方向リストとは正順にも逆順にもたどれる
リスト構造のことなんですが,
mtsedさんの例の5においてはB,D,C,Aが正順で,
B,A,C,Dが逆順になります.
双方向リストのアルゴリズム自体はネットや本に
詳しく書かれていると思いますが,簡単に言うと
各要素に対して次の要素へのポインタと前の要素へのポインタをつけておくことによって,どちらの方向へもたどれる様にするというものです.
一番古いものを正順の一番最後,つまり逆順の2番目に
来るようにしておけば,リストを一回たどれば一番古い
要素にたどり着くことができ,削除することが出来ます.いかがでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(ブラウザ) Android Google でなく Bing検索すれば 何検索したかわからずデータ収集されない? 2 2023/03/10 05:25
- Chrome(クローム) Chromeのアドレスバーに履歴等を表示させないようにしたい 2 2022/09/08 14:20
- docomo(ドコモ) home5G用のdアカウントに登録した連絡先電話番号を削除することはできますか? 貯まってるdポイン 2 2023/06/24 12:51
- Excel(エクセル) 【Excel】指定のセル内容を基に別シートのセルを検索して選択する【VBA】 1 2022/06/16 16:16
- Oracle 質問です。 下記のテーブルとデータがあり、 取得想定結果のように出力したいです。 下記のsqlだと0 2 2023/05/23 19:10
- その他(音楽・ダンス・舞台芸能) 同じ作曲家でも登録しているものとしていないものがある。 1 2022/06/26 19:56
- 携帯型ゲーム機 もう一回質問 3DSを売ります。 初期化しました。SDカード抜きました。使ってないと思うが一応eショ 2 2022/03/31 13:33
- Safari(サファリ) 他人に、Safariの検索履歴を見られている可能性ってありますか? 会社の業務で、Safariを使っ 1 2023/03/15 18:02
- Chrome(クローム) シークレットモード 何に使う? グーグルにも検索結果はわからない? 2 2022/03/30 14:07
- その他(バイク) 新車って登録されたことが無い車両ですか? 走行距離0でも登録を一度でもされたらそれは新車ではなく、た 7 2023/05/29 09:10
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
教えて下さい
-
【エクセル】測定時間がバラバ...
-
Accessで該当データにフラグを...
-
配列でデータが入っている要素...
-
ActiveReportについて
-
エクセルで2つの時系列のデー...
-
ユーザーフォームのテキストボ...
-
VBA 該当データがない時 ...
-
多量のSUMIF式を軽くしたい
-
Excelのマクロでワードのテキス...
-
子ダイアログのデータを親ダイ...
-
Fortran カンマを含む数値デー...
-
パースとはなんですか?
-
Excelで、標準偏差の関数
-
S9タイプからXタイプにデータ...
-
VBA 空白セルを削除ではない方...
-
CString型の文字列連結について
-
EXCEL VBA FREQUENCY関数での...
-
阿武町4630万円誤送金事件。町...
-
COBOL数値転記をCOPY句内での仕様
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
教えて下さい
-
配列でデータが入っている要素...
-
【エクセル】測定時間がバラバ...
-
メモ帳(テキストデータ)をExc...
-
VBA 空白セルを削除ではない方...
-
多量のSUMIF式を軽くしたい
-
Excelのマクロでワードのテキス...
-
エクセルで2つの時系列のデー...
-
この行は既に別のテーブルに属...
-
VBAを使ってOutlookメール本文...
-
シーケンサにパソコンからアク...
-
EXCELVBAでSQLserverからデータ...
-
ブレーカー落ちで壊れたりしな...
-
[C言語] コメント文字列を無視...
-
オープンチヤットでデータ削除...
-
モジュラス103の算出方法について
-
javaでDBからデータを取ってき...
-
カンマからスラッシュに
-
VBA 毎日取得するデータを順番...
-
Android携帯をUSBメモリ代わりに
おすすめ情報