Почти любой алгоритм, можно немного изменить, радикально уменьшив время его работы в лучшем случае. Как?

Question

[Homemade]

Начал читать Кормена. Там есть вот такой вот вопрос, но ответа нету. Я предполагаю, что ответ: "Отдельно обработать лучший случай (через if)".
Вероятно, что я ошибаюсь, поэтому задаю этот вопрос вам.

Comments

[Adamos]

Возможно, это про баланс ресурсов. Жрет больше памяти, но работает быстрее, и наоборот.

Answer 1

[Wataru]

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

Заодно тут ответ на вопрос, почему почти любой? Вы можете уменьшить время до линейного в одном случае. Поэтому, если алгоритм в лучшем случае работает не хуже чем за линейную сложность, то улучшить его таким образом не всегда можно.

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

Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.

Comments

[Adamos]

Поиск минимума легко сводится к О(1) предварительной сортировкой ;)

[Wataru]

Adamos, А сколько эта предварительная сортировка работает?

[Adamos]

Илья Николаевский, "А это уже второй вопрос!" (с)

[xmoonlight]

Илья Николаевский,

Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.

ещё как ускорю: с заранее готовыми (уже посчитанными/отсортированными!) результатами из базы по N-штук с асинхронной обработкой.

[Wataru]

xmoonlight, И как вы поймете, что заданный вот этот набор из n чисел (которые на вход я могу вам подать не отсортированными) это один из вот тех предпосдчитанных результатов? Если вы хоть раз обращаетесь к каждому элементу (а без этого никак точную сумму не получить, ведь если я этот элемент увеличу на 1, вся сумма изменится).

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

[xmoonlight]

Илья Николаевский, про суммы: мы знаем, что от перемены мест слагаемых сумма не меняется.
Я просто пробегусь по массиву от начала до конца с нужными мне длинами шингл (как поток данных, а не как числа!!!), а перестановки - меня не интересуют, т.к. они уже есть в базе.
Всё, что поймаю - моё (результат части всей суммы), что нет - прибавляю как обычно.
А теперь подключим асинхрон!)

[Wataru]

xmoonlight, Ну вот у вас есть "шингл" из, скажем 10 чисел (40 байт). Как, по вашему, его база ищет? Она не может магически догадаться, что это вооон та запись. Для поиска по ключу неважно с каким индексом, хешами и алгоритмами придется ВЕСЬ ключ прочитать хотя бы один раз. И так вы прочитаете КАЖДЫЙ шингл, в итоге вы по одному разу прочитаете все входные данные и получите ту же линейную сложность.

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

[xmoonlight]

Илья Николаевский,

Потому что тупо сложить несколько чисел всегда быстрее чем искать их среди предподсчитанных.

Всё зависит от типа чисел и от типа адресации хранилища. Обычно, такое хранилище - это гиперкуб. Т.е. все числа в шингле - это проекции ответа на его грани. И выполняется гораздо быстрее обычной суммы.

[Wataru]

хранилище - это гиперкуб

На любой современной архитектуре сложить k чисел будет быстрее, чем использовать их как индексы в многомерном массиве. Потому что индексация сама по себе будет складывать и умножать числа для вычисления адреса, и потом еще надо обратится к памяти, чтобы прочитать ответ.
При суммировании же достаточно прибавлять число к регистру. Хороший компилятор сможет использовать те же самые операции, что и вариант с гиперкубом, только больше половины из них будут выкинуты.

[Wataru]

xmoonlight, Чтобы не быть голословным, сравните ассемблер в двух вариантах.

[Homemade]

Илья Николаевский, что вы думаете по этому вопросу?

[xmoonlight]

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

[Wataru]

xmoonlight, Это что вообще там у вас на питоне? вы строите список из 4-х чисел и берете аттрибут val? Но у списка же нет такого аттрибута.

[xmoonlight]

Илья Николаевский, Верно: нет.
Там 4 числа - это просто адресация на результат: просто, чтобы сам принцип работы был понятен. Разумеется, что это через прямую работу с памятью делается.

[Wataru]

xmoonlight,

Там 4 числа - это просто адресация на результат: просто, чтобы сам принцип работы был понятен. Разумеется, что это через прямую работу с памятью делается.

Непонятно. Ваш код на питоне не делает никакой адресации, там заводится список! Смотрите в байт код.

Если вы хотели сделать что-то вроде storage[[a,b,c,d]].val или storage[a][b][c][d].val (через многомерные массивы), то там будет то же самое а то имедленнее, что код на С++, что привел я - вычисление адреса или несколько индексаций.

Сумма в любом случае быстрее.

[xmoonlight]

Илья Николаевский, должна быть быстрее, но далеко не факт при большом количестве слагаемых или чисел с плав.точкой. Нужно исследовать.
Но уверен, что ощутимый прирост будет пусть лишь после 20,50,100 цифр в шингле, но будет. (имхо)

PS:

(через многомерные массивы), то там будет то же самое а то имедленнее, что код на С++, что привел я

список формируется однократно в начале, а прямая адресация к памяти быстрее, чем запрос через массив.

[Wataru]

xmoonlight, Ну смиритесь уже, что глупость сморозили!

прирост будет пусть лишь после 20,50,100 цифр

Уже для 32 бит в "ключе" вам надо несколько гигабайт только что бы сохранить все предподсчитаные ответы. Для 20 цифр вы физически не сможете ничего сделать. Да и обращение к этому монстру будет медленнее тупо сложения частей ключа, потому что оно всегда будет не в кэше.

список формируется однократно в начале, а прямая адресация к памяти быстрее, чем запрос через массив

А куда делась ваша навороченная база данных с асинхронными запросами и шинглами? Во-первых, обращение к многомерному плоскому массиву - это и есть прямая адресация. Смотрите мою ссылку выше - компилятор тупо вычисляет адрес, умножая и складывая индексы.
Далее, прямая адресация, как я уже говорил - самый быстрый способ использовать предподсчет. Но, даже если предположить что у нас бесконечная память и забить на кэш, то тупо сложение будет быстрее прямой адресации! Потому что сложение - это n операций add, а адресация - это n операций add и умножений/сдвигов. Плюс обращение по этому адресу. Даже если сложения заменить на or, то это быстрее адресацию не сделает, ибо в современных процессорах уже давно сложение и битовые операции занимают одно и то же время.

[xmoonlight]

Илья Николаевский,

Ну смиритесь уже, что глупость сморозили!

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

А куда делась ваша навороченная база данных с асинхронными запросами и шинглами?

Никуда. База предпосчитанных результатов - это и есть хранилище в памяти с доступом по прямой адресации.

Во-первых, обращение к многомерному плоскому массиву - это и есть прямая адресация.

Это поиск значений по смещениям, начиная с адреса переменной имени массива. Это НЕ прямая адресация!

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

[Wataru]

xmoonlight,
Если ты не умеешь в ассемблер и тебе непонятно что операция A всегда будет быстрее операций A,B,C, то, хорошо, вот тест:

----------------------------------------------------------------------------------------
Benchmark                              Time             CPU   Iterations UserCounters...
----------------------------------------------------------------------------------------
Sum1_bn/iterations:1000000000       3.30 ns         3.27 ns   1000000000 sum=5
Sum2_bn/iterations:1000000000       3.38 ns         3.38 ns   1000000000 sum=5

Вот код (используется gbenchmark, компилить без оптимизаций, иначе компилятор предподсчитывает все суммы сам):

void Sum1_bn(benchmark::State& state) {
    unsigned char a = 3, b = 2;
    unsigned char sum;
    for (auto _ : state) {
        sum = a + b;
    }
    state.counters["sum"] = sum;
}

char precompute[256][256];
void Sum2_bn(benchmark::State& state) {
    unsigned char a = 3, b = 2;
    precompute[a][b] = a + b;
    unsigned char sum;
    for (auto _ : state) {
        sum = precompute[a][b];
    }
    state.counters["sum"] = sum;
}
BENCHMARK(Sum1_bn)->Iterations(1000000000);
BENCHMARK(Sum2_bn)->Iterations(1000000000);

Вот ссылка на дизассемблер.

> Это поиск значений по смещениям, начиная с адреса переменной имени массива. Это НЕ прямая адресация!

Ты, видимо, не представляешь, как работают многомерные массивы в C++. Посмотри на дизассемблер. Особенно на операцию "movzx eax, BYTE PTR [rax]".

> На будущее: в похожих случаях советую приводить факты с тестов (и код для запуска теста) перед необоснованными репликами в адрес своих оппонентов про глупость, чтобы выглядеть более достойно при ведении конструктивного диалога.

На будущее, прежде чем писать умные слова, остановись и подумай, применимы ли они тут.

[Coomman]

Уважаемый, почитайте что такое дерево отрезков прежде чем делать такие радикальные заявления.

[Wataru]

Coomman, Я знаю про деревья отрезков. А вот вы, видимо, не в курсе, когда и как их применять. Внимание, вопрос, а как долго эту структуру строить? Ее же вам не дед мороз готовой дает. Постройка такого дерева будет не быстрее суммирования всего массива. Там то же количество операций сложения, но сложная индексация.

[Coomman]

Wataru,

Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.

Ваши слова или я придумал?
Когда у нас стоит задача частого обращения этот предподсчет сразу же нивелируется. И кстати момент, когда требуется использовать, можно также легко предподсчитать с помощью производной. Понятное дело, что его никто не будет юзать для подсчета на пару раз. Но тем не менее стоило подобрать пример получше)

[Wataru]

Coomman, Вы додумали задачу сами, не основываясь на моих словах. Дерево отрезков быстрее наивного алгоритма при подсчете суммы только если надо много раз считать сумму, и при этом между суммированиями массив меняется не сильно. А если стоит задача просто, как я сказал:

суммирования всех чисел в массиве

То дерево отрезков будет медленее.

[Coomman]

Wataru,
Вы сами говорите, что некоторые алгоритмы невозможно сделать быстрее линейного времени выполнения и сами же приводите в пример операции, которые вполне легко ускоряются.
Теперь о предподсчете. Что Вы понимаете под медленнее? Построение дерева линейно, запрос это логарифм. Итого получаем линию.
Заметьте, я даже не ссылаюсь на комментарии выше, где говорится о многопоточке (хотя они тоже правы).
Я лишь говорю о том, что Ваш тезис по отношению конкретно к этим операциям неприменим, чем Вы относительно вводите в заблуждение неопытных формучан (так как Ваш ответ помечен как верный). А потом на собесах будут говорить, что у нас суммирование массива всегда линия

[Wataru]

Coomman,

приводите в пример операции, которые вполне легко ускоряются.

Она не ускоряется! Вы не можете подсчитать сумму в массиве быстрее! Вы можете быстрее наивного метода считать кучу сумм в слабо меняющемся массиве, да. Но это другая задача!

Теперь о предподсчете. Что Вы понимаете под медленнее?

А если массив каждый раз целиком новый (n изменения между ними)? Тогда операции изменения будут уже O(n log n). Если с нуля строить дерево - то зачем оно?

Само построение дерева тоже медленнее наивного алгоритма. Не ассимптотически (там тоже линия), а операционно. Там те же n-1 операции сложения, тот же цикл на n-1 итераций, но при этом сверху еще есть битовые сдвиги, инкрименты при адресации и нелинейные обращения к памяти. Это всегда медленнее тупого прохода по массиву. Тупо по количеству циклов процессора.

[Coomman]

Wataru,
Да пускай предподсчет будет хоть 100 лет.

Автор вопроса цитирует Кормена, который утверждает, что с помощью предподсчета можно ускорить почти любой алгоритм.

Тут мы с помощью предподсчета делаем из линии логарифм. Ускорение? Да.
Следовательно нет смысла говорить о скорость предподсчета, если конечный алгоритм в итоге будет иметь меньшую асимптотику (в контексте данного вопроса)

[Wataru]

Coomman,

> Тут мы с помощью предподсчета делаем из линии логарифм.

Почему бы тогда не сделать константу? Давайте предподсчитаем всю сумму, засунем в одну переменную и весь алгоритм - вывести готовое число. Кстати, тут вы опять показываете свое весьма поверхностное знание дерева отрезков. Сумма всего массива в нем итак считается за константу. Логарифм - это оценка сверху для худшего случая произвольного отрезка.

Я так и RSA за константу взламывать умею и задачу коммивояжора решать. Предподсчет же не важен. Лепота! Вам не кажется, что что-то тут не так?

Ответ прост. Предподсчет не важен для фиксированных входных данных. Вы за 100 лет решаете эту конкретную задачу, хардкодите ответ в переменную и тогда, да, решение за константу. В этом кокретном случае. Вот только проверка, что входные данные попадают под этот случай, неизбежна.

> если конечный алгоритм в итоге будет иметь меньшую асимптотику (в контексте данного вопроса)

Перечитайте вопрос. Он про лучший случай. Это один конкретный набор входных данных, ну или какой-то класс входных данных. И я в ответе именно это и утверждаю, что лучший случай можно ускорить почти всегда. Для линейного алгоритма суммы - это не так, потому что проверка попадания в этот случай тоже линейна и улучшения не даст.

[Coomman]

Wataru,
Даже не обращая внимание на стрелки. Понятное дело, что можно все довести до абсурда и константы, но ваше двачевско-плюсовое прошлое оправдаться тут не поможет.

Можно было просто сказать, что да, пример был не совсем верный, написать другой. Спор ни о чем)

[Wataru]

Coomman, Пример был абсолютно верным. Это вы тут доводите до абсурда. Слышали где-то про структуру, которая, вау, за логарифм сумму считает. Как она работает представляете слабо, когда ее применять не знаете. И начинаете нести бред. Нет, чтобы признать, что зря прикопались к примеру.

Answer 2

[xmoonlight]

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

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