Эффективное агрегирование удалений и индексов вставки

Question

У меня есть тип, который используется для обновления пользовательского интерфейса.Это псевдокод для него.

{
  Item[] AllItems;
  long[] ItemsRemovedFromPreviousUpdateByIndex;
  long[] ItemsAddedToPreviousUpdateByIndex;
}

Эти обновления происходят довольно часто и содержат много данных.Мы хотим объединить эти экземпляры и предоставлять только одно обновление каждые 200 мс в пользовательский интерфейс.В окне 200 мс может быть 20 или 30 обновлений.

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

Answer 1

Я бы попытался сохранить эти данные в паре int с, long с или BigInteger с, в зависимости от того, сколько у вас индексов.

Сначала подумайте о том, чтобы сделать что-то вроде этого:

boolean[] added = new boolean[allItems.length];
boolean[] removed = new boolean[allItems.length];

Где логические значения истинны тогда и только тогда, когда элемент с соответствующим индексом не был добавлен / удален.

Но тогда вместо того, чтобы делать это, я бы попытался представить логический массив как длинный или, если необходимо, BigInteger. Так как, tttfftfftf -> 1110010010 -> 914.

Вы можете изучить методы переключения одного бита от 0 до 1, и, если это уже 1, оставьте его в покое. Вам нужно быть умным в вашем случае инициализации, так как вы начинаете со всех 0 (то есть 0) и первый индекс может быть большим, поэтому вам нужно перейти от 0 до 10...0 в одном шаг, который просто 1 << n. Оттуда вы просто переворачиваете отдельные биты и, возможно, сдвигаетесь, если вам нужно перевернуть бит в j > n, где n было от init-case, упомянутого выше.

Имейте в виду, что вам всегда нужно знать длину массива allItems при каждом сбросе, поскольку 00001001 совпадает с 1001, поэтому, если длина равна 8, вы должны интерпретировать 1001 как 00001001.