Опрос: структура данных для установки всех значений в O (1)

Ответ 1

Как насчет array кортежей {timestamp, value}, с дополнительным {timestamp, value}, называемым all. Поскольку вам нужно только относительное время вложений, вы можете использовать монотонно увеличивающийся id для значений метки времени:

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].value
  

• setAll (значение v)

  all = {id++, value}
  

Проблема с этим подходом заключается в том, что в конечном итоге у вас не будет идентификаторов для timestamp и они могут обернуться. Если вы выбрали 64-битное значение для хранения временных меток, это даст вам 18 446 744 073 709 551 616 вставок или setAlls, прежде чем это произойдет. В зависимости от ожидаемого использования структуры данных может быть подходящей фаза очистки O (n), или вы можете просто исключить исключение.

Другая проблема, которая может потребоваться рассмотреть, - многопоточность. Три очевидные проблемы:

• Если id++ не является атомарным, а два потока получили новый id в то же время, тогда вы могли бы получить две записи с одним и тем же идентификатором.
• если инкремент id и присвоение созданного кортежа не являются атомарными (они, вероятно, нет), и были две одновременные вставки, тогда вы могли бы получить условие гонки, в котором побеждает более старый идентификатор.
• если присвоение кортежа не является атомарным, а там insert() одновременно с get(), то вы можете оказаться в позиции, в которой вы сказали {new_id, old_value} в массиве, в результате чего возвращается неправильное значение.

Если какая-либо из этих проблем является проблемой, самым простым решением для этого является "небезопасный поток" в документации (обман). В качестве альтернативы, если вы не можете реализовать методы атомарно на выбранном вами языке, вам нужно будет установить вокруг них какие-то блокировки синхронизации.

Ответ 2

Как насчет массива указателей на одно общее значение? Задайте значение, и все ссылки укажут на одно измененное значение в O (1)..

Ответ 3

Мне просто задали этот вопрос совсем недавно в интервью. Я придумал реализацию хеш-таблицы. Это решило бы проблему исчерпания значений метки времени, но функция безопасности потока должна быть реализована (возможно, используя ленивые методы инициализации)

Скажем, в нашем классе мы имеем приватную переменную _defaultValue, чтобы сохранить значение по умолчанию, и у нас также есть личная хэш-таблица или словарь _hashtable. SetAllValues ​​ может просто установить _defaultValue, равное переданному значению, и _hashtable инициализировать/установить на новую хеш-таблицу и отменить любую ссылку на старую хеш-таблицу. SetValue должен просто добавить новое значение в _hashtable или обновить значение, если ключ (или индекс) уже присутствует в _hashtable. GetValue должен проверить, присутствует ли ключ (или индекс) в _hashtable, а затем вернуть его, иначе верните значение, сохраненное в _defaultValue.

Это мой первый ответ на StackOverflow. Я немного ленив в написании кода. Вероятно, скоро отредактируйте ответ.

Интервьюер кивнул в ответ на это решение, но настаивал на его реализации, не используя хэш-таблицу. Полагаю, он просил меня дать подобный подход, как ответ Тимоти. И я не смог получить его в тот момент: (Anyways, Cheers!

EDIT: Проводка кода (на С#)

class MyDataStruct
{
    private int _defaultValue;
    private Dictionary<int,int> _hashtable;

    public MyDataStruct()
    {
        _defaultValue = 0; // initialize default with some value
        _hashtable = new Dictionary<int, int>();
    }

    public void SetAllValues(int val)
    {
        _defaultValue = val;
        _hashtable = new Dictionary<int, int>();
    }

    public void SetValue(int index, int val)
    {
        if (_hashtable.ContainsKey(index))
        {
            _hashtable.Add(index, val);
        }
        else
        {
            _hashtable[index] = val;
        }
    }

    public int GetValue(int index)
    {
        if (_hashtable.ContainsKey(index))
        {
            return _hashtable[index];
        }
        else
        {
            return _defaultValue;
        }
    }
}

Ответ 4

Мы можем иметь переменную V, которая хранит int и массив содержащего Tuple как {Value, id}..

И глобальная переменная int G (которая будет действовать как идентификатор в SQL и всякий раз, когда выполняется любая операция set или setAll, ее значение получает инкремент на 1)

начальное значение всех идентификаторов и значений 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

Ответ 5

Я получил тот же вопрос в одном из технических интервью.
Вот моя полная готовая к использованию Java-реализация, включая тестовые примеры.

Основная идея состоит в том, чтобы сохранить значение setAll() в специальной переменной (например, joker), а затем правильно отслеживать изменение этого значения.

Чтобы код оставался чистым, некоторые модификаторы доступа были отменены.

Node класс:

class Node {

    int value;
    Integer joker;

    Node(int val, Integer jok) {
        value = val;
        joker = jok;
    }
}

DS класс:

class DS {

    Node[] arr;

    DS(int len) {
        arr = new Node[len];
    }
}

Класс DataStructure:

class DataStructure {

    private boolean isJokerChanged;
    private Integer joker;
    private DS myDS;

    DataStructure(int len) {
        myDS = new DS(len);
    }

    Integer get(int i) {

        Integer result = null;

        if (myDS.arr.length < i) {
            return null;
        }

        // setAll() has been just called
        if (isJokerChanged) {
            return joker;
        }

        if (myDS.arr[i] == null) {

            // setAll() has been previously called
            if (joker != null) {
                result = joker;
            } else {
                result = null;

            }

        } else if (myDS.arr[i].joker == joker) {
            // cell value has been overridden after setAll() call
            result = myDS.arr[i].value;
        } else {
            result = joker;
        }

        return result;
    }

    void setAll(int val) {
        isJokerChanged = true;
        joker = val;
    }

    void set(int i, int val) {
        isJokerChanged = false;
        myDS.arr[i] = new Node(val, joker);
    }
}

Основной класс:

class Main {

    public static void main(String[] args) {

        DataStructure ds = new DataStructure(100);

        Integer res;

        res = ds.get(3);

        ds.set(3, 10);

        res = ds.get(3);

        ds.setAll(6);

        res = ds.get(3);

        res = ds.get(15);

        ds.set(4, 7);

        res = ds.get(4);

        res = ds.get(3);

        ds.setAll(45);

        ds.set(8, 2);

        res = ds.get(3);
    }
}

Ответ 6

Все существующие ответы используют временную метку, которая увеличивается при каждой операции setVal. Это необязательно. Фактически, нужно только увеличить метку времени на setAll. Еще одна проблема, поднятая выше, была арифметическим переполнением. Это можно обрабатывать, не нарушая постоянные временные рамки, обновляя одну ячейку на каждом setAll и тщательно выполняя сравнение времени.

Как это работает

Основная концепция по существу похожа на концепцию других ответов, но с твистом.

Что они делают: сохраняйте значение, используемое для последней операции setAll, отдельно и отслеживайте время выполнения этой операции. Каждый раз, когда они выполняют setVal, они сохраняют текущее время вместе с заданным значением в массиве. Каждый раз, когда они выполняют a getVal, они сравнивают время в данном местоположении со временем последнего setAll, а затем выбирают либо значение в местоположении, либо значение setAll, в зависимости от того, что больше.

Почему это может быть проблемой: предположим, что текущее переполнение времени и операция setAll происходит вскоре после этого. Похоже, что большинство сохраненных значений массива новее, чем значение setAll, когда они на самом деле старше.

Решение: перестаньте воображать, что мы отслеживаем общее количество времени, прошедшее с момента инициализации структуры данных. Представьте себе гигантские часы со "секундной стрелкой", которые тикают не 60 раз по кругу, а примерно 2 ^ n раз по кругу. Позиция секундной стрелки представляет собой время последней операции setAll. Каждая операция setVal хранит это время вместе со значением. Поэтому, если мы выполняем setAll, когда "часы" равны 45, а затем выполняют шесть операций setVal для разных элементов, время setAll и время во всех шести местах будут одинаковыми. Мы хотим сохранить следующий инвариант:

Время в заданном расположении элемента равно времени setAll тогда и только тогда, когда этот элемент был установлен с setVal в последнее время, чем последняя операция setAll.

Очевидно, что описанная выше процедура автоматически гарантирует, что если элемент был установлен недавно, то его время будет равно времени 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 [email protected](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;
}

Ответ 7

/*

В то время, когда я пишу это, все решения на этой странице будут удвоены (или more) объем пространства, необходимый для хранения массива. Следующее решение уменьшает количество потерянного пространства от Ω (n) до θ (n/w), где w - количество бит в "слово" компьютера. На моей машине это 64.

Эта проза в этом ответе написана в комментариях C, поэтому вы можете копировать и вставлять эту ответьте verbatim и скомпилируйте его с вашим компилятором C.

*/

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

/*

Проблема заключается в поддержке чтения и записи значений в массиве в O (1) времени наряду с объемной записью, в которой все значения в массиве записываются сразу в O (1). Это возможно с использованием техники, изобретенной Ахо, Хопкрофт и Насколько я знаю, Ульман. Я представлю версию из-за Гонсало Наварро, "Инициализация массива с постоянным временем в маленьком Space ".

Идея состоит в том, чтобы сохранить три массива метаданных вместе с массивом данных. Мы также сохраните два целых числа: unset, что является последним значением, используемым в объемной записи и size, приближение для числа значений, которые были начиная с последней объемной записи. Во все времена количество различных значений записанная с момента последней объемной записи между size и w * size.

Три массива метаданных описывают информацию о блоках значений w в массив данных. Это:

• nth: nth [i] является i-м уникальным блоком, который должен быть записан до последней написать

• inverse_nth: inverse_nth [i] - порядок, в котором i-й блок массив был записан, считая от 0 при последней объемной записи.

• bitset: j-й бит bitset[i] равен 1, когда ячейка массива пронумерована 64 * я + j записано с момента последней навальной записи.

bitset[i] и inverse_nth[i] разрешены как недопустимые, если i не является член множества {nth[0], nth[1],..., nth[size-1]}. Другими словами, inverse_nth[i] и bitset[i] действительны тогда и только тогда, когда inverse_nth[i] < size и nth[inverse_nth[i]] == i.

Вместо того, чтобы хранить три отдельных массива одинаковой длины, я решил сохранить один array, is_set, с тремя полями.

*/

typedef struct {
  int nth_;
  int inverse_nth_;
  uint64_t bitset_;
} IsSetCell;

typedef struct {
  int unset_;
  int size_;
  IsSetCell is_set_[];
} IsSetArray;

typedef struct {
  IsSetArray * metadata_;
  int payload_[];
} ResettableArray;

/*

Чтобы построить массив, нам нужно значение по умолчанию для возврата, когда чтение значение, которое никогда не было написано.

*/

ResettableArray * ConstructResettableArray(int n, int unset) {
  ResettableArray* result =
      malloc(offsetof(ResettableArray, payload_) + n * sizeof(int));
  if (!result) return NULL;
  n = (n + 63) / 64;
  result->metadata_ =
      malloc(offsetof(IsSetArray, is_set_) + n * sizeof(IsSetCell));
  if (!result->metadata_) {
    free(result);
    return NULL;
  }
  result->metadata_->size_ = 0;
  result->metadata_->unset_ = unset;
  return result;
}

void DestructResettableArray(ResettableArray * a) {
  if (a) free(a->metadata_);
  free(a);
}

/*

Основная часть алгоритма написана и читается метаданные. После IsSet() и Set() определены (ниже), чтение и запись массивов прямой.

*/

bool IsSet(const IsSetArray * a, int i);
void Set(IsSetArray * a, int i);

int GetValue(const ResettableArray * a, int i) {
  if (!IsSet(a->metadata_, i)) return a->metadata_->unset_;
  return a->payload_[i];
}

void SetValue(ResettableArray * a, int i, int v) {
  a->payload_[i] = v;
  Set(a->metadata_, i);
}

void SetAllValues(ResettableArray * a, int v) {
  a->metadata_->unset_ = v;
}

/*

Сложной частью чтения и письма является двунаправленная связь между inverse_nth и nth. Если они указывают друг на друга в точке i (is_set[is_set[i].inverse_nth].nth == i), тогда местоположение я содержит достоверные данные которое было написано после последней объемной записи, пока is_set[i].inverse_nth < size.

*/

uint64_t OneBit(int i) {
  return UINT64_C(1) << i;
}

bool IsSet(const IsSetArray * a, int i) {
  const int cell = i/64, offset = i & 63;
  const int inverse_nth = a->is_set_[cell].inverse_nth_;
  return inverse_nth < a->size_ && a->is_set_[inverse_nth].nth_ == cell &&
         a->is_set_[cell].bitset_ & OneBit(offset);
}

void Set(IsSetArray * a, int i) {
  const int cell = i/64, offset = i & 63;
  const int inverse_nth = a->is_set_[cell].inverse_nth_;
  if (inverse_nth >= a->size_ || a->is_set_[inverse_nth].nth_ != cell) {
    a->is_set_[cell].inverse_nth_ = a->size_;
    a->is_set_[cell].bitset_ = 0;
    a->is_set_[a->size_].nth_ = cell;
    ++a->size_;
  }
  a->is_set_[cell].bitset_ |= OneBit(offset);
}

Ответ 8

Пример Python

class d:
    def __init__(self, l):
        self.len = l
        self.g_p = [i for i in range(self.len)]
        self.g_v = [0 for i in range(self.len)]
        self.g_s = self.len - 1
        self.g_c = 0  

    def getVal(self, i):
        if (i < 0 or i >= self.len):
            return

        if (self.g_p[i] <= self.g_s):
            return self.g_v[self.g_p[i]]

        return self.g_c

    def setVal(self, i, v):
        if (i < 0 or i >= self.len):
            return

        if (self.g_p[i] > self.g_s):
            self.g_s += 1

            self.g_p[self.g_s], self.g_p[i] = self.g_p[i], self.g_p[self.g_s]

        self.g_v[self.g_p[i]] = v

    def setAll(self, v):
        self.g_c = v
        self.g_s = -1

Ответ 9

Относительно ответа Тимоти Джонса:

Проблема с этим подходом заключается в том, что в конечном итоге у вас не будет идентификаторов для timestamp и они могут обернуться. Если вы выбрали 64-битное значение для хранения временных меток, это даст вам 18 446 744 073 709 551 616 вставок или setAlls, прежде чем это произойдет. В зависимости от ожидаемого использования структуры данных может быть подходящей фаза очистки O (n), или вы можете просто исключить исключение.

Это самый худший сценарий, который делает это решение O (n) тоже, а не O (1). Эта структура, хотя и сохраняет большую потенциальную операцию ввода O (n), все еще находится в O (n) эффективности.

Ответ 10

Правильное решение в С#:

public sealed class SpecialDictionary<T, V>
{
    private Dictionary<T, Tuple<DateTime, V>> innerData;
    private Tuple<DateTime, V> setAllValue;
    private DateTime prevTime;

    public SpecialDictionary()
    {
        innerData = new Dictionary<T, Tuple<DateTime, V>>();
    }
    public void Set(T key, V value) => innerData[key] = new Tuple<DateTime, V>(GetTime(), value);
    public void SetAll(V value) => setAllValue = new Tuple<DateTime, V>(GetTime(), value);
    public V Get(T key)
    {
        Tuple<DateTime, V> tmpValue = innerData[key];
        if (setAllValue?.Item1 > tmpValue.Item1)
        {
            return setAllValue.Item2;
        }
        else
        {
            return tmpValue.Item2;
        }
    }
    private DateTime GetTime()
    {
        if (prevTime == null)
        {
            prevTime = DateTime.Now;

        }
        else
        {
            if (prevTime == DateTime.Now)
            {
                Thread.Sleep(1);
            }
            prevTime = DateTime.Now;
        }
        return prevTime;
    }
}

И тест:

static void Main(string[] args)
{
    SpecialDictionary<string, int> dict = new SpecialDictionary<string, int>();
    dict.Set("testA", 1);
    dict.Set("testB", 2);
    dict.Set("testC", 3);
    Console.WriteLine(dict.Get("testC"));
    dict.SetAll(4);
    dict.Set("testE", 5);
    Console.WriteLine(dict.Get("testC"));
    Console.WriteLine(dict.Get("testE"));
    Console.ReadKey();
}