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

Однако, в зависимости от вида, каждые 7, 11, 13 или 17 лет периодические цикады одновременно массово вылезают на свет и превращаются в шумных летающих тварей, спариваются и вскоре умирают.

Хотя наши странные цикады весело уходят в иной мир, возникает очевидный вопрос: это просто случайность, или числа 7, 11, 13 и 17 какие-то особенные?

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

Я занимаюсь программированием уже 15 лет. Но в последнее время при разработке не принято думать об эффективности, простоте и совершенстве: вплоть до того, что мне становится грустно за свою карьеру и за IT-отрасль в целом.

Для примера, современные автомобили работают, скажем, на 98% от того, что физически позволяет нынешняя конструкция двигателя. Современная архитектура использует точно рассчитанное количество материала, чтобы выполнять свою функцию и оставаться в безопасности в данных условиях. Все самолёты сошлись к оптимальному размеру/форме/нагрузке и в основном выглядят одинаково.

Только в программном обеспечении считается нормальным, если программа работает на уровне 1% или даже 0,01% от возможной производительности. Ни у кого вроде нет возражений.

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

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

Перехваченные DVB-потоки НАТО (2002)

Много лет хакеры проводят демонстративные взломы гражданских и военных спутниковых коммуникаций, но безопасность тех остаётся на низком уровне. На последней конференции Black Hat 2020 оксфордский студент Джеймс Павур продемонстрировал, какой спутниковый трафик сейчас в радиоэфире и какую приватную информацию из него можно извлечь.

* Под всё имеется в виду относительно быстрое выполнение операций над единичным элементом массива.

Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире Java — в зависимости от необходимых операций — можно использовать:

• add(obj), get(obj), set(index, obj): базовый набор почти всех списков, например ArrayList.
• add(index, obj): структуры в виде дерева, например TreeList из apache common-collections.
• remove(index): то же, что и выше.
• contains(obj), indexOf(obj): можно использовать связку ArrayList и HashMap.
• remove(obj): … затрудняюсь ответить. В некоторых случаях можно обойтись LinkedHashSet. Решается тривиально при наличии предыдущих двух пунктов, но какие структуры могут и то и другое быстро?

Когда мне понадобилась структура с быстрыми add(obj), get(index), remove(index) и indexOf(obj), то google не дал ответа. Ни примеров кода, ни описания подобных структур я не нашел. Возможно не там искал, пришлось выдумывать самому. Но если кто-то скинет ссылку в комментариях, то буду весьма признателен.

Возможно, кто-то догадался, что можно взять TreeList, который умеет быстро вставлять/удалять элементы в середине списка и добавить к нему HashMap из объекта в индекс в TreeList для быстрого выполнения indexOf(obj). И это будет простое, изящное, но неверное решение. Ведь при добавлении в середину или удалении из середины нужно будет пересчитать индексы, в среднем, для половины элементов. Это ухудшит производительность до O(n).

Дальше я расскажу о структуре данных, которая может всё из перечисленного выше. Которая выполняет любую операцию над одним элементом за O(log(n)) времени. Ну почти — за логарифм выполняется в том случае, когда все объекты в списке различны. Если в списке есть одинаковые объекты, то возможно проседание производительности вплоть до O(log(n) ^ 2).