Pull to refresh
72
0

Пользователь

Send message

Пишем обобщённую хеш-таблицу с открытой адресацией на чистом C

Reading time 28 min
Views 16K

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

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

К разработке этой библиотеки и написанию статьи меня натолкнуло отсутствие незаброшенной библиотеки эффективных хеш-таблицы для C.

Читать далее
Total votes 30: ↑26 and ↓4 +22
Comments 38

Коты в коробочках, или Компактные структуры данных

Reading time 12 min
Views 28K

image


Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?


В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.


А тем временем на Хабре найдется ли герой, способный пересковоговорить три раза подряд
[səkˈsɪŋkt]?

Читать дальше →
Total votes 127: ↑127 and ↓0 +127
Comments 43

Оптимизация кода: память

Reading time 12 min
Views 90K
Большинство программистов представляют вычислительную систему как процессор, который выполняет инструкции, и память, которая хранит инструкции и данные для процессора. В этой простой модели память представляется линейным массивом байтов и процессор может обратиться к любому месту в памяти за константное время. Хотя это эффективная модель для большинства ситуаций, она не отражает того, как в действительности работают современные системы.

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

image

Иерархия памяти работает, потому что хорошо написанные программы имеют тенденцию обращаться к хранилищу на каком-то конкретном уровне более часто, чем к хранилищу на более низком уровне. Так что хранилище на более низком уровне может быть медленнее, больше и дешевле. В итоге мы получаем большой объём памяти, который имеет стоимость хранилища в самом низу иерархии, но доставляет данные программе со скоростью быстрого хранилища в самом верху иерархии.
Читать дальше →
Total votes 80: ↑78 and ↓2 +76
Comments 99

Лабораторная работа: введение в Docker с нуля. Ваш первый микросервис

Reading time 26 min
Views 336K
Привет, хабрапользователь! Сегодня я попробую представить тебе очередную статью о докере. Зачем я это делаю, если таких статей уже множество? Ответов здесь несколько. Во-первых не все они описывают то, что мне самому бы очень пригодилось в самом начале моего пути изучения докера. Во-вторых хотелось бы дать людям к теории немного практики прямо по этой теории. Одна из немаловажных причин — уложить весь накопленный за этот недолгий период изучения докера опыт (я работаю с ним чуть более полугода) в какой-то сформированный формат, до конца разложив для себя все по-полочкам. Ну и в конце-концов излить душу, описывая некоторые грабли на которые я уже наступил (дать советы о них) и вилы, решение которых в докере просто не предусмотрено из коробки и о проблемах которых стоило бы задуматься на этапе когда вас распирает от острого желания перевести весь мир вокруг себя в контейнеры до осознавания что не для всех вещей эта технология годна.

Что мы будем рассматривать в данной статье?

В Части 0 (теоретической) я расскажу вам о контейнерах, что это и с чем едят
В Частях 1-5 будет теория и практическое задание, где мы напишем микросервис на python, работающий с очередью rabbitmq.
В Части 6 — послесловие
Читать дальше →
Total votes 108: ↑107 and ↓1 +106
Comments 36

Изучая go: пишем p2p мессенджер со сквозным шифрованием

Reading time 9 min
Views 44K

Yet another P2P Messenger


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


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


Пример UI чата на ReactJs


Статья ориентирована на новичков интересующихся языком go и пиринговыми сетями.
И для профессионалов, умеющих предлагать разумные идеи или конструктивно критиковать.

Читать дальше →
Total votes 59: ↑56 and ↓3 +53
Comments 25

TgGram — сервис создания сайтов для/из телеграм каналов

Reading time 2 min
Views 25K
Добрый день.

Как известно, контент опубликованный в телеграм не индексируется поисковиками. Я разработал сервис, tggram.com, автоматически создающий сайты для телеграм каналов.

Сразу несколько примеров:

rdslv.tggram.com
botcollection.tggram.com
memefeed.tggram.com

По желанию, возможен! кастомный домен и уникальный стиль, например:

startupoftheday.ru
crazydoge.com
Читать дальше →
Total votes 37: ↑36 and ↓1 +35
Comments 27

Как бесплатно рассказать о своем стартапе в зарубежных СМИ с миллионной аудиторией: сложности и способы их обхода

Reading time 5 min
Views 16K


Миллионы предпринимателей во всем мире мечтают о том, чтобы об их проекте написали ведущие англоязычные издания. Сегодня я расскажу о сложностях, которые могут возникнуть в попытках реализовать это желание, и том, как их можно обойти.
Читать дальше →
Total votes 23: ↑23 and ↓0 +23
Comments 1

Миллион WebSocket и Go

Reading time 11 min
Views 97K

image


Привет всем! Меня зовут Сергей Камардин, я программист команды Почты Mail.Ru.


Это статья о том, как мы разработали высоконагруженный WebSocket-сервер на Go.


Если тема WebSocket вам близка, но Go — не совсем, надеюсь, статья все равно покажется вам интересной с точки зрения идей и приемов оптимизации.

Читать дальше →
Total votes 119: ↑115 and ↓4 +111
Comments 78

Лимиты Telegram bot API и работа с ними на Go

Reading time 5 min
Views 63K
Довольно часто на Хабре появляются статьи о написании бота для Telegram, которые в своем роде, если откинуть уникальность идеи, являются самым обычным туториалом на тему «как получить сообщение от Telegram, обработать его и отправить ответ пользователю». Однако ни в одной из статей, прочтенных мной (конечно же, не берусь утверждать, что прочел их все, но тем не менее) я не встретил упоминания о лимитах отправки сообщений пользователям и как с ними работать. Кого заинтересовал, прошу под кат.
Читать дальше →
Total votes 22: ↑18 and ↓4 +14
Comments 13

Bash-скрипты: начало

Reading time 11 min
Views 1.7M
Bash-скрипты: начало
Bash-скрипты, часть 2: циклы
Bash-скрипты, часть 3: параметры и ключи командной строки
Bash-скрипты, часть 4: ввод и вывод
Bash-скрипты, часть 5: сигналы, фоновые задачи, управление сценариями
Bash-скрипты, часть 6: функции и разработка библиотек
Bash-скрипты, часть 7: sed и обработка текстов
Bash-скрипты, часть 8: язык обработки данных awk
Bash-скрипты, часть 9: регулярные выражения
Bash-скрипты, часть 10: практические примеры
Bash-скрипты, часть 11: expect и автоматизация интерактивных утилит

Сегодня поговорим о bash-скриптах. Это — сценарии командной строки, написанные для оболочки bash. Существуют и другие оболочки, например — zsh, tcsh, ksh, но мы сосредоточимся на bash. Этот материал предназначен для всех желающих, единственное условие — умение работать в командной строке Linux.


Читать дальше →
Total votes 69: ↑61 and ↓8 +53
Comments 123

Как попасть в топ на Kaggle, или Матрикснет в домашних условиях

Reading time 9 min
Views 32K
Хочу поделиться опытом участия в конкурсе Kaggle и алгоритмами машинного обучения, с помощью которых добрался до 18-го места из 1604 в конкурсе Avazu по прогнозированию CTR (click-through rate) мобильной рекламы. В процессе работы попытался воссоздать оригинальный алгоритм Мактрикснета, тестировал несколько вариантов логистической регрессии и работал с характеристиками. Обо всём этом ниже, плюс прикладываю полный код, чтобы можно было посмотреть, как всё работает.

Рассказ делю на следующие разделы:
1. Условия конкурса;
2. Создание новых характеристик;
3. Логистическая регрессия – прелести адаптивного градиента;
4. Матрикснет – воссоздание полного алгоритма;
5. Ускорение машинного обучения в Python.
Читать дальше →
Total votes 42: ↑41 and ↓1 +40
Comments 21

Система рекомендаций интернет магазина на основе методов машинного обучения в Compute Engine (Google Cloud Platform)

Reading time 16 min
Views 14K
С помощью сервисов Google Cloud Platform можно создать эффективную масштабируемую систему рекомендаций для интернет-магазина.

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

Из этой статьи вы узнаете, как на базе Cloud Platform настроить среду для поддержки базовой системы рекомендаций, которую со временем можно будет доработать и расширить.

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


Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Comments 0

Учебное пособие по Nim (часть 1)

Reading time 31 min
Views 17K
Примечание от переводчика
Этот перевод делался по мотивам комментария от пользователя stas3k, в котором он предложил frol перевести две части «Nim Tutorial». Меня это заинтересовало и я перевёл их самостоятельно, в меру своего разумения. Ежели кто найдёт ошибки (они там наверняка есть — глаз под конец совсем уже замылился), сообщайте в личку, буду править.

Введение


“Der Mensch ist doch ein Augentier – schöne Dinge wünsch ich mir.”
(Цитата из песни «Morgenstern» группы «Rammstein». Примерный перевод: «Но человек – глазастый зверь, – мне нужно множество красивых вещей».)

Это – обучающий материал (tutorial) по языку программирования Nim. Предполагается, что вы знакомы с базовыми концепциями программирования, такими как переменные, типы или команды, но глубокие знания не обязательны. Большое количество примеров по сложным нюансам языка, вы можете найти в официальном руководстве. Все примеры кода в этом документе следуют руководству по стилю языка Nim.
Читать дальше →
Total votes 16: ↑15 and ↓1 +14
Comments 22

Учебное пособие по Nim (часть 2)

Reading time 19 min
Views 6.9K
Примечание от переводчика
Первая часть находится здесь: «Учебное пособие по Nim (часть 1)»

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


Введение


«Повторение придаёт нелепости вид благоразумия.» – Норман Вайлдбергер

(в оригинале: "Repetition renders the ridiculous reasonable." – Norman Wildberger)

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

Читать дальше →
Total votes 9: ↑8 and ↓1 +7
Comments 5

Алгоритмы чат бота на базе рекуррентной нейронной сети и расширения языка AIML

Reading time 5 min
Views 35K
На сегодняшний день остается актуальным создание программ имитирующих общение человека. Простейшей моделью общения является база вопросов и ответов к ним [1]. В данном случае возникает проблема описания базы знаний и реализация программы интерпретатора. Язык разметки базы знаний может включать в себя паттерны вопросов и соответствующие им шаблоны ответов, также предысторию диалогов к ним и название соответствующей темы общения.

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

Альтернативным вариантом создания программы виртуального собеседника является использование алгоритмов машинного обучения на базе диалогов общения, именно искусственные нейронные сети. Подходящей моделью ИНС является рекуррентная нейронная сеть, способная хранить, обобщать и прогнозировать различные последовательности. В данной работе в качестве элементов последовательности предлагается использовать индексы соответствующие словам в базе знаний вопросов и ответов.
Читать дальше →
Total votes 9: ↑8 and ↓1 +7
Comments 6

Знакомьтесь, линейные модели

Reading time 10 min
Views 47K
Машинное обучение шагает по планете. Искусственный интеллект, поскрипывая нейронными сетями, постепенно опережает людей в тех задачах, до которых успел дотянуться своими нейронами. Однако не стоит забывать и про простую модель линейной регрессии. Во-первых, потому что на ней построены многие сложные методы машинного обучения, включая нейронные сети. А, во-вторых, потому что зачастую прикладные бизнес-задачи легко, быстро и качественно решаются именно линейными моделями.
И для начала небольшой тест. Можно ли с помощью линейной модели описать:
— зависимость веса человека от его роста?
— длительность ожидания в очереди в магазине в разное время суток?
— посещаемость сайта в фазе экспоненциального роста?
— динамику во времени количества человек, ожидающих поезда на станции метро?
— вероятность, что клиент не оформит заказ на сайте в зависимости от его производительности?
Как вы догадываетесь, на все вопросы ответ будет «Да, можно». Так что линейные модели не так просты, как может показаться на первый взгляд. Поэтому давайте познакомимся с их богатым разнообразием.
Читать дальше →
Total votes 35: ↑31 and ↓4 +27
Comments 22

Рекомендации на потоке

Reading time 7 min
Views 13K
Всем привет!

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


Читать дальше →
Total votes 18: ↑17 and ↓1 +16
Comments 12

93 видео-лекции по Scala

Reading time 4 min
Views 38K
В ходе подготовки спецкурса «Scala for Java Developers» под платформу онлайн-обучения UDEMY, я анализирую другие «лекционные» видео. В библиотеке накопилось какое-то количество ссылок на дельных учебные материалы по Scala (видео на английском).

Для большинства видео указано количество просмотров. Надо сделать несколько замечаний:
1. Количество просмотров не является главным критерием качества и полезности видео, но этот может служить каким-то указателем на ценность.
2. Здесь не все популярное видео, что я встречал, а лишь то, что ценно по моему личному мнению.
3. Если кто-то знает еще хорошее видео — пишите, добавлю в списки.


Читать дальше →
Total votes 21: ↑19 and ↓2 +17
Comments 5

MapReduce: более продвинутые примеры, попробуем без зауми

Reading time 9 min
Views 33K
Чтобы не откладывать в долгий ящик сразу порассказываю несколько других примеров для MapReduce, обещанные в топике "MapReduce без зауми". (Если не понимаете полностью что такое MapReduce — прочитайте тот топик сначала! Без него не разберетесь)

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

Однако тема сама по себе сложная и все же напрячь мозги придется. Когда поймете — будет очень просто.

Входящие ссылки


Допустим у нас есть Интернет. В Интернете есть исходящие ссылки.

Допустим на входе у нас есть такие данные об ИСХОДЯЩИХ ссылках, собранные нашим паучком:

habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com, yandex.ru
thematicmedia.ru -> habrahabr.ru, autokadabra.ru
autokadabra.ru -> habrahabr.ru, yandex.ru


Т.е. мы знаем, что Хабр ссылается на Apple, MS, Ubuntu и Яндекс но кто ссылается на Хабр? Да, вопрос примитивный, но все же разложим на MapReduce. Дальше будет интереснее и этот пример понадобится.

Читать дальше →
Total votes 94: ↑86 and ↓8 +78
Comments 7

Information

Rating
Does not participate
Location
Барбадос
Date of birth
Registered
Activity