SQLite быстр с индексами, а DuckDB быстр без них

DuckDB does not seem to work with indices as well as SQLite does but is blazingly fast when scanning large parts of the table.

SQLite is great at using indices but takes its time when it has to look at the whole table.

Benchmarking DuckDB vs SQLite for Simple Queries 

Теория — это сконцентрированный опыт миллионов, собранные, приведенные в систему правильные решения, отброшенные в сторону бессчетные ошибки.

Теория — это молниеносные мысленные эксперименты вместо долгих и дорогостоящих опытов «в металле», быстрый выбор правильного ответа вместо бесконечного слепого перебора и гадания.

Теория — это кратчайший путь к нужному практическому результату.

Из книги Рудольфа Свореня «Электронника шаг за шагом». 2020 г.

Это заметка-напоминалка о пхп-библиотеках, позволяющих найти сингулярное разложение матрицы (SVD — singular value decomposition).

Из Bellegarda (2005) Latent semantic mapping

Наилучший вариант ↓

PHP — Singular value decomposition SVD Влада Колодки.
Без зависимостей. Один файл svd.php.

include "svd.php";

// Конструирую матрицу
$matrix = [['0.00', '0.00', '0.56', '0.56'. '0.00', '0.00', '1.00'], 
           ['0.49', '0.71', '0.00', '0.00'. '0.00', '0.71', '0.00'],
           ['0.49', '0.71', '0.00', '0.00'. '0.00', '0.71', '0.00'],
           ['0.72', '0.00', '0.00', '0.00'. '1.00', '0.00', '0.00'],
           ['0.00', '0.00', '0.83', '0.83'. '0.00', '0.00', '0.00']];

// Создаю класс для работы с матрицами
$matrixClass = new Matrix;

// Вычисляю SVD
$USV = $matrixClass->svd($matrix);

/*
 Получаю ассоциативный массив, в котором M = USV.
 ВНИМАНИЕ: матрица V уже транспонирована.

 $matrices['U'] = $U;
 $matrices['S'] = $S;
 $matrices['W'] = $W;
 $matrices['V'] = $this->matrixTranspose($V);
 $matrices['Rank'] = $rank;
 $matrices['K'] = $k;
*/

// Восстанавливаю исходную матрицу
$input = $matrixClass->matrixMultiplication($USV['U'] ,$matrixClass->matrixMultiplication($USV['S'], $USV['V']));
$input = $matrixClass->matrixRound($input);

Тяжеловесная библиотека ↓

MathPHP — Powerful modern math library for PHP
Огромное число разнообразных функций. Установка через композер.

Полный перечень функций для работы с матрицами.

use MathPHP\LinearAlgebra\Matrix;
use MathPHP\LinearAlgebra\MatrixFactory;

// Create an m × n matrix from an array of arrays
$matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
];
$A = MatrixFactory::create($matrix);

// Basic matrix data
$array = $A->getMatrix();  // Original array of arrays
$rows  = $A->getM();       // number of rows
$cols  = $A->getN();       // number of columns

// Matrix decompositions
// LU decomposition
$LU = $A->luDecomposition();
$L  = $LU->L;  // lower triangular matrix
$U  = $LU->U;  // upper triangular matrix
$P  = $LU-P;   // permutation matrix

// QR decomposition
$QR = $A->qrDecomposition();
$Q  = $QR->Q;  // orthogonal matrix
$R  = $QR->R;  // upper triangular matrix

// SVD (Singular Value Decomposition)
$SVD = $A->svd();
$U   = $A->U;  // m x m orthogonal matrix
$V   = $A->V;  // n x n orthogonal matrix
$S   = $A->S;  // m x n diagonal matrix of singular values
$D   = $A->D;  // Vector of diagonal elements from S

// Crout decomposition
$LU = $A->croutDecomposition();
$L  = $LU->L;  // lower triangular matrix
$U  = $LU->U;  // normalized upper triangular matrix

// Cholesky decomposition
$LLᵀ = $A->choleskyDecomposition();
$L   = $LLᵀ->L;   // lower triangular matrix
$LT  = $LLᵀ->LT;  // transpose of lower triangular matrix

// Eigenvalues and eigenvectors
$eigenvalues   = $A->eigenvalues();   // array of eigenvalues
$eigenvecetors = $A->eigenvectors();  // Matrix of eigenvectors

// Solve a linear system of equations: Ax = b
$b = new Vector(1, 2, 3);
$x = $A->solve($b);

Библиотека для машинного обучения ↓

PHP-ML — Machine learning library for PHP
Не по теме. Не понял, есть ли SVD.

Don’t Repeat Yourself

Нижеприведенный текст взят из комментария к статье на Хабре про конечные автоматы.

Как то у меня эта статья ассоциируется со школьной программой по информатике 30 летней давности. Когда классе в 7м начинается изучение двоичной системы исчисления, но до 11 класса остается совершенно непонятным зачем эта двоичная система исчисления была нужна и как она вообще связана с информатикой.

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

И из 2й системы исчисления школьники прыгали сразу в паскаль, где двоичная система нужна была разве чтобы сложные конструкции с if писать.

Так и в статье перечисляется набор фактов о развитии информатики и конечных автоматов, перечислены основные элементы, но вот как это работает непонятно.

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

А дальше разрозненные факты про машину Тьюринга и отсылка к тому что это разновидность автомата. И далее высокоуровневые автоматные языки программирования.

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

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

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

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

• Космонавт пролетащий сквозь трубу? Но откуда такие огромные конструкции в космосе.

• Устройство для создания искусственной невесомости? А такие есть?

• Фотомонтаж? Не похоже.

В общем для меня это фото — загадка.

Может кто-то знает, что здесь изображено?

—-
Upd. Загадка разгадана.

Игорь Вишня подсказал, что это коллаж Мацея Ребиша (Maciej Rebisz). Он поместил уменьшенного космонавта в сопла ракеты «Союз».

Готова первая версия сайта со списком всех родов диатомовых водорослей.

micro-algae.ru/diatoms/all-genera

Сайт двуязычный. Имеет минималистичный дизайн.

Меню сайта позволяет выбрать способ группировки родов диатомовых:

• макси: по отделам и семействам,
• мини: по семействам,
• роды: только роды без группировки.

Подменю дает возможность увидеть роды из всех подклассов, из одного выбранного подкласса (Bacillariophycidae, Coscinodiscophycidae, Fragilariophycidae), или роды с неопределенным систематическим положением (Undefined).

Это единственный сайт, который показывает сплошной список 1375 родов диатомовых водорослей.

Продолжение следует...

Пространные рассуждения о том, почему был выбраны именно такие ранги высших таксонов, приведены в ВК.

Филогенетическое дерево, построенное по молекулярно-генетическим данным, неустойчиво.

Потому, что:

• если к имеющемуся множеству последовательностей добавить пару десятков новых и перестроить дерево, то это его изменит;
• если мы поменяем способ объединения (группировки) данных, то это тоже изменит дерево;
• если мы возьмем молекулярные данные другого сорта, то и это изменит дерево.

Следовательно, структура филогенетического дерева непостоянна.

Об этом же пишет википедия:

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

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

Как-то коллега заметила, что не знает смысла слова «смарти», значит она не умная.

Я парировал, что знания не есть ум.

Ум — это умение использовать имеющиеся знания и делать правильные выводы на их основе.

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

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

Будьте смарти.

В прошлый раз я вытащил данные о 1375 родах диатомовых из Вормса и рассказал, что их можно сохранить в таблице Экселя.

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

К счастью, у меня есть опыт проектирования структуры БД и создания таксономических информационных систем.

Таксономическая БД

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

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

Более подробно о функциях и устройстве ТБД
можно почитать в заметке

• «Создаем таксономическую базу данных».

и в статье 2018 года:

• Лях А. М., Лелеков С. Г. (2018) Модульная структура таксономической базы данных.

Примеры использования ТБД можно увидеть:

• В коллекции паразитов рыб Мирового океана, разработанной моей скромной персоной)
• У Архипа — библиотеки изображений диатомовых водорослей, который, на данный момент, ушел в неоплачиваемый отпуск.

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

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

После борьбы с сервером Вормса и поиском наиболее оптимального способа получения данных, мне удалось собрать номенклатурную информацию о 1375 родах диатомовых водорослей.

Часть из них невалидна, то есть относится к ошибочным, неверно описанным или синонимичным названиям.

Номенклатура в JSON

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

Поэтому json-файл с данными о таксоне является самодостаточным: он не зависит от других файлов и содержит достаточно номенклатурных данных для определения названия, статуса и положения таксона в иерархическом древе. То есть json-файл это отдельная полноценная запись таксономической базы данных.

Остается преобразовать полученные json-файлы в работоспособную базу.

JSON → Эксель

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

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

Но Эксель мы не сможем нормально использовать на сервере. Поэтому для доступа к данным в вебе потребуется настоящая СУБД.

Для работы мне потребовался список всех известных к настоящему времени родов диатомовых. Вот результаты попыток его получить.

Статьи

Рода диатомовых перечислены в некоторых публикациях. Например, в каталоге родов диатомовых 1999 года

Fourtanier E. & Kociolek J.P. (1999) Catalogue of diatom genera.

Из которого вырос каталог названий диатомовых 2009 года, тех же авторов.

Fourtanier E. & Kociolek J.P. (2009) Catalogue of diatom names.

Но мне нужен электронный список — текстовый файл или отформатированная таблица. Извлечь список из пдф статей — сложная задача. Поэтому этот вариант мне не подходит.

Базы данных

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

Почти все названия диатомовых хранят:

• Альгабейз (algaebase.org),
• Вормс (marinespecies.org),
• Диатомбейз (diatombase.org).

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

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

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

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

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

АПИ

Альгабейз не предоставляет никакой иной официальной возможности доступа к базе, кроме как через интерфейс веб-страницы. Майкл Гури зорко охраняет собранные таксономические данные.

К счастью Вормс — это открытая система. Он предоставляет АПИ для извлечения данных.

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

/AphiaRecordsByTaxonRankID/{ID} 
Get the AphiaRecords for a given taxonRankID (max 50)

Сейчас он возвращает только первые 50 названий (родов). Остальные остаются недоступными.

Картинка сегенерирована Гигачатом

В русском языке скорость мы называем единственным термином — скорость.

В английском для обозначения скорости используются термины speed и velocity. Но их семантика различна.

Speed — это скалярная (числовая) величина, которая обозначает просто скорость движения.

Velocity — это векторная величина (вектор), которая обозначает как скорость, так и направление движения.

То есть когда мы говорим speed, то подразумеваем, что что-то просто двигалось с такой-то скоростью. А когда мы говорим velocity, то, помимо значения скорости, еще указываем направление движения.

Во всех разделах анализа текста.

Рис. I.1 из Miner G. et al. (2012) Practical text mining and statistical analysis for non-structured text data applications

Интересно, фамилия первого автора специально подобрана под содержимое книги или так получилось?

Прокрастинация — это склонность откладывать дела на потом, даже если они важны и срочны. Это происходит, когда человек избегает выполнения задач, предпочитая заниматься чем-то менее важным, но более приятным или удобным.

Белоснежка, нарисованная Франсуа Рока, пример правильно прокрастинирующей принцессы

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

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

Симлер К. Хэнсон Р. «Слон в голове. Скрытые мотивы в повсевдневной жизни.»

Американское математическое общество (AMS) выработало стандарт для классификации разделов математики. Он регулярно обновляется.

https://mathscinet.ams.org/mathscinet/msc

Текущая версия стандарта MSC 2020 включает 97 разделов, подразделы которых перечислены на более, чем 200 страницах.

Приятного изучения.

Если вам понравилась заметка, то вы можете купить мне пироженку, задонатив в телетайп-канале «Математический рок-н-ролл».

Фотограф Лукас Холас. Серия «Портреты животных».

Математический рок-н-ролл

За последние несколько месяцев я опубликовал более 30 классных популярных математических заметок для ВК канала «Ежик в матане». Но ленточное устройство ВК оставляет их активным сутки, иногда чуть больше, после чего они канут в Лету, то есть становятся практически недоступными. Это неудобно.

Чтобы избежать потери заметок, начинаю переносить их в Телетайп, в блог «Матеатический рок-н-ролл».

1. Теперь посты будут всегда доступными, пока существует Телетайп)
2. Блог в Телетайпе содержит уникальные заметки, посвященные необычной математике, описанной доступным языком.
3. За заметки вы можете меня поблагодарить донатом. Это поможет написать новые посты.

Первый пост называется «Оценка средних и карьера Вики». Он содержит краткий обзор различных средних значений.

Это была моя самая первая заметка для «Ежика», благодаря которой стал одни из его пишущих редакторов.

Заходите. Будет интересно.

Математический рок-н-ролл

Целоисчисленная матрица — это матрица, все элементы которой являются целыми числами.

Определитель целоисчисленной матрицы — тоже целое число. (Очевидно же.)

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

Очевидно, что если множество возможных элементов матриц конечно, то и число возможных богемных матриц заданного размера тоже конечно.

Пусть мы ищем среди всех богемных матриц только те, определитель которых равен нулю. Ищем при помощи кода на Питоне. Определитель матрицы вычисляем так:

dt = np.linalg.det( a )

И вот тут возможна ошибка.

Если мы будем выбирать матрицы по условию dt==0, то получим неверный результат.

Using that test (dt==0) Python got the right number of [...] matrices when mdim=2 or mdim=3, but the test dt==0 failed a few times when mdim=4, and (after a long time computing) reported 15,015,617 singular matrices; the true number is 15,099,201. This is because np.linalg.det is computing the determinant from a numerical factoring (which introduces rational numbers and rounding error) and the roundoff error means that sometimes a zero determinant was not being reported as precisely zero.

Правильный результат получится если мы используем условие dt<0.5.

https://computational-discovery-on-jupyter.github.io/Computational-Discovery-on-Jupyter/Contents/bohemian-matrices.html#table-of-results