OCaml (aka Objective Caml), а также прочие ML'и, F#, Coq, etc

ocaml@conference.jabber.ru

Пятница, 27 сентября 2013< ^ >

Конфигурация комнаты

Участники комнаты

GMT+4
[00:12:52] Kakadu вошёл(а) в комнату
[00:17:41] tilarids вошёл(а) в комнату
[00:23:35] tilarids вышел(а) из комнаты
[00:23:49] tilarids вошёл(а) в комнату
[00:26:59] tilarids вышел(а) из комнаты
[00:27:12] tilarids вошёл(а) в комнату
[00:30:17] tilarids вышел(а) из комнаты
[00:30:50] tilarids вошёл(а) в комнату
[00:34:39] tilarids вышел(а) из комнаты: Machine going to sleep
[01:03:05] Kakadu вышел(а) из комнаты
[02:17:39] komar вышел(а) из комнаты: Logged out
[02:17:42] komar вошёл(а) в комнату
[03:12:59] <komar> Кишочки: http://komar.bitcheese.net/ru/tech/инструкция-по-разборке-Runbo-X5
[03:13:08] <komar> Ой, не туда.
[06:26:20] f[x] вошёл(а) в комнату
[07:12:52] ForNeVeR вошёл(а) в комнату
[09:52:47] f[x] вышел(а) из комнаты
[10:13:15] zinid вошёл(а) в комнату
[10:34:34] f[x] вошёл(а) в комнату
[10:40:23] <gds> (вопрос сюда, так как касается моего камлопроекта; а вообще надо не сюда.)
есть у меня направленный граф, задана одна вершина, из которой доступны остальные.  но получение дочерних вершин -- весьма медленная операция.  хочу найти в нём минимальные циклы.  как пооптимальнее бы?  понятно, можно закешировать везде соответствия "вершина -> дочерние", но есть чо поумнее?
[10:40:52] <gds> сериализация взаимно-рекурсивных значений -- ад какой-то.
[10:43:53] <f[x]> ответ - ocamlgraph
[10:44:23] <f[x]> а вообще я не знаю
[10:44:46] <f[x]> я даже не уверен что знаю что такое минимальные циклы
[10:45:11] <f[x]> наверное надо папиры в интернетиках искать - граф прям сильно большой?
[10:45:24] <f[x]> пройти по нему всему и построить кастрированное представление
[10:45:37] <ADEpt> +1
[10:45:51] <ADEpt> потому как все подобные алгоритмы и так сами по себе не дешевые
[10:45:59] <ADEpt> а дорогая базовая операция может вообще все убить
[10:46:11] <f[x]> угу, и кастрация не будет сильно заметна ;)
[10:54:52] <f[x]> прикольный баг сейчас сделал - Old.(i) вместо old.(i)
[10:54:58] <f[x]> фиг заметишь
[10:55:31] <f[x]> в новом камле тут ворнинг наверное будет про unused open
[11:01:43] <aleksey> gds: а пошто тебе минимальные циклы?  а компонент связности не хватит?
[11:01:58] <gds> а вот если циклов мало, то, может, как-нибудь попроще можно сделать?  То есть, я вот обрабатываю вершины, иду в подвершины.  И, может, как-нибудь фиксировать путь, которым иду, помечать вершины, и на основании найденного цикла пытаться его минимизировать?  Если придёт что-нибудь на ум -- сообщите.
[11:02:29] <f[x]> это ты дедлоки искать хочешь что-ли?
[11:02:48] <f[x]> реверс-инжиниринг по чятику
[11:02:50] <gds> aleksey: у меня весь граф связный, если правильно понимаю термин.  то есть, из корневой вершины доступны все остальные.
[11:03:23] <f[x]> точнее наверное задетые рядки в транзакции, а не дедлоки
[11:03:25] <f[x]> угадал?
[11:03:31] <aleksey> компонента связности -- это когда из любой её вершины доступна любая
[11:04:02] <gds> f[x]: я хочу сериализовывать значения на основании их рантайм-представления, но так, чтобы подзначения с типом pers 'a сериализовывались в отдельных блоках.  Но вполне возможна ситуация:
type t = { a : option (pers t) }
let x = { a = None }
let y = { a = Some (mkpers x) }
x.a := Some (mkpers y)
[11:05:46] <gds> а с транзакциями я решил просто, даже упрощённо.  Глобальный лок на запись при коммите.  То есть, в данный момент времени только одна писалка.  Но при этом читать значения у других транзакций будет получаться (когда писалка не пишет в конкретно это значение).  Увидев Unix.lockf, понял, что можно сделать менее гранулярно, чем блокировка файла целиком.
[11:07:15] <gds> aleksey: предлагаешь смотреть, что доступно из каждой вершины, и доступна ли сама вершина из себя?  Если так, то вполне реально таким способом идти.  Но будет ли это достаточно быстро, учитывая, что дочерних доставать долго?  Пока не могу сообразить.
[11:07:36] <gds> да, отвечая на вопросы: граф обычно не слишком большой.
[11:07:57] <aleksey> поиск компонент связности делается за линейное время от количества рёбер и вершин
[11:08:43] <gds> почему именно минимальные циклы хотел -- для n значений будет примерно 2n-1 сериализаций, если они в цикле.  Если без цикла -- n сериализаций.  Ну, тут у меня расклад примерно как у окамла, когда он компилирует взаимно-рекурсивный let rec.
[11:09:33] <gds> aleksey: то есть, можно за O(E+V) получить информацию для всего графа, доступна ли каждая вершина из себя?
[11:10:17] <aleksey> ну да
[11:10:56] <gds> получу, что корень доступен из себя, и всё, 2n-1 будет большим.  Плохо.
[11:12:07] <aleksey> вот тут ссылки на 3 алгоритма: http://en.wikipedia.org/wiki/Strongly_connected_component
[11:14:34] <aleksey> я детям только первый из них рассказываю.  он проще, но требует двух dfs.  если надо быстрее, то на второй надо смотреть
[11:38:17] <f[x]> ADEpt: когда вы там уже женгу зарелизите, а то в мыллисте даже название правильно с первого раза не пишут :) или хотите сделать всё right с первого раза?
[11:38:38] <ADEpt> f[x]: так она ж релизится раз в неделю, как часы
[11:38:50] <ADEpt> https://github.com/janestreet/jenga
[11:39:06] ermine вошёл(а) в комнату
[11:39:13] <ADEpt> или раз в две недели....\
[11:39:33] <f[x]> ну зааннаунсите имелось ввиду
[11:39:42] <ADEpt> она активно пилится
[11:39:56] <ADEpt> буквально на этой неделе были backward-incompatible changes
[11:40:02] <ADEpt> так что анонсировать рановато
[11:40:20] <ADEpt> но я лично omake выкинул на свалку истории уже месяца два как :)
[11:42:16] <f[x]> во скока раз быстрее камлобилда?
[11:42:23] <gds> aleksey: благодарю за информацию.  Первый выкину, он требует построения обратных ссылок, а вот Тарзана (Так!) можно взять.  Буду чесать репу.
[11:42:39] <gds> а каким детям ты рассказываешь?  Учишь кого-то?
[11:42:56] <ADEpt> f[x]: не знаю, не мерял. Оно умеет persistent mode, а  камлобилд - нет, так что скорость не сильно важна :)
[11:43:10] <f[x]> а что это такое?
[11:43:15] <f[x]> висит и постоянно ребилдит?
[11:43:19] <ADEpt> f[x]: ага
[11:43:49] <ADEpt> f[x]: нормально обрабатывая ситуации типа "добавили-убрали .ml, поменяли правила, ..."
[11:44:00] <aleksey> gds: олимпиадников
[11:44:09] <gds> omake тоже висит.  По крайней мере, падвендой.  Но висит в плохом смысле слова.  Надеюсь, у вас будет другой расклад.
[11:44:14] <ADEpt> для работы над кучей близко-родственных фич/веток в одном большом репозитории - самое оно
[11:45:28] <ADEpt> gds: omake - да, типа висит. По при изменении omakefile-ов рестартует сам себя (а у нас рестарт занимает минуты), не может нормально пережевать ситуацию вида "появился mli там, где раньше был только ml", и т.п.
[12:18:10] Typhon вошёл(а) в комнату
[13:09:32] Kakadu вошёл(а) в комнату
[15:54:58] f[x] вышел(а) из комнаты
[19:55:57] <gds> какие же уроды в caml-list.  они спорят со мной!
[20:03:07] f[x] вошёл(а) в комнату
[20:04:31] <komar> Согласен.
[20:05:08] ADEpt вышел(а) из комнаты
[20:33:20] Kakadu вышел(а) из комнаты
[20:44:20] f[x] вышел(а) из комнаты
[21:19:31] zinid вышел(а) из комнаты
[21:57:25] n06r1n вошёл(а) в комнату
[22:03:25] Typhon вышел(а) из комнаты
[22:28:59] n06r1n вышел(а) из комнаты
[22:37:30] ermine вышел(а) из комнаты
[23:03:44] komar вышел(а) из комнаты: Replaced by new connection
[23:03:44] komar вошёл(а) в комнату
[23:40:19] Kakadu вошёл(а) в комнату