В этой теме уже много ответов, но тот, который лучше всего работал (и простейший - одна строка!) для меня, был модификацией комментария Нила Э. Пирсона от 21 апреля 2013 года:
< blockquote>Если вы застряли в своей кнопке отправки #submit, вы можете обойти ее, украв другой метод экземпляра экземпляра формы ().
blockquote>Мое изменение в его методе, и что сработало для меня:
document.createElement('form').submit.call(document.getElementById(frmProduct));
О, сегодня мне нужно было определить, является ли число идеальным кубом, и подобное решение было ОЧЕНЬ медленным.
Итак, я придумал довольно умную альтернативу
cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)
Очень простую. Я думаю, мне нужно использовать дерево для более быстрого поиска, но сейчас я попробую это решение, может быть, оно будет достаточно быстрым для моей задачи. Если нет, я отредактирую ответ, указав правильную структуру данных
Я думаю, что предоставленный вами код является самым быстрым из тех, что вы собираетесь получить:
is_square n = sq * sq == n
where sq = floor $ sqrt $ (fromIntegral n::Double)
Сложность этого кода: один sqrt, одно двойное умножение , одно приведение (dbl-> int) и одно сравнение. Вы можете попробовать использовать другие методы вычислений, чтобы заменить sqrt и умножение только целочисленной арифметикой и сдвигами, но, скорее всего, это не будет быстрее, чем один sqrt и одно умножение.
Единственное место, где может быть целесообразно использовать другой метод, - это если процессор, на котором вы работаете, не поддерживает арифметику с плавающей запятой. В этом случае компилятору, вероятно, придется сгенерировать sqrt и двойное умножение в программном обеспечении, и вы можете получить преимущество в оптимизации для вашего конкретного приложения.
Как указано в другом ответе, все еще существует ограничение на большие целые числа, но если вы не собираетесь сталкиваться с этими числами, вероятно, лучше воспользоваться аппаратной поддержкой с плавающей запятой, чем писать свой собственный алгоритм.
В статье Википедии о целочисленных квадратных корнях есть алгоритмы, которые можно адаптировать в соответствии с вашими потребностями. Метод Ньютона хорош тем, что сходится квадратично, т. Е. Вы получаете вдвое больше правильных цифр на каждом шаге.
Я бы посоветовал вам держаться подальше от Double
, если ввод может быть больше, чем 2 ^ 53
, после чего не все целые числа могут быть точно представлены как Double
.
В комментарии к другому ответу на этот вопрос вы обсуждали мемоизацию. Имейте в виду, что эта техника помогает, когда шаблоны пробников имеют хорошую плотность. В данном случае это означает проверку одних и тех же целых чисел снова и снова. Насколько вероятно, что ваш код будет повторять одну и ту же работу и, таким образом, выиграет от кэширования ответов?
Вы не дали нам представления о распределении ваших входных данных, поэтому рассмотрим быстрый бенчмарк, использующий отличный пакет criterion:
module Main
where
import Criterion.Main
import Random
is_square n = sq * sq == n
where sq = floor $ sqrt $ (fromIntegral n::Double)
is_square_mem =
let check n = sq * sq == n
where sq = floor $ sqrt $ (fromIntegral n :: Double)
in (map check [0..] !!)
main = do
g <- newStdGen
let rs = take 10000 $ randomRs (0,1000::Int) g
direct = map is_square
memo = map is_square_mem
defaultMain [ bench "direct" $ whnf direct rs
, bench "memo" $ whnf memo rs
]
Эта нагрузка может быть или не быть точным представителем того, что вы делаете, но в том виде, в котором она написана, частота пропусков кэша кажется слишком высокой:
Есть очень простой способ проверить идеальный квадрат - буквально, вы проверяете, имеет ли квадратный корень из числа что-либо кроме нуля в дробной части. Часть этого.
Я предполагаю, что функция извлечения квадратного корня возвращает плавающую точку, и в этом случае вы можете выполнить (Псевокод):
func IsSquare (N) sq = sqrt (N ) return (sq modulus 1.0) равняется 0,0
Иногда не стоит делить задачи на слишком мелкие части (как, например, проверка is_square
):
intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted xs (y:ys) | head xs > y = intersectSorted xs ys
intersectSorted (x:xs) ys | head ys > x = intersectSorted xs ys
intersectSorted (x:xs) (y:ys) | x == y = x : intersectSorted xs ys
squares = [x*x | x <- [ 1..]]
weird = [2*x+1 | x <- [ 1..]]
perfectSquareWeird = intersectSorted squares weird
Это не особенно красиво или быстро, но вот версия без каста, без FPA, основанная на методе Ньютона, которая работает (медленно) для произвольно больших целых чисел:
import Control.Applicative ((<*>))
import Control.Monad (join)
import Data.Ratio ((%))
isSquare = (==) =<< (^2) . floor . (join g <*> join f) . (%1)
where
f n x = (x + n / x) / 2
g n x y | abs (x - y) > 1 = g n y $ f n y
| otherwise = y
Возможно, ее можно ускорить с помощью дополнительных хитростей теории чисел.
Подумайте об этом так: если у вас положительное int n
, тогда вы в основном выполняется двоичный поиск в диапазоне чисел от 1 до n, чтобы найти первое число n '
, где n' * n '= n
.
Я не знаю Haskell, но этот F # должно быть легко преобразовать:
let is_perfect_square n =
let rec binary_search low high =
let mid = (high + low) / 2
let midSquare = mid * mid
if low > high then false
elif n = midSquare then true
else if n < midSquare then binary_search low (mid - 1)
else binary_search (mid + 1) high
binary_search 1 n
Гарантированно O (log n). Легко модифицировать идеальные кубы и более высокие мощности.