[WT] [Архив]  [Поиск] Главная Управление
[Совместно с Ычаном]
[Назад] [Вся нить] [Первые 100 сообщений] [Последние 50 сообщений]
Ответ в нить [Последние 50 сообщений]
Имя
Animapcha image [@] [?]
Тема   ( ответ в 15681)
Сообщение flower
Файл 
Пароль  (для удаления файлов и сообщений)
Параметры   
  • Прежде чем постить, ознакомьтесь с правилами.
  • Поддерживаются файлы типов 7Z, BZ, BZ2, GIF, GZ, JPG, MO, MP3, OGG, PDF, PNG, PSD, RAR, SVG, SWF, TXT, XCF, ZIP размером не более 10000 кБ.
  • Ныне 2181 unique user posts. Посмотреть каталог
  • Максимальное количество бампов треда: 500
Файл: 148684155914.png-(659.24KB, 720×720, junior_developer_kyon.png)
15681
No. 15681 Закреплено watch    
Здесь можно получить помощь и консультацию по любому языку программирования, в любой сфере разработки. Не важно, программируете ли вы собственного робота, пишете серверную приблуду, интегрируете чужие API, ковыряете игру, или пытаетесь сделать сайт на Wordpress - если аноним что-то об этом знает, он обязательно поможет.

Примеры кода лучше выкладывать в виде ссылок на http://pastebin.com или http://ideone.com
Фронтендные вещи лучше выкладывать на http://jsfiddle.net

Не знаете, какой язык и библиотеки взять для вашей задачи? Вам сюда.
Не знаете, где клиент, а где сервер? Вам сюда.
Не понимаете, что такое ООП? Вам сюда.
Написали код, и не понимаете, почему не работает? Вам сюда.
Обнаружили кусок кода, и не понимаете, как оно вообще могло работать? Вам тоже сюда.
Не знаете, как подступиться к проблеме? Вам обязательно сюда.

Аноним будет стараться дать максимально точный ответ на ваш вопрос и не пытаться предложить вам поменять весь стек технологий только потому что не знает, как решить проблему с тем что у вас есть. Впрочем, если вы забиваете гвоздь микроскопом, аноним постарается вас об этом предупредить.

Чтобы не сбивать новичков с толку, а также не разбавлять полезную информацию мусором, беспредметные споры типа "какой язык / парадигма / библиотека / етц лучше" здесь запрещены.

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

Пополняемая база знаний: http://pastebin.com/AGhLZppH
Cсылки на прошлые нити указывают сразу на архив

Другие тематические нити (не стесняйтесь их поднимать):
Java: >>/dev/13949
Python: >>/dev/14767
Сайтостроение: >>/dev/13701
Ren'Py: >>/dev/14429
Upwork: >>/dev/14444

Архив нитей:
http://410chan.org/dev/arch/res/14160.html

Прошлая нить пока тонет тут: >>/dev/14160
129 сообщений пропущено. Показаны 50 последних сообщений Развернуть все изображения
No. 16326    
>>16325
Чтобы решить, какой из вариантов лучше, придется оценить объем данных, возвращаемых запросом. Допустим, в примере с файлами. Сколько весит одна строка таблицы этих самых файлов? Вряд ли много: айдишник картинки, оригинальное название, вес, размеры, трудно еще что-то придумать. То есть это считанные байты. Дальше, сколько картинок в среднем приходится на один пост? Это проще оценить, зайдя на уже существующую борду с множественным прикреплением. Пропущено ХХ постов/УУ файлов в помощь. Вангую небольшое число, в пределах 1-2. А сколько в среднем постов в треде? Скорее всего, что-то в районе бамплимита, то есть несколько сотен.
В итоге для треда с N постов: в первом варианте выполнятся N запросов, каждый из которых вернет 1-2 строки, плюс запрос с самими сообщениями (допустим, 500 строк).
Вариант второй: пишем запрос с джойном, который вернет и посты, и файлы. На каждый пост теперь придется по 1-2 строк, итого один запрос на, в худшем случае, 1000 строк. Прибавка в весе строки небольшая: в подчиненной таблице несколько легких полей.

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

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

Тут голый sql не подходит принципиально. Гугли ORM, именно он решает эти задачи.
No. 16327    
>>16326
>код, выводящий результаты такого запроса, выглядит очень костыльным.
Угу. И нарушает принципы инкапсуляции: по-хорошему, про эти картинки (или что там у нас) вообще должен знать лишь код, отвечающий за вывод поста, а вся остальная программа этим заморачиваться не должна.

>Гугли ORM
Погуглил.
Хм… Если третьим вариантом решения будет заменить самодельный костыль на фабричную инвалидную коляску…
Пожалуй, вспомню-ка я слова классиков про преждевременную оптимизацию, и откачусь пока на первый вариант. А в эту сторону смотреть буду, лишь если при его использовании скорость генерации страницы превысит… ну, скажем, 0.5 секунды.
Но за само озвучивание варианта — спасибо! Очевидно, что в по-настоящему сложных случаях нужно использовать именно его.

Also, если брать пример с картой ответов, то там, как мне сейчас кажется, джойном не обойдешься, придётся делать вложенный запрос (таблица кросс-линков будет иметь две ссылки на таблицу постов). Так что в нём — как бы, наоборот, от такой "оптимизации" дольше не получилось…
No. 16328    
>>16327
>фабричную инвалидную коляску
Очень точно замечено, но других способов подружить базу данных и ООП не наблюдается. С другой стороны, в таких фреймворках есть кеширование, и если его нормально настроить, немалая часть запросов вообще не будет дергать базу.

>пример с картой ответов
Джойна как раз хватит как для получения списка постов, на которые ссылается текущий, так и списка ответов на него. Тебе же нужны только ссылки на связанные посты, а не они сами. Однако, тут уж точно придется выполнять по запросу на каждый пост, и стоит подумать о том, важна ли такая "правильность" базы в ущерб скорости.

Алсо, быстродействие сайта обеспечивается далеко не только оптимизацией запросов. Можно, например, сделать серверный рендеринг в html и кеширование некоторых страниц. Не уверен, что это хорошо подходит для борды, но знать про такой способ стоит.
No. 16329    
>>16328
>Однако, тут уж точно придется выполнять по запросу на каждый пост
Эм… Навскидку, я вижу для ссылок на все посты данного треда (для простейшего случая, когда доска у нас только одна) примерно вот такой запрос (в sql "плаваю", вполне мог наложать):
select refs.post_to, refs.post_from, posts.thread_id from refs, posts 

where refs.post_to in 
        (selectpost_id from posts where thread_id = ?) and 
    posts.post_id = refs.post_from;

Но он, мне кажется, тормозить будет сильно.

>Не уверен, что это хорошо подходит для борды
AFIAK, как раз борды что-то такое используют очень активно. Треды генерятся один раз при написании поста, а дальше отдаётся готовый html. И как раз здесь, кстати, карты ответов, если их вдруг добавить, малину могут попортить сильно…
No. 16330    
>>16325
>в процессе обработки постов обращаемся к этой структуре и извлекаем данные уже из нее.
Оптимизация, Стиви, используй её!
Посты в треде идут как? По порядку. ORDER BY в запрос таблицы ссылок прописать можно? Можно. Иди по порядку и запрашивай информацию по востребованию.
А данные в памяти за тебя либа похранит.

>>16326
>код, выводящий результаты такого запроса, выглядит очень костыльным.
Код, который будет ожидать переменное количество аргументов от БД тоже будет костыльный. А можно просто няяяшно яравнивать RID первой таблицы и цапать/дописывать на живое или загонять в массив только нужное и передавать все остальные аргументы в нетронутом виде.

>>16329
>И как раз здесь, кстати, карты ответов, если их вдруг добавить, малину могут попортить сильно…
Если их присобачивать через жабаскрипт, то не очень.
No. 16332    
>>16329

Я для свой имидж борды делал так:

у меня было две таблицы.

TABLE thread

id
post_id

TABLE post
id
thread_id
text
refs
time

в refs я хранил hstore или аналог записей(много записей в одной ячейке)

когда достовал тред делала так

SELECT * FROM post AS ps
JOIN tread AS tr
on tr.id = ps.tread_id and tr.id = ?
order by time

и дальше работал с этим

По поводу рефов, когда кто-то постил >>NUM
я это парсил, и обновлял пост, когда заносил другой пост в базу.

и того когда я рендерил посты, я просто достовал для каждого поста список рефов, и формировал жаваскриптовые ссылки.

Алсо, в SQL не нужно использовать WHERE IN (большое количество элементов) так как это накладывает нагрузку на базу пропорционально кол-во элементов. Лучше ее заменить.

По поводу оптимизации базы. Держим базу на быстрых дисках, и по больше кешей в памяти, правильно указываем индексы и ключи, и тогда все будет шустро пока в таблице не будет около ляма записей(зависит от ресурсов, но как бы в 2017 можно положить).
No. 16333    
>>16329
Да, действительно, можно. Мне что-то пришло в голову, что кросс-линкинг должен действовать в обе стороны, а нужен-то только список ответов, так что от задачи с файлами вообще отличий нет. Кстати, джойном можно сделать то же самое: SELECT refs.post_to, fr.post_id, fr.thread_id FROM posts to JOIN refs ON refs.post_to = to.post_id JOIN posts fr ON refs.post_from = fr.post_id WHERE to.thread_id = ?. Какой из запросов будет быстрее - вопрос открытый. Правда, получившийся список придется разбирать, чтобы ответы на пост показать под самим постом. Впрочем, если ответы надо просто перечислить, можно написать запрос с group_concat().

>Треды генерятся один раз при написании поста, а дальше отдаётся готовый html. И как раз здесь, кстати, карты ответов, если их вдруг добавить, малину могут попортить сильно…

Ээ... Так страницу все равно придется перестраивать при добавлении нового ответа в тред, не? И карты ответов лишних затруднений не создадут.
No. 16335    
>>16330
>Код, который будет ожидать переменное количество аргументов от БД тоже будет костыльный
ЯННП. Говорилось о том, что вывести результат запроса к файлам/рефам одного поста проще простого, а всего треда - нет. Можно объяснить понятнее?

>>16332
Загуглил hstore. Это фича постгреса, в mysql ее заменить особо нечем.
No. 16336    
>>16335
Так хрони строку с пробелами, потом парси кодом, видел такое в Продакшене, на дохрена юзеров
No. 16337    
>>16335
>Можно объяснить понятнее?
Можно: как бы бы не вызывались рефы, впихивать это вовнутрь страницы будет боль: либо впихивается готовый пост целиком, для чего нужен костыль-обёртка при запросе, либо сначала впихиваются посты, а потом надо как-то допихнуть ссылки, что тоже костыль.

Сферическое в вакууме "запросить только ссылки для одного поста и ничего с этим не делать" никому не нужно.
No. 16338    
>>16333
>Так страницу все равно придется перестраивать при добавлении нового ответа в тред, не?
При добавлении нового ответа в любой тред, если он ссылается на наш. При условии, что мы, конечно, хотим обеспечить работу нашей карты ответов на уровне всей борды, а не только отдельного треда.
No. 16339    
>>16333
И да, твой вариант запроса почти наверняка будет быстрее, потому что в моём (из >>16329) оно, как показали тесты, не хочет использовать никакие ключи с результатами вложенного. Выше, вон, говорят (>>16332), что с WHERE IN ключи и не должны работать. Надеюсь, с твоим вариантом такой фигни не будет.
No. 16340    
>>16332
Не лучше ли будет посмотреть в сторону NoSQL хранилища? Типов данных мало связей почти нет.
No. 16341    
>>16336
Вообще говоря, это нарушение атомарности данных. И проявится оно как только кто-то удалит свой пост. Каскадное удаление для такого поля, естественно, настроить нельзя, и чтобы убрать ссылки на "мёртвый" ответ, придётся делать отдельный запрос по всем постам, да ещё и с LIKE, и вручную изменять эту строку.

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

>>16338
Такое обычно при перекатах делают. Вряд ли это скажется на производительности, ибо будет вызывать нечасто.

>>16339
Пустил ради интереса на похожей структуре оба запроса, так мускуль вложенный запрос сам оптимизировал так, что он совпал с запросом с джойнами.
No. 16342    
>>16341
>Вообще говоря, это нарушение атомарности данных. И проявится оно как только кто-то удалит свой пост. Каскадное удаление для такого поля, естественно, настроить нельзя, и чтобы убрать ссылки на "мёртвый" ответ, придётся делать отдельный запрос по всем постам, да ещё и с LIKE, и вручную изменять эту строку.

Хм действильно. Про удаление поста я не подумал. Думаю тогда в следующей итерации борды буду держать буду отдельную таблицу для рефов.
No. 16351    
Немного статистики.

>>16325
Вариант 2 по сравнению с вариантом 1 на моих тестах даёт выигрыш примерно вдвое.

>>16341
>мускуль вложенный запрос сам оптимизировал
В ситуации, когда учитываются доски, т.е. ключём служит пара (post_id, board_id) он у меня это сделать не смог. Соответственно, >>16333 обгонял по скорости >>16329 почти на порядок.

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

>>16327
>нарушает принципы инкапсуляции
Чтобы этого избежать, заводим под это дело отдельный класс (который, очевидно, скоро станет деревом классов), который скрывает от приложения тонкости работы с базой и берёт на себя… wait, мы только что начали делать на коленке свою собственную реализацию ORM.
No. 16352    
>>16351
>Плохая идея.
На самом деле здесь два подхода: произвольный и последовательный доступ к данным. Последовательный доступ обычно используется, если произвольный слишком дорог.

Но в нашем случае затраты на обеспечение произвольного доступа минимальны (но, всё же, не строго нулевые). Вопрос: должны ли мы его обеспечить изначально, если в приложении мы пока можем обойтись последовательным (а затраты на переделку его в будущем будут выше)?
No. 16353    
>>16351
>обязательно в том порядке, в котором они идут в посте
Где ты это там увидел?
Есть реляция X
post_ID->post_stuff
, что, кроме странных случаев, и так с
AUTOINCREMENT PRIMARY KEY
по
post_ID
. Есть реляция Y
post_ID->repy_post_ID
, что тоже, по идее, заполняется инкрементивно по второму параметру.

Когда мы хотим взять информацию о посте с ответами, то
SELECT * FROM X (WHERE ...) AS T; SELECT * FROM Y WHERE post_ID in T.post_ID;

repl=fetch(Y)

while post=fetch(X);

  // Add post details

  while repl and repl.post_ID == post.post_ID:

    // Add reply details

    repl=fetch(Y)


Чем это более связано джойна с последующим выгребанием нужных данных?

>>16341
>И проявится оно как только кто-то удалит свой пост
А если вместо статики пересчитывать строку через тот же concat()?
В конце-концов, можно в самой БД написать функцию, что при запросе будет выдавать посты со всеми ответами в строковом значении.
No. 16354    
>>16353
Сорри, только сейчас заметил, что написал.
Фикшу:

>>16351
>в котором они идут в посте
в котором мы их получили в исходном запросе
No. 16357    
>>16351
>В ситуации, когда учитываются доски
В принципе, то, что вложенный запрос при возможности автоматически преобразовался в джойн, как раз и говорит о том, что последний лучше.
>еще одно нарушение инкапсуляции
При любой работе с результатом запроса напрямую все равно будет получаться процедурный код, а не ООП. При попытке соблюсти ООП - самопальный кривой ORM. Других вариантов нет.

>>16353
>А если вместо статики пересчитывать строку через тот же concat()?
В том смысле, что реально схему ответов хранить в отдельной таблице, а в таблице постов хранить что-то вроде кешированного результата запроса к таблице ответов? Возможно, но придется отслеживать изменения в рефах и обновлять это поле. Делать это в коде в одной транзакции с удалением/перемещением/добавлением поста? Будет работать, но это, вообще говоря, возложение нетипичной функции на логику. Правильно было бы это делать в хранимой процедуре, но я сильно сомневаюсь, что они разрешены на обычных хостингах.

Родина им дала реляционные БД - связывай, нормализуй данные. Не хочу, хочу в них nosql делать.
No. 16358    
Файл: 14940504616.png-(309.04KB, 750×1000, 4d723b2427a0f6253b6ee5ed2e906b49.png)
16358
Какой посоветуете си-подобный скриптовый язык для написания гуев? Хочу чтобы язык был не дохлый, и чтобы была нормальная документация. И чтобы оно было в репах Дебиана.
No. 16359    
>>16358 А попробуй tcl/tk. Он не С-подобный, но всё остальное подходит.
No. 16361    
>>16359
Это шутка? Я немного погуглил, и нагуглил libgtk2-perl и даже libgtk3-perl, похоже оно мне какраз, правда примеры еще не смотрел.
No. 16362    
>>16361 Шутка в чем? Tk сделан для gui специально, скриптовей некуда.
No. 16363    
Файл: 149407194123.png-(28.38KB, 90×128, coverimage-90x128.png)
16363
Анончики, дорогие мои, есть у кого-нибудь gchandbook.org в электронном виде? Жаба душит 80$ отдавать.
No. 16364    
>>16362
Слышал что tk это нечто старое и ужасно выглядящее. Да и синтаксис не сишный, а мне бы сишный.
No. 16365    
>>16364 Ну как бы выбранный Перл тоже не С-подобный.
No. 16366    
>>16363
Заходи на fex.net
Вводи ключ 785192433606

По идее это та книга которую ты хочешь. Там epub.
Если не получится, то сделаю тебе раржпег.
No. 16367    
>>16365
Ну он, ИМХО, среди интерпретируемых языков, наиболее си-подобен.
No. 16374    
Файл: 149409579846.jpg-(11.65KB, 256×256, 1405174852147.jpg)
16374
>>16366
Спасибо огромное, анончик! Она самая.
No. 16378    
Стив, помоги мне понять, как грамотно написать реализацию простой транспортной сети(требуется только находить в ней мин.поток). Пишу на джаве, так как требуется gui, с ним то я, как раз, дружу, в отличии от графов.
No. 16379    
>>16378
Вот тебе пример реализации такой сети (вообще она flow network):
http://algs4.cs.princeton.edu/64maxflow/FlowNetwork.java.html
Зависимости:
http://algs4.cs.princeton.edu/64maxflow/FlowEdge.java.html
http://algs4.cs.princeton.edu/64maxflow/Bag.java.html

Вообще она используется здесь http://algs4.cs.princeton.edu/64maxflow/ чтобы найти
maximum flow / minimum s-t cut. Но по идее реализация сети есть реализация сети, и ты с ней что захочешь сможешь сделать. Скажи если вдруг не подойдет.
No. 16380    
>>16379
Спасибо, попробую разобраться.
No. 16389    
Добрый вечер. Это все я последний вопрос про транспортные сети. Я понял, что у меня проблемы и я нуждаюсь в человеке прерастно владеющим js, знакомым с графами и желательно библеотекой d3. Если кто-нибудь может помочь не за спасибо конечно отзовитесь. Главное, что реально помощь нужна.
Отпишитесь, если можете, буду очень благодарен.
Кода там 150 строк собсно.
No. 16390    
>>16389
Напиши тут что нужно сделать.
No. 16393    
>>16390
Есть 140 строчек кода на js который выполняет поиск максимального потока в транспортной сети. Нужно его разобрать и переделать под поиск минимального потока. Ну или хотя бы пояснить мне че да как в нем работает.
No. 16394    
>>16393
Найди компаратор, поменяй знак.
No. 16395    
>>16389
>>16393
Я порылся еще, и мне кажется, что от тебя хотят чтобы ты решил т.н. задачу "Максимального потока минимальной стоимости". По крайней мере вот человек просит ему помочь найти минимальный поток в графе (а транспортная сеть - это граф): http://stackoverflow.com/q/18598399
>In the literature this is a minimum cost flow problem.
Принятое предложение http://stackoverflow.com/a/19963452 также совпадает с одним из решений задачи максимального потока минимальной стоимости.

Вот реализация решения такой задачи на Java:
https://archive.is/20130124171045/sites.google.com/site/indy256/algo/min_cost_flow

Ты можешь как-то уточнить, что это именно то что от тебя хотят?
No. 16399    
>>16394
Там не все так просто. Там алгоритм немного другой. А точнее измененный.
>>16395
Нет, именно минимальный поток. Алгоритм его поиска есть в "кофман - введение в прикладную комбинаторику" на 370 страничке, если меня не подводит память.
No. 16400    
>>16399
Вот сама функция которая ищет максимальный поток.
vs -vertex set и es edge set соответственно.
https://hastebin.com/nisaveciqo.js
No. 16413    
>>16399
>>16400

Давай попробуем сравнить два алгоритма по твоей книжке (максимальный и минимальный) и то что делает жаваскрипт.

Первый шаг в поиске максимального потока: найти любой поток, удовлетворяющий ряду условий. Можно взять нулевой поток.
Первый шаг в поиске минимального потока: найти любой поток, удовлетворяющий другому ряду условий. В частности, для всех дуг на пути поток через них должен быть >= их емкости.
Что делает жаваскрипт? Насколько я понимаю, он берет именно нулевой.
No. 16414    
>>16399
>>16400
>>16413

Второй шаг в поиске максимального потока: найти полный поток. Для этого искать пути, все дуги в которых не насыщены, и увеличивать поток через них до насыщения хотя бы одной. Повторять пока не останется путей со всеми ненасыщенными дугами.
Второй шаг в поиске минимального потока: найти полный поток. Для этого "уменьшать поток, идущий через дуги от входа к выходу". Очень непонятный шаг, к которому не то что бы давали какие-то объяснения.
Что делает жаваскирипт? Он начинает искать пути с ненасыщенными дугами и по ходу дела помечает пройденные вершины. Это инициируется в мейн лупе, вызовом:

  while (path = findAugmentingP(rG)) {
    augment(path, rG);
    logState(rG, path);
  }

findAugmentingP(rG)
- это и есть поиск пути с ненасыщенными дугами. Эта функция ищет ненасыщенные пути, и заодно помечает пройденные вершины. Как только она находит "ненасыщенный" путь, мы переходим в тело цикла и жаваскрипт сразу пытается насытить в таком пути хотя бы одну дугу, вот в этой функции:
augment(path, rG)

Тут жаваскрипт проходит все дуги, смотрит сколько у них осталось емкости до насыщения, и выбирает минимальную остаточную емкость:

var b = bottleneck(path.slice(0), rG);

Потом он просто повышает поток на всём пути на это значение, чтобы насытить дугу:

    path.forEach(function(v) {
      if (u === v) {return;}
      ...
      fEdge.flow += b;
      bEdge.flow -= b;

      u = v;
    });

И так до тех пор пока таких путей не останется.
No. 16415    
>>16399
>>16400
>>16414

Третий шаг в поиске максимального потока: собственно найти максимальный поток. Для этого помечаем + все вершины, у которых есть ненасыщенные дуги и - все вершины у которых есть дуги с ненулевым потоком. Если в этот список попадает и выход, то находим путь до него, в котором все вершины помечены и увеличиваем там поток на некоторое вычисляемое значение. Повторяем этот шаг заново, пока выход попадает в список помеченных вершин.
Третий шаг в поиске минимального потока: собственно найти минимальный поток. Для этого помечаем + все вершины, у которых есть дуги с потоком, превышающим емкость и - все остальные вершины на пути. Если в этот список попадает и выход, то находим путь до него, в котором все вершины помечениы и уменьшаем поток через него на неуказанное значение. Повторяем этот шаг заново, пока выход попадает в список помеченных вершин.
Что делает жаваскрипт? У жаваскрипта третий шаг скомбинирован со вторым. Также в коде для этого выполнена оптимизация.
Обрати внимание на эти строчки и комментарии:

      // Consider edges which have nonzero residual flow.
      var es = rG.get(u).filter(function(e){return e.flow>0;});
      ...
      // return the min residual capacity of any edge on the path.
      ...
      if (edge.flow < min) {min = edge.flow;}

Т.е. автор кода говорит, что во flow он держит не просто поток через дугу, а конкретно остаточный поток. Т.е. то, что осталось "добить" до насыщения дуги.

Вот в этом куске, упомянутом в шаге 2 он повышает поток на дуге до насыщения, по правилам описанным в шаге 3:

    path.forEach(function(v) {
      ...
      fEdge.flow += b;
      bEdge.flow -= b;
      ...
    });

No. 16416    
>>16399
>>16400
>>16415

Основная проблема с поиском минимального потока в том, что он плохо описан в книге.
Это французская книга 68го года, переведенная на русек в 75м году. И либо автор что-то не дописал, либо переводчики нормально не перевели то что сами не поняли. Даже пример на поиск минимального потока расписан гораздо менее детально, чем пример для поиска максимального. Вместо нормального объяснения постоянные отсылки к плохо определенным правилам и "легко увидеть, что".

Теперь перейдем к тому, как жаваскрипт генерирует граф для прохода.


var rG = initResidual(vs,es)
...
  function initResidual(vs,es) {
    var g = d3.map(),
        outgoing,
        incoming;

    vs.forEach(function(v) {
      g.set(v.id, []);
    });

    es.forEach(function(e) {
      var bEdge = {target: e.target.id, flow: e.capacity};
      var fEdge = {target: e.source.id, flow: 0};

      outgoing = g.get(e.source.id) || [];
      outgoing.push(bEdge);

      incoming = g.get(e.target.id) || [];
      incoming.push(fEdge);

      g.set(e.source.id, outgoing);
      g.set(e.target.id, incoming);
    });

    return g;
  }


В частности, как инициализируются дуги:

      var bEdge = {target: e.target.id, flow: e.capacity};
      var fEdge = {target: e.source.id, flow: 0};

Как мы видим, у обеих дуг не указывается емкость, потому что под flow подразумевается всегда остаточный поток. Поэтому исходящей дуге всегда выставляется остаточный поток равный ёмкости, а входящей 0.

Надо ли это как-то адаптировать к поиску минимального потока - не очень понятно. Еще надо понять, что ж нам надо-то с дугами делать.
No. 16417    
Файл: 149531843428.jpg-(28.14KB, 640×480, azumanga15007.jpg)
16417
>>16399
>>16400
>>16416

Дальше только тупые предположения.

Возможно, остаточный поток через исходящие дуги надо задать отрицательным (потому что они все перенасыщены), при этом на входящие оставив 0.

Если теперь нам надо помечать перенасыщенные вершины, а не вершины с ненулевым потоком, то возможно условие
var es = rG.get(u).filter(function(e){return e.flow>0;});

Надо заменить на
var es = rG.get(u).filter(function(e){return e.flow<0;});


Если все дуги изначально перенасыщены, то возможно, что нам надо снижать поток через них до их ёмкости. Т.е. вместо

    min = parseFloat('Infinity');
    ...
    if (edge.flow < min) {min = edge.flow;}
    ...
    return min;

Написать

    max = parseFloat('-Infinity');
    ...
    if (edge.flow > max) {max = edge.flow;}
    ...
    return max;

А вот это

    es.forEach(function(l) {
      var edge = rG.get(l.target.id).filter(function(e) { return e.target === l.source.id})[0];
      l.flow = edge.flow;
    });

    // Display the max flow
    var sinkIncedent = rG.get(1);
    var total = 0;
    sinkIncedent.forEach(function (e) {
      total += e.flow;
    });

Заменить на

    var total = 0;
    es.forEach(function(l) {
      var edge = rG.get(l.target.id).filter(function(e) { return e.target === l.source.id})[0];
      l.flow = l.capacity + edge.flow;
      if(l.target.id === 1) {
          total += l.capacity;
      }
    });

    // Display the max flow
    var sinkIncedent = rG.get(1);
    sinkIncedent.forEach(function (e) {
      total += e.flow;
    });


Но я крайне сомневаюсь что оно так будет работать.
No. 16420    
Попробую еще тут спросить.
>Ни кто не сталкивался с таким? Использую в приложении chromium web view версии 58.0 на Android 6. Загружаю в него локальную страницу с формой, скриптом на js и рекапчей. В рандомный момент (иногда сразу иногда через пару часов работы приложения) после загрузки страницы перестают работать кнопки (input) и не нажимается галочка на рекапче. При этом нет никаких сообщений в logcat и консоли JavaScript. Обновление страницы или повторная загрузка не помогают. Пересоздание webview тоже не помогает. Баг исчезает только после полного перезапуска приложения.
No. 16421    
Как на MySQL написать оракловскую конструкцию
datetime_column >= trunc(add_months(current_date,-1),'mm')

and datetime_column < trunc(add_months(current_date,2),'mm')

No. 16422    
>>16421
Если перекладывать её дословно, то можно вот так:

datetime_column >= DATE_ADD(LAST_DAY(DATE_SUB(NOW(), 2, MONTH)), 1, DAY)
datetime_column < DATE_ADD(LAST_DAY(DATE_ADD(NOW(), 1, MONTH)), 1, DAY)

Как видишь, поскольку в MySQL проще получить последний день месяца, чем первый, то делается слегка наоборот.
No. 16423    
>>16422
Послал тебе лучей бобра, завтра попробую. А то у меня нет нормального доступа к базе, только лагучая приблуда на java.
No. 16424    
>>16420
Я бы посоветовал обмазаться дебагом сильнее. Повесь на все возможные рабочие события коллбеки, который будут плеваться в console.log, банально по всяким тач-ивентам, клик-ивентам и т.д. И потом включай удаленный дебаг по кабелю и смотри что происходит когда приложение "подвисло" - дергаются ли вообще события эти или нет, ну и всякое такое. На основании этого можно будет уже дальше дебажить. Ибо webview в целом (и ведра в особенности) это боль и там вагон и тележка потенциальных проблем может быть.
[Назад] [Вся нить] [Первые 100 сообщений] [Последние 50 сообщений]

Удалить сообщение []
Пароль  
[Mod]