aston-team-project/docs/tasks/StudentOccurrenceIndexFinder.md

Техническое задание: многопоточный поиск индексов Student

Задача

Реализовать многопоточный поиск всех вхождений заданного объекта Student в MyList<Student>.

Метод не должен выводить никаких сообщений в консоль.

Результатом работы должен быть массив int[], содержащий индексы всех элементов исходной коллекции, которые равны переданному Student.

Сравнение выполнять через существующий Student.equals().

---

Входная информация

Основной метод принимает:

MyList<Student> students

Исходная коллекция студентов.

Student target

Студент, вхождения которого необходимо найти.

---

Выходная информация

Метод возвращает:

int[]

Массив должен содержать индексы всех совпавших элементов.

Пример:

Исходная коллекция:

[Student A, Student B, Student A, Student C, Student A]

Результат:

[0, 2, 4]

Индексы должны быть расположены в порядке возрастания.

При отсутствии совпадений:

[]

При пустой коллекции:

[]

---

Название класса

StudentOccurrenceIndexFinder

---

Публичные методы и контракты

findOccurrences

public int[] findOccurrences(
        MyList<Student> students,
        Student target
);

Метод должен:

1. Проверить входные параметры.
2. Разделить коллекцию на диапазоны индексов.
3. Передать каждый диапазон отдельной задаче.
4. Выполнить поиск в нескольких потоках.
5. Получить от каждого потока найденные индексы.
6. Объединить результаты.
7. Вернуть индексы в порядке возрастания.
8. Не изменять исходную коллекцию.
9. Не изменять объекты Student.
10. Не выводить ничего в консоль.

---

Вспомогательные методы

Количество и вид private методов могут быть выбраны разработчиком.

Рекомендуется выделить:

private int calculateThreadCount(int size);

Определяет количество рабочих потоков.

private int countChunkSize(int size, int threadCount);

Определяет размер диапазона для одной задачи.

private MyList<Integer> findInRange(
        MyList<Student> students,
        Student target,
        int fromIndex,
        int toIndex
);

Обрабатывает диапазон:

[fromIndex, toIndex)

и возвращает индексы найденных совпадений.

---

Работа с многопоточностью

Рекомендуемый подход

Не использовать общий контейнер результатов, к которому одновременно обращаются несколько потоков.

Также не рекомендуется использовать мьютексы (synchronized, Lock, ReentrantLock) для хранения результата.

Лучше использовать модель:

                MyList<Student>
                       │
          ┌────────────┼────────────┐
          ↓            ↓            ↓
      Поток 1       Поток 2       Поток 3
       диапазон     диапазон       диапазон
          │            │            │
          ↓            ↓            ↓
      MyList<Integer> MyList<Integer> MyList<Integer>
          └────────────┼────────────┘
                       ↓
                 основной поток
                       ↓
                    merge
                       ↓
                     int[]

Каждый поток создаёт собственный контейнер MyList<Integer> и записывает найденные индексы только в него.

Это позволяет избежать состояния гонки без синхронизации общей структуры.

---

Разбиение коллекции на потоки

Количество потоков рекомендуется определять на основании:

Runtime.getRuntime().availableProcessors()

Количество потоков не должно превышать количество элементов:

threadCount = min(
    availableProcessors(),
    students.size()
)

Пример

Для коллекции из 10000 элементов и четырёх рабочих потоков:

Поток 1 → [0, 2500)
Поток 2 → [2500, 5000)
Поток 3 → [5000, 7500)
Поток 4 → [7500, 10000)

Каждый индекс должен принадлежать ровно одному диапазону.

Не допускаются:

• пропущенные индексы;
• обработка одного индекса несколькими потоками.

---

Поиск внутри потока

Каждая задача обрабатывает только свой диапазон.

Для каждого индекса:

Student student = students.get(index);

затем:

target.equals(student)

Если результат true, индекс добавляется в локальный:

MyList<Integer>

Пример:

Поток 1 → [0, 8, 15]
Поток 2 → [21, 24]
Поток 3 → [30, 42, 48]
Поток 4 → [63]

---

Объединение результатов

Основной поток после завершения всех задач должен получить локальные результаты и объединить их.

Рекомендуется передавать задачи в порядке возрастания диапазонов:

Результат 1 → диапазон 0
Результат 2 → диапазон 1
Результат 3 → диапазон 2
...

Если каждая задача добавляет индексы в возрастающем порядке, а результаты объединяются в порядке диапазонов, итоговый массив уже будет отсортирован:

[0, 8, 15, 21, 24, 30, 42, 48, 63]

В этом случае дополнительная сортировка результата не требуется.

Arrays.sort() и другие готовые методы сортировки использовать не следует, поскольку порядок можно гарантировать самим алгоритмом объединения.

---

Потокобезопасность

Мьютексы

Использование мьютексов для результата не требуется.

Не рекомендуется использовать:

synchronized

Lock

ReentrantLock

AtomicInteger

для общего результата.

Причина: потоки не должны изменять одну общую структуру.

Каждый поток работает со своим:

MyList<Integer>

а объединение выполняется после завершения параллельной части одним потоком.

---

Рекомендуемые классы и импорты

Для реализации рекомендуется использовать стандартные средства Java:

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

Рекомендуемая схема:

ExecutorService
      ↓
Callable<MyList<Integer>>
      ↓
Future<MyList<Integer>>

Каждый Callable обрабатывает свой диапазон и возвращает собственный MyList<Integer>.

После получения всех Future основной метод объединяет результаты.

После завершения работы ExecutorService должен быть корректно закрыт.

При InterruptedException необходимо восстановить статус прерывания текущего потока:

Thread.currentThread().interrupt();

---

Использование MyList

Сторонние контейнеры не допускаются.

Запрещено использовать:

ArrayList
LinkedList
Vector
CopyOnWriteArrayList
ConcurrentLinkedQueue
и другие стандартные контейнеры

как хранилище промежуточных или итоговых результатов.

Для результатов каждого потока использовать:

MyList<Integer>

Итог преобразовать в:

int[]

---

Требуется ли изменять MyList

Текущего интерфейса достаточно для реализации задачи:

public interface MyList<T> {

  void add(T element);

  T get(int index);

  T set(int index, T element);

  T remove(int index);

  int size();

  boolean isEmpty();
}

Дополнительные методы добавлять не требуется.

Для задачи достаточно:

size()
get(index)
add(index)

Поскольку поиск выполняется только на чтение, а результаты каждого потока добавляются в его собственный MyList<Integer>, существующего интерфейса достаточно.

Важно

Метод:

void add(T element);

должен добавлять элемент в конец коллекции.

Это позволяет каждому потоку формировать свои индексы в порядке их обнаружения.

---

Использование Student

Изменения в Student не требуются.

Использовать существующий метод:

equals(Object obj)

Сравнение выполнять:

target.equals(students.get(index))

Не использовать:

==

Не сравнивать объекты вручную по отдельным полям.

Не использовать toString() для определения совпадения.

---

StudentBuilder

Изменения в StudentBuilder не требуются.

Он не участвует в алгоритме поиска.

---

Обработка входных данных

Если:

students == null

выбросить:

IllegalArgumentException

Если:

target == null

выбросить:

IllegalArgumentException

Для пустой коллекции вернуть:

new int[0]

Без создания рабочих потоков.

---

Обобщённый алгоритм реализации

1. Проверить students и target.
2. Получить размер коллекции.
3. Если размер равен 0 → вернуть [].
4. Вычислить количество потоков.
5. Разделить индексы коллекции на непересекающиеся диапазоны.
6. Создать Callable для каждого диапазона.
7. Запустить задачи через ExecutorService.
8. Каждый поток:
      - получает fromIndex и toIndex;
      - проходит свой диапазон;
      - сравнивает Student через equals();
      - записывает найденные индексы в собственный MyList<Integer>.
9. Основной поток получает результаты через Future.
10. Объединяет MyList<Integer> в порядке диапазонов.
11. Преобразует результат в int[].
12. Возвращает массив.

---

Примеры тестов

Одно совпадение

[A, B, C, D]

Искомый:

C

Ожидается:

[2]

Несколько совпадений

[A, B, A, C, A]

Ожидается:

[0, 2, 4]

Нет совпадений

[A, B, C]

Искомый:

D

Ожидается:

[]

Все элементы совпадают

[A, A, A, A]

Ожидается:

[0, 1, 2, 3]

Пустая коллекция

Ожидается:

[]

Один элемент

Проверить:

[A] + A → [0]
[A] + B → []

Проверка границ диапазонов потоков

Проверить коллекции размеров:

1
2
3
4
10
100
1000

Особое внимание уделить совпадениям:

на последнем элементе одного диапазона;
на первом элементе следующего диапазона.

Каждый индекс должен быть найден ровно один раз.

Проверка порядка результата

Создать совпадения в разных диапазонах.

Проверить, что результат имеет вид:

[0, 3, 7, 12, 25, 49, 100]

и находится в порядке возрастания без использования дополнительной сортировки.

Проверка Student.equals()

Создать два разных экземпляра Student с одинаковыми значениями полей.

Один поместить в коллекцию, второй передать как target.

Проверить, что индекс считается совпадением согласно equals().

Проверка неизменности коллекции

После выполнения метода проверить:

• размер MyList;
• порядок элементов;
• значения всех элементов.

Проверка отсутствия вывода

Перехватить стандартный вывод и убедиться, что выполнение findOccurrences() не выводит сообщений в консоль.

Большая коллекция

Создать коллекцию, например из 100000 студентов, с заранее известными индексами совпадений.

Проверить:

• все ожидаемые индексы найдены;
• лишних индексов нет;
• индексы идут по возрастанию;
• итоговый массив имеет правильный размер.

Git

Название ветки:

feature/student-occurrence-index-finder

Результат

Необходимо реализовать:

StudentOccurrenceIndexFinder.java

Существующие интерфейсы и классы:

MyList.java
Student.java
StudentBuilder.java

изменять не требуется.