Discreet and not discrete.

Дерево слияний в git представляет собой граф, который эквивалентен графу зависимостей возможностей ПО.

Например, если мы сливаем ветки сложный-функционал и тесты-сложного-функционала, и при этом у нас робот проверяет сборку и тесты, то, фактически, в процессе доведения слияния до приемлемого состояния мы выполняем 1) работу по созданию функционала, 2) работу по проверке функционала и 3) работу по отслеживанию требований - нам нужен сложный функционал и нам нужны тесты к нему, чтобы формально его проверить.

Получается, что управление требованиями и планирование можно вести в ветках git/mercurial.

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

Это приводит к простой возможности разделить данные на несколько машин, а также к возможности использовать разные эффективные алгоритмы работы с матрицами, включая оптимизированные алгоритмы умножения матриц (см. hypersparse matrix multiplication и SUMMA).

Здесь мы подходим к необходимости распознавать алгоритмы, записанные пользователем в DSL на циклах, допустим. Ну, это уже было украдено до нас, неоднократно.

Вся индустрия ПО о-ши-ба-ет-ся, особенно, та часть которая "я _________ (датасайнтист/доктор/инженер/финансист - подчеркнуть или вписать), а не программист". Как я уже рассказывал, Amgen обратился в ParSci за решением задачи корректности анализа статистических данных - треть медицинских статей содержала ошибки типа "у эксперимента 1 p=0.04, у эксперимента 2 p=0.038, поэтому мы считаем доказанной гипотезу эксперимента 2" (прямое сравнение p-значений). По идее, отрубив возможность сравнивать p значения напрямую (нет реализации Ord), мы, типами, ограничивали бы возможность допущения ошибок такого типа, получая из Хаскельного кода структуру анализа эксперимента и получения выводов. Они заказали у ParSci библиотеку подключения к R, для использования уже отлаженных и оптимизированных алгоритмов с улучшенными типами, но, как известно, работа ушла на сторону и появился Tweag (если я правильно понимаю).

В дни моего использования Data.IntMap он не был завязан на конкретное представление целого, как ключа. Поэтому его можно было перепилить под меньшее целое (например, 32 бита) и это радикально увеличивало производительность - и мусора меньше, и с кешем получше и, если это кто ещё не знал, 64-битная платформа лучше работает с 32-битными значениями. Поэтому разреженные матрицы связности я хранил в IntMap (IntMap a), что, в сумме позволило обогнать код на Си (clustering coefficients) в десять (10) раз по скорости.

Почему так?

Потому, что IntMap уже сортированные. И их пересечение имеет сложность O(n). При анализе безмасштабных графов вы в обязательном порядке зайдёте на узел со связностью O(количество узлов графа) - так уж устроены эти графы.

Код на Си использовал несортированное представление связности узла - он сперва копировал в буфер, потом сортировал и после выполнял пересечение для сортированных представлений. То есть, при старте с пустого графа выполнялось O(N) сортировок сложностью O(NlogN) для пересечений и O(N) вставок. В сумме сложность была O(N^2logN). При использовании сортированного представления на IntMap мы получаем O(NlogN) сложность вставок и O(N^2) сложность пересечений. Разница на графе в 16 миллионов узлов получилась в десять раз - то есть, код на Хаскеле был медленный (должно было получиться 24 раза), но всё равно быстрее Си.

Что самое приятное, я всё это проделал "не приходя в сознание" - взял сперва Data.Map, потом Data.IntMap, потом поменял ключ в IntMap и вуаля! получил довольно быстро работающую программу.

Вот, вроде, и всё.

PS
История с Tweag уточняется. Может быть, я неправильно помню.

Оригинал взят у vikond65 в Первый Армагеддон

Verilog это 1985 год, на два года позже VHDL, который был основан на языке Ada, принятом в 1979 году.

Для понимания - 1978 это год появления алгоритма вывода типов Хиндли-Милнера, когда в его имени появилось второе имя (первое - это 1968 год). Ada появилась через год после появления ML.

Поэтому Ada имеет структурную систему типов (positive это подмножество integer, или unsigned это такой специально ограниченный std_logic_vector (массив)).

Verilog пошёл по ещё более простому пути - он ВСЁ ЗАШИЛ В ЯЗЫК.

В VHDL есть тип std_logic, состоящий из девяти значений - неопределенного, не подключенного, 1 (буквально - подключение к цепи питания), 0 (подключение к земле), короткое замыкание (соединили вместе 1 и 0), питание через сопротивление, земля через сопротивление, среднее напряжение (как если бы мы смотрели на точку, подсоединённую к питанию и земле через резисторы) и "наплевать" (don't care).

Этот перечисляемый тип позволяет имитировать подключение двух (и более) выходов к одному входу. Таким образом, можно имитировать поведение многофункциональной периферии типа портов ввода-вывода микроконтроллеров.

При желании, в VHDL вы можете создавать свои типы со своими функциями разрешения, например, имитируя протокол самосинхронной логики.

В Верилоге это невозможно.

Не все типы VHDL позволяют соединять два выхода. Например, тип bit (ограничение character: только '0' и '1') так поступать не позволяет. И современная внутрикристальная микроэлектроника тоже не позволяет. Поэтому вы можете написать ядро процессора с использованием bit, bit_vector и соответствующих операций, а периферию описать с помощью std_logic(_vector).

В Верилоге это невозможно. ;)

Вышеуказанное разделение очень важно - положительно, вся современная периферия является аналоговой. Поэтому правильным решением было бы разрешить логику типа bit/bit_vector и периферию моделировать аналогово. Но в во времена создания этих языков на такое не хватило бы всех вычислительных ресурсов мира, поэтому - std_logic и тому подобное.

И если посмотреть на эти языки внимательней, вы поймёте, что такая беда не из-за злого умысла, и не потому, что авторы стандартов не пишут компиляторы. Это потому, что в то время создатели языков не знали и не могли лучшего. При этом создатели VHDL знали чуть лучшее, чем создатели Верилога, которые вообще ленивые сволочи.

А далее изначальные решения проекта языка диктуют направление последующих решений.

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

Немного терминологии.

Любую формулу можно привести к коньюнктивной нормальной форме - конъюнкции дизъюнкций литералов. Конъюнкция - Логическое И. Дизъюнкция - Логическое ИЛИ. Литерал здесь - прямое или обратное значение булевой переменной. x или ~x. Дизъюнкцию ещё можно называть ограничением, именно они ограничивают возможные значения переменных КНФ.

Самый первый алгоритм вычисления выполнимости (Davis-Putnam, DP) делал так называемое разрешение (resolution): если у нас есть в КНФ две дизъюнкции x\/Y и ~x\/Z, то мы можем заменить две эти формулы на формулу y\/z. Здесь x переменная, а Z и Y - дизъюнкции. Алгоритмически это выполняется так: для всех a, содержащих x и всех b, содержащих ~x, выполнить разрешение a и b. Исходные формулы можно убрать. Если разрешение выполнялось для формул вида x\/y\/A и ~x\/~y\/B, то в результате получится тривиальная формула y\/~y\/A\/B - тождественно равная истине.

Если при итеративном применении этого правила мы пришли к пустой дизъюнкции, то формула невыполнима (пример: x/\~x). Если в конце получилась пустая формула (все разрешения завершились тривиально), то формула выполнима. Может также получиться набор независимых формул, в этом случае тоже легко найти решение. Если мы не можем произвести разрешение по какому-то литералу, то по нему нельзя сделать выбор - зафиксируем его переменную в его значении.

Этот вариант требует большого количества пространства.

Второй алгоритм, предложенный Logemann и Loveland (LL в сокращении DPLL), перебирал значения всех переменных КНФ. Зафиксировав значение переменной, он проверял, не выводятся ли значения других переменных из уже зафиксированных и не приводит ли этот вывод к противоречию. Если можно было произвести вывод значений, он производился. Если у нас вывелись два противоположных значения, то это противоречие. При противоречии производился откат, убирались все результаты текущего вывода и фиксированное значение заменялось на противоположное.

Вот простая КНФ: a \/ b \/ c /\ a \/ b \/ c. Если мы зафиксируем значения a=Ложь и b=Ложь, то из первой дизъюнкции выводится c=Истина, а из второй - c=Ложь. Противоречие. Заменив любое из фиксированных значений a и b, мы получим удовлетворяющее присваивание.

Зайдем с другой стороны. Зафиксируем c=False. Вторая дизъюнкция станет тривиально истинной. Останется только первая. Выберем a=Ложь, останется только вывод b=Истина.

Здесь пространство не так важно, зато сложность алгоритма в худшем случае экспоненциальная. Важно, что "в худшем случае". Если мы каким-то образом можем выбирать правильные значения фиксируемых переменных (по структуре задачи, по предыдущему опыту решения похожих задач, наконец, нам подсказали!), то мы можем решить задачу быстрее, чем за полный перебор всех значений.

Это очень важно. Решатель Minisat показывает отличные результаты в категории "Индустриальные задачи" в соревновании решателей булевой выполнимости в частности потому, что он выбирает для новых переменных значение v=Ложь. Оказывается, большая часть задач этой категории имеет решение с ключевыми переменными, равными Лжи. А вот в категории "Случайные задачи" он отстает - там отлично работают системы, что учитывают структуру задачи (решатель march_xx из таких, например) или просто стохастические алгоритмы типа WalkSAT.

В середине 90-х решатель GRASP совершил прорыв - он начал запоминать причины, по которым решатель пришёл к конфликту, добавляя дизъюнкции противоречия (conflict clauses) к задаче. Здесь преследуются две цели - избегнуть в будущем похожей ситуации и автоматически перещелкнуть последнее выбранное значение.

Пример приведу все на том же конфликте выше. Мы установили переменные a=Ложь и b=Ложь и получили конфликт c и ~c. Мы говорим, что мы не должны посетить в будущем такой набор переменных, при котором a=Ложь И b=Ложь. Мы добавляем к нашей задаче ещё одно ограничение - ~(~a/\~b)=a\/b. Последней мы выбрали переменную b, отменяем её выбор. Новая задача a\/b\/c /\ a\/b\/~c /\ a\/b с выбором a=Ложь автоматически выберет b=Истина (третье ограничение) и решение будет найдено.

Это риешение важно ещё и потому, что если мы запоминаем все причины конфликтов, то мы (а) экспоненциально быстрее полного перебора (доказано) и (б) можем начинать с чистого листа и не придём к той же ситуации.

Рестарт перебора с чистого листа позволяет избежать перебора в окрестности заведомо плохого решения.

Современные решатели начинают с чистого листа довольно часто - после нескольких сотен конфликтов. Есть тендениця ещё увеличить частоту рестартов.

Надо далее рассказать про способы выбора ограничений противоречий, а также надо рассказать про реальную реализацию перебора в том же MiniSAT.

Последняя ссылка на сегодня - glueminisat. Это вариант всё того же MiniSAT, только с улучшенным механизмом выбора ограничений противоречий.

Дискуссия.

Могу предложить свою копеечку.

Итак, вы не поверите, представление графа зависит от задачи.

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

Если граф плотный - плотные массивы атрибутов. Хотя это вряд ли.

Если граф меняется часто, то стоит использовать отображения типа Map Int (Map Int a). Персистентная структура защитит вас от ошибок (см. zipper as insecticide), а также позволит выявить параллелизм.

Не стоит использовать индексы узлов, отличные от целых. Бесполезная просадка по производительности.

Я списался с Андреем Михайловичем Степановым, он сказал, что похожий результат опубликовал А.П. Ершов в работе "О сущности трансляции" - журнал Программирование, 1977, 5, с. 21-39.

Когда-то про неё упоминал.

Сегодня съездил в ИТМ, встретился с АМС (Андреем Михайловичем Степановым;), и обогатился новыми знаниями.

Оказывается, АМС (которая вычислительная система или виртуальная машина) выросла из работ по пониманию естественного языка.

Андрей Михайлович сделал программу, которой нв вход подавался текст, а потом можно было задавать вопросы. Сперва программа могла отвечать только "да", "нет", "не знаю" или выдавать объект, который был ответом на вопрос.

Потом она могла создавать предположения и отвечать в их контексте. "Если девушка - это Наташа, а брат инженера - Пётр, то..."

Её на демонстрации был задан вопрос в 30 слов, на который она ответила правильно. Потом руководству ИТМ звонил Гермоген Сергеевич Поспелов и просил отыскать Андрея Михайловича, чтобы тот продиктовал ему этот вопрос.

Основная идея была в том, чтобы соединять-склеивать слова между собой. Поступающие на вход слова сравнивались со склеенными словами на стеке и производилось повторное склеивание. "Игорь и Пётр братья" - "и" объединит Игоря и Петра, "братья" скажет, что Игорь брат Петру и наоборот, а также то, что оба мужчины. "Игорь учится в ФизТехе" означает это же и то, что Игорь - будущий инженер. "Наташа подарила брату Петра книгу" выдаст после склейки слов, что Наташа - женщина, а после склейки с базой знаний - ещё и то, что что она подарила книгу Игорю. И тд, и тп.

Склейка осуществлялась на основе атрибутов, которые образовывали связи.

Это напоминает вывод типов для понимания предложений, но чуть более общего вида. Да ещё и сильно раньше - примерно в районе 1979 года, неподалёку от рождения алгоритма W.

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

Так вот.

Теперь у меня есть три демки АМС - ещё досовских. Также я думаю отсканировать три препринта, что мне дали на время. Демки могу отослать прямо сейчас, о готовности препринтов в электронном виде сообщу.

А также я думаю уговорить Андрея Михайловича рассказать про АМС на MskHUG или совершенно отдельно. Если кому интересно послушать про АМС, не сочтите за труд сообщить об этом. Здесь ли, письмом ли.

Английскую Тигрицу озвучивает Анджелина Джоли. Нашу уж не знаю, кто.

Битва на мосту с Тай Луном. Джоли на каждый удар издаёт отдельный вскрик, даже просто большие движения она озвучивает отдельно. В русской озвучке же удар от удара и от движения не отличить.

Начальный диалог той же битвы - наш Тай Лун говорит в нос. Ну не может великий боец иметь такой голос. У английской озвучке всё в порядке.

По озвучивает мелкий Галустян. Английский Джек Блэк очень даже корпулентен.

Мне очень нравится лицензия, фильмы становятся более понятными. ;)

PS
Ещё там использован КРИК ВИЛЬГЕЛЬМА. О, ужас. ;)
PPS
Об отношении к работе: Dustin Hoffman's contract includes a stipulation in which allows him to do additional voice recording sessions without hindrance should he be unsatisfied with his performance.

"В контракте Дастина Хоффмана был указано, что он может без проблем перезаписывать свою партию, если будет неудовлетворён результатом своих трудов."

zelych сподвигнул. ;)

Я не думаю, что это то, что он хотел, тем не менее, я напишу. Потому, что надо. ;)

( Collapse )