Haskell - разбить список на два подсписка с ближайшими суммами

Question

Я новичок в Haskell, пытаюсь узнать больше о языке, решая некоторые онлайн-тесты / задачи.

Проблема / вопрос довольно длинная, но для ее части требуется код, который может найти число, которое делит данный список на два (почти) равных (по сумме) подсписка.

Дано [1..10]

Ответ должен быть 7, поскольку 1+2+..7 = 28 & 8+9+10 = 27

Вот как я это реализовал

-- partitions list by y
partishner :: (Floating a) => Int -> [a] -> [[[a]]]
partishner 0 xs = [[xs],[]]
partishner y xs = [take y xs : [drop y xs]] ++ partishner (y - 1) xs


-- finds the equal sum
findTheEquilizer :: (Ord a, Floating a) => [a] -> [[a]]
findTheEquilizer xs = fst $ minimumBy (comparing snd) zipParty
  where party = (tail . init) (partishner (length xs) xs) -- removes [xs,[]] types
        afterParty = (map (\[x, y] -> (x - y) ** 2) . init . map (map sum)) party
        zipParty = zip party afterParty -- zips partitions and squared diff betn their sums

Дано (last . head) (findTheEquilizer [1..10]) выход: 7

---

Для чисел около 50k работает нормально

λ> (last . head) (findTheEquilizer [1..10000])                                                   
   7071.0 

Проблема начинается, когда я добавляю в списки больше чем 70k элементов. Это займет вечность, чтобы вычислить.

---

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

Answer 1

Я спросил в комментарии, и ОП говорит, что [1..n] на самом деле не определяет вопрос. Да, я думаю, что спрашивается, как [1 -> n] в случайном порядке возрастания, например [1,3,7,19,37,...,1453,...,n].

И все же ..! Даже согласно приведенным ответам, для списка, подобного [1..n], нам действительно не нужно выполнять какую-либо операцию со списком.

• Сумма [1..n] равна n*(n+1)/2.
• Что означает, что нам нужно найти m для n*(n+1)/4
• Что означает m(m+1)/2 = n*(n+1)/4.
• Так что если n == 100, то m^2 + m - 5050 = 0

Все, что нам нужно, это формула где a = 1, b = 1 и c = -5050, что дает разумный корень 70,565 ⇒ 71 (округлено). Давай проверим. 71*72/2 = 2556 и 5050-2556 = 2494, что говорит 2556 - 2494 = 62 минимальная разница (<71). Да, мы должны разделиться на 71. Так что просто сделайте, как <code>result = [[1..71],[72..100]] over ..!

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

Answer 2

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

approxEqualSums
  :: (Num a, Ord a)
  => [a] -> (Maybe a, [a])
approxEqualSums as0 = stepHare 0 Nothing as0 0 as0
  where
    -- ht is the current best guess.
    stepHare _tortoiseSum ht tortoise _hareSum []
      = (ht, tortoise)
    stepHare tortoiseSum ht tortoise hareSum (h:hs)
      = stepTortoise tortoiseSum ht tortoise (hareSum + h) hs

    stepTortoise tortoiseSum ht [] hareSum hare
      = stepHare tortoiseSum ht [] hareSum hare
    stepTortoise tortoiseSum ht tortoise@(t:ts) hareSum hare
      | tortoiseSum' <= hareSum
      = stepTortoise tortoiseSum' (Just t) ts hareSum hare
      | otherwise
      = stepHare tortoiseSum ht tortoise hareSum hare
      where tortoiseSum' = tortoiseSum + 2*t

Используется:

> approxEqualSums [1..10]
(Just 6,[7,8,9,10])

6 - последний элемент перед переходом через половину, а 7 - первый после этого.

Answer 3

Вот код, который эмпирически ведет себя лучше, чем линейный, и достигает 2 000 000 всего за 1 секунду даже при интерпретации:

g :: (Ord c, Num c) => [c] -> [(Int, c)]
g = head . dropWhile ((> 0) . snd . last) . map (take 2) . tails . zip [1..]
         . (\xs -> zipWith (-) (map (last xs -) xs) xs) . scanl1 (+) 

g [1..10]      ==> [(6,13),(7,-1)]                        -- 0.0s
g [1..70000]   ==> [(49497,32494),(49498,-66502)]         -- 0.09s
g [70000,70000-1..1] ==> [(20502,66502),(20503,-32494)]   -- 0.09s
g [1..100000]  ==> [(70710,75190),(70711,-66232)]         -- 0.11s
g [1..1000000] ==> [(707106,897658),(707107,-516556)]     -- 0.62s
g [1..2000000] ==> [(1414213,1176418),(1414214,-1652010)] -- 1.14s  n^0.88
g [1..3000000] ==> [(2121320,836280),(2121321,-3406362)]  -- 1.65s  n^0.91

Он работает, выполняя частичные суммы с scanl1 (+) и принимая общую сумму за last, так что для каждой частичной суммы, вычитая ее из общей суммы, получается сумма второй части разбиения.

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

Значение должно быть выбрано из пары (результат g), чтобы абсолютное значение второго компонента было меньше между ними.

Это достигается с помощью minimumBy (comparing (abs . snd)) . g.

---

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

Ответ не утверждает, что « лучше линейного», он говорит «он ведет себя лучше линейного» [в тестируемом диапазоне проблем размеры], которые неопровержимо показывают эмпирические данные.

Наконец, обращение к власти . Роберт Седжвик - специалист по алгоритмам. Возьми это с собой.

(и, конечно, алгоритм обрабатывает неупорядоченные данные так же, как и упорядоченные).

Что касается причин неэффективности кода OP: map sum . inits не может не быть квадратичным, но эквивалент scanl (+) 0 является линейным. Радикальное улучшение происходит из-за большого количества избыточных вычислений в первом, которых избегают во втором. (Другой пример этого можно увидеть здесь .)

Answer 4

Хорошо, во-первых, давайте проанализируем, почему он работает вечно (... на самом деле не навсегда, просто медленно), взглянем на функцию партишнера:

partishner y xs = [take y xs : [drop y xs]] ++ partishner (y - 1) xs

, где take y xs и drop y xs - линейное время выполнения, т. Е. O (N), и, таким образом,

[take y xs : [drop y xs]]

тоже есть O (N).

Однако, он запускается снова и снова рекурсивным способом для каждого элемента данного списка. Теперь предположим, что длина заданного списка равна M, каждый вызов функции-партнера принимает O (N) раз, чтобы завершить вычисление:

O(1+2+...M) = (M(1+M)/2) ~ O(M^2)

Теперь в списке 70 тысяч элементов, по крайней мере, нужно 70 тысяч ^ 2 шага. Так почему это зависает.

Вместо использования функции партишнера вы можете суммировать список линейным образом:

sumList::(Floating a)=>[a]->[a]
sumList xs = sum 0 xs
    where sum _ [] = []
          sum s (y:ys) = let s' = s + y in s' : sum s' ys

и findEqilizer просто суммируют заданный список слева направо (leftSum) и справа налево (rightSum) и принимают результат как исходную программу, но весь процесс занимает линейное время.

findEquilizer::(Ord a, Floating a) => [a] -> a
findEquilizer [] = 0 
findEquilizer xs = 
    let leftSum  = reverse $ 0:(sumList $ init xs)
        rightSum = sumList $ reverse $ xs
        afterParty = zipWith (\x y->(x-y) ** 2) leftSum rightSum
    in  fst $ minimumBy (comparing snd) (zip (reverse $ init xs) afterParty)

Answer 5

Мне кажется, что реализация довольно хаотична. Например, partishner, кажется, создает список списков списков a, где, если я правильно понял, внешний список содержит списки с каждыми двумя элементами: список элементов «слева» и список элементов на «право». В результате для построения списков потребуется O (n ² ) .

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

Мне кажется, что может быть проще реализовать «алгоритм развертки»: сначала мы вычисляем сумму всех элементов в списке. Это значение справа, если мы решили разделить в этой конкретной точке, затем мы начинаем двигаться слева направо, каждый раз вычитая элемент из суммы справа и добавляя его к сумме слева. , Мы можем каждый раз оценивать разницу в баллах, например:

import Data.List(unfoldr)

sweep :: Num a => [a] -> [(Int, a, [a])]
sweep lst = x0 : unfoldr f x0
    where x0 = (0, sum lst, lst)
          f (_, _, []) = Nothing
          f (i, r, (x: xs)) = Just (l, l)
              where l = (i+1, r-2*x, xs)

Например:

Prelude Data.List> sweep [1,4,2,5]
[(0,12,[1,4,2,5]),(1,10,[4,2,5]),(2,2,[2,5]),(3,-2,[5]),(4,-12,[])]

Таким образом, если мы выберем разделение в первой точке разделения (перед первым элементом), сумма справа будет на 12 больше, чем сумма слева, если мы разделим после первого элемента, сумма на справа (11) на 10 больше суммы слева (1).

Затем мы можем получить минимум этих разбиений с помощью minimumBy :: (a -> a -> Ordering) -> [a] -> a:

import Data.List(minimumBy)
import Data.Ord(comparing)

findTheEquilizer :: (Ord a, Num a) => [a] -> ([a], [a])
findTheEquilizer lst = (take idx lst, tl)
    where (idx, _, tl) = minimumBy (comparing (abs . \(_, x, _) -> x)) (sweep lst)

Затем получаем правильное значение для [1..10]:

Prelude Data.List Data.Ord Data.List> findTheEquilizer [1..10]
([1,2,3,4,5,6,7],[8,9,10])

или за 70'000:

Prelude Data.List Data.Ord Data.List> head (snd (findTheEquilizer [1..70000]))
49498

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