Хламидомонада / Говнокод #22737 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  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 CHayT, (Updated )

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

  • ava CHayT # Ссылка на оригинал 0

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

  • ava roman-kashitsyn # Ссылка на оригинал 0

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

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

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

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

    • ava CHayT # Ссылка на оригинал 0 ⇈

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

      • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

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

      • ava roman-kashitsyn # Ссылка на оригинал 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 # Ссылка на оригинал 0 ⇈

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

          • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

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

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

Я, guest, находясь в здравом уме и твердой памяти, торжественно заявляю:

    А не использовать ли нам bbcode?

    ↑
    8
    ↓