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

Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире 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).

Я из тех, кто ставит на Caps Lock переключение раскладки потому, что лень нажимать 2 клавиши, когда можно нажимать одну. Я бы даже хотел 2 ненужные клавиши: одну бы я использовал для включения английской раскладки, а вторую для русской. Но вторая ненужная клавиша — это вызов контекстного меню, которая настолько ненужная, что выпиливается многими производителями ноутбуков. Так что приходится довольствоваться тем, что есть.

А ещё я не хочу при переключении окон искать их иконки на панели задач, ловить взглядом названия при листании через Alt+Tab, листать рабочие столы и т. д. Я хочу нажать комбинацию клавиш (в идеале вообще одну, но свободных ненужных клавиш уже нет) и сразу попасть в нужное мне окно. Например так:

• Alt+F: Firefox
• Alt+D: Firefox (Private Browsing)
• Alt+T: Terminal
• Alt+M: Калькулятор
• Alt+E: IntelliJ Idea
• и т. д.

Причём, по нажатию, например, на Alt+M я хочу видеть калькулятор вне зависимости от того, запущена ли в данный момент эта программа. Если запущена, то её окну надо передать фокус, а если нет — запустить нужную программу и передать фокус когда она загрузится.

На случаи, которые не покрываются предыдущим сценарием, я хочу иметь универсальные комбинации клавиш, на которые можно легко назначить любые из открытых окон. Например, у меня назначены 10 комбинаций от Alt+1 до Alt+0, которые не привязанные ни к каким программам. Я могу просто нажать Alt+1 и окно, которое сейчас в фокусе, будет получать фокус при нажатии Alt+1.

Под катом описание ещё пары фич и ответ на то, как можно это сделать. Но сразу предупрежу, что подобная кастомизация «под себя» может вызвать сильную зависимость и даже ломку при необходимости использовать Windows, Mac OS или даже чужой компьютер с Linux.

Микроконтроллеры AVR довольно дешевы и широко распространены. Наверно, с них начинает почти любой embedded разработчик. А среди любителей правит балом Arduino, сердцем которого обычно является ATmega328p. Наверняка многие задумывались: как можно заставить их звучать?

Если посмотреть на существующие проекты, то они бывают нескольких типов:

1. Генераторы квадратных импульсов. Генерация с помощью ШИМ или дергать пины в прерываниях. В любом случае, получается очень характерный пищащий звук.
2. Использование внешнего оборудования типа MP3 декодера.
3. Использование ШИМ для вывода 8 битного (иногда 16 битного) звука в формате PCM или ADPCM. Поскольку памяти в микроконтроллерах для этого явно не достаточно, то обычно используют SD карту.
4. Использование ШИМ для генерации звука на основе волновых таблиц, подобных MIDI.

Последний тип для меня был особенно интересен, т.к. почти не требует дополнительного оборудования. Представляю сообществу свой вариант. Для начала небольшое демо:



Заинтересовавшихся прошу под кат.