Category: наука

Category was added automatically. Read all entries about "наука".

with Cat The Cat

Почитывая sibved

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

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

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

Ну, и главная теорема генетических алгоритмов в том, что если у какого-то поведения есть преимущество, после большого количества испытаний оно проявится, как ведущее.
with Cat The Cat

Модуль-банку

Ваш сайт не содержит информации о том, как добраться до вас. В разделе о банке есть что угодно, кроме адресов.

Техподдержка по телефону не может сориентировать на местности - "со стороны Пресненской набережной" не говорит ничего, если не видно этой самой Пресненской набережной. А в Москва-сити её не видно. В результате опоздание на 15 минут превратилось в опоздание на 30.

Опоздание на полчаса критично - потому, что у всех ваших сотрудников всё расписано по получасовым интервалам. Теория о массовом обслуживании говорит, что ресурсы должны быть задействованы на 60% в среднем, чтобы позволять плавно обрабатывать неожиданные события. Но вы об этом не слышали, а ваши сотрудники даже гордятся тем, что не могут обслужить опоздавшего.
with Cat The Cat

Про ГМО.

Скорость возникновения новых продуктов может превысить скорость адаптации к ним.

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

Приспособиться же к помидорам с генами арктических рыб тяжело.
with Cat The Cat

Мой любимый анекдот про дешевизну индийских ученых и программистов.

Один индийский ученый, имя которого я запамятовал, изобрёл замечательный способ улучшения соединений в кластерах. Вместо соединения в кольцо, где требуется всего 1 сетевой контроллер и logN контроллеров для гиперкуба, он предложил соединять машины в стиле распределенной хэш-таблицы. Вот, примерно, вот как здесь: http://www.freedomlayer.org/articles/dht_intro.html

Типа, делаем 2 контроллера и получаем ускорение передачи сообщений в два раза.

Идея похожа, детали отличаются.

Так вот, когда один мой знакомый обратился к нему с предложением побеседовать, сей индийский ученый потребовал (не попросил! потребовал!) $50 000 (пятьдесят тысяч долларов) только за возможность поужинать за предварительной беседой.

(прочитав последнее эссе Поля Грема)
with Cat The Cat

Довольно неправильное мнение об одной устаревшей статье.

Вот тут.

ARIES на самом деле сборник рецептов "как построить хранилище БД" для состояния дел до 1992 года. После 1992 года тоже кое-что придумали. Точнее, пересмотрели то, что уже имеется.

Итак, приступим. Прямое использование B+-tree выгодно, когда вставок либо заметно меньше чтений, либо они часто следуют по порядку возрастания ключа. В противном случае локальность записей становится мала и B+-tree деградирует, даже чтение становится медленным (не из последовательных адресов). Ситуация с большим числом записей не по порядку нормальна для многих задач из жизни и обязательно встретится, если есть хоть какие-то нетривиальные индексы.

Получается, что B+-tree это не совсем динамическая структура данных и что необходимо прибегать к логарифмическому методу. Всё это выливается в структуру типа LSM-дерева. LSM-дерево - набор B+-деревьев увеличивающегося размера, в деревьях большего размера лежат более старые данные, иногда производится слияние деревьев с перезаписью новых данных, если более новая информация переходит некий порог по объёму. При слиянии деревьев данные из нового дерева вставляются по порядку, приводя к лучшей локальности записи и меньшей фрагментации данных.

Что приятно, это то, что логарифмический метод применим гораздо шире, чем хранение индексированных данных в БД. Его можно применить и к данным типа GIS, многомерным структурам поиска. Один пример дан в лекции по логарифмическому методу (диаграммы Вороного), но есть ещё одна медленная структура - k-d дерево. Поиск быстрый, построение медленное. Её ускоряют ровно таким же методом - разбив на несколько уровней.

Что интересно, статья про логарифмический метод 1980 года.

Для поддержания высоких уровней изоляции и возможности всё ещё остаться в своём уме, используется Multi-Version Concurrency Control, MVCC - ведение нескольких структур данных с копированием при записи. При commit транзакции записывается корень новых данных. Ссылка, кстати, ведет прямо на список баз данных, что используют MVCC. При MVCC лог не особо и нужен - можно просто хранить несколько последних корней дерева. Это потребует некоторого переосмысления структуры БД - скорее всего, всё надо хранить в одном файле, - но всё ещё не сложно реализовать.

Последнее про базы - БерклиДиБи на один записанный байт записывает 10 (десять) байт лога.

Про параллельное выполнение транзакций. Если упорядочить транзакции, то выполнение можно сделать детерминированным и легко разделяемым по репликам. Что интересно, лог также упрощается или даже упраздняется. В любом случае он становится высокоуровневым, а не байто-ориенированным, как в ARIES.

По сумме вышесказанного, я считаю, что ARIES сегодня это очень плохо. Используйте что-нибудь другое. Целее будете.

Последнее - про квантовые компьютеры, там в комментариях было "открыли новое". Дам ещё одну ссылку: http://dr-klm.livejournal.com/123882.html

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

И вот ещё. Не всё там гладко. В первых версиях обычные компьютеры вообще побивали D-Wave, даже на симуляции квантовых процессов!

(D-Wave не имеет связей атомов "все со всеми", поэтому он не квантовый компьютер, а "квантовый оптимизатор")

Это я слегка злорадствую, на самом деле. ;)
with Cat The Cat

Про R и атомы.

В процессе не столь давней работы в ParSci, участвовал в обсуждении добавления типов в R или возможности написания библиотечки на Хаскеле для связи с R.

Потому, что в трети (30%) медицинских исследований приводятся выводы типа "у результатов группы 1 p1=0.31, у результатов группы 2 p1=0.29, p1>p2, что ясно доказывает эффективность действия лекарства." То есть, значения p сравниваются напрямую или по порогу (здесь значимо, а тут нет), без вычисления вероятности такого события. Ведь разность в p значениях тоже вероятностна, и вероятность именно такой разницы может быть велика.

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

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

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

PS
В результате им, по-моему, сделали такую библиотеку.
with Cat The Cat

Как ускорить попарную нормализованную корреляцию в тысячу раз.

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

C(si,sj) = sumk=1..L[siksjk/(|si| |sj|)]

Если длина последовательности 1000, а последовательностей тоже 1000, то всего получается 1000*1000*(1000-1)/2=499500000 умножений и чуть меньше сложений. То есть, сложность O(LN2). Здесь L - длина последовательности, а N - их количество

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

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

Хорошие последовательности имеют спектр вида 1/f - "розовый" шум или даже красный шум, с большими низкими частотами и амплитуда частоты (примерно) уменьшается с её возрастанием. Низкие частоты вносят большой вклад в корреляцию, поэтому разумно брать их в качестве существенной части.

Плохие последовательности имеют спектр вида 1 - "белый" шум, где все частоты представлены равномерно. Это производная "красного" шума. Здесь существенную часть выбрать сложно, ведь корреляция по одной частотной составляющей может быть перекрыта любыми другими частотами.

Если говорить о практической пользе, то "хорошие" последовательности наблюдаются в колебаниях цен на продукты, а "плохие" - в "выгоде", (ценаi+1-ценаi)/ценаi.

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

С плохими последовательностями такой трюк не пройдет.

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

Но для них придумали особый подход - проекции на случайные вектора.

Мы генерируем псевдослучайные последовательности, числом M и длиной L, со значениями 1 и -1, и выполняем с ними свертку всех последовательностей. Получается вектор длиной M, sketch vector, набросок.

Так вот, доказано, что расстояние между нормализованными векторами-набросками пропорционально корреляции между последовательностями: D(x, x) = 2(1+corr(x,y)). D - расстояние, x - временная последовательность, x - нормализованный вектор-набросок. Отсекая по расстоянию, мы отсекаем по корреляции. Можно отсечь все с корреляцией менее порога (колебания цены на схожие продукты), можно отсечь все с корреляцией выше порога (конкурирующие компании).

Все. Остались только технические вопросы - как сделать подходящий генератор псевдослучайных чисел, как считать побыстрее в процессе добавления элементов в последовательности и тп. Это, натурально, решается очень просто.
with Cat The Cat

Теория категорий для чайников.

demmonoid поделился ссылочкой.

7-я страница:
Теория категория помогает упорядочить мысли...

...Но совершенно необязательно помогает понять предмет исследования (и даже может мешать)
Тем не менее, надо бы почитать. ;)
with Cat The Cat

Парадоксы.

Что меня ещё интересует.

А есть ли какой способ проверки логической теории на существование в ней парадоксов?

А то меня смущает опыт Агды2. Несмотря на тщательно выстроенную теорию (кандидатская диссертация, ни много, не мало), с проверкой останова, с иерархией вселенных, в ней всё равно отыскали возможность построить противоречие.

Вот нельзя ли это как-то формализовать, что-ли?