Отображение числовых диапазонов на отдельные элементы с доступом O (1) - PullRequest
Новая
       28

Отображение числовых диапазонов на отдельные элементы с доступом O (1)

1 голос
/ 15 декабря 2011

Вопрос прост, я хочу отобразить каждое число от 0 до N-1 на количество элементов K

Примечание: i, j, k, ..., z - разные значения (иначе я бы не использовал разные буквы :)).

Есть ли способ иметь структуру и функцию f (i), возвращающие соответствующий элемент за время O (1), занимающие разумное количество пространства? (Вектор из N элементов с каждым элементом из диапазона, указывающего на элемент, на который он влияет, НЕ является разумным количеством места)

Я могу подумать о деревьях B, которые дадут мне время доступа O (log (n)), но мне интересно, есть ли эффективное решение O (1).

Заранее спасибо!

Bruno

Ответы [ 2 ]

2 голосов
/ 15 декабря 2011

Если ваши i, k, ..., z произвольные, то не приходит в голову алгоритм с временным ограничением O (1) и разумным пространственным ограничением раскладная функция(i)! = функция складывания (i + 1).

Если к некоторым картам часто обращаются только некоторые элементы, вы также можете создать кэш для отображения, что приведет к O (1) в кеше.-hit case и O (lookup-function) для отсутствия кеша.Конечно, поиск в кэше повлияет на время, затрачиваемое на каждый элемент, даже в случае отсутствия кэша, но это не повлияет на сложность O вашего алгоритма.

Edit

В основном то, что вы хотите реализовать, может быть выражено в виде оператора Pascal case с наборами в качестве меток: 

case n of 
0..i-1:
  value:=0;
i..i+k-1:
  value:=1;
// ...
i+k+...+z+2..N-1:
  value:=K;
end

Для этой проблемы поиск в Google действительно оказывается интересным документом:

В этой статье описывается новая схема построения статических поисковых деревьев с использованием многоствольных поисковых деревьев.[...] Мы показываем, что для разреженных наборов случаев метод производит в среднем более быстрый код, чем существующие методы, требуя O (1) времени с небольшой константой для среднего поиска.

Эрлингссон, Кришнамурти, Раман : Ясный и эффективный анализ случаев

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

Для общей проблемы создания эффективного кода для описаний падежа у Чжао и Амарлы есть интересная статья который использует профилирование для достижения чего-то похожего на использование кеша.Их статья также интересна для соответствующего рабочего раздела, который ссылается на статью от Kannan и Proebsting ( Исправление к созданию хорошего кода для оператора case. ), которая требует O (n^ 2) время установки для кластеризации.Однако у меня нет доступа к этой статье, и похоже, что это приведет только к чрезвычайно оптимизированному дереву поиска, что приведет к времени выполнения O (log (n)).

0 голосов
/ 15 декабря 2011

Если я правильно понимаю вопрос, вы сможете вычислить отображение напрямую, используя div mod. (См. объяснение операторов в C )

Например, в Python 

def my_map(n,k,i):
  elements_per_bin = n/k if n%k is 0 else n/k + 1  #in case n is exactly divisible by k
  return i/elements_per_bin

В качестве примера, пусть n = 10, k = 3 

>>> n=10
>>> k=3
>>> def f(i):
      return my_map(n,k,i)
>>> range(n)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> map(f,range(n))
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2]

Итак, {0,1,2,3} -> 0, {4,5,6,7} -> 1 и т. Д.

Я предполагаю, что у вас уже есть данные из исходного массива / структуры данных где-то в памяти. Теперь вы должны иметь возможность индексировать его, вычисляя индекс массива из сопоставления (может потребоваться построить обратную функцию my_map).

Вычисление индекса - O (1), и вы используете только пространство из исходного массива.

Извините, если я неправильно понял отображение.

...