Ищем иголку в стоге без использования всем известных алгоритмов

[Germanjon]

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

1. Сформируйте массив со всеми значениями от 0 до cell.
2. cell раз случайным образом поменяйте значения двух элементов этого массива. Будем считать, что получится тщательно перемешанный массив. Его можно даже сохранить, чтобы не тратить время в следующий раз на генерацию.
3. Дальше последовательный перебор элементов перемешанного массива.

[Paul_Stark]

Не пойму где тут отслеживание уже выбранных ячеек массива? выглядит как мой первый метод, или я что-то не так понял, объясните подробнее пожалуйста!

[Germanjon]

Итоговый массив содержит перемешанный перечень всех ячеек (все значения уникальны). Если вы последовательно проходите по нему (элемент0, элемент1, элемент2...), то:
— Не возвращаетесь к уже посещённой ячейке.
— Гарантированно проходите все ячейки по одному разу.

[Paul_Stark]

То есть массив с указателями на номера ячеек исследуемого массива? не меняя адреса значений массива, я меняю набор указателей к этим значениям. Хорошо, я попробую так сделать!)

[Paul_Stark]

Вот мои результаты, возможно корявенько, но как есть. в setup определяется цикл значений от 0 до cell, все остальное по старому, те же методы + вот новый, код которого прилагаю

Картинки

[Germanjon]

Да, я имел в виду этот метод, но есть один нюанс: формирование массива из случайных уникальных элементов занимает определённое время.
Чтобы обеспечить грамотное сравнение поиска иголки, нужно как-то исключить этот период из вычислений:
— Или сохранить «перемешанный» массив куда-либо и затем обращаться непосредственно к нему (без генерации в начале программы).
— Или запускать счётчик времени после перемешивания массива, перед началом поиска.

[Germanjon]

PS. Исходник лучше выкладывать в виде текста, с использованием тега

[vassabi]

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

так что вам нужно предварительно сделать таблицу для рендома размером в cell, где
а) будут храниться предвычесленные числа random(i+1) и
б) они не должны повторяться
а потом уже запускать численный эксперимент.
Впрочем, по построению такого массива заметно, что в среднем он будет тратить столько же времени на поиск, сколько и поиск с конца (хотя, все зависит того, насколько равномерный у вас рандом
в
// Рандомим иглу и кидаем ее в стог
needle = random(cell + 1);
potenArr[needle] = 1;
)

[Paul_Stark]

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

[BugM]

Выбор рандомного, но каждый раз другого значения, из ограниченного массива это типовая задача.

Для начала можно почитать про shuffle array и брать элементы в порядке сортировки.
Почитать тут

[Paul_Stark]

Спасибо за наводку!)

[Compolomus]

На самом деле вариантов много, можно разделить стог на 10 маленьких, перебирать маленькие с начала до конца, но выбирать маленький стог рандомно. Можно даже проверенные исключать из массива.
То есть массив 1… 10
Рандом выдал 2
Исключаем 2 из массива
Следующий Рандом из 9 элементов

[Paul_Stark]

Примерно так я и решил эту задачу, после каждой проверки я урезал массив и проверял по новой, подробнее в будущем)

[anatolii_kostrygin]

У меня такое ощущение, что вы до конца не решили, что именно измеряете:
Исходная задача: определить, какой поиск быстрее, рандом или последовательный.

Вы предлагаете скорость измерять напрямую — временем работы. Тогда на самом деле вы просто показали, что рандом (а особенно на Arduino) работает раз в 100 медленнее, чем просто обращение к случайной ячейке массива. Разумный результат — интуитивно хочется, чтобы «одна операция» стоила примерно «единицу времени». А вот вывод неверный — дело тут не в удаче, что вы собственно и показали.

С точки зрения математика, «быстрее» надо измерять не в секундах, а в количестве обращений к массиву: сколько раз в среднем надо «ткнуть» в массив, чтобы попасть в нужный элемент.
Ответ известен — если вы «последовательно идёте» вдоль массива длины 100, то в среднем на 50-м ходу будете попадать. Если тыкать каждый раз в случайное место массива, то вероятность попасть за один «тычок» = 1/100. В среднем нужно 100 попыток. Итого рандомный алгоритм ровно в два раза медленнее в среднем, чем последовательный.
А если в рандомном алгоритме вы не будете проверять те ячейки, которые уже проверяли, как предлагали выше, то алгоритмы работают одно и то же время.

Имхо, почитайте про основы теорвера — часто они позволяют отвечать на вопросы без программирования Arduino, «оставляя время на что-нибудь весёлое» (простите за шпильку).
Для затравки:
habr.com/ru/post/365855
habr.com/ru/post/433512
habr.com/ru/post/178817

[Paul_Stark]

Согласен, под «капот» функции рандома в среде ардуино я не заглядывал, поэтому не могу с утверждением заявлять, что функция рандома работает быстро или медленно, те функции, что я видел, состояли из нескольких арифметический операций, без глубоких обращений к таймерам или чему то еще, что могло бы занимать время. Поэтому мыслей о том, что функция рандома замедлила среднюю скорость алгоритма в 57 раз, меня не посетила

[anatolii_kostrygin]

Мне кажется, я не четко выразил мысль в предыдущем комментарии.

У вас была задача сравнить два алгоритма, вы написали бенчмарк. Главное тут — чётко зафиксировать, что и как вы измеряете. Основных способа два:

• «Метод инженера»: давайте измерим время работы в секундах
• «Метод математика»: чёрт с ним, с секундами, будем измерять в «попугаях». Например, числе обращений к массиву.

ИМХО, здесь стоило выбрать второй метод. Вы же интересуетесь, как быстрее «искать иголку в стоге сена». Смею предположить, что исходная проблема была вполне «некомпьютерной», вроде поиска нужной бумажки в стопке. В этой ситуации наш «рандом» ничуть не медленнее последовательного выбирания бумажек. При этом «время работы» алгоритма пропорционально числу заглядываний в стопку.

ЗЫ Зачем-таки вам массив? Вы же ищете одну иголку и не интересуетесь значениями в остальных ячейках. Вот код на питоне псевдокод (только методы поиска)

код

heap_size = 1000  # размер стога
needle = random(heap_size)  # запоминаем позицию иголки

# последовательный поиск
def seq_search(_needle):
    for i in 1..heap_size:
        if i == _needle:
            return

# случайный поиск
def rand_search(_needle):
    n_checks = 0
    do:
        i = random(heap_size)
        ++n_checks
    while (i != _needle)
    return n_checks  # заодно вернём количество "обращений к стогу"