Разбор задач

3адача1

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

int bitCounter1(int N) {
    int count = 0;

    for (int i = 0; i < 32; i++) {
        count += N & 1;
        N = N >> 1; 
    }
return count;
}

В этой функции используется count += N & 1, а не count += N % 2 потому что операция N & 1 возвращает 0 или 1, тогда как N % 2 может вернуть -1, в зависимости от знака N.

int bitCounter2(int N) {
    int count = 0;

    while (N != 0) {
        count += N & 1;
        N = N >>> 1;
    }
}

В этой функции, в отличие от предыдущей, используется >>>, так как при сдвиге >> в начало числа добавляются биты, соответствующие знаку числа, а при сдвиге >>> всегда добавляются нули. Соответственно, в BitCounter1 не важно какие биты записываются в начало числа, так как используется цикл for, выполняющий конечное число действий. А в BitCounter2 используется цикл while, для выхода из которого нужно получить 0, и, следовательно, необходимо чтобы в начало числа записывались нули.

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

Воспользовавшись выражением N = N & (N - 1) получим функцию:

int bitCounter 3(int N) {
    int count = 0;

    while (N != 0) {
        count ++;
        N = N & (N - 1)
    }
}

Рассмотрим что делают с числом N следующие операции: N = (N & 0x55555555) + ((N >>> 1) & 0x55555555). Число 0x55555555 = (01010101010101010101010101010101) Соответственно (N & 0x55555555) обнуляет нечетные биты числа, а ((N >>> 1) & 0x55555555) — четные. Результатом сложения полученных чисел будет такое число, в каждой паре бит которого записано количество единиц в этой паре.

Теперь воспользуемся числом 0x33333333 = (00110011001100110011001100110011) , чтобы записать в каждую четверку бит количество единиц в ней, числом 0x0F0F0F0F = (00001111000011110000111100001111) для записи количества единичных бит в группу из 8 бит, числом 0x00FF00FF = (00000000111111110000000011111111) для записи количества единичных бит в группу из 16 бит и числом 0x0000FFFF = (00000000000000001111111111111111) для записи количества единичных бит в группу из 32 бит, то есть в само число.

int bitCounter4 (int N) {
    N = (N & 0x55555555) + ((N >>> 1) & 0x55555555);
    N = (N & 0x33333333) + ((N >>> 2) & 0x33333333);
    N = (N & 0x0F0F0F0F) + ((N >>> 4) & 0x0F0F0F0F);
    N = (N & 0x00FF00FF) + ((N >>> 4) & 0x00FF00FF);
    N = (N & 0x0000FFFF) + ((N >>> 4) & 0x0000FFFF);
    return N;
}

Задача 2

Напишите функцию, которая подсчитывает количество единичных байтов в данном очень длинном(скажем, из миллиарда элементов) массиве байтов. Функция должна быть оптимизирована по скорости. Использование функций, аналогичных задаче 1, для подсчета битов в каждом элементе не эффективно. Для повышения эффективности заведем вспомогательный массив или воспользуемся оператором switch.

Заведем массив int table[256], значения которого равны количеству единиц в двоичной записи числа типа byte. Нумерация массива начинается с 0, а числа типа byte принимают значения от -128 до 127. Заполнять массив будем следующим образом: первому элементу массива будет соответствовать количество единиц, использующихся в записи числа -128, второму элементу — количество единиц, использующихся при записи числа -127 и так далее. Соответственно, по индексу index + 128 мы сможем получить количество единиц в числе index. Тогда для подсчета битов необходимо достаточно бежать по исходному массиву и складывать значения массива table[index + 128].

int table[256]; 
int bitCounter1(byte[] array) {
    int count = 0;
    
    for (int i = 0; i < N; i++) {
        count += table[array[i] + 128];
    }
    return count;
}

В качестве другого решения рассмотрим функцию, которая возвращает количество единичных бит в числе с помощью оператора switch().

int oneByteBitCounter(byte value) {
    switch(value) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 1;
        case 3: return 0;
        case 4: return 1;
        ...
    }
}
int  bitCounter2(byte[] array) {
    int count - 0;
    for (int i = 0; i < N; i++) {
        count += oneByteBitCounter(array[i]);
    }
    return count;
}

Оба эти решения очень похожи, но в Java быстрее будет работать 2 вариант, так как при каждом обращении к массиву, Java проверяет, не выходим ли мы за границы. В С,С++ например, работать будет одинаково.

Стандартные структуры данных.

Изучение языка начинается с переменных. Когда переменных не хватает, то используют массивы. Простой массив — проще, чем структура данных. Но массив не всегда удобен, потому что, например, в процессе работы нельзя изменить его размер.

1.Массив переменной длины (линейные структура данных)

Для начала, рассмотрим какие операции можно сделать с обычным массивом:

• создать (инициализировать) массив (A = new int[10])
• получить значение элемента массива по индексу (int k = A[i])
• записать значения элемента массива по индексу (A[i] = 8)
• получить длины массива (int length = A.length)

У массива переменной длины больше возможностей:

• Создание (инициализация) массива нулевой длины
• Добавление нового элемента в конец массива
• Получение длины массива
• Получение значения элемента массива по индексу
• Изменение элемента массива по индексу
• Добавление элемента в массив в указанное место по индексу
• Удаление элемента из массива по индексу

Реализация:

Обычный массив int[200] выглядит следующим образом. Это 800 байт, расположенных в памяти подряд. При работе с таким массивом могут возникнуть как минимум 2 проблемы:

• столько свободной памяти может не оказаться
• в процессе работы может понадобиться массив большей длины. Поскольку длину массива не увеличить, придется завести еще один массив.

Рассмотрим реализации массива переменной длины.

Каждый элемент списка представляет собой пару: значение элемента, например int, и указатель на следующий элемент списка, или указатель на null, если данный элемент является последним в списке. Таким образом, список представляет собой цепочку элементов. При такой реализации не будет проблем с выделением памяти, так как создать элемент можно в любом месте памяти, а о положении этого элемента можно будет узнать с помощью указателя на него.

Отступление:

Введем понятие O(n). f(n) = O(g(n)), если существуют m, M такие что для любого n m * g(n) < f(n) < M * g(n). f1 = O(lg(n)) и f2 = O(ln(n)) — одно и тоже. Их отношение константа. Заметим, что O(n) не всегда быстрее O(n2). 109*n при малых n больше, чем 10-9*n2.
O(1) — константное время
O(n) — линейное время
O(n2) — квадратичное время

Посмотрим на время работы операций для стандартной реализации массива переменной длины:

• Получение длины массива — O(n), в стандартных реализациях длина хранится отдельно
• Получение значения элемента по индексу — для получения значения необходимо пробежаться по списку до элемента index, следовательно — O(index)
• Изменение значения элемента по индексу — для изменения значения элемента необходимо пробежаться по списку до элемента inldex и лишь потом изменить его, следовательно — O(index)
• Добавление элемента в массив — если добавляем элемент в конец массива и не храним указатель на конец списка, то O(N), если храним — то O(1). Если добавляем в начало — O(1).
• Вставка элемента в массив по индексу — O(index)
• Удаление элемента из массива по индексу — O(index)

Рассмотрим реализацию массива переменной длины в Java 5.0.

В Java существует встроенный тип LinkedList<Integer>. <Integer> означает, что в данном массиве будут храниться элементы типа int. Так же можно использовать <Byte> — для элементов типа byte, <Char> — для элементов типа char.Для использование встроенного типа необходимо до объявления класса написать import java.util.LinkedList.

Рассмотрим несколько операций LinkedList.

import java.util.LinkedList; 

LinkedList<Integer> list; 

list = new LinkedList<Integer>(); // создание(инициализация) массива
list.add(25); // добавление элемента в конец массива
list.size(); // получение  длины массива
list.isEmpty(); // проверка массива на наличие в нем элементов
list.get(index); // получение значения элемента массива по индексу
list.set(index, value); // изменение элемента массива по индексу
list.add(index, value); // добавление элемента в массив по индексу
list.remove(index); // удаление элемент из массива по индексу 

Замечание: В Java предусмотрены некоторые дополнительные возможности для работы с типом LinkedList. Часто возникают ситуации, когда необходимо пробежаться по всему списку, например, необходимо посчитать сумму элементов списка. Если для этого использовать функцию get(ndex), то время работы такого цикла будет квадратичным.

 
  for (int i = 0; i < list.size; i++){
      sum += list.get(i);
  }

 for (int i : list) {
      sum += i;
  }