Сортировка слиянием в Haskell
Ответ: notasecret
https://developers.google.com/console/help/#service_accounts
Ваше приложение нуждается в закрытый ключ при запросе токена доступа OAuth 2.0 при взаимодействии между серверами. Google не хранит копию этого закрытого ключа, и этот экран является единственным местом для получения этого конкретного закрытого ключа. Когда вы нажимаете кнопку «Скачать закрытый ключ», закрытый ключ в формате PKCS # 12 загружается на локальный компьютер. Как показывает экран, вы должны надежно хранить этот ключ.
Имя загруженного закрытого ключа является отпечатком ключа.
При проверке ключа на вашем компьютере или использовании ключа в вашем приложении вам необходимо будет предоставить пароль notasecret . Обратите внимание, что хотя пароль для всех секретных ключей, выданных Google, одинаков (notasecret), каждый ключ является криптографически уникальным.
4 ответа
Лучший способ разделить список, чтобы избежать проблемы, на которую указывает CesarB:
split [] = ([], [])
split [x] = ([x], [])
split (x : y : rest) = (x : xs, y : ys)
where (xs, ys) = split rest
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergesort ys) (mergesort zs)
where (ys, zs) = split xs
РЕДАКТИРОВАТЬ: Исправлено.
Попробуйте эту версию:
mergesort :: [String] -> [String]
mergesort = mergesort' . map wrap
mergesort' :: [[String]] -> [String]
mergesort' [] = []
mergesort' [xs] = xs
mergesort' xss = mergesort' (merge_pairs xss)
merge_pairs :: [[String]] -> [[String]]
merge_pairs [] = []
merge_pairs [xs] = [xs]
merge_pairs (xs:ys:xss) = merge xs ys : merge_pairs xss
merge :: [String] -> [String] -> [String]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
= if x > y
then y : merge (x:xs) ys
else x : merge xs (y:ys)
wrap :: String -> [String]
wrap x = [x]
- Плохая идея - сначала разделить список. Вместо этого просто составьте список из списков одного участника. Haskell ленив, это будет сделано в нужное время.
- Затем объединяйте пары списков, пока у вас не будет только один список.
Изменить : Тот, кто проголосовал против этого ответа: вышеупомянутая реализация сортировки слиянием имеет тот же алгоритм как используется в ghc Data.List.sort, за исключением удаления функции cmp. Что ж, авторы ghc могут ошибаться: - /
Я не уверен, является ли это причиной вашей проблемы, но помните, что списки представляют собой последовательную структуру данных. В частности, для length xs и splitAt n xs потребуется время, пропорциональное длине списка ( O (n) ).
В C и Java вы, скорее всего, используете массивы, которые занимают постоянное время для обеих операций ( O (1) ).
Изменить: отвечая на ваш вопрос о том, как сделать его более эффективным, вы также может использовать массивы в Haskell.
В Haskell строка представляет собой отложенный список символов и имеет те же накладные расходы, что и любой другой список. Если я помню прямо из выступления Саймона Пейтона Джонса в 2004 году, стоимость места в GHC составляет 40 байт на символ. Для сравнения яблок с яблоками вам, вероятно, следует использовать сортировку Data.ByteString , которая предназначена для обеспечения производительности, сопоставимой с другими языками.