Предварительное вычисление большой таблицы значений

Question

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

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

Моя проблема в том, что в настоящее время я делаю что-то подобное, что занимает довольно много времени для вычисления

  for(double i = 0; i <= 1 ; i += 0.0001)
      for(double j = 0; j <= 1; j+= 0.0001)
           answer = formula(i,j); //do the math
           if( Math.abs(answer - answerWanted) < 0.001)
                //close match found

Видя, что формулы статичны, я наверняка смогу предварительно рассчитать эти значения. Я предполагаю, что тогда будет гораздо быстрее найти значение, чем выполнить много вычислений.

Я никогда не делал ничего подобного раньше. Кто-нибудь знает, какие структуры данных использовать / как индексировать / как хранить результаты? На данный момент я думаю только о том, что я мог бы как-то отсортировать ответы, чтобы уменьшить пространство поиска, или просто инициализировать огромный массив во время выполнения. Если это имеет значение, ответ может быть в диапазоне от 0 до 2000.

Answer 1

Альтернативой является использование более интеллектуального алгоритма поиска.Лучший выбор будет зависеть от вашей функции, но хорошим началом, вероятно, будет алгоритм Nelder-Mead (Downhill Simplex):

http://en.wikipedia.org/wiki/Nelder–Mead_method

Это значительно сократит количество вычислений.Локальные минимумы могут быть проблемой для некоторых алгоритмов поиска, но Nelder-Mead может использовать многие / большинство из них.

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

Answer 2

По существу, у вас есть массив 10000 * * 10000 *.Это займет примерно 800 МБ памяти кучи Java, если вы сохраните ее в памяти.

Вот несколько стратегий, которые могут помочь:

• Храните данные в таблице базы данных.Вероятно, вы могли бы достичь времени доступа менее миллисекунды (в зависимости от продукта базы данных, настройки, шаблонов доступа и т. Д.), И кэш в памяти улучшил бы ситуацию.Предполагая, что вы сохранили {i, j, value} троек, вам нужно будет индексировать на {i, j} для прямого просмотра и {value} для обратной функции.

• Если формула непрерывнаи относительно гладко, вы можете уменьшить количество сохраненных точек данных (например, до 1000 на 1000) и использовать интерполяцию, чтобы получить приблизительные значения для промежуточных точек данных.

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

---

Во всем этом вам необходимо учитыватьчто обратная функция вряд ли будет функцией 1-к-1.Скорее всего, будут значения, которые появляются в нескольких {i, j} точках, и, возможно, другие значения, для которых функция не определена.

Answer 3

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

hth

Answer 4

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

Предварительно рассчитайте более грубую сетку, чем вы смотрите, а затем попытайтесь уточнить свой ответ, сделав шаг в два раза меньше размера вашей сетки и исследуя (выПридется их подсчитать) по восьми соседним точкам.Выберите лучшее, разрежьте сетку пополам и повторяйте, пока не получите желаемую точность.Это приводит к 8 вычислениям на шаг (у вас всегда есть центральное значение из предыдущего шага), чтобы перейти от 100x100 к вашему разрешению, нужно всего 7 шагов, чтобы в общей сложности 56 вызовов к вашей функции вычислений.

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

Даже при сетке 1000x1000 вы ищете максимум 8 мегабайт для сеткии 32 вычисления, чтобы сходить его.

Answer 5

Попробуйте Hash Map от Double до Set<Pair<Double, Double>>

HashMap<Double, Set<Pair<Double, Double>> Answers;

// fill in answers
for(double i = 0; i <= 1 ; i += 0.0001)
    for(double j = 0; j <= 1; j+= 0.0001) {
        answer = formula(i,j);
     Set<Double> existing;
        if (Answers.hasKey(answer)) {
          existing = Answers.get(answer);
        }
        else {
          existing = new Set<Pair<Double, Double>>;
       }
       existing.add(new Pair(i, j));
       Answers.set(answer, existing);
    }
}

// look up all the possible inputs for an answer

Set<Pair<Double, Double>> inputs = Answers.get(output);

Iне рассматривал обратное, но это просто ...

Answer 6

Насколько сложна формула? Если он не чередуется с быстрым и уменьшающимся увеличением, вы можете изменить значение приращения на значение, превышающее .0001, а затем связать ответ, используя последовательно меньшие приращения, как только вы узнаете два значения, ответ на который вы хотите получить между

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

Answer 7

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

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

select formula, value from pre_computed_values 
    where value >= givenvalue - Epsilon and value <= givenvalue - Epsilon

, где Epsilon - очень небольшое значение (диапазон, которым вы довольны, например, 0,001 в вашем случае)