Самый эффективный способ перечисления элементов в C / C ++

Question

У меня есть список, скажем, 100 несортированных предметов. Каждый элемент принадлежит группе. Группа, к которой принадлежит элемент, является просто членом класса элементов.

Использование C / C ++ Я ищу наиболее эффективный способ сканирования списка элементов, проверки, в какой группе они находятся, и вывода элемента на экран. Вот подвох, хотя. Как только элемент из группы был напечатан на экране, я не хочу больше печатать элементы, принадлежащие этой группе.

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

Answer 1

Сортировка элементов по значению группы (если это указатель , то вы можете использовать его адрес, иначе лексикографический сортировка строки ). Затем переберите этот отсортированный список, всегда беря первый элемент каждой группы.

Это займет примерно

n + n * log(n)

Я думаю, что это разумная альтернатива между размером вашего исполняемого файла и скоростью.

Answer 2

Вы написали c / c ++ в вопросе, так что вот немного кода на c. Пара вопросов в порядке. Станет ли группа пригодной для печати в будущем? Является ли список товаров статичным? Имеет ли значение, какой элемент из определенной группы вы печатаете?

Я бы предложил следующую конструкцию (с моим ограниченным пониманием проблемы):

Массив списков.

  typedef struct node{
    void *item; /* this is your item */
    node *next; 
  } node_t;

  typedef struct {
    node_t *my_group;
    int used;
  } group_t;

  static group_t my_items[NUM_OF_GROUPS]; /* this is your ordered by groups list.*/

Еще лучше, используйте список списков. group_t будет:

typedef struct group{
  node_t *my_group;
  group *next_free;
} group_t;

Answer 3

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

Пример кода:

#include <unordered_map>
#include <string>
#include <iostream>

std::string getGroupForNumber( int num )
{
//
}

int main()
{
    typedef std::tr1::unordered_map< std::string, bool > hashmap;
    hashmap groupsPrinted;

    for( int i = 0 ; i < 100 ; ++i ) {
        if ( groupsPrinted[ getGroupForNumber( i ) ] == false ) {
            groupsPrinted[ getGroupForNumber( i ) ] = true;
            std::cout << i << std::endl;
        }
    }
    return 0;
}

Answer 4

Стоимость печати на экране на несколько порядков больше, чем что-либо еще, что вы можете сделать с объектами. Если у вас был массив из 10 миллионов объектов только в нескольких группах, сортировка не является разумным вариантом. Если группы могут быть идентифицированы с помощью статического индекса (то есть целого числа в данном диапазоне), просто используйте массив масок, чтобы указать, был ли он замечен. Если группы более сложные, вы можете сохранить группы, которые были видны в любой заданной структуре данных (хэш, дерево и т. Д.).

Answer 5

А как насчет групп? ты можешь получить новую группу? И может ли группа стать актуальной после того, как вы напечатаете одного из ее членов?

Answer 6

Чтобы ответить еще на несколько вопросов.

Является ли список предметов статичным?

Нет, он может уменьшаться или расти в любое время.

Имеет ли значение, какой предмет из конкретную группу вы печатаете?

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

Answer 7

Сохраните std :: набор имен групп, элементы которых больше не должны печататься.

Answer 8

Если вы можете нумеровать группы 0 ... 99, тогда вам понадобится массив логических значений или набор битов, если вы хотите оптимизировать. Инициируйте весь массив в «ложь». Установите arr [groupId] = 'true' после печати и проверьте значение в следующий раз перед печатью. STL не требуется.