Рубрика «биты»

Бумажный бит: создание механической памяти из оригами - 1

«Бегущий по лезвию», «Воздушная тюрьма», «Heavy Rain» — что общего между этими представителями массовой культуры? Во всех в той или иной степени присутствует древнее японское искусство по складыванию бумаги — оригами. В кино, играх и в реальной жизни оригами частенько используется в качестве символа определенных чувств, каких-то воспоминаний или своеобразного послания. Это скорее эмоциональная составляющая оригами, но с точки зрения науки в бумажных фигурках сокрыто множество интересных аспектов из самых разных направлений: геометрия, математика и даже механика. Сегодня мы с вами познакомимся с исследованием, в котором ученые из Американского института физики создали устройство хранения данных за счет складывания/раскладывания фигурок оригами. Как именно работает бумажная карта памяти, какие принципы в ней реализованы и сколько данных может хранить такое устройство? Ответы на эти вопросы мы найдем в докладе ученых. Поехали.Читать полностью »

Храним числа экономно - 1 Недавно в одном из проектов встала задача: есть набор множеств (Set), которые надо достаточно эффективно хранить в оперативной памяти. Потому что множеств много, а памяти мало. И с этим надо что-то делать.

Так как язык, на котором всё это написано — C#, то есть нюансы. А именно, что стандартный HashSet<int> на хранение одного числа тратит 16 байт, также влияет филл фактор. Есть более эффективные реализации (когда-нибудь и про них напишу), но с другой стороны, можно же тупо хранить в массивах, по 4 байта на число (требуется хранить инты), что достаточно эффективно. Но можно ли уменьшить ещё?

Сразу скажу, у меня нет ответа, как лучше сделать, возможно его не существует, ибо есть множество факторов, связанных с особенностями распределения конкретных данных. Но есть идеи, которыми я поделюсь: какие варианты экономии памяти существуют. Также рекомендую до прочтения поста подумать самостоятельно, всё-таки это неплохая разминка для ума. Для определённости сформулирую задачу следующим образом:

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

В статье будет много букв и цифр и ни одной картинки (кроме упакованного котика на КДПВ).
Читать полностью »

Добрый день. Эту статью я написал специально для студентов курса «Алгоритмы для разработчиков» в OTUS и сегодня хочу поделиться ею со всеми читателями нашего блога.

Шахматный конь стоит на шахматной доске и задумчиво смотрит в шахматную даль.
Сколько разных ходов он может сделать?

image

Хвала изобретателю шахмат, на доске 64 клетки.
Хвала архитектору компьютеров — у типа ulong тоже 64 бита.
Это же надо было случиться такому совпадению!
Напрашивается гениальная идея — хранить всю доску в одном целом числе! Для этого решения существует даже специальный термин — Bitboard — битовая доска.

Так как же быстро найти количество ходов шахматного коня, используя эту идею?Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js