В PostgreSQL существует очень удобный механизм рекомендательных блокировок, они же — advisory locks. Мы в «Тензоре» используем их во многих местах системы, но мало кто детально понимает, как конкретно они работают, и какие проблемы можно получить при неправильном обращении.
Рубрика «Алгоритмы» - 50
Фантастические advisory locks, и где они обитают
2020-02-13 в 11:20, admin, рубрики: advisory lock, dba, postgresql, sql, Администрирование баз данных, Алгоритмы, базы данных, Блог компании Тензор, параллельные вычисления
Мой бот для Russian AI Cup 2019
2020-02-12 в 17:08, admin, рубрики: ai cups, codeside, russian ai cup, russian ai cup 2019, Алгоритмы, Блог компании Mail.Ru Group, разработка игр, Спортивное программирование
Так уж получилось, что этот чемпионат стал для меня первым, где я смог занять достойное место, за которое не стыдно, поэтому и статью решил тоже написать только сейчас. Путь, которым я шел к этому месту: 1192-е место на чемпионате 13-го года, 241-е на чемпионате 17-го года, 91-е на чемпионате 18-го года и, наконец, 16-е (и 5-е в песочнице) место на этом.
Читать полностью »
Kaboom: необычный сапёр
2020-02-11 в 8:02, admin, рубрики: Алгоритмы, Блог компании Cloud4Y, логические игры, математика, ненормальное программирование, разработка игр, сапёр, теория игр
В детстве я три раза в неделю по часу-полтора сидел на работе у отца. Меня пускали за компьютер, где из развлечений был лишь сапёр и Paint. Рисовать мне быстро надоедало, зато желание открыть всё поле и не взорваться мотивировало искать новые и новые способы прохождения этой игры. Спустя много лет я случайно наткнулся на интересную статью про клона сапёра, и не мог пройти мимо. Предлагаю и вам ознакомиться с ней. Это история о разработке Kaboom, клона легендарной игры Сапёр с собственной изюминкой.Читать полностью »
Сверхсовременные иммутабельные структуры данных
2020-02-10 в 11:31, admin, рубрики: c++, C++ Russia, immer, jrg-cpp, jrg-immer, Алгоритмы, ПрограммированиеГодами эксперты в С++ рассуждают о семантике значений, иммутабельности и разделении ресурсов за счет коммуникации. О новом мире без мьютексов и гонок, без паттернов Command и Observer. На деле все не так просто. Главная проблема по-прежнему в наших структурах данных.
Иммутабельные структуры данных не меняют своих значений. Чтобы что-то с ними сделать, нужно создавать новые значения. Старые же значения остаются на прежнем месте, поэтому их можно без проблем и блокировок читать из разных потоков. В итоге ресурсы можно совместно использовать более рационально и упорядоченно, ведь старые и новые значения могут использовать общие данные. Благодаря этому их куда быстрей сравнить между собой и компактно хранить историю операций с возможностью отмены. Все это отлично ложится на многопоточные и интерактивные системы: такие структуры данных упрощают архитектуру десктопных приложений и позволяют сервисам лучше масштабироваться. Иммутабельные структуры — секрет успеха Clojure и Scala, и даже сообщество JavaScript теперь пользуется их преимуществами, ведь у них есть библиотека Immutable.js, написанная в недрах компании Facebook.
Под катом — видео и перевод доклада Juan Puente с конференции C++ Russia 2019 Moscow. Хуан рассказывает про Immer — библиотеку иммутабельных структур для C++. В посте:
- архитектурные преимущества иммутабельности;
- создание эффективного персистентного векторного типа на основе RRB-деревьев;
- разбор архитектуры на примере простого текстового редактора.
Машинное обучение на Android
2020-02-09 в 18:12, admin, рубрики: data mining, DataLearner, open source, алгоритм, Алгоритмы, визуализация данных, извлечение данных, искусственный интеллект, приложениеПривет! Представляю вашему внимаю перевод статьи из журнала APC.
Машинное обучение и интеллектуальный анализ данных – это практические разработки ИИ, благодаря которым появляются приложения различных тематик, начиная от воздухоплавания и заканчивая зоологией. Эти процессы чаще всего выполняются в облаке, на ПК или ноутбуке, гораздо реже – в смартфоне.
Однако недавно в Google Play появилось новое бесплатное приложение под названием «DataLearner», с помощью которого можно добывать данные. Оно не требует внешних ресурсов и доступа с полномочиями суперпользователя.
Вычислительные ресурсы смартфонов
Многие ошибочно полагают, что для машинного обучения и добычи данных требуется много ресурсов облачной вычислительной системы или по меньшей мере мощный компьютер. Однако в конечном счёте всё сводится к размеру анализируемых данных и типу машинного обучения, которое вы хотите применить.
У компьютерного обучения есть свои уровни сложности. Если представить, что такая недавно появившаяся техника глубокого обучения, как свёрточная нейросеть (CNN) – это автомобиль с высокой удельной мощностью, то другие техники, например, дерево поиска решений и многие прочие «лесные» методы обучения – это горячие «хэтчбеки». Они показывают отличные результаты, быстры и легки даже при ограниченных вычислительных возможностях CPU.
Читать полностью »
Как работают реляционные базы данных (Часть 1)
2020-02-09 в 16:53, admin, рубрики: algorithms, dbms, rdbms, sql, Администрирование баз данных, АлгоритмыПривет! Представляю вашему вниманию перевод статьи
"How does a relational database work".
Когда дело доходит до реляционных баз данных я не могу не думать, что чего-то не хватает. Они используются везде. Существует множество различных баз данных: от небольшого и полезного SQLite до мощной Teradata. Но есть только несколько статей, которые объясняют, как работает база данных. Вы можете искать сами по запросу "howdoesarelationaldatabasework" («как работают реляционные базы данных») чтобы увидеть, как мало результатов. Более того, эти статьи — короткие. Если же вы ищете последние модные технологии (BigData, NoSQL или JavaScript), вы найдете больше углубленных статей, объясняющих, как они работают.
Являются ли реляционные базы данных слишком старыми и слишком скучными, чтобы их можно было объяснить вне университетских курсов, исследовательских работ и книг?
Визуализация линий напряженности и движений электростатических зарядов, симулирование движения планет солнечной системы
2020-02-09 в 13:14, admin, рубрики: gif-анимация, python, python3, Алгоритмы, астрономия, визуализация данных, красота, физикаПривет, сегодня я хочу вам предложить наглядное пособие по моделированию некоторых физических процессов и показать как получить красивые изображения и анимации. Осторожно много картинок.
Читать полностью »
Самый простой алгоритм для создания Филворда (Часть 1)
2020-02-09 в 12:39, admin, рубрики: c++, Алгоритмы, игры, разработка игр, филвордыПривет. В этой статье я хочу поделиться с вами немного своим опытом и показать вам мой простой алгоритм, который я придумал для создания Филворда.
Под «Филвордом» я буду иметь ввиду эту многим знакомую игру.
В игре есть поле размером обычно NxN заполненное словами. Наша цель — найти все слова.
В нашей версии не будет букв в поле, которые не принадлежат ни одному слову и служат для сбивания игрока, а также не будет букв, которые принадлежат сразу нескольким словам. Обычный классический Филворд. И так, задача поставлена. Нужно решать.
Первым делом я всегда разбиваю задачу на подзадачи. Для решения этой задачи мне понадобится:
- БД со словами.
- Алгоритм, который вставляет слова в поле.
- Алгоритм, который проверяет выбранное пользователем слово на корректность. К примеру мы в поле поместили слово «программирование», а пользователь увидел там «мир» и выделяет это слово. Пользователь прав – такое слово есть, но мы его не загадывали. Нам нужен алгоритм, который будет проверять догадки пользователя и говорить ему прав он или нет.
Все, игра простая поэтому пунктов тоже не много. Начнем выполнять по порядку.
1) БД со словами.
Для решение данной задачи я сделал простую БД с несколькими таблицами, каждая из которых хранит в себе слова определенной длинны. Таблица words_2 хранит в себе слова длинной в две буквы. Таблица words_3 хранит в себе слова длинной в три буквы и так далее. Выглядеть это будет примерно так:
Пример
PRESENT — ультралегкое блочное шифрование (перевод оригинальной статьи PRESENT: An Ultra-Lightweight Block Cipher)
2020-02-08 в 12:48, admin, рубрики: алгоритм шифрования, Алгоритмы, информационная безопасность, криптография, облегченные алгоритмы, перевод с английскогоПривет! Привожу тут перевод оригинальной статьи «PRESENT: An Ultra-Lightweight Block Cipher» за авторством Robert B. Weide Богданова, Лендера, Паара, Пошмана, Робшава, Сеурина и Виккелсоя.
Аннотация
После внедрения AES потребность в новых алгоритмах блочного шифрования резко упала, поскольку в большинстве случаев AES является отличным решением. Однако, несмотря на простоту реализации, AES не подходит для сверх ограниченных окружений, типа RFID меток и считывателей. В данной статье будет описан сверх-легкий блочный шифрующий алгоритм PRESENT. Во время разработки этого алгоритма во внимание были приняты как эффективность воплощения в железо, так и надежность шифровки. В итоге результат системных требований сравним с сегодняшними ведущими компактными потоковыми шифрами.
Читать полностью »
Отложенный Alpha blending
2020-02-07 в 9:30, admin, рубрики: alpha blending, Алгоритмы, Блог компании Playrix, обработка изображений, разработка игрВ этой статье я хочу поговорить о методах смешивания растеризуемой геометрии. Классические модели смешивания полупрозрачных объектов — Alpha, Additive, Multiplicative — объединяет один и тот же принцип отрисовки: последовательно рисуем один примитив за другим, смешивая получаемые на выходе фрагментного шейдера пиксели с тем, что находится в текущем буфере. Каждый новый примитив обновляет область буфера, в которую рисуется; в случае с альфа-смешиванием объекты, которые находятся выше, заслоняют ранее отрисованные. Но что если хочется что-то сделать с группой объектов, рисуемых поверх сцены, — например, обрезать их по маске или подсветить? Тут сразу в голову приходят два решения: или внести изменения в их материал (т.е. изменить шейдер, расширить набор текстур), к примеру, добавив проекцию еще одной текстуры, которая будет отвечать за маску прозрачности. Однако если у нас много разношерстных объектов, менять каждый уникальный материал неудобно и чревато ошибками. Второй вариант — нарисовать все интересующие нас объекты в отдельный полноэкранный таргет и рисовать уже его на финальную сцену. Тут мы можем сделать с его содержимым все, что захотим, но это требует выделения лишней памяти и, что самое неприятное, — переключения рендер таргетов. Это не самая «дешевая» операция на мобильных устройствах, которую будет необходимо выполнить дважды. А если захочется вот так работать с несколькими слоями?
