Найти минимум в массиве используя наиболее оптимальный алгоритм

@_Ivana · Регистрация: 01.03.2013

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

Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее оптимальный алгоритм, написать код, реализующий его идею, и обосновать его теоретически.

@GbaLog- · 08.08.2016, 09:52

Ferrari F1, Потому что затратит время на "создание" этих самых потоков. Ну, в моем случае, просто затратит время на осознание того, что их создать нельзя и надо их эмулировать или как там на самом деле это делается.

ValeryS · 08.08.2016, 10:06

Сообщение от Ferrari F1

если потоки выполняются синхронно, то это должно создавать выигрыш во времени.

не факт
давай рассмотрим твой вариант по 2 элемента и массив на 128 элементов(считать удобней

), допустим есть 100 процессоров значит все потоки выполняются параллельно,
первый проход 64 потока, дополнительный массив 64 элементов
второй проход 32 потоков, доп массив 32 элемента
третий проход 16 потоков, доп массив 16 элементов
четвертый проход 8 потоков, доп массив 8 элементов
пятый проход 4 потока, доп массив 4 элемента
шестой проход 2 потока, доп массив 2
седьмой проход 1 поток, выход
вроде бы всего 7 сравнений
но нужна дополнительная память, а это расходы на обслуживания памяти, в отличии от однопоточного где работа скорее всего будет вестись с регистрами
плюс обслуживание потоков
я как то разворачивал цикл от 2 до 128,, здесь же была задачка, так вот,после какого то числа, скорость исполнения резко падала, поскольку результаты заносились в ОЗУ а не в регистры
в общем пробовать надо
и универсального решения нет

поскольку от сложности O(N) никуда не уйдешь

@Voivoid · 08.08.2016, 10:06

Сообщение от _Ivana

А на словах передали, что f-ки запускаются в разных потоках/на разных компьютерах, а s рассчитывается из размера массива и количества независимых ядер/компьютеров. Он сказал - пойдет.

Меняй преподавателя

Этот код мало того, что не cache friendly ( т.к. постоянно приходится обращаться к разным частям массива), так и, как я уже говорил, попытки распараллелить алгоритм будут в целом бесполезными. Очевидно же, что на процессор нагрузка минимальная ( парочка арифметических операций ), а основная нагрузка здесь будет на шину памяти ( которая, как правило, одна для всех ядер ).

@LVV · 08.08.2016, 11:23

Сообщение от IGPIGP

факт того, что на процессоре в 5Гц, это будет быстрее чем на процессоре в 1 Гц, не говорит об ускорении алгоритма.

Здравая мысль.
Можно ли ускорить поиск наименьшего элемента массива в миллион раз раз?
Можно, если использовать миллион компьютеров!
Разбиваем массив на миллион частей.
И одновременно выполняем:
на первом компьютере - поиск в первой части массива,
на втором - во второй части (если она есть)
и т.д.
на последнем - находим минимум из минимумов, найденных на предыдущих компьютерах.
(разумеется, это примитивные рассуждения, без рекурсии и прочих тонкостей):

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

IGPIGP · 08.08.2016, 12:44

Сообщение от Ferrari F1

IGPIGP, в теории, если потоки выполняются синхронно, то это должно создавать выигрыш во времени. Очевидность

Вас не проведёшь Ferrari F1. Вы знаете секрет. Так раскройте его, пояснив в чём это противоречит сказанному мной и другими?

Добавлено через 6 минут

Сообщение от ValeryS

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

если целые сравнивать, -да. А если оператор сравнения вычисляет вероятность совпадения характеристик методом кореляционных моменnов? У много-поточности есть аргументы и на небольших массивах.

@Ferrari F1 · 08.08.2016, 12:54

IGPIGP, ничем) Моя беда в том, что я очень тороплюсь с ответом практически всегда.
Тороплюсь так, что очень поверхностно читаю и понимаю комментарии людей, на чьи сообщения я впоследствии отвечаю...

IGPIGP · 08.08.2016, 13:02

Сообщение от IGPIGP

А если оператор сравнения вычисляет вероятность совпадения характеристик мета галактик методом корреляционных моментов?

(шутка юмора) написал неправильно.

Сообщение от Ferrari F1

Моя беда

Бывает)

@_Ivana · 08.08.2016, 14:55 **[ТС]**

Сообщение от Voivoid

Меняй преподавателя

Ну мыж теоретики, у нас и кафедра теоретического рассусоливания на отвлеченные темы

Так что препод подходящий. А всякие кеши-шины-векторизации и прочие детали реализации для нас непринципиальны (по крайней мере в этой задаче) - нам главное ~~хвост~~ принцип

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

@Voivoid · 08.08.2016, 15:17

Сообщение от _Ivana

нам главное хвост принцип

Принцип тож не очень, т.к. UB на пустом массиве

@_Ivana · 08.08.2016, 15:19 **[ТС]**

Сообщение от Voivoid

UB на пустом массиве

ну это ерунда, и опять таки детали реализации, не влияющие на принцип. А он в том, что некоторые алгоритмы тривиально распараллеливаются, а некоторые не очень

@Voivoid · 08.08.2016, 15:27

Сообщение от _Ivana

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

Тогда надо писать на haskell'е и надеяться на оптимизации компилятора

@_Ivana · 08.08.2016, 15:36 **[ТС]**

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

IGPIGP · 08.08.2016, 16:53

Сообщение от _Ivana

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

Дык этого же не было в условии и каждый наивно подумал, что мыж практики тут все (кроме меня

).

@_Ivana · 08.08.2016, 16:57 **[ТС]**

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

влиянием далеких звезд можно пренебречь

IGPIGP · 08.08.2016, 17:23

Сообщение от _Ivana

влиянием далеких звезд можно пренебречь

Ну их свет не влияет не на кеш ни на шину. Это и так ясно. Теорию струн трогать не будем.

@_Ivana · 08.08.2016, 17:25 **[ТС]**

Так и кеш с шиной не влияют на принцип алгоритма распараллеливания. А фраза про далекие звезды действительно встречалась у нас в задачках по физике, даже не на тему теории струн

@zarko97 · 03.02.2017, 14:48

C++
1
return *std::min_element(std::begin(arr), std::end(arr));

MrGluck · 03.02.2017, 17:10

Для С++17 есть constexpr версия min_element, так что "дождались".
Но для С++11 уже можно сделать CT алгоритм
http://stackoverflow.com/quest... mpile-time

Так что самый быстрый алгоритм вычисляет результат в момент компиляции и при выполнении мы лишь выводим результат.

Добавлено через 8 минут
Дабы не быть голословным:
http://www.open-std.org/jtc1/s... /n4618.pdf
Страница 993,

// 25.5.7, minimum and maximum
template<class ForwardIterator>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

Croessmah · 03.02.2017, 17:35

Сообщение от MrGluck

Так что самый быстрый алгоритм вычисляет результат в момент компиляции и при выполнении мы лишь выводим результат.

Если загнать в узкие рамки,
то самый быстрый алгоритм будет
тот, который работает с
массивом из одного элемента.

IGPIGP · 02.06.2017, 18:44

Сообщение от Croessmah

Если загнать в узкие рамки,
то самый быстрый алгоритм будет
тот, который работает с
массивом из одного элемента.

Массив указателей указывающих на элементы одного списка с некоторым шагом. Тут есть и расширяемости и произвольного доступа по чуть-чуть. А чтобы не класть в список обратные ссылки на узлы хранимые в массиве можно сделать итераторы списка переменными. А ещё лучше - список - хранилище (куда всё заходит по мере поступления), и ещё пара о которой сказано, то есть упорядоченный список итераторов хранилища и вектор часть данных которого - итераторы данного списка. Это лучше увидеть. Вот тута:
https://www.cyberforum.ru/blog... g4772.html

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32

	Найти минимум в массиве используя наиболее оптимальный алгоритм 03.08.2016, 22:30. Показов 15324. Ответов 186 Метки нет (Все метки) Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее оптимальный алгоритм, написать код, реализующий его идею, и обосновать его теоретически. 4

@GbaLog- Любитель чаепитий 3745 / 1801 / 566 Регистрация: 24.08.2014 Сообщений: 6,020 Записей в блоге: 1
	08.08.2016, 09:52
	Ferrari F1, Потому что затратит время на "создание" этих самых потоков. Ну, в моем случае, просто затратит время на осознание того, что их создать нельзя и надо их эмулировать или как там на самом деле это делается. 0

@Ferrari F1 807 / 534 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	08.08.2016, 12:54
	IGPIGP, ничем) Моя беда в том, что я очень тороплюсь с ответом практически всегда. Тороплюсь так, что очень поверхностно читаю и понимаю комментарии людей, на чьи сообщения я впоследствии отвечаю... 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	08.08.2016, 15:36 [ТС]
	Voivoid, ну вы же понимаете, что любая теоретическая задача должна решаться в рамках каких-либо условий и ограничений. Есть абстракция "массив" - это доступ за определенное количество времени (условных тактов) к любому элементу - все, это данность. А в реальности в одних ситуациях у нас оказывается есть некий кеш памяти, и если массив не влезает весь в кеш, то при доступе к разным участкам/элементам происходит перезагрузка кеша, что замедляет общий доступ. То же самое про векторизацию и т.п. Но нам на уроках теории фиолетово это все - мы занимаемся принципами. А на уроках практики мы будем учитывать все эти особенности аппаратной реализации. И то, только если они там будут. 1

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	08.08.2016, 17:25 [ТС]
	Так и кеш с шиной не влияют на принцип алгоритма распараллеливания. А фраза про далекие звезды действительно встречалась у нас в задачках по физике, даже не на тему теории струн 0