[details="Спойлер"]
int arr[10] = {553, 555, 555, 554, 556, 555, 557, 554, 552, 555}; //Массив с числами
int arrD[10] = {0};
byte arrC[10] = {0}; //Кол-во повторов числа
void setup() {
// put your setup code here, to run once:
Serial.begin(9600);
for (byte n = 0; n < 10; n++) {
for (byte k = 0; k < 10; k++) {
if (arrD[k] == 0) {
arrD[k] = arr[n];
++arrC[k];
break;
}
if (arrD[k] == arr[n]) {
++arrC[k];
break;
}
}
}
byte m = 0, ind = 0;
for (byte n = 0; n < 10; n++) {
if (arrD[n] == 0) break;
Serial.print(arrD[n]); Serial.print(" = "); Serial.println(arrC[n]);
if (arrC[n] > m) {
ind = n;
m = arrC[n];
}
}
Serial.print("maxD: "); Serial.println(arrD[ind]);
}
void loop() {
// put your main code here, to run repeatedly:
}
Результат:
553 = 1
555 = 4
554 = 2
556 = 1
557 = 1
552 = 1
maxD: 555
[/details]
Необходимо найти в массиве чисел число максимально повторяющееся.
Я это сделал. Но возможно ли как-то оптимизировать мой код или он написан верно? Нужна скорость работы ну и использование памяти. Я не особо в программировании, поэтому прошу посмотреть.
Вообще-то об оптимизации, как правило, имеет смысл говорить только если длина массива существенно превышает 10.
Ваш алгоритм имеет асимптотическую сложность O(N^2), тогда как в оптимальном случае он может иметь сложность не хуже O(N*log(N)). (в частных случаях - до O(N))
Но не факт, что на 10 элементах такой алгоритм будет работать быстрее Вашего.
А если просто отсортировать массив методом “половинная вставка” (так кажется называется?) и в момент сортировки если элемент уже существует в массиве - увеличивать его счетчик?
На выходе получим отсортированный массив без повторений (можно из него получить быстро максимальное и минимальное значение) и количество вхождений каждого элемента массива в первоначальном.
А про числа в массиве arr что-то известно? Например, максимальное и минимальное значения? Если известно, то, возможно, удастся сделать это совсем просто и линейно по скорости.
Скорее всего нет. В массиве будет выборка с аналогового датчика. Хочу попробовать фильтровать именно так. Так как другие фильтры(легкие, например среднее арифметическое) все равно не то.
Задача толком не объяснена, но позволю себе предположить, что это придётся делать много раз и надо вынести в функцию. Если так, то не забывайте перед началом заполнять вспомогательные массивы нулями. Это они у Вас только в первый раз “и так заполнены”, а потом в них старая грязь будет.
Опять, же толком ничего непонятно, но вот из этого:
Я делаю вывод, что в реальности значения будут не сильно отличаться друг от друга, в пределах 10-20 от min до max.
Тогда бы я ушёл от квадратичности и сделал бы линейно. Рассказывать как? Или Вас всё устраивает и с квадратичным алгоритмом?
@TempArd
У вас реально хороший алгоритм. Я написал без второго массива - но как ни старался, он получается медленнее вашего процентов на 20-25, в зависимости от данных. Зато расход памяти у меня чуть ниже.
Я думал об этом. Как вариант, если MaxC < COUNT_NUM / 3 то применить арифметическое усреднение. Надеясь, что таких случаев будет мало…
По второму вопросу …вряд ли так будет. Но, надо тогда подумать , если это станет проблемой.
Спасибо, учту. А так, да, это будет отдельной функцией.
Именно так. Но в частных случаях эти значения будут либо увеличиваться либо уменьшаться. Данные с датчика давления воды. (Идет набор воды, идет расход воды, и собсно третье, когда система в покое и шумит датчик) На этот случай у меня пока решение такое, Брать минимальное при постоянном уменьшении(расходе) и максимальное при увеличении(наборе), ну или последние 3 значения усредненные.
Если не затруднит и я в этом разберусь, то конечно вариант посмотрю. Искал перед вопросом в интернете, но не смог найти для себя решение. И как-то неожиданно в башке родился алгоритм. Хотя я далеко не программист, но что-то могу)
Спасибо. Возможно мне будет важна память а не скорость. Но пока и то и другое важно)
Как говорится дуракам везет))) Ну или новичкам) Хотя, я давно связан с программированием, но далеко не программист нисколько вообще… (хобби на которое катастрофически не хватает времени :()
узнаёте минимальное и максимальное значение данных в массиве. Это делается за 1 проход по массиву. Допустим dataMin и dataMax;
заводите вспомогательный массив байтов tmpBuf размером dataMax - dataMin и заполняете его нулями;
делаете один проход по основному массиву: для каждого значения val из основного массива, увеличиваете на 1 значение tmpBuf[val - dataMin].
делаете один проход по вспомогательному массиву с целью запомнить индекс максимального значения в нём (idxMax).
результат: число dataMin + idxMax - наиболее часто встречается в исходном массиве.
Для проверки и сравнения, я вынес Ваш квадратичный метод в функцию findMax; написал вышеописанный линейный метод в виде функции linearFindMax (в ней, вместо подробных комментариев, проставлены номера шагов алгоритма, описанного выше); написал функцию тестирования testOneMethod, которая вызывает переданную ей функцию 20 тысяч раз; а в функции setup вызвал testOneMethod дважды - для квадратичного и линейного алгоритмов.
Результат, полученный на Nano приведен внизу текста программы. Как видите, линейный метод выигрывает по времени в полтора раза. Что касается памяти, то в линейном массив размером “в разброс данных” против двух массивов равных размеру исходного массива в квадратичном. Кто выигрывает, зависит от “разброса данных”.
Текст тестового скетча
#include <stdint.h>
int arr[10] = {553, 555, 555, 554, 556, 555, 557, 554, 552, 555}; //Массив с числами
constexpr size_t arrSize = sizeof(arr) / sizeof(arr[0]);
int findMax(void) {
int arrD[arrSize] = {0};
byte arrC[arrSize] = {0}; //Кол-во повторов числа
for (byte n = 0; n < arrSize; n++) {
for (byte k = 0; k < arrSize; k++) {
if (arrD[k] == 0) {
arrD[k] = arr[n];
++arrC[k];
break;
}
if (arrD[k] == arr[n]) {
++arrC[k];
break;
}
}
}
byte m = 0, ind = 0;
for (byte n = 0; n < arrSize; n++) {
if (arrD[n] == 0) break;
//Serial.print(arrD[n]); Serial.print(" = "); Serial.println(arrC[n]);
if (arrC[n] > m) {
ind = n;
m = arrC[n];
}
}
//Serial.print("maxD: "); Serial.println(arrD[ind]);
return arrD[ind];
}
int linearFindMax(void) {
//
// ШАГ №1
//
int dataMax = INT16_MIN;
int dataMin = INT16_MAX;
for (uint8_t i = 0; i < arrSize; i++) {
const int ai = arr[i];
if (ai > dataMax) dataMax = ai;
if (ai < dataMin) dataMin = ai;
}
//
// ШАГ №2
//
const size_t tmpSize = dataMax - dataMin;
uint8_t * tmpBuf = reinterpret_cast<uint8_t *>(calloc(tmpSize, sizeof(uint8_t)));
if (! tmpBuf) {
Serial.println("Что-то с памятью моей стало :(");
return 0;
}
//
// ШАГ №3
//
for (uint8_t i = 0; i < arrSize; i++) ++tmpBuf[arr[i] - dataMin];
//
// ШАГ №4
//
uint8_t indMax = 0, maxRep = 0;
for (uint8_t i = 0; i < tmpSize; i++) {
const uint8_t tbi = tmpBuf[i];
if (tbi > maxRep) {
maxRep = tbi;
indMax = i;
}
}
free (tmpBuf); // Массив tmpBuf больше не нужен, освобождаем память
//
// ШАГ №5
//
return dataMin + indMax;
}
void testOneMethod(const char * title, int (* f)(void)) {
uint32_t sum = 0;
constexpr int total = 20000;
const uint32_t start = millis();
for (uint16_t cnt = 0; cnt < total; cnt++) sum += f();
const uint32_t duration = millis() - start;
Serial.print("***** \"");
Serial.print(title);
Serial.println("\" test");
Serial.print("Результат: ");
Serial.println(sum / total);
Serial.print("Время: ");
Serial.print(duration);
Serial.println(" мс");
}
void setup(void) {
// put your setup code here, to run once:
Serial.begin(9600);
testOneMethod("Square", findMax);
testOneMethod("Linear", linearFindMax);
}
void loop(void) {}
///////////////
//
// Результат
//
// ***** "Square" test
// Результат: 555
// Время: 1525 мс
// ***** "Linear" test
// Результат: 555
// Время: 999 мс
Спасибо, Евгений. Я разберусь в этом варианте. Но уже сразу вижу, что шаг № 1 можно убрать. А Макс и Мин можно запоминать при заполнении массива… (при считывании значений с датчика)
Разобрался.) Чем меньше разница между мин и макс, тем быстрее и меньше памяти…
Во временном массиве кол-ва вхождений чисел индекс не само число, как в примерах для мелких чисел (0…9) в интернете, а разница от числа из массива и меньшего значения числа из этого массива. Хитро!
