インターネットで次のインタビューの質問に遭遇しました。
getValue(int インデックス)、setValue(int インデックス、int 値)、setAllValues(int 値) がすべて O(1) であるデータ構造を記述してください。
1 番目と 2 番目の操作を O(1) で実行するには配列で十分ですが、3 番目の操作 (setAllValues) には何が提案できますか?
29002 次
18 に答える
67
と呼ばれる追加arrayのタプルの はどうですか。挿入の相対時間のみを気にするので、タイムスタンプの値に単調増加を使用できます。{timestamp, value}{timestamp, value}allid
type Entry {
int timestamp,
int value
}
type structure {
int id
Entry all
Entry[] array
}
すべてのフィールドを 0 に初期化します。その後、次のように動作するはずです。
setValue(インデックス i、値 v):
array[i] = {id++, value}値 getValue(インデックス i)
if(all.timestamp > array[i].timestamp) return all.value else return array[i].valuesetAll(値 v)
all = {id++, value}
このアプローチの問題は、最終的にタイムスタンプの ID が不足し、ラップアラウンドする可能性があることです。タイムスタンプを格納するために 64 ビット値を選択した場合、これが発生する前に 18,446,744,073,709,551,616 回の挿入または setAlls が得られます。データ構造の予想される用途に応じて、O(n) クリーンアップ フェーズが適切な場合もあれば、単に例外をスローする場合もあります。
考慮する必要があるかもしれないもう 1 つの問題は、マルチスレッドです。3 つの明らかな問題:
id++アトミックではなく、2 つのスレッドが同時に new を取得しidた場合、同じ ID を持つ 2 つのエントリを取得できます。- id の増分と作成されたタプルの割り当てが一緒に原子的ではなく (おそらくそうではない)、2 つの同時挿入があった場合、古い ID が勝つという競合状態が発生する可能性があります。
- タプルの代入がアトミックではなく
insert()、同時にが存在する場合、配列内でget()発言権を持っている位置になって{new_id, old_value}しまい、間違った値が返される可能性があります。
これらのいずれかが問題である場合、これに対する最も簡単な解決策は、ドキュメントに「スレッドセーフではない」と記載することです (不正行為)。または、選択した言語でメソッドをアトミックに実装できない場合は、何らかの同期ロックを配置する必要があります。
于 2012-04-04T06:03:16.263 に答える
4
単一の共通値へのポインターの配列はどうですか？値を設定すると、すべての参照がO（1）で変更された単一の値を指します。
于 2012-04-04T06:06:02.583 に答える
2
既存の回答はすべて、setVal操作ごとに増分されるタイムスタンプを使用します。これは必要ありません。実際、必要なのは のタイムスタンプをインクリメントすることだけsetAllです。一部で提起されたもう 1 つの問題は、算術オーバーフローでした。これは、それぞれの単一のセルを更新し、setAll慎重に時間比較を実行することで、一定の時間範囲を破ることなく処理できます。
使い方
基本的な概念は本質的に他の回答の概念と似ていますが、ひねりがあります。
機能: 最後のsetAll操作に使用された値を個別に保存し、操作が実行された時間を追跡します。を実行するたびsetValに、指定された値とともに現在の時刻が配列に格納されます。を実行するgetValたびに、指定された場所の時刻と最後にsetAll発生した時刻を比較し、その場所の値またはsetAll大きい方に応じて値を選択します。
これが問題になる理由: 現在の時刻がオーバーフローし、setAllその後すぐに操作が発生したとします。setAll格納された配列値のほとんどは、実際には古い値よりも新しいように見えます。
解決策: データ構造の初期化から経過した合計時間を追跡していると想像するのはやめましょう。円の周りを 60 回ではなく、円の周りを 2^n 回刻む「秒針」を持つ巨大な時計を想像してみてください。秒針の位置は、最後にsetAll操作した時刻を表します。各setVal操作は、この時間を値とともに保存します。したがってsetAll、「クロック」が 45 のときに a を実行し、次にsetVal異なる要素に対して 6 つの操作を実行すると、setAll時間と 6 つの場所すべての時間は同じになります。次の不変条件を維持したいと考えています。
特定の要素位置の時間は、その要素が最後の操作よりも最近
setAllに設定された場合にのみ、時間と等しくなります。setValsetAll
明らかに、上記の手順により、要素が最近設定された場合、その時間が同じ時間になることが自動的に保証されますsetAll。課題は、逆の含意も保持することです。
つづく ....
コード
Haskell は私が最もよく知っている言語なので、これを書きましたが、この仕事にとって最も自然な言語とは言えません。
{-# LANGUAGE BangPatterns #-}
module RepArr where
import Control.Monad.Primitive
import Data.Primitive.MutVar
import qualified Data.Vector.Mutable as V
import Data.Vector.Mutable (MVector)
import Control.Applicative
import Prelude hiding (replicate)
import Control.Monad.ST
import Data.Word
-- The Int in the MutVar is the refresh pointer
data RepArr s a = RepArr (MutVar s (Word, a, Int)) (MVector s (Word,a))
-- Create a fancy array of a given length, initially filled with a given value
replicate :: (PrimMonad m, Applicative m) => Int -> a -> m (RepArr (PrimState m) a)
replicate n a = RepArr <$> newMutVar (0,a,0) <*> V.replicate n (0,a)
getVal :: PrimMonad m => RepArr (PrimState m) a -> Int -> m a
getVal (RepArr allv vec) n = do
(vectime, vecval) <- V.read vec n
(alltime, allval, _) <- readMutVar allv
if (fromIntegral (alltime - vectime) :: Int) > 0
then return allval
else return vecval
setVal :: PrimMonad m => RepArr (PrimState m) a -> Int -> a -> m ()
setVal (RepArr allv vec) i v = do
(!alltime, _, _) <- readMutVar allv
V.write vec i (alltime, v)
setAll :: PrimMonad m => RepArr (PrimState m) a -> a -> m ()
setAll r@(RepArr allv vec) v = do
(oldt, _, oldc) <- readMutVar allv
getVal r oldc >>= setVal r oldc
let !newc = case oldc+1 of
op1 | op1 == V.length vec -> 0
| otherwise -> op1
let !newt = oldt+1
writeMutVar allv (newt, v, newc)
潜在的な (まれな) ガベージ コレクションの一時停止を回避するには、実際にはIntとのWord値をボックス化解除し、ポリモーフィック ベクトルの代わりにボックス化解除されたベクトルを使用する必要がありますが、私はあまり気分が悪く、これはかなり機械的な作業です。
これはCのバージョンです（完全にテストされていません）：
#include <malloc.h>
struct Pair {
unsigned long time;
void* val;
};
struct RepArr {
unsigned long allT;
void* allV;
long count;
long length;
struct Pair vec[];
};
struct RepArr *replicate (long n, void* val) {
struct RepArr *q = malloc (sizeof (struct RepArr)+n*sizeof (struct Pair));
q->allT = 1;
q->allV = val;
q->count = 0;
q->length = n;
int i;
for (i=0; i<n; i++) {
struct Pair foo = {0,val};
q->vec[i] = foo;
}
return q;
}
void* getVal (struct RepArr *q, long i) {
if ((long)(q->vec[i].time - q->allT) < 0)
return q->allV;
else
return q->vec[i].val;
}
void setVal (struct RepArr *q, long i, void* val) {
q->vec[i].time = q->allT;
q->vec[i].val = val;
}
void setAll (struct RepArr *q, void* val) {
setVal (q, q->count, getVal (q, q->count));
q->allV = val;
q->allT++;
q->count++;
if (q->count == q->length)
q->count = 0;
}
于 2015-03-06T01:43:04.420 に答える
2
int を格納する変数 V と、それを含む Tuple の配列を {Value, id} として持つことができます。
そして、グローバル int 変数 G (これは SQL の ID のように機能し、set または setAll 操作が行われるたびに値が 1 ずつ増加します)
初期のすべての Id と V 値はデフォルトで null と言います。
so V = null All Tuple = {null, null}
set(index i, val v) -> G = G+1, arr[i].Val = v, arr[i].Id = G
get(index i) -> if V.Id > arr[i].Id return V.Val else return arr[i]
set-all(val v) -> G= G+1, V.Id= G, V.Val = v
于 2014-08-23T08:11:54.630 に答える
0
ティモシー・ジョーンズの答えについて：
このアプローチの問題は、最終的にタイムスタンプの ID が不足し、ラップアラウンドする可能性があることです。タイムスタンプを格納するために 64 ビット値を選択した場合、これが発生する前に 18,446,744,073,709,551,616 回の挿入または setAlls が得られます。データ構造の予想される用途に応じて、O(n) クリーンアップ フェーズが適切な場合もあれば、単に例外をスローする場合もあります。
これはまさに、このソリューションを O(1) ではなく O(n) にする最悪のシナリオです。この構造は、潜在的な O(n) 挿入操作を大幅に節約しますが、依然として O(n) 効率です。
于 2015-03-05T13:01:16.337 に答える
0
この問題に対するC#での私の実装:
public class MyStruct
{
public MyStruct(int val)
{
this.value = val;
this.currentTime = 0;
}
public int value { get; set; }
public int currentTime { get; set; }
}
public class Struct
{
public List<MyStruct> array = new List<MyStruct>();
public MyStruct all = new MyStruct(0);
public int GetValue(int index)
{
if(all.currentTime >= array[index].currentTime)
{
return all.value;
}
else
{
return array[index].value;
}
}
public void Set(int index, int value)
{
if(array.Count <= index)
{
array.Add(new MyStruct(value));
}
else
{
array[index].value = value;
}
array[index].currentTime = all.currentTime +1;
}
public void SetAll(int value)
{
all.value = value;
all.currentTime++;
}
public void Delete(int index)
{
array[index].currentTime = 0;
array[index].value = -1;
}
}
チェン・ルガシ
于 2020-10-21T12:17:01.973 に答える
0
まあ、私はイベントに基づいてそれをしました。見てみな。
internal class Program
{
public static void Main(string[] args)
{
SomeUsefullDataStructure ds = new SomeUsefullDataStructure();
ds.SetValue(1, "11");
ds.SetValue(2, "22");
var result = ds.GetValue(2);
ds.SetAllValues("haha");
Console.ReadKey();
}
}
public class SomeUsefullDataStructure
{
private delegate void SetValueDelegate(string newValue);
private event SetValueDelegate SetValueEventFired;
private Dictionary<int, StringDataEntry> dict = new Dictionary<int, StringDataEntry>();
public string GetValue(int key)
{
if (dict.ContainsKey(key))
{
return dict[key].StringValue;
}
throw new ArgumentException("no such key");
}
public void SetValue(int key, string value)
{
if (dict.ContainsKey(key))
{
dict[key].UpdateValue(value);
}
else
{
StringDataEntry stringDataEntry = new StringDataEntry(value);
SetValueEventFired += stringDataEntry.UpdateValue;
dict.Add(key, stringDataEntry);
}
}
public void SetAllValues(string value)
{
SetValueEventFired(value);
}
}
public class StringDataEntry
{
public string StringValue { get; private set; }
public StringDataEntry(string value)
{
StringValue = value;
}
public void UpdateValue(string newValue)
{
StringValue = newValue;
}
}
于 2020-11-12T13:38:33.873 に答える