Блог

Я импортирую элементы из XML-файла. Каждый XML-элемент ( FoodItem , Person Order , CoffeeRun , — это класс, и каждый из этих элементов будет иметь уникальный идентификатор (уникальный для этого класса).

 <person>
<id>0</id>
<name>...</name>
</person>

<FoodItem>
<id>0</id>
<name>Coffee</name>
</FoodItem>
  

Я пытаюсь разработать подкласс DatabaseItem , который гарантирует, что никакие 2 объекта класса не будут иметь одинаковый идентификатор. Можете ли вы помочь мне, помогая мне разработать эффективный алгоритм, который гарантирует, что ни один объект не будет иметь тот же идентификатор, что и другой?

Мои два подхода кажутся мне немного неэффективными:

• Используйте статический вектор класса, который содержит все ИСПОЛЬЗУЕМЫЕ идентификаторы на данный момент. Когда создается новый DatabaseID( int requestedID ) объект, я проверяю, доступен ли идентификатор, просматривая все используемые значения в векторе, чтобы проверить, что идентификатор еще не существует, я думаю, это большая скорость?

• Используйте статический класс bool, vector где каждому элементу vector соответствует идентификатор (так vector[1] будет соответствовать объекту с идентификатором 1). Я проверяю, уже ли принят идентификатор, проверяя, является ли этот элемент в vector true if ( v[nID] == true ) { // this ID is already taken } . Это кажется неэффективным, потому что это означает, что мой vector займет много памяти, верно?

• Я не знаком с использованием maps в C , но, возможно, мне следует использовать его здесь?

Любой совет по эффективному алгоритму был бы действительно полезен:

 class DatabaseItem
{
    public:
        static unsigned int instanceCount;

        DatabaseItem()
        {
            // Assign next available ID
        }

        DatabaseItem( unsigned int nID )
        {
            // Check that that id is not already taken
            // if id is taken, look for next available id amp;
            // give the item that id
        }

    private:
        unsigned int uniqueID;
};

// My solution: Do you have any better ideas that ensure no objects jave the same ID?
// This seems REALLY inefficient...
class DatabaseItem
{
    public:
        static unsigned int instanceCount;
        static vector <unsigned int> usedIDs;

        DatabaseItem()
        {
            DatabaseItem::instanceCount  ;
            uniqueID = instanceCount;
            usedIDs.add( instanceCount );
        }

        DatabaseItem( unsigned int nID )
        {
            if ( isIDFree( nID ) )
            {
                uniqueID = nID;
            }
            else uniqueID = nextAvailableID();

            DatabaseItem::instanceCount  ;
        }

        bool isIDFree( unsigned int nID )
        {
            // This is pretty slow to check EVERY element

            for (int i=0; i<usedIDs.size(); i  )
            {
                if (usedIDs[i] == nID)
                {
                    return false;
                }
            }

            return true;
        }

        unsigned int nextAvailableID()
        {
            while ( true )
            {
                unsigned int ID = 0;

                if ( isIDFree( ID ) )
                {
                    return ID;
                }
                else ID  ;
            }
        }

    private:
        unsigned int uniqueID;
};


// Alternate that uses boolean vector to track which ids are occupied
// This means I take 30000 boolean memory when I may not need all that
class DatabaseItem
{
    public:
        static unsigned int instanceCount;
        static const unsigned int MAX_INSTANCES = 30000;
        static vector <bool> idVector;

        // Is this how I initialise a static class vector...? (note this code will be outside the class definition)
        // vector <bool> DatabaseItem::idVector( MAX_INSTANCES, false );

        DatabaseItem()
        {
            uniqueID           = nextAvailableID();
            idVector[uniqueID] = true;
        }

        DatabaseItem( unsigned int nID )
        {
            if ( nID >= MAX_INSTANCES )
            {
                // not sure how I shd handle this case?
            }

            if ( idVector[nID] == false )
            {
                uniqueID      = nID;
                idVector[nID] = true;
            }
            else
            {
                uniqueID           = nextAvailableID();
                idVector[uniqueID] = true;
            }

            instanceCount  ;
        }

        unsigned int nextAvailableID()
        {
            for (int i=0; i<idVector.size(); i  )
            {
                if ( !idVector[i] )
                {
                    return i;
                }
            }

            return -1;
        }

        bool isIDFree( unsigned int nID )
        {
            // Note I cannot do this: Because I am using Mosync API amp; it doesn't support any C   exceptions'

            // I declare idVector with no size! so not idVector( 30000, false)... just idVector;
            // then I allow an exception to occur to check if an id is taken

            try
            {
                return idVector[nID];
            }
            catch (...)
            {
                return true;
            }
        }

    private:
        unsigned int uniqueID;
};
  

vector<bool> Реализован с одним битом на bool, поэтому он не тратит впустую столько места, сколько вы предполагаете.

A set<unsigned int> — простое решение для этого. vector<bool> Быстрее. Оба варианта могли бы использовать немного памяти. В зависимости от ваших шаблонов использования есть несколько других решений:

• unsigned int all_taken_upto_this; В сочетании с set<int> , охватывающим все нестандартные идентификаторы, которые выше all_taken_upto_this — удалите из набора и увеличьте счетчик, когда сможете.

• A, map<unsigned int, unsigned int> который логически обрабатывается как begin,end состоящий либо из выбранных, либо из свободных последовательностей. Для правильной реализации потребуется немного повозиться (например, объединение последовательных элементов map при добавлении последнего идентификатора между двумя элементами)

Вероятно, вы могли бы использовать предварительно созданную структуру данных типа «разреженный набор битов» — я не знаю ни одной реализации OTOH.

В зависимости от количества элементов и пары других проблем, вы могли бы рассмотреть возможность их фактического хранения (или, по крайней мере, указателей на них) в map. Это было бы довольно просто реализовать, но займет некоторое место. С другой стороны, это обеспечит вам быстрый поиск по id , что может быть явным преимуществом, если в XML есть перекрестные ссылки. Карта (предполагающая указатели) будет выглядеть следующим образом:

 std::map<int, std::shared_ptr<Object> > id_map;
std::shared_ptr<Object> p( new Object( xml ) );
if ( !id_map.insert( std::make_pair( p->id, p ) ).second ) {
   // failed to insert, the element is a duplicate!!!
} 
  

Если вы не привязаны к использованию целого числа, вы можете посмотреть GUID (глобальные уникальные идентификаторы). В зависимости от используемой платформы обычно можно найти пару служебных функций для динамической генерации GUID. При использовании Visual Studio я использовал функцию CoCreateGuid.

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