Сообщение Re[7]: Кстати, про Гугель от 06.11.2018 3:33
Изменено 06.11.2018 3:37 ylp
Re[7]: Кстати, про Гугель
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>в разделе "сортирующие сети" и "параллельные вычисления". Могу, правда, ошибаться и там будет квадрат логарифма от размера массива, а не логарифм размера массива.
ylp>>Эти алгоритмы работают не сравнивая попарно элементы, а обрабатывая весь массив целиком (т.е. предполагается не стандартная фон-неймановкая архитектура, а другая модель вычислений). На практике такого полно — GPU, ASIC и т. д.
CM>1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения.
> Соответственно, величина О-фактора останется абсолютно той же.
о, пошли философские разговоры. Люблю такое. что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
CM>3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
CM>Звон ты где-то услышал, но смысл — вообще не понял.
я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
CM>Здравствуйте, ylp, Вы писали:
ylp>>в разделе "сортирующие сети" и "параллельные вычисления". Могу, правда, ошибаться и там будет квадрат логарифма от размера массива, а не логарифм размера массива.
ylp>>Эти алгоритмы работают не сравнивая попарно элементы, а обрабатывая весь массив целиком (т.е. предполагается не стандартная фон-неймановкая архитектура, а другая модель вычислений). На практике такого полно — GPU, ASIC и т. д.
CM>1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения.
> Соответственно, величина О-фактора останется абсолютно той же.
о, пошли философские разговоры. Люблю такое. что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
CM>3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
CM>Звон ты где-то услышал, но смысл — вообще не понял.
я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
Worst-case performance {O(log^{2}(n))} parallel time
Re[7]: Кстати, про Гугель
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
CM>1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения.
> Соответственно, величина О-фактора останется абсолютно той же.
о, пошли философские разговоры. Люблю такое. Что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
CM>3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
CM>Звон ты где-то услышал, но смысл — вообще не понял.
я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
CM>Здравствуйте, ylp, Вы писали:
CM>1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения.
> Соответственно, величина О-фактора останется абсолютно той же.
о, пошли философские разговоры. Люблю такое. Что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
CM>3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
CM>Звон ты где-то услышал, но смысл — вообще не понял.
я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
Worst-case performance {O(log^{2}(n))} parallel time