1. Haskell / Говнокод #22737

    −100

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    topSort :: V.Vector ([Int], [Int])
       -> Either String [Int]
topSort kob =
  let
    sup u k = do
      let max i = (i,) . head . snd <$> k `MV.read` i
      l <- mapM max u
      case filter (uncurry (==)) l of
        [(a,_)] -> return $ Right a
        x -> return $ Left "Topology error"

    rewrite k s (i, j) = do
      let f x | x == s && j < 0 = []
              | x == s = [j]
              | otherwise = [x]
      when (j>=0) $ MV.modify k (_1 %~ (i:)) j
      MV.modify k (_2 %~ (>>= f)) i

    go u k =
      readSTRef u >>= \case
        [a] -> return $ Right [a]
        u_ -> sup u_ k >>= \case
          Right s -> do
            modifySTRef' u $ Data.List.delete s
            s_d <- fst <$> MV.read k s
            mapM_ (rewrite k s) $ zip s_d (tail s_d ++ [-1])
            tail <- go u k
            return $ (s:) <$> tail
          Left err ->
            return  $ Left err

  in runST $ do
    u <- newSTRef $ [0..V.length kob-1]
    k <- V.thaw kob
    liftM reverse <$> go u k

    Пишем на декларативном языке

    Запостил: CHayT, 04 Апреля 2017

    Комментарии (7) RSS

    • ava CHayT 04.04.2017 09:40 # 0

      seo-post: о преимуществах функциональной парадигмы перед императивной
      Ответить

    • ava roman-kashitsyn 04.04.2017 12:22 # 0

      Если бы не название функции, я бы не догадался, что тут происходит. Где ты это откопал?

      Я так понимаю, u — это список(sic!) ещё не посещённых вершин. Не понятно только, зачем нужен медленный список внутри мутабельной переменной, когда гораздо проще использовать мутабельный массив, как это делается в Data.Graph?

      > Either String
      тоже забавно, stringly typed programming

      Ну и import Data.Graph (topSort), разумеется.
      Ответить

      • ava CHayT 04.04.2017 12:47 # 0

        > Где ты это откопал?
        Сам высрал как прототип. Во время бессонницы, скажу в оправдание.
        > Не понятно только, зачем нужен медленный список внутри мутабельной переменной, когда гораздо проще использовать мутабельный массив, как это делается в Data.Graph?
        В основном потому что этот код мутировал из иммутабельного.
        > import Data.Graph (topSort)
        Это не просто граф, т.к. входные данные несут не только инвормацию о рёбрах, но ещё и об относительном порядке в результирующем массиве. Обычный топсорт её проебёт.
        Ответить

        • ava roman-kashitsyn 04.04.2017 13:03 # 0

          > Обычный топсорт её проебёт
          Используй алгоритм Kahn-а вместо dfs, он может выдавать лексикографически-минимальную топологическую сортировку.
          Ответить

        • ava roman-kashitsyn 04.04.2017 13:30 # 0

          Вот так примерно выглядит императивный Kahn на псевдокоде (писал на коленке, могут быть косяки, но идея должна быть ясна):
          def toposort(Graph G(V, E)):
  Vect<Vertex> out_degree(0, |V|);
  Vect<Vertex> toposort;
  Heap<Vertex> heap(CompareAsYouLike);

  foreach (from, to) in E {
    out_degree[from]++;
  }

  foreach v in V {
    if out_degree[v] == 0 {
      heap.push(v);
    }
  }

  while !heap.empty() {
    Vertex v = heap.extract_min();
    toposort.push(v);
    foreach (from, to) in incoming_edges(G, v) {
      out_degree[from] -= 1;

      if out_degree[from] == 0 {
        heap.push(from);
      }
    }
  }

  if toposort.size() != |V| {
    raise TopologyError;
  }

  return toposort;
}
          Как видишь, для эффективности нужно иметь ещё и инвертированный граф, чтобы быстро находить рёбра, входящие в вершину ("incoming_edges(G, v)").
          Ответить

          • ava CHayT 04.04.2017 19:17 # 0

            У меня роль играет, в каком именно порядке рёбра определены в _каждой_ вершине, так что это не просто некий граф, а более информативная кобенация, которую можно было бы представить и обычным графом, но гораздо большего размера.
            Ответить

            • ava roman-kashitsyn 04.04.2017 21:16 # 0

              А что это меняет? Слишком сложно будет посчитать отношение порядка между вершинами?
              Ответить

    Добавить комментарий