Преобразование рекурсивного алгоритма «разделяй и властвуй» в итерационную версию

Question

Преобразование рекурсивного алгоритма «разделяй и властвуй» в итерационную версию

UPDATE:

Исходный ответ устарел. Mongodb теперь поддерживает расширенный полнотекстовый поиск со многими функциями.

ОРИГИНАЛЬНЫЙ ОТВЕТ:

Следует отметить, что поиск с регистрозависимым регистром нечувствителен / i означает, что mongodb не может искать по индексу, поэтому запросы к большим наборам данных могут занять много времени.

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

. В качестве альтернативы вы можете хранить заглавную копию и искать ее. Например, у меня есть таблица User, у которой есть имя пользователя, которое является смешанным случаем, но идентификатор является заглавной копией имени пользователя. Это гарантирует, что дублирование, чувствительное к регистру, невозможно (иметь возможность «Foo» и «foo» не будет разрешено), и я могу выполнить поиск по id = username.toUpperCase (), чтобы получить поиск по имени пользователя без регистра.

Если ваше поле большое, например тело сообщения, дублирование данных, вероятно, не является хорошим вариантом. Я считаю, что использование альтернативного индексатора, такого как Apache Lucene, является лучшим вариантом в этом случае.

0

python divide-and-conquer recursion dynamic-programming algorithm

задан cestyx 18 January 2019 в 15:58

1 ответ

Другие вопросы по тегам:

python divide-and-conquer recursion dynamic-programming algorithm

Похожие вопросы:

score 0 · Answer 1

Ниже я преобразовал программу, чтобы использовать продолжение (then) и батут (run / recur). Он развивает линейный итеративный процесс и не будет переполнять стек. Если вы не сталкиваетесь с проблемой переполнения стека, это мало поможет вашей конкретной проблеме, но может научить вас, как сгладить вычисления ветвления.

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

import numpy as np

def identity (x):
  return x

def recur (*values):
  return (recur, values)

def run (f):
  acc = f ()
  while type (acc) is tuple and acc [0] is recur:
    acc = f (*acc [1])
  return acc

def myfunc (a):
  # def recursive(w,i,j)
  def loop (w = a, i = 0, j = len(a)-1, then = identity):
    if i == j:                # same
      return then (w[i])      # wrap in `then`
    else:                     # same
      k = (j - i) // 2 + i    # same
      return recur \          # left=recursive(w,i,k)
        ( w
        , i
        , k
        , lambda left:
          recur               # right=recursive(w,k+1,j)
            ( w
            , k + 1
            , j
            , lambda right:
                then          # wrap in `then`
                  (f (left, right)) # same
            )
        )
  return run (loop)

def f (a, b):
    return a + b              # same

a = np.random.rand(10)        # same
print(a, myfunc(a))           # recursive(a, 0, a.shape[0]-1)

# [0.5732646  0.88264091 0.37519826 0.3530782  0.83281033 0.50063843 0.59621896 0.50165139 0.05551734 0.53719382]

# 5.208212213881435