Как я могу сделать так, чтобы пределы счета занимали слишком много времени для больших целых чисел? - PullRequest
Новая
       14

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

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

У меня с Владимиром Грыговым очень серьезная проблема.

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

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

Сначала я расскажу вам проблему, которую необходимо решить в определенных пределах: у нас в базе данных очень много данных.Ec INT_MAX.Для каждого из этих данных мы должны отсортировать их по алгоритму на две группы, и одна должна иметь интерпретацию красного цвета, а вторая должна быть синей.

Алгоритм считает с полем ID, которое является некоторым значением AUTO_INCREMENT.Для этого значения мы проверяем, равно ли это значение 1. Если да, это данные красного цвета.Если это ноль, это синие данные.Если это больше.Затем, вы должны вычесть номер 2 и проверить еще раз.

После большого метода мозгового штурма мы выбрали метод for for loop, но это было очень медленно для большого числа.Итак, мы хотели убрать цикл, и моя коллега сказала мне использовать рекурсию.

Я так и сделал.Но ... после реализации я получил неизвестную ошибку для больших целых чисел и, например, long long int, и после него было написано, что: "Исключение переполнения стека"

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

Большое спасибо.Все вы.

1 Ответ

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

После вашего комментария я думаю, что смогу решить: 

public bool isRed(long long val) { 
if (val==1) 
  {return true; } 
else if (val==0) 
  { return false; } 
  else { return isRed(val - 2); }
}

Любое приличное значение для val легко сломает это.Нет никакого способа, которым это могло бы работать с рекурсией.Ни один ЦП не будет поддерживать стековую трассировку close до половины длины. MaxInt!

Однако есть некоторые общие проблемы с вашим кодом:

  1. Сейчас это наиболееигольчатый комплекс "это четное число" проверять никогда.Большинство людей используют Modulo, чтобы понять это.if(val%2 == 0) return false; else return true;
  2. тип long long кажется выключенным.Вы повторили тип?Вы имели в виду использовать BigInteger?

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

    public bool isRed (long long val){ for(;val >= 0; val = val -2){ if(value == 0) return false; } return true; }

...