Есть очень длинный неотсортированный массив, и проверка одного элемента
дорогая (например, сравнение хешей). Нужно распараллелить поиск: найти индекс
элемента, удовлетворяющего условию, используя workers горутин. Это
slices.IndexFunc, только параллельный. Чтобы искать конкретное значение x,
передают func(v T) bool { return v == x }.
// Find возвращает индекс любого элемента arr, для которого match(arr[i]) == true,
// или -1, если такого нет.
func Find[T any](ctx context.Context, arr []T, workers int, match func(T) bool) (int, error)
Требования
- Если подходящих элементов несколько, можно вернуть любой из них. Если нет
ни одного —
(-1, nil). Пустой массив — (-1, nil).
match вызывается для каждого элемента не больше одного раза и не больше
чем в workers горутинах одновременно (workers < 1 считается как 1).
Поиск действительно параллельный: если элементов хватает, работают все workers.- Ранняя остановка: как только кто-то нашёл элемент, остальные горутины
быстро прекращают проверку, а не досматривают свою часть до конца.
- При отмене
ctx поиск прекращается, и функция возвращает (-1, ctx.Err()).
match прервать нельзя, но новые элементы после отмены не проверяются.
- После возврата
Find не остаётся запущенных ею горутин. Код проходит go test -race.
Пример
arr := []int{7, 3, 9, 42, 5, 42, 1}
i, err := Find(ctx, arr, 3, func(v int) bool { return v == 42 })
// i == 3 или i == 5, err == nil
i, _ = Find(ctx, arr, 3, func(v int) bool { return v == 100 })
// i == -1
// FindFirst возвращает наименьший индекс i, для которого match(arr[i]) == true, или -1.
func FindFirst[T any](ctx context.Context, arr []T, workers int, match func(T) bool) (int, error)
- Результат тот же, что у последовательного
slices.IndexFunc.
- Ранняя остановка сохраняется: после того как найден индекс
k, элементы
правее k больше не проверяются. Элементы левее k проверять, конечно,
приходится.
- Остальные требования те же, что у
Find. Если ctx отменили до того, как
ответ стал известен точно, возвращается (-1, ctx.Err()).
Устно: когда параллельный поиск медленнее последовательного? Как выбрать
workers и размер куска?