Arduino.ru

Для быстрого поиска есть деревья и хеш-таблицы.

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

Может покажете код, а то что-то непонятно, где там у вас может быть затык

если число в конце массива хорошо справится шейкерный метод

если число в конце массива - надо искать с конца!

Написан конечно криво... я только учусь)))

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

Так... массивы заполняются динамически с СОМ порт. Подскажите, плз, терминальную программу, которая может посылать НЕПРЕРЫВНО коды, которые я ввел в окно. ОФ...топик(((

Что-то я не заметил, чтобы в теме было написано что есть "всё", чтобы знать, что производительности хватит на "всё"

Это как?

кто у нас тут программисты?... обязаны знать )))

byte Array[100] = {0};

void setup() 
{
Array[99] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

результат в терминале: 

52 microsec
Index45 = 99

52 мкс для этого - довольно много

Макс, а если в 11 строчке размер не вычислять, а  записать явно?

for (byte i=0; i<100; i++)

все равно 52

если массив int то 72 мкс, а если инкремент в цикле фор тоже сделать int то 88 мкс

да, точно... компилятор сам это заменяет при оптимизации...

а так?

byte Array[100] = {0};

void setup() 
{
Array[99] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
  }
prevtime = micros()-prevtime;
Serial.print (prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

я тоже думал, что так будет быстрее и уже попробовал , все равно 52))  Понятно, что в реале поиск чуть меньше времени занимает, т.к. измерение времени поиска и распечатка тоже занимает время. Но, я думаю, может микросекунд на 5 поменьше. 

ну да, я тоже уже попробовал... :)

И через указатели вместо массива.. та же цифра с точностью до мкс.

Удивительная стабильность.

byte Array[100] = {0};

void setup() 
{
Array[99] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

52 microsec
Index45 = 99

конечно много, если всего одна строчка и можно сделать за 4 микросекунды )))
 

4 microsec
Index45 = 99

byte Array[100] = {0};

void setup() 
{
Array[99] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[100-i]==45){ index45 = 100 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

а если число в середине окажется? )) ну все равно чуть быстрее:  44 мкс. 

byte Array[100] = {0};

void setup() 
{
Array[50] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[100-i]==45){ index45 = 100 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

ну да, только твой первый код находил 50-й элемент быстрее :)

byte Array[100] = {0};

void setup() 
{
Array[50] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[100-i]==45){ index45 = 100 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

да, но в этом случае если не применять шейкер, то оно найдётся быстрее, за
28 microsec
Index45 = 49

Тема обсосана мной лет 25 назад, в не сортированном массиве выигрывает быстрый поиск

нифига подобного, проверил, закомментировал цикл фор. Показывает 0 мкс. Поэтому всё точно вплоть до 1 мкс. 

не ну это повезло, мыж за максимальное время боремся, чтоб оно минимально было)) 

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

PS метод половинного деления тоже проигрывает

52 микросекунды на обработку 100 элементов - это по 8 тактов на элемент.

byte Array[100] = {0};

void setup() 
{
Array[50] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[100-i]==45){ index45 = 100 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

Строго говоря, сразу надо уменьшать длину цикла вдвое (11 строка).

А выигрыш за счет того, что за проход цикла проверяется не 1, а 2 элемента. Меньше накладные расходы на организацию цикла. Если в цикле проверять по 10 элементов, будет еще быстрее. 

Собственно, расчет примерно такой:

- проверка окончания цикла - 2 такта,

- проверка, сравнение и переход - 6 тактов,

Если в цикле 1 сравнение - 8 тактов, если 2 сравнения - 14 тактов, но самих циклов вдвое меньше.

Нету никакого быстрого поиска. Шейкер - это метод сортировки, а не поиска.

Фикция все это.

Поиск в неотсортированном массиве О(n). Быстрее не получится.

это похоже на разгон процессора под жидким азотом, только ради результата. Неужели эта цифра действительно большая ? ну что в нашем мире 52 мкс для любительского хобби? я delay по  100 200 мс, иногда не стремаюсь ставить в своих проектах. 

а вот когда обсчитывать надо 3 дома услуги ЖКХ на 286 машине и между расчётами тебе наливают, можно спиться, если не оптимизировать )))

Собственно, листинг цикла:

for (byte i=0; i<sizeof(Array); i++)
 60c:	c0 e0       	ldi	r28, 0x00	; 0
  {
   if (Array[i]==45){ index45 = i; break; }
 60e:	81 91       	ld	r24, Z+
 610:	8d 32       	cpi	r24, 0x2D	; 45
 612:	21 f0       	breq	.+8      	; 0x61c <main+0x112>
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
 614:	cf 5f       	subi	r28, 0xFF	; 255
 616:	c4 36       	cpi	r28, 0x64	; 100
 618:	d1 f7       	brne	.-12     	; 0x60e <main+0x104>
void setup() 
{
Array[99] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 
 61a:	c0 e0       	ldi	r28, 0x00	; 0
uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
  }
  uint32_t posttime = micros();
 61c:	0e 94 69 01 	call	0x2d2	; 0x2d2 <micros>

В регистре r28 у нас переменная цикла i, а в регистр r24 мы загружаем очередной элемент массива. Остальное, думаю, понятно: по адресу 610 сравниваем число с 45 и, если сравнение увенчалось успехом, следующим оператором покидаем цикл. По адресу 614 инкремент переменной цикла (сделан любопытно: i -= 255;), 616 - проверка на окончание цикла.

Вроде как вывод одного символа в порт занимает 16мкс.
Так что не на 5.

Во-первых, вывод в порт в подсчет времени не входит, а во-вторых, Serial.print() не выводит символ в порт, а лишь помещает его в буфер вывода, что намного бысрее.

не, вывод ведь не влияет, если скетч внимательно посмотреть. Тем более я проверил, и микрос тоже не влияет. 

4 microsec
Index45 = 99

byte Array[100] = {0};

void setup() 
{
Array[99] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<sizeof(Array); i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[100-i]==45){ index45 = 100 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

Ну,  детские ошибки-то исправьте!

1. за границы массива-то не надо вылазить!

2. Вы в цикле сравниваете с начала и с конца, но при этом нафига-то идёте черезь весь массив! Т.е. если искомого элемента в массиве нет, то Вы каждый элемент сравните с 45 ДВАЖДЫ!

3. В ограничении цикла нельзя использовать sizeof - это сработает только при байтовом массиве чисто по совпадению. При любом другом типе (int, long) всё повалится нахрен.

интересно почему так?

Не знаю.

В принципе, для байта "i++;" и "i -=255;" - это одно и то же. Может автор дизассемблера так самовыразился. А может - чтобы флаги состояния после операции правильно расставились. Я не силен в системе команд AVR.

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

так видимо будет правильней:
 

byte Array[100] = {0};

void setup() 
{
Array[89] = 45;            // делаем последнюю ячейку массива равной 45 например
//Array[49] = 45;
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<50; i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[99-i]==45){ index45 = 99 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");

Serial.print ("Index45 = "); Serial.print (index45); 
 

}

void loop() {}

кстати, даже для самого тяжёлого случая поиск занимает 48 микросекунд на ниже приведённом скетче, может покажете быстрый поиск?
 

byte Array[100] = {0};

void setup() 
{
Array[24] = 45;            // делаем последнюю ячейку массива равной 45 например
Serial.begin (115200);

byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<25; i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[49-i]==45){ index45 = 49 - i; break; }
   if (Array[i+50]==45){ index45 = i+50; break; }
   if (Array[99 -i]==45){ index45 = 99 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");
Serial.print ("Index45 = "); Serial.print (index45); 
}

void loop() {}

Да напиши уж сразу все сто сравнений на if, гений программирования блин.

Быстрого поиска по неупорядоченному массиву не существует. Нужно либо сортировать массив, либо использовать деревья. В любом случае O(log(N)).

Но Вы на правильном пути: 

uint32_t prevtime = micros(); // время начала поиска 
if (Array[0]==45){ index45 = 0; break; }
if (Array[1]==45){ index45 = 1; break; }
if (Array[2]==45){ index45 = 2; break; }
if (Array[3]==45){ index45 = 3; break; }
if (Array[4]==45){ index45 = 4; break; }
...
if (Array[99]==45){ index45 = 99; break; }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск

а пальцем показать сможешь? или ты всё языком?
 

byte Array[100] = {0};

void setup() 
{
Serial.begin (115200);
randomSeed(analogRead(0));
uint8_t s = random(100);
Array[s] = 45;            // делаем последнюю ячейку массива равной 45 например


byte index45 = 0; 

uint32_t prevtime = micros(); // время начала поиска 
for (byte i=0; i<25; i++)
  {
   if (Array[i]==45){ index45 = i; break; }
   if (Array[49-i]==45){ index45 = 49 - i; break; }
   if (Array[i+50]==45){ index45 = i+50; break; }
   if (Array[99 -i]==45){ index45 = 99 - i; break; }
  }
Serial.print (micros()-prevtime); // распечатаем сколько времени составил поиск
Serial.println (" microsec");
Serial.print ("Index45 = "); Serial.println (index45); 
}

void loop() {}

получается, что компилятор реализует функцию весьма эффективно, на ассемблере это было бы
приблизительно 5-8 инструкций, то-есть 35-56  микросекунд приблизительно, переводом на ассемблер
не решить задачу, остаётся только алгоритм...

Тому кто технарям ставит задачу по ЖКХ и даёт 286 машины надо в рот насрать.

так дело давно было, на заре автоматизации )))

Ассемблерный листинг был размещен в сообщении №29.

Так что, кто умеет читать - читает, а кто не умеет - гадает, сколько это приблизительно могло бы быть.

вот это что ли?
 

for (byte i=0; i<sizeof(Array); i++)
02
	 60c:   c0 e0           ldi r28, 0x00   ; 0

конечно не умею, не вижу тут размерности массива, совсем...

посмотрел внимательней, сделано через взад, а чё, так тоже можно, особенно в свете общемировых тенденций...

 614:	cf 5f       	subi	r28, 0xFF	; 255
 616:	c4 36       	cpi	r28, 0x64	; 100

 614:	cf 5f       	subi	r28, 0xFF	; 255
 616:	c4 36       	cpi	r28, 0x64	; 100

subi r28,ff и  inc r28 оба занимают 2 байта, как любая команда, выполняются ОДИН так и делают ОДНО И ТОЖЕ. Только SUBI больше флагов выставляет. Поэтому компилятор её и предпочитает. Нет аргументов в пользу inc, кроме "читаемости человеком". Как ты думаешь, компилятору важна "читаемость" человеком его кода? ;))))

 614:	cf 5f       	subi	r28, 0xFF	; 255
 616:	c4 36       	cpi	r28, 0x64	; 100

я учил ассемблер по книге Питера Нортона, меня не переделать уж

Долго думал, что в ответ написать. Ничего кроме:

--Возьми с полки порожок! 

не пришло в голову! ;)))

 614:	cf 5f       	subi	r28, 0xFF	; 255
 616:	c4 36       	cpi	r28, 0x64	; 100

А я по Питеру Абелю. Чье кунфу сильнее? :-)

скорее твоё, тогда у процессора уровней ещё небыло