Является ли параллельный линейный поиск O (1)?

Question

Давайте представим, что мы хотим найти элемент в массиве из n элементов, и мы можем создать столько потоков, сколько захотим.Давайте назначим отдельный поток для каждого элемента массива и посмотрим, что операция сравнения намного дороже, чем создание потоков.Можно ли сказать, что такой алгоритм поиска является O (1)?

Код:

import java.util.concurrent.atomic.AtomicBoolean;

public class scratch {
    static int[] a = new int[100];
    static final int n = 3;
    static boolean expensiveCompare(int pos) {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e){}
        return a[pos] == n;
    }

    static AtomicBoolean answer = new AtomicBoolean(false);

    public static void main(String... args) {
        long start = System.currentTimeMillis();
        a[2] = 3;
        Thread[] threads = new Thread[100];
        for(int i=0; i < 100; ++i) {
            final int k = i;
            threads[i] = new Thread(new Runnable() {
                @Override
                public void run() {
                    if(expensiveCompare(k)) {
                        answer.compareAndExchange(false, true);
                    }
                }
            });
            threads[i].start();
        }

        for(int i = 0; i < 100; ++i) {
            try {
                threads[i].join();
            }catch (InterruptedException e) {}
        }

        System.out.println("Elapsed: " + (System.currentTimeMillis() - start));
        System.out.println("Answer:" + answer);
    }
}

Печать: "Elapsed: 1000"

public class scratch {
    static final int n = 3;
    static int[] a = new int[100];
    static boolean answer = false;

    static boolean expensiveCompare(int pos) {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
        }
        return a[pos] == n;
    }

    public static void main(String... args) {
        long start = System.currentTimeMillis();
        a[2] = 3;
        for (int i = 0; i < 100; ++i) {
            answer |= expensiveCompare(i);
        }
        System.out.println("Elapsed: " + (System.currentTimeMillis() - start));
        System.out.println("Answer:" + answer);
    }
}

Печать:"Прошло 100000".

Answer 1

Предположим, что количество элементов N не ограничено, и столько потоков, сколько требуется, могут работать параллельно.

Давайте даже предположим, что все потоки уже запущены и работают, чтобы избежать O (N) Стоимость.Затем сравнения могут быть выполнены за время O (1), по одному на поток.Но это еще не все: вы также хотите знать, был ли найден ключ, и, необязательно, каким потоком.

Этот набор результатов не может быть выполнен в O (1), поскольку никакая инструкция процессора не обрабатывает неограниченное число аргументов.,Поскольку это число ограничено, даже если игнорировать конфликты в общей памяти, лучшее, что вы можете сделать, - объединить N результатов в виде дерева (N => N / k => N / k² => N / k³ ...=> 1) и получить один результат после O (Log N) этапов (количество обрабатываемых битов уменьшается геометрическим образом).

Таким образом, в лучшем случае сложность O (Log N).[И по иронии судьбы, если данные отсортированы, вы не можете разбить один поток с миллиардом.]

---

Это общее правило: нет проблем, так что все входные данные вносят свой вклад в решениеможет быть решен за время O (1), независимо от вычислительной мощности.

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

Answer 2

Ваш код O (1) не из-за потоков, а из-за того, что размер массива постоянен (100).Если мы заменим это переменной, то это:

for(int i=0; i < n; ++i) {

уже будет O (n).Даже не имеет значения, что вы делаете внутри цикла (если вы не измените i или n), только заголовок цикла уже выполнит O (n) количество инструкций.

В более общем смысле, вы даже не можете запустить n потоков за O (1), поэтому запуск потоков n не может дать вам время O (1) (и, конечно, при условии, что все потоки равныработает параллельно, т.е. притворяется, что у вас бесконечное количество ядер).

считают, что операция сравнения намного дороже, чем создание потоков

Это не имеет значениянасколько дорогая каждая операция.Это просто константы, а big-O не заботится о константах.

Answer 3

Этот вопрос затрагивает один из более тонких аспектов нотации big-O: модель стоимости .

Когда мы думаем о том, сколько «шагов» будет выполнять определенный алгоритмЧтобы выполнить задачу, нам нужно решить, что мы можем сделать за один шаг.В большинстве случаев люди принимают модель затрат, когда любая базовая инструкция, такая как сравнение, базовая арифметическая операция или вызов функции, стоит 1 шаг.Это полезное упрощение, даже если на реальных компьютерах выполнение этих операций может занимать разное количество времени, в зависимости от факторов, которые не учитываются моделью (например, добавляем ли мы два числа в регистры, в кэш, в основную память,на диске?), потому что это позволяет нам думать о том, как программа масштабируется до больших входов, не суетясь о слишком большом количестве деталей.

Однако в некоторых приложениях подходят разные модели затрат: например, при написании сетевого программного обеспечения вы можете посчитать передачу по сети как один шаг, а любые вычисления, которые происходят на одном узле, являются бесплатными, независимо оталгоритм.Точно так же было бы полезно проанализировать алгоритмы, разработанные для хорошей работы с локальностью памяти, основываясь на том, сколько раз им нужно читать из основной памяти, игнорируя стоимость любой работы, которую они выполняют с тем, что они читают.Ни один из этих подходов не является «правильным» - они все измеряют абстрактное, вымышленное число - но они могут быть полезны для разных вещей.

Итак, чтобы ответить на ваш вопрос напрямую: является ли этот алгоритмO (1) или O (n) зависит от модели затрат.Если вы решите, что начальные потоки свободны и что одна операция с любым количеством потоков считается одним шагом, тогда да, это O (1).Если вы решите, что запуск потока стоит единицы работы или что операция с одним потоком считается единицей работы, то это O (n).Какая модель затрат подходит для ваших целей, зависит от вопроса, на который вы хотите ответить.

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

Answer 4

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

В реальной жизни у вас ограниченное количество ЦП или вычислительных узлов.Если у вас k процессоров, это что-то вроде O (n / k) , потому что вы делаете k сравнений за раз.

Теперь, если k многоменьше чем n (что характерно для ПК), то O (n / k) ~ O (n).Например, если ваш процессор имеет 4 ядра (и он не растет), k = 4, и, если потенциально n = 100000, то O (n / k) по-прежнему равно O (n).

Если ваш массивочень мала, и k близко к n (n / k