Отслеживание индексов массива, которые отвечают некоторым требованиям в C - PullRequest
Новая
       43

Отслеживание индексов массива, которые отвечают некоторым требованиям в C

0 голосов
/ 01 ноября 2011

Такая ситуация возникает довольно часто.Вы перебираете массив, и если некоторые элементы удовлетворяют некоторому требованию, вы хотите отслеживать их индексы на потом.Вот что я имею в виду: 

for(i=0;i<10;++i)
{
     if(array[i] > 10)
     {
          //Keep track of this index for later use.
     }
}

Простым решением было бы создать массив из 10 элементов, и если, скажем, 2-й элемент больше 10, можно сделать индексы [i] = 1;Но я чувствую, что такой подход не так хорош.Мне понадобится большой массив для хранения этого, и большая часть пространства будет потрачена впустую.

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

Этот код должен работать на AVR Mega, и я использую AVR-GCC, поэтому требуется решение только для C.

Ответы [ 3 ]

3 голосов
/ 02 ноября 2011

Вы можете использовать растровое изображение: используется только 1 бит на индекс вместо 16 или 32 бит на индекс. 

uint32_t bitmap[10] = {0}; // works for array size up to 320 elements
for(i=0;i<10;++i)
{
     if(array[i] > 10)
     {
          //Keep track of this index for later use.
          bitmap[i/32] |= (uint32_t)1 << (i%32);
     }
}

for(i=0;i<10;++i)
{
     if((bitmap[i/32] >> (i%32)) & 1)
     {
         // Later use :)
         // Put some code here
     }
}
0 голосов
/ 02 ноября 2011

Я бы сказал, что на ПК лучше всего использовать динамически растущий связанный список или стек.

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

0 голосов
/ 02 ноября 2011

Если вы чувствуете, что много места будет потрачено впустую, используя дополнительный массив для запоминания «специальных» индексов, попробуйте точно определить, сколько места будет потрачено впустую.Затем используйте меньший массив.Например, если вы знаете, что должны запомнить не более 4 индексов, объявите массив размером 4.

Вы также можете объявить небольшой массив, недостаточно большой, чтобы запомнить все индексы, и запустить цикл, который заполняетэто несколько раз: 

int indices[4];
int number_of_indices = 0;
int i_start = 0; // array entries up to this index were already checked
while (i_start < 10) {
    for(i=i_start;i<10;++i)
    {
        if(array[i] > 10)
        {
            //Keep track of this index for "later use" below.
            indices[number_of_indices++] = i;
            // If 4 indices have been gathered, break the loop and use them
            if (number_of_indices == 4)
            {
                break;
            }
        }
    }
    i_start = i;

    // Put "Later use" here :)
    // Do something for the list of indices gathered so far
}
...