Создание огромной таблицы поиска, проблемы с производительностью

Я хотел бы создать таблицу поиска, и для этого я думаю об использовании словаря. В словаре будут ключи, соответствующие целому числу (или, в моем случае, перечисляемому типу из класса Enum), а значениями будут 2, 3 или 4 пустых массива. Но мне как-то неохота использовать такой подход, так как в этом словаре огромное количество информации, и 99% ее может вообще не использоваться для каких-то задач. Таким образом, нет смысла создавать единый объект, содержащий всю информацию для поиска, и хотя я размышляю, я почти уверен, что есть лучший подход для выполнения того, что я хочу сделать.

Итак, исходя из мира C++, я бы создал unordered_map типов enum для указателей на функции, где в функции я бы создал массив static (чтобы он создавался только один раз), а затем возвращал бы указатель массива. Таким образом, я бы создал экземпляр только той части таблицы поиска, которая действительно необходима для программы, а не целиком.

Но я пытаюсь сделать что-то подобное в Python, поэтому я хотел бы знать, как это сделать наиболее эффективно.

ИЗМЕНИТЬ

Итак, вот что я придумал до сих пор. Я смешал предложения, сделанные @AaronDigulla и @DanielRoseman, хотя @runonce, возможно, больше не нужен. Подкласс dict переопределяет метод __getitem__ и проверяет, существует ли ключ в словаре. Если это не так, он вызывает функцию (используя eval() в объединенной строке из значений ключа словаря). Буду признателен за любые улучшения данного кода. Это выглядит довольно сложно, но работает, поэтому мне интересно, можно ли его еще больше упростить.

import collections, types
import numpy as np

Quadrature = collections.namedtuple("Quadrature", "wgt xi eta zeta")

category_map = { "t3" : "tri" #... more types
               }


class Integrator(dict):

  def __init__(self, *args, **kwargs):
    self.update(*args, **kwargs)

  def __getitem__(self, key):

    if not key in self:

      fn = '{}_{}gp'.format(category_map[key[0]], str(key[1]))
      super().__setitem__(key, eval(fn)())

    val = super().__getitem__(key)
    return val

  def __repr__(self):
    dictrepr = dict.__repr__(self)
    return '%s(%s)' % (type(self).__name__, dictrepr)

  def update(self, *args, **kwargs):
    print ('update', args, kwargs)
    for k, v in dict(*args, **kwargs).items():
        self[k] = v

def run_once(f):
  def wrapper(*args, **kwargs):
    if not wrapper.has_run:
      wrapper.has_run = True
      return f(*args, **kwargs)
  wrapper.has_run = False
  return wrapper


@run_once
def tri_3gp():
  xi   = np.array([2/3., 1/6., 1/6.])
  eta  = np.array([1/6., 1/6., 2/3.])
  wgt  = np.array([2/3., 2/3., 2/3.]);
  return Quadrature(wgt, xi, eta, None)

python-3.x python performance lookup-tables
person aaragon    schedule 05.09.2014    source источник
comment
Попробуйте pout-словари, они работают как хэш-карты и имеют хорошую производительность. Они на самом деле слишком медленные с вашим набором данных? (вы проверяли это?). Вы даже можете переопределить его, чтобы кэшировать некоторые результаты, если вам нужно всего несколько, и, таким образом, увеличить скорость поиска.   -  person Etse    schedule 05.09.2014
comment
Означает ли огромный, что он все еще помещается в память? И откуда берутся ваши ценности? Вы уже знакомы с memcache/momorise в качестве декораторов? например, посмотрите здесь: blog.isotoma.com/2009/09/   -  person Argeman    schedule 05.09.2014
comment
Этот вопрос, вероятно, будет полезен вам, а также эту реализацию в качестве декоратора функции.   -  person Carsten    schedule 05.09.2014
comment
@Argeman, это все равно поместилось бы в памяти, но это определенно было бы пустой тратой времени, так как большая часть этого не будет использоваться в окончательной программе.   -  person aaragon    schedule 05.09.2014
comment
Я бы сказал, что не использовать память - пустая трата времени. Так что, если вам не нужна память для чего-то другого, все должно быть в порядке.   -  person Etse    schedule 05.09.2014

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете сделать то же самое в Python. На самом деле это даже проще, так как функции сами по себе являются первоклассными объектами: вы можете хранить их в словаре и вызывать по мере необходимости.

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

global_dict = {}

def func1():
    if 'param1' not in global_dict:
        global_dict['param1'] = my_complicated_function_for_param_1()
    return global_dict['param1'] = my_complicated_function_for_param_1()



lookup_dict = {
    'param1': func1,
    ...
}

# now do the lookup:
my_result = lookup_dict[my_param]()

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

person Daniel Roseman    schedule 05.09.2014

arrow_upward
1
arrow_downward

Это довольно просто сделать в Python. См. этот вопрос, как создать декораторы «запустить один раз»: -loop">Эффективный способ выполнения функции только один раз в цикле

Теперь вы можете разместить функции для создания данных на карте. Декоратор позаботится о том, чтобы они запускались не более одного раза (в первый раз, когда вы их вызываете). Тогда цикл будет таким:

@run_once
def funcForKey():
    ...

lookup_dict = {
    'key': funcForKey,
    ...
}

result = lookup_dict[x]()

() после [] вызывает функцию.

Вы также можете попробовать класс:

class Data(object):
    @run_once
    def key(self):
        ...

data = Data()

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

a = 'key'
result = getattr(data, a)()

или, если имя постоянно во время выполнения, просто:

result = data.key()
person Aaron Digulla    schedule 05.09.2014
comment
Итак, вы подразумеваете, что я мог бы использовать этот тип декоратора для заполнения карты по требованию, верно? - person aaragon; 05.09.2014
comment
да. Декоратор выполняет кэширование за вас. - person Aaron Digulla; 05.09.2014