Обработка очереди в несколько потоков

@Steny · Регистрация: 19.02.2015

Студворк — интернет-сервис помощи студентам

народ, помогите с проблемой. есть два массива: первый выполняет функцию очереди, второй - конечный результат обработки. требуется "раздербанить" очередь по потокам, при этом каждый поток должен иметь доступ к актуальным данным обоих массивов. сразу приведу код, чтоб объяснить.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.ArrayList;
 
public class TestClass {
    ArrayList<String> ochered = new ArrayList<String>();
    ArrayList<String> gotovo = new ArrayList<String>();
 
    public TestClass() {
        // заполняем
        for (int i = 0; i < 1000; i++) {
            double chislo = 100 * Math.random();
            ochered.add(Double.toString(chislo));
        }
        // обрабатываем
        PotokOcheredi potok1 = new PotokOcheredi();
        PotokOcheredi potok2 = new PotokOcheredi();
        PotokOcheredi potok3 = new PotokOcheredi();
        potok1.start();
        potok2.start();
        potok3.start();
        try {
            potok1.join();
            potok2.join();
            potok3.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
 
    public class PotokOcheredi extends Thread {
        public PotokOcheredi() {
            super();
        }
 
        public void run() {
            while (!ochered.isEmpty()) {
                String temp = ochered.get(ochered.size() - 1);
                ochered.remove(ochered.size() - 1);
                boolean est = false;
                for (int i = 0; i < gotovo.size(); i++) {
                    String temp2 = temp.substring(0, temp.indexOf("."));
                    if (gotovo.get(i).startsWith(temp2)) {
                        est = true;
                        break;
                    }
                }
                if (!est) {
                    gotovo.add(temp);
                }
            }
        }
    }
}

в массиве ochered подготавливаются исходные данные. затем в каждом потоке эта очередь дербанится (получаю строку с конца очереди и сразу ее удаляю). затем в цикле проверяю наличие целой части во втором массиве. если ее нет - добавляем всю строчку во второй массив. и так пока не закончится вся очередь (дожидаемся окончания всех потоков). сразу хочу сказать по поводу "бессмысленности" кода - это лишь пример, но логика будет примерна такая. т.е. нужно будет дербанить первый массив, затем проверять по определенному услонию наличие записи во втором.

сразу возникают 2 проблемы:
1. выдергивание записи из первого массива (очереди). есть ненулевая вероятность того, что:
1.1. два или более потока захватят одну и ту же запись (как следствие - ошибка при попытке удаления записи из массива у потока, который взял ее позже)
1.2. попытка взятия вторым потоком записи, которая уже удалена (ошибка - выход за границы массива)
2. момент работы со вторым массивом. допустим первый поток проверяет в цикле на наличие целой части, а второй уже все проверил и добавляет строку во второй массив. первый поток не увидит этих новых данных (где то вычитал, что каждый поток кеширует для себя общие данные и работает уже с ними, время от времени синхронизируя кэш), т.е. первый поток будет полагать, что длинна второго массива равна 6 (допустим), в то время как она уже равна 7.

сразу хочу объясниться по поводу синхронизации. конечно можно было бы при каждом доступе к общим данным их синхронизировать, но есть одно большое НО - каждая такая синхронизация кушает время. при работе с большим количеством данных - разница во времени становится весьма ощутимой. поэтому вопрос - возможно ли проводить синхронизацию как-то избирательно? т.е. если во второй массив не добавлялись никакие данные - то и синхронизировать нет никакой надобности. а вот когда один из потоков пишет данные в массив - автоматически обновлять все данные в остальных потоках (чтобы поток видел, что длинна массива уже 7, а не 6). возможно ли такое реализовать и как?

ну и по первой проблеме - возможно есть какие-то более быстрые массивы для совместного доступа? хранить планируется String, но возможно есть что-то более универсальное.

данных - гигабайты, хочется разгребать их в несколько потоков, без ущерба для данных.

буду рад любой помощи - мысли, как это можно реализовать, конкретные ссылки, примеры кода. спасибо!

@Gibby · 30.05.2013, 18:53

Это лишь пример, но...Целая часть берется вот так:
Java
1
(int) number;
Вместо поиска перебором используйте HashSet или HashMap (в зависимости от того, какие у вас данные) — это серьезно повысит скорость поиска. На больших объемах разница будет на порядки (и, возможно, тогда вам не потребуется использовать потоки).
Зачем вы удаляете данные из исходного массива? Это занимает время, а смысла в этой операции я не вижу.
Касательно многопоточности. Что вам мешает дать каждому потоку свой "фронт работ" и пусть он там трудится. Дайте ему startIndex и endIndex и все.

Добавлено через 13 минут
Другое дело, встает вопрос доступа к итоговому набору данных. В момент, когда один поток хочет добавить данные, все остальные должны прекратить поиск. Вообще говоря, есть специальный класс Lock, но каким образом его использовать в данном случае я, к сожалению, не знаю.

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .