структура данных для хранения кусочной функции - PullRequest
Новая
       8

структура данных для хранения кусочной функции

0 голосов
/ 16 ноября 2018

Я хочу реализовать функцию, которая: 

f(x) = a0   -inf < x < b0
       a1    b0 <= x < b1
       a2    b1 <= x < b2
       ...
       an    bn-1 <= x < bn
       an+1  bn <= x < +inf

Вместо простой реализации if-else. 

def func(x):
    if x<b0: return a0
    elif x<b1: return a1
    .....

У меня есть лучшая структура данных, чтобы организовать это?

Кроме того, как я могу написать «мета-функцию», которая возвращает оптимизированный «func (x)» с учетом двух последовательностей {an}, {bn}.

Ответы [ 2 ]

0 голосов
/ 17 ноября 2018

Вы могли бы просто хранить массивы a и b.Затем, чтобы найти значение, вы можете выполнить двоичный поиск в массиве b, чтобы найти индекс значения, возвращаемого в массиве a.

Это на самом деле работает довольно хорошо, но я пришелболее быстрый способ сделать это, что я считаю довольно круто, когда мне пришлось реализовать конечный автомат для этого пакета лексического анализа (https://github.com/mtimmerm/dfalex).

Представление вашей функции было бы двоичным деревом, хранимым последовательнов массиве, как мы обычно делаем для куч: https://www.geeksforgeeks.org/array-representation-of-binary-heap/

Корень дерева находится в array[0], левый потомок любого array[i] находится в array[2i+1], а правый потомок вarray[i] находится на array[2i+2]. Все листья дерева представляют собой a (результат) значения в порядке, а внутренний узел между каждой парой смежных a значений - это b (аргумент) значение вкоторый вы переключаетесь от одного к другому.

Порядок дерева кучи в массиве гарантирует, что все значения a будут находиться в конце непрерывно.

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

def lookup(x, array, num_internal_nodes)
    i=0
    while (i < num_internal_nodes):
        i = i*2 + (1 if x<array[i] else 2)
    return array[i]

Извинения, если я ошибся с синтаксисом python - это не тот язык, который я хорошо знаю.

Если вам нужно создать функцию, которая просто принимает входное значение, вы можете построить представление массива и вызвать функцию, которая делает замыкание следующим образом: 

def makeF(array, num_internal_nodes):
    def f(x):
        return lookup(x, array, num_internal_nodes)
    return f

Чтобы построить представление массиваПрежде всего, из вашей функции просто создайте массив соответствующего размера (num_internal_nodes*2+1), а затем выполните предварительный обход дерева, заполнив поля a (лист) и b (внутренний).значения в порядке.

0 голосов
/ 16 ноября 2018

Если n большое, вы хотите уменьшить количество if операторов. В Python это можно сделать, сохранив ваши данные в словаре: 

fx = {b0: a0, b1: a1, b2: a2, ..., bn: an, math.inf: an+1}

Для заданного значения x выполните двоичный поиск по ключевым значениям словаря. Это дает вам соответствующий ключ для использования, а затем используйте сам словарь, чтобы получить соответствующее значение. Если ваш язык не позволяет использовать inf в качестве ключа, вы можете хранить значение an+1 отдельно от словаря, возможно, сохраняя оба в двух кортеже.

Это уменьшает максимальное количество тестов с n до log2(n).

«Мета-функция» проста в Python, так как функции являются первоклассными объектами в Python. Вы не указываете предпочитаемый язык: дайте мне знать, если вам нужен пример «мета-функции» в Python.

...