Уникальные элементы списка и соответствующие индексы - PullRequest
Новая
       19

Уникальные элементы списка и соответствующие индексы

2 голосов
/ 20 апреля 2019

Учитывая список vs, я хочу получить список vs' уникальных элементов vs, а также индексы элементов vs в vs'.Например, если vs = [7, 8, 7, 8, 9] я хочу получить [7,8,9] (уникальные элементы) и [0,1,0,1,2] (индексы).

Простая реализация: 

import           Data.List
import           Data.Maybe

unique :: Eq a => [a] -> ([a], [Int])
unique vs = (vsnub, indices)
  where
  vsnub = nub vs
  indices = map (\v -> fromJust $ elemIndex v vsnub) vs

Есть либолее эффективный вариант?

Я реализовал следующий псевдокод (говоря, что vs - список чисел) с помощью изменяемых векторов, но это медленно: 

n = length of vs
idx = list of n integers (to store the indices)
visited = [false, false, ..., false] (n elements)
nvs = list of n numbers (to store the unique elements)
count = 0 
for(i = 0; i < n; ++i)
{
  if(not visited[i])
  {
    nvs[count] = vs[i]
    idx[i] = count
    visited[i] = true
    for(j = i+1; j < n; ++j)
    {
      if(vs[j] = vs[i])
      {
        visited[j] = true
        idx[j] = count
      }
    }
    count ++
  }
}
nvs = first 'count' elements of nvs

РЕДАКТИРОВАТЬ

Вот мой код с использованием изменяемых векторов (медленно): 

{-# LANGUAGE ScopedTypeVariables #-}
import           Control.Monad               ((>>=))
import           Data.Vector.Unboxed         (Unbox, Vector, freeze, (!))
import           Data.Vector.Unboxed.Mutable (IOVector, new, write)
import qualified Data.Vector.Unboxed.Mutable as VM

unique' :: forall a . (Unbox a, Eq a) => [a] -> IO (Vector a, Vector Int)
unique' vs = do
  let n = length vs
  idx <- VM.replicate n 0 :: IO (IOVector Int)
  visited <- VM.replicate n False :: IO (IOVector Bool)
  nvs <- new n :: IO (IOVector a)
  let inner :: Int -> Int -> Int -> IO ()
      inner i j count | j == n = return ()
                      | otherwise =
                        if vs !! i == vs !! j
                          then do
                            write visited j True
                            write idx j count
                            inner i (j+1) count
                          else inner i (j+1) count
  let go :: Int -> Int -> IO (IOVector a)
      go i count | i == n = return $ VM.take count nvs
                 | otherwise = do
                   vst <- VM.read visited i
                   if not vst
                     then do
                       write nvs count (vs !! i)
                       write idx i count
                       write visited i True
                       _ <- inner i (i+1) count
                       go (i+1) (count + 1)
                     else go (i+1) count
  nvs' <- go 0 0 >>= freeze
  idx' <- freeze idx
  return (nvs', idx')

Ответы [ 2 ]

3 голосов
/ 20 апреля 2019

Это вариант решения oisdk, в котором используется alterF вместо более старого, менее мощного и странного insertLookupWithKey. 

import qualified Data.Map.Strict as M
import Data.Bifunctor

uniqInds :: Ord a => [a] -> ([a], [Int])
uniqInds = go 0 M.empty
  where
    go i m [] = ([],[])
    go i m (x:xs) = case M.alterF chg x m of
       Right m' -> bimap (x:) (i:) (go (i+1) m' xs)
       Left j -> second (j:) (go i m xs)
      where
        -- The value wasn't found. Insert its index.
        chg Nothing = Right (Just i)
        -- The value was found. Return its index.
        chg (Just j) = Left j

Используется alterF с функтором Either Int. На каждом шаге вы или получаете сохраненный индекс или , вы получаете новую карту.

3 голосов
/ 20 апреля 2019

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

  • Элементы, которые вы уже видели (и их позиции).
  • Позиция в списке вывода, в которой вы находитесь.

Первый из них может быть инкапсулирован с Map, а второй с Int. 

uniqInds :: Ord a => [a] -> ([a], [Int])
uniqInds = go 0 Map.empty
  where
    go i m [] = ([],[])
    go i m (x:xs) = case Map.insertLookupWithKey (\_ _ j -> j) x i m of
        (Nothing, m') -> first (x:) (second (i:) (go (i+1) m' xs))
        (Just j , m') ->             second (j:) (go i     m' xs)

Map.insertLookupWithKey - это функция, которая позволяет нам выполнять поиск и изменять одновременно. first и second отображают функцию на первый и второй элементы в кортеже соответственно. Вы действительно можете переписать эту функцию в виде сгиба: 

uniqInds :: Ord a => [a] -> ([a], [Int])
uniqInds xs = foldr f (\_ _ -> ([],[])) xs 0 Map.empty
  where
    f x xs i m = case Map.insertLookupWithKey (\_ _ j -> j) x i m of
        (Nothing, m') -> first (x:) (second (i:) (xs (i+1) m'))
        (Just j , m') ->             second (j:) (xs i     m')
...