Индексирование структуры данных Haskell для запросов

Question

У меня есть Data.Vector из Dog записей, каждая из которых идентифицирует House, где живет указанная собака.Мне понадобится процедура поиска, чтобы найти всех собак, которые живут в доме, примерно так, как показано ниже, но мне нужны постоянные поиски времени, которые не может обеспечить эта первая версия.

dogs_by_houses dogs h = [ d | d <- Vec.toList dogs, h == house d ]

Как я понимаю,Основное правило для оптимизации кода на Haskell состоит в том, что компилятор вычисляет каждое выражение только один раз внутри его лямбда-выражения.Поэтому я должен построить таблицу поиска для этого конкретного dogs внутри выражения dogs_by_houses dogs, прежде чем связывать h, да?

Я предполагаю, что Data.Vector - лучший инструмент для этой задачи, хотя, по-видимому,Вы не можете уменьшить их, как вы могли бы векторов C ++.Я бы реализовал это примерно следующим образом:

dogs_by_houses :: Vec.Vector Dog -> Int -> [Dog]
dogs_by_houses dogs = let {
        dog_house = house_id . house ;
        v0 = Vec.replicate (maximum . map dog_house $ Vec.toList dogs) [] ;
        f v d = let { h = dog_house d } in v // [(h,d:v!h)] ;
        dbh = Vec.foldl' f v0 dogs
   } in (dbh !)

Есть ли здесь какая-то глупость в оптимизации?Я предполагаю, что теги строгости для таких переменных, как dbh, не сильно помогут, поскольку по определению dogs необходимо пройти, прежде чем dbh имеет смысл.

Есть ли какое-то большое преимущество, если сделать это с MVector и create вместо сгибов возвращаются модифицированные неизменяемые векторы?Все мои попытки использовать MVector и create до сих пор заканчивались, должны быть менее краткими, различные слои do s или fold (>>), как конструкции или что-то еще.Я предполагаю, что компилятор должен просто собрать dbh на месте, даже без явного указания MVector.

Нельзя ли достичь этого алгоритма с помощью списков?Иногда вы видите, как люди строят бесконечные списки простых чисел, а затем выбирают n-е простое число с помощью primes !! n.Я бы предположил, что для получения n-го простого числа таким образом требуется обходить первые n простых чисел в списке каждый раз, когда вы делаете это.И наоборот, я заметил, что GHC хранит строки как строки C, а не списки.Будет ли компилятор просто представлять известные элементы списка в виде массива, а не пересматривать список для каждого из них?

Обновление:

Я использовал ответы Пола Джонсона и Луиса Вассермана, чтобы построить функцию для индексации произвольного вектора таким образом, потому что я должен сделать это на основе нескольких различных функций индексации.

vector_indexer idx vec = \i -> (Vec.!) t i
  where m = maximum $ map idx $ Vec.toList vec
        t = Vec.accumulate (flip (:)) (Vec.replicate m []) 
               $ Vec.map (\v -> (idx v, v)) vec
dogs_by_houses = vector_indexer (house_id . house)

Я еще не профилировал это, но в конце концов.Я ожидаю, что нужно написать my_d_by_h = dogs_by_houses my_dogs и позвонить my_d_by_h, чтобы извлечь выгоду из индексации.

Answer 1

Однажды меня поймала мерзкая гоча, делающая что-то подобное. Я использовал Data.Map.Map в качестве таблицы поиска, но принцип был тот же. Моя функция взяла список пар ключ-значение, сконструировала карту и вернула функцию поиска. Это произошло примерно так:

makeTable :: [(Key, Value)] -> Key -> Value
makeTable pairs = ((fromList pairs) !)

Мне казалось очевидным, что я мог бы написать что-то вроде

myTable = makeTable [("foo", fooValue), ("bar", barValue)  ... and so on]

Тогда я мог бы найти O (log N), сказав

v = myTable "foo"

Однако GHC фактически сделал перестроение всей Карты из списка для каждого вызова. Когда вы создаете частичное приложение таким образом, GHC не пытается выяснить, какие значения он может извлечь из полученных им аргументов, он просто сохраняет необработанные аргументы и выполняет всю функцию для каждого вызова. Совершенно разумное поведение, но не то, что я хотел.

Вместо этого я должен был написать:

makeTable pairs = \k -> table ! k
   where table = fromList pairs

Я полагаю, вам придется сделать то же самое.

Answer 2

Я бы построил таблицу с

Vec.accumulate (:) (Vec.replicate maxHouse []) 
  (Vec.map (\ d -> (dog_house d, d)) dogs)

, который определенно выделит максимум один промежуточный вектор, и я подозреваю, что он может быть достаточно умен, чтобы вообще не выделять какие-либо промежуточные векторы.