Учитывая 2 списки уникальных, заказываемые, несмежных элементов, говорят:Поиск всех индексов некоторых элементов в данном списке. Можно ли это сделать меньше, чем O (n^2) без массивов в Haskell?
['d', 'a', 'z', 'b']
Я хочу найти свой индекс в другом списке, скажем:
['a', 'b', 'z', 'd']
Результатом будет список с их позиции:
[3, 0, 2, 1] -- element at 0 is at 3,
-- element at 1 is at 0, etc.
Это также можно сделать в O(n log n) раз с несколькими видами. Я предполагаю, что второй список является перестановкой первого.
import Data.List
import Data.Ord
import Data.Function
correspIx :: Ord a => [a] -> [a] -> [(Int, Int)]
correspIx = zip `on` map fst . sortBy (comparing snd) . zip [0..]
correspIx возвращает список пар с индексами соответствующих друг другу:
correspIx "dazb" "abzd" == [(1,0),(3,1),(0,3),(2,2)]
Нам нужен еще один сорт, чтобы получить результат, указанный в вопросе:
correspIx' :: Ord a => [a] -> [a] -> [Int]
correspIx' xs ys = map snd $ sortBy (comparing fst) $ correspIx xs ys
Теперь correspIx' "dazb" "abzd" == [3,0,2,1] ,
Я думаю, что этот ответ более функциональный, так как он не использует таблицы Hash, которые, как я полагаю, используют массив под капотом. –
@ LayGonzález, это зависит от того, насколько строго вы интерпретируете «хэш-таблицу». В Haskell «HashMap» представлен как trie. – dfeuer
Одно простое решение заключается в создании Data.Map или хэш-таблицу, используя второй список, так что вы можете иметь O (Log н) поиск по индексу вместо O (п).
Сначала вы должны создать карту всех символов в целевом массиве, а затем у вас есть два варианта:
Вы можете использовать merge sort сортировки списка в O(n log n) времени, и если массив лексем вы ищет постоянную длину, вы будете делать постоянное количество запросов в O(log n).
Другие решения - взять целевой массив и поместить его все в карту хэша, а затем искать там.
Является ли второй список гарантией перестановки первого? – dfeuer
Теория предсказывает, что без массивов функциональное программирование не более O (log n) раз медленнее. В самом деле, вы можете заменить массив на древовидную карту, имеющую O (log n) доступ вместо O (1). Итак, если вы можете определить алгоритм O (f (n)) в императивном мире, вы знаете, что вы можете достичь O (f (n) log f (n)) в функциональном мире. Можно ли закрыть этот пробел, остается открытой проблемой, AFAIK. (На практике многие функциональные языки поддерживают массивы напрямую, поэтому, чтобы избежать проблемы) – chi
@chi Где я мог прочитать эту теорию (или, под каким именем я должен искать)? – phg