Печальная правда в том, что Set.member тоже дорогой.
В первой версии вы проверяете для каждого хвоста, был ли он замечен ранее, и если да, игнорируйте его, в противном случае вставьте все его непустые элементы. Если входные данные достаточно нерегулярны, то это O (n) тестов членства и O (n ^ 2) вставок, всего O (n ^ 2 * log n) (при условии, что O (1) средняя стоимость для сравнений). Если вход является периодическим с самым коротким (положительным) периодом p, только первые хвосты p приводят к вставкам, так что это O (n) тесты и O (p * n) вставки, O (p * n * log n) в целом (это немного обманут, средняя стоимость для сравнений может быть до O (p), если p> 1, и O (n), если p == 1, но если сам период нерегулярен, O (1) для сравнений в порядке) .
Во втором
substringsSB s = substringsSB' Set.empty s
substringsSB' m str = substrings' m (init . B.tails $ str)
where
substrings' m [] = m
substrings' m (s:ss) | Set.member s m = m
| otherwise = substrings' insertTail ss
where
insertTail = insertInits m $ reverse $ (tail . B.inits $ s)
вы проверяете для каждого хвоста, был ли он замечен ранее, если это так, остановитесь. Это хорошо, но не дает большого выигрыша по сравнению с первым В первом случае, если хвост был замечен ранее, все остальные хвосты также были замечены ранее, поэтому вы пропускаете только самое большее O (n) тестов членства, O (n *) журнал п) операции. Для обычно нерегулярного ввода, только несколько самых коротких хвостов были замечены ранее, поэтому пропускаются только несколько тестов - очень небольшое усиление.
insertInits m [] = m
insertInits m (s:ss) | Set.member s m = m
| otherwise = insertInits (doInsert s m) ss
doInsert k m = {-# SCC "doInsert" #-}Set.insert k m
Если хвост еще не виден (нормальный), вы начинаете вставлять его отрывки - от самых длинных до самых коротких - разрыв, если таковые были замечены ранее (потому что тогда все более короткие отряды также были замечены ранее). Это замечательно, если много длинных инициатов встречается несколько раз, но если нет, все, что у вас есть, - это O (n ^ 2) дополнительных тестов членства.
Для обычного нерегулярного ввода длинные подстроки не встречаются несколько раз, но есть несколько коротких подстрок, и несколько сохраненных вставок не компенсируют дополнительные тесты членства, что делает второй метод более медленным с постоянным коэффициентом.
(Членское тестирование дешевле, чем ввод, поэтому коэффициент должен быть меньше 2.)
Для периодического ввода первый метод также позволяет избежать ненужных вставок, второй сохраняет O (n) тесты во внешнем цикле, но добавляет O (p * n) тесты во внутреннем цикле, что делает его несколько хуже, чем в нерегулярном. случай.
Но для некоторых входов второй метод может быть значительно лучше. Попробуйте оба для
main = do
let x = substringsSB $ B.pack $ replicate 9999 97 ++ [98]
print (Set.size x)
Вы можете улучшить вторую версию, заменив дорогой member перед вставкой на дешевое size сравнение после вставки,
substringsSB str = go 0 Set.empty (init $ B.tails str)
where
go sz m (s:ss)
| Set.member s m = m
| otherwise = go nsz nm ss
where
(nsz,nm) = insInits sz m (reverse . tail $ B.inits s)
go _ m [] = m
insInits sz m (s:ss)
| sz1 == sz = (sz,m)
| otherwise = insInits sz1 nm ss
where
nm = Set.insert s m
sz1 = Set.size nm
insInits sz m [] = (sz,m)
Это приближает его к первой версии в общем случае, делает его немного лучше (здесь), чем первая версия для concat $ replicate n "abcde" и намного лучше для приведенного выше примера зла.