Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
mayton,


На скорую рука как-то так. Правда цепочки типа 1->2->3->4 коллапсируют в пустое множество

import scala.annotation.tailrec

val data = {
  scala.io.Source.fromFile("war-and-society-1-2-3-4-simple-edges.sorted.csv").getLines()
    .map { l =>
      val arr = l.split(",").map(_.toInt)
      arr(0) -> arr(1)
    }.toArray
}



@tailrec
def processGraph(data: Array[(Int, Int)]): Array[(Int, Int)] = {
  val inputs = data.groupBy(_._2).map { case (k, v) => k -> v.map(_._1) }
  val outputs = data.groupBy(_._1).map { case (k, v) => k -> v.map(_._2) }

  val singleLinks = outputs.filter(_._2.length == 1).filter{case (from,Array(to)) => Array(from).toList == inputs(to).toList }.map { case (from, Array(to)) => from -> to}

  if (singleLinks.isEmpty) {
    return data
  }

  val newData = collection.mutable.HashSet[(Int, Int)]()

  data.foreach { case (from, to) =>
    // нашли связь 1вых->1вх
    if (singleLinks.get(from) == Option(to)) {
      // перенести исходящие узлы удаляемго узла к преды дущему
      outputs.get(to).foreach { outs =>
        outs.foreach { out =>
          newData.add((from, out))
        }
      }
    } else {
      if (!singleLinks.exists { case (f, t) => (t == from)} ) {
        newData.add((from, to))
      }
    }
  }

  processGraph(newData.toArray)

}

processGraph(data)
14 сен 20, 15:15    [22196650]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Leonid Kudryavtsev
Может я чего не понял, но если ноды схлопываются только в том случае, когда между ними единственный маршрут, то для каждой пары нод нужно искать путь из одной ноды в другую.

Сложность "тупого рекурсивного" поиска маршрута прикидочно может достигать 50 000 (кол-во нод) x 5 (путей из каждой ноды) => до 50 - 250 тысяч рекурсий/циклов, и отжирать примерно столько же стека. Теоретически возможно тут нужно было бы 50 000 возводить в степень 5-ки, но это если искать все маршруты. Нам же нужен только факт, что такой маршрут есть, т.е. если мы повторно входим в ноду, то поиск сразу же прекрашаем.

Я думаю что мы можем уйти от рекурсии с глубиной 50 тысяч и DFS. Я надеялся что последовательно удаляя 1 ребро за другим
мы будем быстро возвращаться на старт. И вместо 50 тыщ уровней стека просто получить столько же обычных вызвово.

Из оптимизаций. Ээээ... новые вершины - вряд-ли будут давать позитивный эффект в схлопываниях и смежные с ними ребра можно
забросить в отстойник. В какую-то очередь где мы вернемся к ним не скоро. Или как-то промаркировать их
как неудаляемые (immortal).
14 сен 20, 15:17    [22196652]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Leonid Kudryavtsev

Поскольку схлопывание может быть рекурсивным (например граф вырождается в банальное кольцо), алгоритм возможно рекурсивно запускать до 50 000 раз.

Хм.... кольцо. Это интересная вещь. Надо подумать.

Скорее всего - невозможно в рамках базовой постановки. Или мне надо будет решить где в этом кольце начало и где конец.
Чтобы правильно соединить все ID вершин участников кольца.
14 сен 20, 15:23    [22196661]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80, спасибо. Я посмотрю. Пока у нас нету тест кейса. Но я думаю сегодня-завтра сделаю учебный набор из 10-20 ребер
чтоб конять тривиальные проверки.
14 сен 20, 15:26    [22196663]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
mayton

Хм.... кольцо. Это интересная вещь. Надо подумать.

На мой взгляд кольцо должно схлопнутся в одну ноду. Или я не правильно понял задачу/смысл задачи.

IMHO
14 сен 20, 15:41    [22196673]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Есть литературное произведение. Например.

Андрей Болконский бухал с Безуховым. Бухал с Безуховым долго.


И если разбить его на токены по пробелу то получается цепочка переходов. (Опустим точки и запятые для упрощения)

Андрей -> Болконский -> бухал -> с -> Безуховым. -> Бухал -> с -> Безуховым -> долго.


После схлопывания.

Наподобие Марковской цепи. Где есть вероятности переходов из 1 состояния в другое.
Но оно содержит (по своей природе) уникальные под-цепочки которые однозначно определены.

И в данном случае на выходе мы должны иметь некие состояния автомата типа

"Андрей Болконский" -> "Бухал с Безуховым"
"Бухал с Безуховым" -> "Бухал с Безуховым" // Здесь есть вероятность повтора состояния. Мультиграф. Ребро указывает циклично на свою-же вершину.
"Бухал с Безуховым" -> "долго"


Топологически получаем нормализованный автомат вида

1 -> 2
2 -> 2
2 -> 3


В нем еще не хватает вероятностей переходов. Но наш алгоритм схлопывания убирает единичные где (P=1.0)
и оставляет дробные где например есть ветка (0.4/0.6) Впрочем это отдельная тема.

Поэтому кольцо здесь пока алгоритмически - неясно. Как его потом интерпретировать.

Сообщение было отредактировано: 14 сен 20, 15:52
14 сен 20, 15:55    [22196681]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

Откуда: Bay Area, CA
Сообщений: 2296
mayton

1 -> 2
2 -> 2
2 -> 3



Петли просто надо исключать еще на шаге валидации вершины.

Собственно это без разницв есть ли кольца в графе или нет. Вершина с которой начал должна остаться от всего кольца. Не надо создавать новых вершин просто исходящая вершина всхлопывает входящую и все ее исходящие переписывет на себя равно как и входящие.
14 сен 20, 23:22    [22196968]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Sergunka
mayton

1 -> 2
2 -> 2
2 -> 3



Петли просто надо исключать еще на шаге валидации вершины.

Собственно это без разницв есть ли кольца в графе или нет. Вершина с которой начал должна остаться от всего кольца. Не надо создавать новых вершин просто исходящая вершина всхлопывает входящую и все ее исходящие переписывет на себя равно как и входящие.

По поводу не-создания новых вершин. Это была оптимизация под мультипоточность.
Впрочем мы еще обсудим.

Сейчас пока задача-прим - корректность. Я сегодня сделаю 3-5 модульных тестов и на них
мы будем гонять наши алгоритмы.

50 000 вершин будет потом. Позже. Отобразить их на экране - тоже проблема. То graphviz зависает
на рендеринге. То браузер не может открыть большую картинку или svg-файл.
15 сен 20, 10:09    [22197057]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Zzz79

ну вот твои эти графы ? нахуа они в современном программировании?так чисто на собесе собесера унизить?)

По поводу того где используются графы. Организация Thomson Reuters собирает сведения по физ-лицам
и организациям и складывает их в БД семантического веба. Некоторые сведения имеют статус Open Source
и вы можете тут почитать https://developers.thomsonreuters.com/ и там-же можно скачать образцы
графов в формате Turle (ttl) и кажется Trig.

Фрагмент.

+
@prefix tr-common: <http://permid.org/ontology/common/> .
@prefix fibo-be-le-cb: <http://www.omg.org/spec/EDMC-FIBO/BE/LegalEntities/CorporateBodies/> .
@prefix vcard: <http://www.w3.org/2006/vcard/ns#> .
@prefix tr-org: <http://permid.org/ontology/organization/> .
@prefix mdaas: <http://permid.org/ontology/mdaas/> .
@prefix tr-fin: <http://permid.org/ontology/financial/> .

<https://permid.org/1-5064696466>
        a                            tr-org:Organization ;
        tr-common:hasPermId          "5064696466"^^xsd:string ;
        mdaas:HeadquartersAddress    "India\n"^^xsd:string ;
        tr-org:hasActivityStatus     tr-org:statusActive ;
        tr-org:isIncorporatedIn      <http://sws.geonames.org/1269750/> ;
        fibo-be-le-cb:isDomiciledIn  <http://sws.geonames.org/1269750/> ;
        vcard:organization-name      "PI Prestige International India Pvt Ltd"^^xsd:string .

<https://permid.org/1-5064706661>
        a                            tr-org:Organization ;
        tr-common:hasPermId          "5064706661"^^xsd:string ;
        mdaas:HeadquartersAddress    "India\n"^^xsd:string ;
        tr-org:hasActivityStatus     tr-org:statusActive ;
        tr-org:isIncorporatedIn      <http://sws.geonames.org/1269750/> ;
        fibo-be-le-cb:isDomiciledIn  <http://sws.geonames.org/1269750/> ;
        vcard:organization-name      "Hexagon Composites India Pvt Ltd"^^xsd:string .


Мы немного работали с TR и насетапили им 1 пилотный проектик.

Для процессинга используются библиотеки такие java libs как Apache Jena, Eclipse RDF.

Для хранения используется Amazon Neptune.

Или из опенсорцного Neo4j, но последний я не юзал.

Из языков запросов используется SPARQL. На нем можно делать поисковые запросы типа найти все
вершины обладающие сетом атрибутов. Есть еще вариант java DSL для поисковых запросов.
Кажется называется Gremlin. По нему я хотел создать отдельный топик.

Семантический веб - это граф. Где вершины и рёбра несут мета-информацию о какой-то области.

Но в данной конкретной задаче у меня ребро не несет никакого смысла а в семантическом вебе - ребер
может быть много и на них может быть много смыслов. Например следующий скрипт на языке turtle
описывает различные узлы и связи между ними. Например в узел :member смотрят 3 ребра и исходящие
узлы - это мемберы.

@prefix : <https://sql.ru/forum#>
@prefix :rdfs <https://......#>

:mayton a :member;
           a :moderator.   
:leoniz a :member;
           sname "Кудрявцев".
:stas rdfs:type :member.

В данном примере rdf:type и артикль "a" - синонимы. Просто такой вот макрос. Вот так вот на черепашке
я описал например достаточно гибкую schema-less модель данных.

Описать подобную структуру реляционкой очень сложно. Зачастую - сложнее даже чем EAV. Почти невозможно.
Я пробовал.

Тоесть графовые задачи реально существуют и работают. И игры со схлопыванием - это просто какая
то частная задача. Которая возможно и имеет коробочное решение в Neptune/Neo4j но мне их
движки внутри не интересны.

А мне интересны нестандартные и сложные структкуры данных которые бросают челлендж.

Вот так вот.

Если ты хочешь качать скилы в мультипоточке - то gogo со мной. Если хочешь делать гороскопы в телеграме - то
... как хочешь короче.
15 сен 20, 19:23    [22197741]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80, сделал консольное приложение так.

+
package ru.sql

import scala.annotation.tailrec

object Dimonz {

  val data = {
    scala.io.Source.fromFile("war-and-society-1-2-3-4-simple-edges.sorted.csv").getLines()
      .map { l =>
        val arr = l.split(",").map(_.toInt)
        arr(0) -> arr(1)
      }.toArray
  }

  @tailrec
  def processGraph(data: Array[(Int, Int)]): Array[(Int, Int)] = {
    val inputs = data.groupBy(_._2).map { case (k, v) => k -> v.map(_._1) }
    val outputs = data.groupBy(_._1).map { case (k, v) => k -> v.map(_._2) }

    val singleLinks = outputs.filter(_._2.length == 1)
      .filter { case (from, Array(to)) => Array(from).toList == inputs(to).toList }
      .map { case (from, Array(to)) => from -> to }

    if (singleLinks.isEmpty) {
      return data
    }

    val newData = collection.mutable.HashSet[(Int, Int)]()

    data.foreach { case (from, to) =>
      // нашли связь 1вых->1вх
      if (singleLinks.get(from) == Option(to)) {
        // перенести исходящие узлы удаляемго узла к преды дущему
        outputs.get(to).foreach { outs =>
          outs.foreach { out =>
            newData.add((from, out))
          }
        }
      } else {
        if (!singleLinks.exists { case (f, t) => (t == from) }) {
          newData.add((from, to))
        }
      }
    }

    processGraph(newData.toArray)

  }

  def main(args: Array[String]): Unit = {
    processGraph(data)
  }

}



Хм... 26 секунд. Неплохо. Еще остался пустяк - проверить корректность.

mayton@ryzen-ssd:/storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80$ sbt run
[info] welcome to sbt 1.3.13 (Ubuntu Java 11.0.8)
[info] loading project definition from /storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80/project
[info] loading settings for project root from build.sbt ...
[info] set current project to dimonz80 (in build file:/storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80/)
[info] Compiling 1 Scala source to /storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80/target/scala-2.13/classes ...
https://repo1.maven.org/maven2/org/scala-sbt/compiler-bridge_2.13/1.3.5/compiler-bridge_2.13-1.3.5.pom
  100.0% [##########] 2.8 KiB (4.8 KiB / s)
[info] Non-compiled module 'compiler-bridge_2.13' for Scala 2.13.3. Compiling...
[info]   Compilation completed in 7.12s.
[info] running ru.sql.Dimonz 
[success] Total time: 26 s, completed Sep 15, 2020, 9:08:08 PM
15 сен 20, 21:10    [22197827]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Хм... пару недель назад я запилил Map<Edge, Edge> в качестве коллекции ребер.
И при этом я точно помню что Set<Edge> меня чем-то не устраивал.

Чьорт побьери... я забыл ЧЕМ!

import static java.lang.String.format;
import static java.lang.String.valueOf;
import static java.util.Collections.unmodifiableMap;

/**
 * Directed, Weight graph
 */
public class Graph implements Serializable {

    static Logger logger = LoggerFactory.getLogger(Graph.class);

    // TODO: Leonid proposes to get rid of Edges instead of primitives.
    private Map<Edge, Edge> edgeWeigthMap;
    private Map<String, Vertex> vertexMap;
    private transient LinkedHashMap<String, Object> statistics;
15 сен 20, 21:53    [22197854]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

Откуда: Bay Area, CA
Сообщений: 2296
mayton

По поводу не-создания новых вершин. Это была оптимизация под мультипоточность.
Впрочем мы еще обсудим.


На самом деле мультипоточность тут возможно только при том если граф можно разбить на непересекающиеся графы. Если только нет активного желания связываться с вершинами которые связывают подмножества графов между собой. Но это будет очень гиморно, но скорость должна подрасти. Там только фокус в том, что вершины которые связаны с другими подграфами нельзя всхлапывать.
16 сен 20, 02:25    [22197991]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

Откуда: Bay Area, CA
Сообщений: 2296
dimonz80,

Красивый код
16 сен 20, 02:26    [22197992]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
mayton
Хм... пару недель назад я запилил Map<Edge, Edge> в качестве коллекции ребер.
И при этом я точно помню что Set<Edge> меня чем-то не устраивал.

Чьорт побьери... я забыл ЧЕМ!

import static java.lang.String.format;
import static java.lang.String.valueOf;
import static java.util.Collections.unmodifiableMap;

/**
 * Directed, Weight graph
 */
public class Graph implements Serializable {

    static Logger logger = LoggerFactory.getLogger(Graph.class);

    // TODO: Leonid proposes to get rid of Edges instead of primitives.
    private Map<Edge, Edge> edgeWeigthMap;
    private Map<String, Vertex> vertexMap;
    private transient LinkedHashMap<String, Object> statistics;



Эээ... Я сейчас обидные, наверно, вещи говорить буду. Но есть мнение, что одна их главных проблем ООП это то, что программист начинает делать модель мира, в котором существует поставленная проблема, а не решать саму проблему. Т.е. если для решения задач типа предложенной в топике ты начинаешь писать такой код, то что-то не так в консерватории, интерпрайз головного мозга. По-моему, тут надо рисовать на простом листке в клетку и забыть про ООП, патерны и прочую шелупонь до того момента, пока это все не станет продакшн кодом, т.е. забыть навсегда))), а при реализации использовать максимально примитивные структуры. Я думаю, именно поэтому ты забыл, зачем Set поменял на Map)) Я бы точно забыл, когда перед глазами мельтешат всякие privatы, loggerы, public class implements Serializablы)))


Есть пример жизненный, когда на собесе (кажется в Ланит) предложили сделать тестовое задание, чисто алгоритмическое. Я вот тоже нагородил там, класс на классе сидит интерфейсом погоняет. Сделал , отправил на проверку, они говорят - неверно. Я тогда просто листик в клетку взял и карандаш, успокоился и нарисовал за пару часов решение, чисто схематично, потом за пару минут оттранслировал его в код, который можно было на любом языке практически сделать, и выслал снова, они говорят - вот теперь все верно, только с первого раза надо было сделать, отдыхай, родной.)) Но я не расстроился, т.к. это было самое лучшее тестовое задание с точки зрения подумать, а не кодить.


По теме топика:

От интерпрайза маятник качнулся в противоположную сторону - байтоjobство))

Попробовал сделать на матрицах. Чтобы сэкономить на памяти, решил использовать упакованную матрицу связности, т.е. кодировать связи битами, когда матрица хранит числа, каждое из которых является субматрицей, где каждый бит в числе кодитует связь (1 - связь есть, 0 - связи нет).

Расчет был на уменьшение матрицы как таковой в n^2 раз, где n - кол-во бит в числе. Это даст меньше итераций по массиву, а вычисление связи в субматрице - битовая операция и поэтому все должно быть быстро.


Для упрощения субматрицы должны были быть квадратные, т.е. 16, 64 и т.д битные, чтобы быть 4х4, 8х8 и т.д. Сначала принялся делать на Long (8x8), однако обжегся на порядке бит (little-endian), когда для половины числа надо было кодировать биты по другому, это в общем не сложно, но чтобы не усугублять, пока взял Short (4x4). Запилил функции для установки/снятия каждого отдельного бита, получения отдельных столбцов и строк.


Для нахождения пар узлов - кандидатов на удаление нужно найти элемент матрицы с установленной 1 на пересечении пустых в других ячейках строки с столбца. Если вычисление строки имеет сложность O(1) (просто взять нужный подмассив), то вычиление столбца - O(n), т.к. нужно пройтись в всем строкам и взять нужый элемент. И получается, что сканирование матрицы для нахождения нужных строк и столбцов имеет квадратичную сложность как минимум плюс еще пройтись по строке и столбцу и проверить что в там есть одна нужная 1 в нужном месте. Короче, все равно медленно.

Была идея отразить матрицу по диагонали и получить быстрый доступ к столбцам, т.к. теперь они стали строками. Но это двойной расход памяти и задача по сути сводится к предложенному мной выше решению, когда поиск ведется по 2м словарям: типа Узел->{Выходы} и Узел->{Входы}.


В итоге Fail! И по скорости и по памяти. Если на матрице работает медленно и с хипом -Xmx2g, то на словарях Узел->{Выходы} и Узел->{Входы} менее минуты и по памяти хватает дефолтных для scala REPL -Xmx256m
16 сен 20, 02:42    [22197993]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Sergunka
dimonz80,

Красивый код


это Proff-of-concept из говна и палок.
16 сен 20, 02:43    [22197994]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Sergunka
dimonz80,

Красивый код


И тут тебе не code review!!!
16 сен 20, 02:46    [22197995]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Zzz79
mayton,вот и охота тебе этой дичью заниматься)

ты мне деда моего напоминаешь) уже давно телеки плоские,а он все в ламповых ковыряется,чего то там пояет,модернизирует)

ну вот твои эти графы ? нахуа они в современном программировании?так чисто на собесе собесера унизить?)

я это все к чему- у нас в команду залетел такой овощ- он графы там всякие знает,сколько чего где выбирается -где логорифм ,где On
и диплом есть ,а работать не может) потому что на реальных проектах нет ни графов ни кардиналов) есть чужой говнокод и есть невнятные задачи тупых аналитиков из пту,к которым приложены тесты тестировщиков ,которые вообще ничего не заканчивали кроме школы- и он пасует - потому что тут нужно иметь мозг,который должен искать варианты)

вся эта олд скул школа говно знаний - типо реляционой алгебры,хрень про бинарны дерьвья - она вся в прошлом ,как и пилоты ,которые руками штурвал крутили)

посади пилота из прошлого в современный боинг- он с места его не сдвинет) так и олд скул прогеры - тупо пасуют - у меня живой пример - чувак реально в IT 20 лет - но дуб дубом и скорей всего будет уволен


Пилотов учат летать на планере без мотора, чтобы они жопой закон Бернулли почувствовали.
16 сен 20, 04:46    [22197997]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Вспомнил.
16 сен 20, 09:00    [22198087]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80

Эээ... Я сейчас обидные, наверно, вещи говорить буду. Но есть мнение, что одна их главных проблем ООП это то, что программист начинает делать модель мира, в котором существует поставленная проблема, а не решать саму проблему. Т.е. если для решения задач типа предложенной в топике ты начинаешь писать такой код, то что-то не так в консерватории, интерпрайз головного мозга. По-моему, тут надо рисовать на простом листке в клетку и забыть про ООП, патерны и прочую шелупонь до того момента, пока это все не станет продакшн кодом, т.е. забыть навсегда))), а при реализации использовать максимально примитивные структуры. Я думаю, именно поэтому ты забыл, зачем Set поменял на Map)) Я бы точно забыл, когда перед глазами мельтешат всякие privatы, loggerы, public class implements Serializablы)))

Ахахах. Я-же писал в начале топика

mayton
То второе ограничение - медленная скорость поиска смежных вершин
по матрице - я не преодолел.


По поводу ООП головного мозга и все такое. В родительской задаче ребро - МАТЕРИАЛЬНО. Оно несет нагрузку.
И если в данном топике (в схлопывании) мы действительно можем его закодировать 1 битом то родительском - нет.

Вопрос - делать ли мне спициализированную библиотеку для данного топика или оставить обобщённую? Ну
для меня как-бы очевидно. Оставлю общую.
16 сен 20, 10:44    [22198153]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Sergunka
mayton

По поводу не-создания новых вершин. Это была оптимизация под мультипоточность.
Впрочем мы еще обсудим.


На самом деле мультипоточность тут возможно только при том если граф можно разбить на непересекающиеся графы. Если только нет активного желания связываться с вершинами которые связывают подмножества графов между собой. Но это будет очень гиморно, но скорость должна подрасти. Там только фокус в том, что вершины которые связаны с другими подграфами нельзя всхлапывать.

Да. В этом челлендж этой задачи. Пока она принципиально не сегментируется.
Я не могу ее разделить на независимые подграфы. Хотя допускаю что такие
несвязные компоненты реально существуют. Но в родительском топике
мы просто находили такие себе сверх-вершины которые имели по сотне связей.
(это популярные артикли и предлоги в литературном произведении).

И можно было если не найти несвязны компоненты - то хотя-бы просто начать алгоритм
с узлов имеющих мощность например больше 50.

Интересно что все методики деления коллекции по хешу например - полезные для мультипоточного
процессинга - в нашем случае бесполезны. Уже на 2 уровне связей нелья ничего гарантировать
в отношении хеша и связности.
16 сен 20, 10:50    [22198162]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80

Для нахождения пар узлов - кандидатов на удаление нужно найти элемент матрицы с установленной 1 на пересечении пустых в других ячейках строки с столбца. Если вычисление строки имеет сложность O(1) (просто взять нужный подмассив), то вычиление столбца - O(n), т.к. нужно пройтись в всем строкам и взять нужый элемент. И получается, что сканирование матрицы для нахождения нужных строк и столбцов имеет квадратичную сложность как минимум плюс еще пройтись по строке и столбцу и проверить что в там есть одна нужная 1 в нужном месте. Короче, все равно медленно.

Если вы посмотрите на граф глазами или на матрицу (не знаю как) то вы обратие внимание что она - очень разреженная.
Состоит из вакуума. Именно поэтому я решил трекать списк incomng/outgoing сввязей чтобы убрать из задачи линейный
поиск пл 50_000 соседенй и свести его тоже к линейному но более быстрому по ИЗВЕСТНЫМ соседям.

Кстати из курса численных методов. Физики и математики любят матрицы плотности как пенопласт.
У них даже есть для этого специальный инструмент Разреженных Матриц https://en.wikipedia.org/wiki/Sparse_matrix

И у меня была вначале идея касающаяся именно этого способа хранения. Но те матрицы ничего мне не гарантировали в плане
быстого lookup соседей. Они просто обеспечивали декартовый доступ по сжатым данным. А это вобщем мне было не надо.
16 сен 20, 10:56    [22198178]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
mayton


По поводу ООП головного мозга и все такое. В родительской задаче ребро - МАТЕРИАЛЬНО. Оно несет нагрузку.
И если в данном топике (в схлопывании) мы действительно можем его закодировать 1 битом то родительском - нет.

Вопрос - делать ли мне спициализированную библиотеку для данного топика или оставить обобщённую? Ну
для меня как-бы очевидно. Оставлю общую.



Ну тут тебе никто не указ. Твоя библиотека - твои правила. Поинт в том, что в ООП сначала мы накидаем модель как ее сходу увидели, а потом превозмогаем, пытаясь решить задачу, используя выдуманные нами же на ходу термины. Это нас ограничивает, нам жаль отказаться от уже с заботой написаных public class Graph implements Serialazable с логгером внутри))). Однако манипулировать примитивами может оказаться намного проще быстрее и экономичнее, чем сложными объектами. К тому же для примитивов с большей долей вероятности существует готовая мат. модель и алгоритмы.

А материальность ребра может быть вражена просто в еще дном числе, строке или наборе чисел и строк в добавок к существующей паре {вершина, вершина}.

IMHO, все эти классы Vertex, Edge, Graph годятся лишь как фасад к манипулированию числами, массивами и прочей низкоуровневой ерундой.

Когда я пытался возиться с матрицами, то пришлось делать некоторую нормализацию, т.е. приведение номеров вершин из исходных данных к индексам столбцов и строк. Т.е. это как всякие свертки и прочие преобразования Фурье и Лапласа в математиве. Мы свою модель приводим к какому-то удобоваримому для решения задачи виду, решаем задачу и разворачиваем обратно, чтобы придти к исходной системе координат. Вот.

Надеюсь на ваше понимание.
16 сен 20, 12:14    [22198296]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
mayton
Хм... пару недель назад я запилил Map<Edge, Edge> в качестве коллекции ребер.
И при этом я точно помню что Set<Edge> меня чем-то не устраивал.

Чьорт побьери... я забыл ЧЕМ!

import static java.lang.String.format;
import static java.lang.String.valueOf;
import static java.util.Collections.unmodifiableMap;

/**
 * Directed, Weight graph
 */
public class Graph implements Serializable {

    static Logger logger = LoggerFactory.getLogger(Graph.class);

    // TODO: Leonid proposes to get rid of Edges instead of primitives.
    private Map<Edge, Edge> edgeWeigthMap;
    private Map<String, Vertex> vertexMap;
    private transient LinkedHashMap<String, Object> statistics;

Основное

По поводу этой загадочной мапы где ключ и значение декларированы как один и тот-же объект.

Мне нужна была процедура поиска ребра в графе по идентификаторам двух вершин.
Например.

@NotNull
    public Edge extractEdgeByIds(@NotNull String id1,@NotNull String id2) {
        Edge keyEdge = new Edge(new Vertex(id1), new Vertex(id2));
        return edgeWeigthMap.get(keyEdge);
    }


Ребро содержит ключевые поля. Такие как v1,v2 - это ссылки на вершины к которому оно прикрепляется.
Это реальные объекты из текущего инстанса графа.

Тоесть по частичной (неполной) информации о ребре надо ивзлечь полную. Именно поэтому вместо

Set<Edge> 


что было достаточно просто и логично я ввел

Map<Edge, Edge> 

где семантика первого генерализованного параметра Edge - просто нужна чтоб заработали алгоритмы
хеш-поиска и уже восстановили ребро в полном наборе атрибутов. Hash-code и Equals соотвественно
работают только по ключевым атрибутам.

Альтернативное решение. Я мог завести синтетический составной ключ ребра типа String и складывать
туда сериализацию вершин в строку например "1->2" но с моей точки зрения это оверхед т.к. в первом
варианте я экономлю на ссылках на Edges без создания доп-объекотв String (напоминаю 260 тысяч ребер)
которые могут подгрузить память.
Map<String, Edge> 


Еще альтерантивное решение. Я мог завести ключ PairOfVertices или Pair<Vertex,Vertex>
но это тоже не давало явного преимущества перед простотой 1 варианта.

А из Set<Edge> нельзя было сделать поиск. Можно проверить contains() и извлечь итератор.
Но поиск по частичным ключам - нельзя.

Что еще

Также ребро содержит доп-атрибуты. В моём случае это weight (вес) но в будущем это будет генерик.
Чтоб добавлять произвольные атрибуты.
/**
 * Directed, Weight Edge
 */
public class Edge implements Serializable, Externalizable {

    static final long serialVersionUID = 2L;

    // Key fields
    private Vertex v1;
    private Vertex v2;

    // Non-key
    private int weight;

    // Displayeable


    public Edge(@NotNull Vertex v1, @NotNull Vertex v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

    public Edge(@NotNull Vertex v1, @NotNull Vertex v2, int weight) {
        this.v1 = v1;
        this.v2 = v2;
        this.weight = weight;
    }
16 сен 20, 12:23    [22198306]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80

Когда я пытался возиться с матрицами, то пришлось делать некоторую нормализацию, т.е. приведение номеров вершин из исходных данных к индексам столбцов и строк. Т.е. это как всякие свертки и прочие преобразования Фурье и Лапласа в математиве. Мы свою модель приводим к какому-то удобоваримому для решения задачи виду, решаем задачу и разворачиваем обратно, чтобы придти к исходной системе координат. Вот.

Надеюсь на ваше понимание.

Я 100% буду подходить к примитивам когда исчерпаю возможности перформанса объектов. Но на данном этапе
такая разработка (на кривой Шипилёва) находится в точке экстремума где код еще на стал "свинским" по отношению
к читающему и можно еще рассуждать об алгоримах. Как вы понимаете когда программист-одиночка занят
глубоким перформансом - он ведет себя как свинья по отношению к тем что собирается глазами этот код
читать.

Да конешно в данном топике самый большой свинтус - это я. Так что не переживайте. А ваш сорс на Scala
я раскурю чуть позже и покрою тестами. Пока я как-бы ничего не могу сказать. Мой код покрыт лишь на
примитивных операциях а схлопывание еще не реализовано.
16 сен 20, 12:29    [22198315]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
Последние сообщения читал по диагонали, но или я не правильно понимаю задачу или Ваш код выглядит слишком просто (т.е. делает что-то не то).

Не очень понимаю, какие правила для того, что бы посчитать что ноды A и B можно схлопнуть и где данная проверка в Вашем коде (scale не знаю) ?
16 сен 20, 13:25    [22198386]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Java Ответить