各要素を読み取らずにデータセットからデータを検索

Question

アルゴリズムとデータ構造の学習を始めたばかりで、興味深い問題が発生しました。
私はこの問題を解決するためにいくつかの助けが必要です。

私に与えられたデータセットがあります。データセット内には、文字とそのそれぞれに関連付けられた番号があります。私は現在の文字のそれぞれに関連する最大の数字の合計を評価しなければならない。リストは文字でソートされませんが、各文字のグループは、データセット内のその文字のインスタンスがなくなって繰り返されます。
さらに、データセット内の各文字に関連付けられた最大数は、データセット内のその文字の参照の最大位置に常に表示されます。データセット全体の長さを知り、そのデータセットに関連付けられた行番号を指定してデータを取得することができます。
たとえば、

C-7 
C-9 
C-12 
D-1 
D-8 
A-3 
M-67 
M-78 
M-90 
M-91 
M-92 
K-4 
K-7 
K-10 
L-13 
length=15 
get(3)= D-1(stores in class with character D and value 1) 

彼らはそれぞれL,K,M,A,D,Cに関連付けられている最高の数値であるとして、上記のための答えは13+10+92+3+8+12でなければなりません。
最も簡単な解決策はもちろん、すべての要素を調べることですが、最も効率的なアルゴリズム（データセットの長さよりも短いデータセットを読み取ること）は何ですか？

Answer 1

キーが何であるかは特定できないため、それぞれを1つずつ確認する必要があります。

簡単な操作のために、私はデータセットをループし、インデックスiのキーがi+1のインデックスと等しいかどうかを確認します。そうでなければ、ローカル最大値を持っています。

次に、そのキーの既存のキー：値のペアがない場合はその値をハッシュまたはディクショナリに格納します。存在する場合は、既存の値が現在の値よりも小さいかどうかを確認して上書きしますそれが本当なら。

Answer 2

統計を使って楽観的にいくつかの項目をスキップすることができますが、A 1を読んだとすると、A 10 - 良いと読んだ5つの項目をスキップします。あなたはさらに5つ、B 3をスキップするので、戻って何が入っているのかを読む必要があります。

実際には動作しません。テキストではありません。

IOはブロック単位で発生するためです。データは通常約8kのチャンクに格納されます。つまり、最小の読み込みサイズです（プログラミング言語が他のサイズの読み込みを提供する場合でも、最終的に読み込みブロックに変換されてバッファリングされます）。

どうすれば次の行を見つけることができますか？まあ、\nが見つかるまで読む...

この種のデータには何も保存しない。より大きなレコード（数KB、ファイルのような）とインデックスがあれば、それは違うでしょう。しかし、その指数を構築するには、少なくとも1回はすべて読む必要があります。

このように、最も速いアプローチは、データ全体を一度直線的にスキャンすることです。