Рубрика «Алгоритмы» - 38

в 10:44, , рубрики: CUDA, gpu, hash table, Алгоритмы, Блог компании Mail.Ru Group, Видеокарты, высокая производительность, никто не читает теги, хранение данных
Простая хэш-таблица для GPU - 1

Я выложил на Github новый проект A Simple GPU Hash Table.

Это простая хэш-таблица для GPU, способная обрабатывать в секунду сотни миллионов вставок. На моём ноутбуке с NVIDIA GTX 1060 код вставляет 64 миллиона случайно сгенерированных пар ключ-значение примерно за 210 мс и удаляет 32 миллиона пар примерно за 64 мс.

То есть скорость на ноутбуке составляет примерно 300 млн вставок/сек и 500 млн удалений/сек.

Таблица написана на CUDA, хотя ту же методику можно применить к HLSL или GLSL. У реализации есть несколько ограничений, обеспечивающих высокую производительность на видеокарте:

  • Обрабатываются только 32-битные ключи и такие же значения.
  • Хэш-таблица имеет фиксированный размер.
  • И этот размер должен быть равен двум в степени.

Для ключей и значений нужно зарезервировать простой разграничивающий маркер (в приведённом коде это 0xffffffff).
Читать полностью »

в 13:35, , рубрики: Алгоритмы, графы, жадные алгоритмы, клики, математика

Доброго времени суток.

В свободное время провёл небольшое исследование.

В теории графов известен жадный алгоритм поиска кликового числа. Далеко не всегда он даёт верный результат. Под катом проводится анализ результатов работы жадного алгоритма при его комбинации с частичным перебором множеств вершин на графах из «DIMACS benchmark set».

Читать полностью »

в 13:07, , рубрики: java, jrg-algorithms, jrg-java, Алгоритмы

Пишем поиск подстроки лучше, чем в учебниках - 1

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

// Для использования String.repeat нужен JDK 11 и выше:
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

Мы ждем, ждем, ждем… По крайней мере, на моем ноутбуке 2015 года c OpenJDK 13 поиск иголки в стоге сена занимает около минуты. Наша старая добрая JVM прошла сквозь десятилетия перформанс-тюнинга, в ней эффективно реализованы интринсики для String.indexOf и так далее. Что же могло пойти не так?

Это начало серии из нескольких статей, любезно предоставленных их автором, Linas Medžiūnas, и изначально опубликованых в блоге WiX Engineering.

Читать полностью »

в 7:52, , рубрики: hydra2020, hydraconf, sptdc, sptdc2020, Алгоритмы, высокая производительность, параллельное программирование, распределенные системы

Theory is when you know everything but nothing works.
Practice is when everything works but no one knows why.
In distributed systems, theory and practice are combined:
nothing works and no one knows why.

Чтобы доказать, что шутка в эпиграфе — абсолютная глупость, мы уже в третий раз проводим SPTDC (school on practice and theory of distributed computing). Об истории школы, её сооснователях Петре Кузнецове и Виталии Аксёнове, а также об участии JUG Ru Group в организации SPTDC мы уже рассказывали на Хабре. Поэтому сегодня — о школе в 2020 году, о лекциях и лекторах, а также об отличиях школы от конференции.

Школа SPTDC пройдёт с 6 по 9 июля 2020 года в Москве.

Все лекции будут на английском языке. Основные темы лекций: persistent concurrent computing, cryptographic tools for distributed systems, formal methods for verifying consensus protocols, consistency in large-scale systems, distributed machine learning.

SPTDC 2020 — третья школа о практике и теории распределённых вычислений - 1
Сразу догадались, в каком воинском звании персонажи на картинке? Я вас обожаю.
Читать полностью »

в 9:55, , рубрики: Алгоритмы, геометрия, математика, праздники, Работа с 3D-графикой

Приближалось восьмое марта, у меня была реализация автоматизированной отрисовки поверхностей сплайнами — почему бы не написать статью с цветами.

Получилось примерно так:

(Почти) Автогенерация цветов - 1

Под катом будет еще, берегите трафик.
Читать полностью »

в 14:19, , рубрики: MEMS, акселерометр, Алгоритмы, Глобальные системы позиционирования, магнитометр, математика, мэмс, робототехника, углы Эйлера

МЭМС акселерометры, магнитометры и углы ориентации - 1

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

Чтобы понять, на какие точности углов мы можем рассчитывать, нужно приложить некоторое количество усилий.

TL;DR: Описан небольшой скрипт для Octave/MATLAB, позволяющий оценить ошибки расчёта углов ориентации по измерениям МЭМС акселерометров и магнитометров. На входе скрипта — параметры датчиков из даташитов (и/или погрешности калибровки). Статья может быть полезна тем, кто начинает использовать инерциальные датчики в своих устройствах. Небольшой ликбез по датчикам прилагается. Ссылка на гитхаб тоже.
Читать полностью »

в 9:22, , рубрики: big data, data science, ERG, redmadrobot, алгоритм, Алгоритмы, Блог компании REDMADROBOT, данные, ИИ, искусственный интеллект, машинное обучение, нейросети, обработка изображений

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

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

Как мы забрали у человека сито и помогли мельнице - 1

В 1949 году советский пилот-геологоразведчик Михаил Сургутанов пролетал над одной из территорий Казахстана (урочище Сарбай) и, взглянув на компас, заметил, что стрелка стала игнорировать Север и зажила своей жизнью. Да, как в кино при обнаружении каких-то магнитных аномалий.
Читать полностью »

в 18:31, , рубрики: MCMC, python, Алгоритмы, Блог компании Издательский дом «Питер», книги, марковские цепи, машинное обучение, Профессиональная литература, статистика

Привет!

Напоминаем, что ранее мы анонсировали книгу "Машинное обучение без лишних слов" — и теперь она уже в продаже. Притом, что для начинающих специалистов по МО книга действительно может стать настольной, некоторые темы в ней все-таки затронуты не были. Поэтому всем заинтересованным предлагаем перевод статьи Саймона Керстенса о сути алгоритмов MCMC с реализацией такого алгоритма на Python.
Читать полностью »

в 14:42, , рубрики: Алгоритмы, машинное обучение, нейросети, университет Райса

image

Разработчики из Университета Райса в Хьюстоне, штат Техас, разработали новый алгоритм машинного обучения, который получил название SLIDE. По их словам, эта схема обучения ИИ будет более эффективна при работе на центральных процессорах, чем на графических. Читать полностью »

в 12:51, , рубрики: Алгоритмы, искусственный интеллект, компьютерные модели, мозг, МТИ, Научно-популярное, нейронные сети, распознавание лиц

imageФото: news.mit.edu

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

1...1020...373839...5060...315
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js