689 lines
16 KiB
Markdown
689 lines
16 KiB
Markdown
# Техническое задание: многопоточный поиск индексов `Student`
|
|
|
|
## Задача
|
|
|
|
Реализовать многопоточный поиск всех вхождений заданного объекта `Student` в `MyList<Student>`.
|
|
|
|
Метод **не должен выводить никаких сообщений в консоль**.
|
|
|
|
Результатом работы должен быть массив `int[]`, содержащий индексы всех элементов исходной коллекции, которые равны переданному `Student`.
|
|
|
|
Сравнение выполнять через существующий `Student.equals()`.
|
|
|
|
---
|
|
|
|
## Входная информация
|
|
|
|
Основной метод принимает:
|
|
|
|
```java
|
|
MyList<Student> students
|
|
```
|
|
|
|
Исходная коллекция студентов.
|
|
|
|
```java
|
|
Student target
|
|
```
|
|
|
|
Студент, вхождения которого необходимо найти.
|
|
|
|
---
|
|
|
|
## Выходная информация
|
|
|
|
Метод возвращает:
|
|
|
|
```java
|
|
int[]
|
|
```
|
|
|
|
Массив должен содержать индексы всех совпавших элементов.
|
|
|
|
Пример:
|
|
|
|
```text
|
|
Исходная коллекция:
|
|
|
|
[Student A, Student B, Student A, Student C, Student A]
|
|
|
|
Результат:
|
|
|
|
[0, 2, 4]
|
|
```
|
|
|
|
Индексы должны быть расположены в порядке возрастания.
|
|
|
|
При отсутствии совпадений:
|
|
|
|
```text
|
|
[]
|
|
```
|
|
|
|
При пустой коллекции:
|
|
|
|
```text
|
|
[]
|
|
```
|
|
|
|
---
|
|
|
|
# Название класса
|
|
|
|
```text
|
|
StudentOccurrenceIndexFinder
|
|
```
|
|
|
|
---
|
|
|
|
# Публичные методы и контракты
|
|
|
|
## `findOccurrences`
|
|
|
|
```java
|
|
public int[] findOccurrences(
|
|
MyList<Student> students,
|
|
Student target
|
|
);
|
|
```
|
|
|
|
Метод должен:
|
|
|
|
1. Проверить входные параметры.
|
|
2. Разделить коллекцию на диапазоны индексов.
|
|
3. Передать каждый диапазон отдельной задаче.
|
|
4. Выполнить поиск в нескольких потоках.
|
|
5. Получить от каждого потока найденные индексы.
|
|
6. Объединить результаты.
|
|
7. Вернуть индексы в порядке возрастания.
|
|
8. Не изменять исходную коллекцию.
|
|
9. Не изменять объекты `Student`.
|
|
10. Не выводить ничего в консоль.
|
|
|
|
---
|
|
|
|
# Вспомогательные методы
|
|
|
|
Количество и вид `private` методов могут быть выбраны разработчиком.
|
|
|
|
Рекомендуется выделить:
|
|
|
|
```java
|
|
private int calculateThreadCount(int size);
|
|
```
|
|
|
|
Определяет количество рабочих потоков.
|
|
|
|
```java
|
|
private int countChunkSize(int size, int threadCount);
|
|
```
|
|
|
|
Определяет размер диапазона для одной задачи.
|
|
|
|
```java
|
|
private MyList<Integer> findInRange(
|
|
MyList<Student> students,
|
|
Student target,
|
|
int fromIndex,
|
|
int toIndex
|
|
);
|
|
```
|
|
|
|
Обрабатывает диапазон:
|
|
|
|
```text
|
|
[fromIndex, toIndex)
|
|
```
|
|
|
|
и возвращает индексы найденных совпадений.
|
|
|
|
---
|
|
|
|
# Работа с многопоточностью
|
|
|
|
## Рекомендуемый подход
|
|
|
|
Не использовать общий контейнер результатов, к которому одновременно обращаются несколько потоков.
|
|
|
|
Также **не рекомендуется использовать мьютексы** (`synchronized`, `Lock`, `ReentrantLock`) для хранения результата.
|
|
|
|
Лучше использовать модель:
|
|
|
|
```text
|
|
MyList<Student>
|
|
│
|
|
┌────────────┼────────────┐
|
|
↓ ↓ ↓
|
|
Поток 1 Поток 2 Поток 3
|
|
диапазон диапазон диапазон
|
|
│ │ │
|
|
↓ ↓ ↓
|
|
MyList<Integer> MyList<Integer> MyList<Integer>
|
|
└────────────┼────────────┘
|
|
↓
|
|
основной поток
|
|
↓
|
|
merge
|
|
↓
|
|
int[]
|
|
```
|
|
|
|
Каждый поток создаёт **собственный контейнер `MyList<Integer>`** и записывает найденные индексы только в него.
|
|
|
|
Это позволяет избежать состояния гонки без синхронизации общей структуры.
|
|
|
|
---
|
|
|
|
# Разбиение коллекции на потоки
|
|
|
|
Количество потоков рекомендуется определять на основании:
|
|
|
|
```java
|
|
Runtime.getRuntime().availableProcessors()
|
|
```
|
|
|
|
Количество потоков не должно превышать количество элементов:
|
|
|
|
```text
|
|
threadCount = min(
|
|
availableProcessors(),
|
|
students.size()
|
|
)
|
|
```
|
|
|
|
### Пример
|
|
|
|
Для коллекции из `10000` элементов и четырёх рабочих потоков:
|
|
|
|
```text
|
|
Поток 1 → [0, 2500)
|
|
Поток 2 → [2500, 5000)
|
|
Поток 3 → [5000, 7500)
|
|
Поток 4 → [7500, 10000)
|
|
```
|
|
|
|
Каждый индекс должен принадлежать **ровно одному диапазону**.
|
|
|
|
Не допускаются:
|
|
|
|
- пропущенные индексы;
|
|
- обработка одного индекса несколькими потоками.
|
|
|
|
---
|
|
|
|
# Поиск внутри потока
|
|
|
|
Каждая задача обрабатывает только свой диапазон.
|
|
|
|
Для каждого индекса:
|
|
|
|
```java
|
|
Student student = students.get(index);
|
|
```
|
|
|
|
затем:
|
|
|
|
```java
|
|
target.equals(student)
|
|
```
|
|
|
|
Если результат `true`, индекс добавляется в локальный:
|
|
|
|
```java
|
|
MyList<Integer>
|
|
```
|
|
|
|
Пример:
|
|
|
|
```text
|
|
Поток 1 → [0, 8, 15]
|
|
Поток 2 → [21, 24]
|
|
Поток 3 → [30, 42, 48]
|
|
Поток 4 → [63]
|
|
```
|
|
|
|
---
|
|
|
|
# Объединение результатов
|
|
|
|
Основной поток после завершения всех задач должен получить локальные результаты и объединить их.
|
|
|
|
Рекомендуется передавать задачи в порядке возрастания диапазонов:
|
|
|
|
```text
|
|
Результат 1 → диапазон 0
|
|
Результат 2 → диапазон 1
|
|
Результат 3 → диапазон 2
|
|
...
|
|
```
|
|
|
|
Если каждая задача добавляет индексы в возрастающем порядке, а результаты объединяются в порядке диапазонов, итоговый массив уже будет отсортирован:
|
|
|
|
```text
|
|
[0, 8, 15, 21, 24, 30, 42, 48, 63]
|
|
```
|
|
|
|
В этом случае дополнительная сортировка результата не требуется.
|
|
|
|
**`Arrays.sort()` и другие готовые методы сортировки использовать не следует**, поскольку порядок можно гарантировать самим алгоритмом объединения.
|
|
|
|
---
|
|
|
|
# Потокобезопасность
|
|
|
|
## Мьютексы
|
|
|
|
Использование мьютексов для результата **не требуется**.
|
|
|
|
Не рекомендуется использовать:
|
|
|
|
```java
|
|
synchronized
|
|
```
|
|
|
|
```java
|
|
Lock
|
|
```
|
|
|
|
```java
|
|
ReentrantLock
|
|
```
|
|
|
|
```java
|
|
AtomicInteger
|
|
```
|
|
|
|
для общего результата.
|
|
|
|
Причина: потоки не должны изменять одну общую структуру.
|
|
|
|
Каждый поток работает со своим:
|
|
|
|
```text
|
|
MyList<Integer>
|
|
```
|
|
|
|
а объединение выполняется после завершения параллельной части одним потоком.
|
|
|
|
---
|
|
|
|
# Рекомендуемые классы и импорты
|
|
|
|
Для реализации рекомендуется использовать стандартные средства Java:
|
|
|
|
```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;
|
|
```
|
|
|
|
Рекомендуемая схема:
|
|
|
|
```text
|
|
ExecutorService
|
|
↓
|
|
Callable<MyList<Integer>>
|
|
↓
|
|
Future<MyList<Integer>>
|
|
```
|
|
|
|
Каждый `Callable` обрабатывает свой диапазон и возвращает собственный `MyList<Integer>`.
|
|
|
|
После получения всех `Future` основной метод объединяет результаты.
|
|
|
|
После завершения работы `ExecutorService` должен быть корректно закрыт.
|
|
|
|
При `InterruptedException` необходимо восстановить статус прерывания текущего потока:
|
|
|
|
```java
|
|
Thread.currentThread().interrupt();
|
|
```
|
|
|
|
---
|
|
|
|
# Использование `MyList`
|
|
|
|
Сторонние контейнеры **не допускаются**.
|
|
|
|
Запрещено использовать:
|
|
|
|
```text
|
|
ArrayList
|
|
LinkedList
|
|
Vector
|
|
CopyOnWriteArrayList
|
|
ConcurrentLinkedQueue
|
|
и другие стандартные контейнеры
|
|
```
|
|
|
|
как хранилище промежуточных или итоговых результатов.
|
|
|
|
Для результатов каждого потока использовать:
|
|
|
|
```java
|
|
MyList<Integer>
|
|
```
|
|
|
|
Итог преобразовать в:
|
|
|
|
```java
|
|
int[]
|
|
```
|
|
|
|
---
|
|
|
|
# Требуется ли изменять `MyList`
|
|
|
|
Текущего интерфейса **достаточно для реализации задачи**:
|
|
|
|
```java
|
|
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();
|
|
}
|
|
```
|
|
|
|
Дополнительные методы добавлять **не требуется**.
|
|
|
|
Для задачи достаточно:
|
|
|
|
```java
|
|
size()
|
|
get(index)
|
|
add(index)
|
|
```
|
|
|
|
Поскольку поиск выполняется только на чтение, а результаты каждого потока добавляются в его собственный `MyList<Integer>`, существующего интерфейса достаточно.
|
|
|
|
### Важно
|
|
|
|
Метод:
|
|
|
|
```java
|
|
void add(T element);
|
|
```
|
|
|
|
должен добавлять элемент в конец коллекции.
|
|
|
|
Это позволяет каждому потоку формировать свои индексы в порядке их обнаружения.
|
|
|
|
---
|
|
|
|
# Использование `Student`
|
|
|
|
Изменения в `Student` **не требуются**.
|
|
|
|
Использовать существующий метод:
|
|
|
|
```java
|
|
equals(Object obj)
|
|
```
|
|
|
|
Сравнение выполнять:
|
|
|
|
```java
|
|
target.equals(students.get(index))
|
|
```
|
|
|
|
Не использовать:
|
|
|
|
```text
|
|
==
|
|
```
|
|
|
|
Не сравнивать объекты вручную по отдельным полям.
|
|
|
|
Не использовать `toString()` для определения совпадения.
|
|
|
|
---
|
|
|
|
# `StudentBuilder`
|
|
|
|
Изменения в `StudentBuilder` **не требуются**.
|
|
|
|
Он не участвует в алгоритме поиска.
|
|
|
|
---
|
|
|
|
# Обработка входных данных
|
|
|
|
Если:
|
|
|
|
```java
|
|
students == null
|
|
```
|
|
|
|
выбросить:
|
|
|
|
```java
|
|
IllegalArgumentException
|
|
```
|
|
|
|
Если:
|
|
|
|
```java
|
|
target == null
|
|
```
|
|
|
|
выбросить:
|
|
|
|
```java
|
|
IllegalArgumentException
|
|
```
|
|
|
|
Для пустой коллекции вернуть:
|
|
|
|
```java
|
|
new int[0]
|
|
```
|
|
|
|
Без создания рабочих потоков.
|
|
|
|
---
|
|
|
|
# Обобщённый алгоритм реализации
|
|
|
|
```text
|
|
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. Возвращает массив.
|
|
```
|
|
|
|
---
|
|
|
|
# Примеры тестов
|
|
|
|
## Одно совпадение
|
|
|
|
```text
|
|
[A, B, C, D]
|
|
```
|
|
|
|
Искомый:
|
|
|
|
```text
|
|
C
|
|
```
|
|
|
|
Ожидается:
|
|
|
|
```text
|
|
[2]
|
|
```
|
|
|
|
## Несколько совпадений
|
|
|
|
```text
|
|
[A, B, A, C, A]
|
|
```
|
|
|
|
Ожидается:
|
|
|
|
```text
|
|
[0, 2, 4]
|
|
```
|
|
|
|
## Нет совпадений
|
|
|
|
```text
|
|
[A, B, C]
|
|
```
|
|
|
|
Искомый:
|
|
|
|
```text
|
|
D
|
|
```
|
|
|
|
Ожидается:
|
|
|
|
```text
|
|
[]
|
|
```
|
|
|
|
## Все элементы совпадают
|
|
|
|
```text
|
|
[A, A, A, A]
|
|
```
|
|
|
|
Ожидается:
|
|
|
|
```text
|
|
[0, 1, 2, 3]
|
|
```
|
|
|
|
## Пустая коллекция
|
|
|
|
Ожидается:
|
|
|
|
```text
|
|
[]
|
|
```
|
|
|
|
## Один элемент
|
|
|
|
Проверить:
|
|
|
|
```text
|
|
[A] + A → [0]
|
|
[A] + B → []
|
|
```
|
|
|
|
## Проверка границ диапазонов потоков
|
|
|
|
Проверить коллекции размеров:
|
|
|
|
```text
|
|
1
|
|
2
|
|
3
|
|
4
|
|
10
|
|
100
|
|
1000
|
|
```
|
|
|
|
Особое внимание уделить совпадениям:
|
|
|
|
```text
|
|
на последнем элементе одного диапазона;
|
|
на первом элементе следующего диапазона.
|
|
```
|
|
|
|
Каждый индекс должен быть найден ровно один раз.
|
|
|
|
## Проверка порядка результата
|
|
|
|
Создать совпадения в разных диапазонах.
|
|
|
|
Проверить, что результат имеет вид:
|
|
|
|
```text
|
|
[0, 3, 7, 12, 25, 49, 100]
|
|
```
|
|
|
|
и находится в порядке возрастания без использования дополнительной сортировки.
|
|
|
|
## Проверка `Student.equals()`
|
|
|
|
Создать два разных экземпляра `Student` с одинаковыми значениями полей.
|
|
|
|
Один поместить в коллекцию, второй передать как `target`.
|
|
|
|
Проверить, что индекс считается совпадением согласно `equals()`.
|
|
|
|
## Проверка неизменности коллекции
|
|
|
|
После выполнения метода проверить:
|
|
|
|
- размер `MyList`;
|
|
- порядок элементов;
|
|
- значения всех элементов.
|
|
|
|
## Проверка отсутствия вывода
|
|
|
|
Перехватить стандартный вывод и убедиться, что выполнение `findOccurrences()` не выводит сообщений в консоль.
|
|
|
|
## Большая коллекция
|
|
|
|
Создать коллекцию, например из `100000` студентов, с заранее известными индексами совпадений.
|
|
|
|
Проверить:
|
|
|
|
- все ожидаемые индексы найдены;
|
|
- лишних индексов нет;
|
|
- индексы идут по возрастанию;
|
|
- итоговый массив имеет правильный размер.
|
|
|
|
## Git
|
|
|
|
Название ветки:
|
|
|
|
```text
|
|
feature/student-occurrence-index-finder
|
|
```
|
|
|
|
## Результат
|
|
|
|
Необходимо реализовать:
|
|
|
|
```text
|
|
StudentOccurrenceIndexFinder.java
|
|
```
|
|
|
|
Существующие интерфейсы и классы:
|
|
|
|
```text
|
|
MyList.java
|
|
Student.java
|
|
StudentBuilder.java
|
|
```
|
|
|
|
изменять не требуется.
|