Is it bad practice to maintain two copies of the same data, if they are in different data structures?

user_2717373 0
Viewed 159

Say I have a universal set of indexed objects, U, and a subset of these objects, S. S is large (say, 1,000,000 elements), however U is MUCH larger (say, 100,000,000 at least).

I would like to perform two basic operations on these sets:

(1) Given any integer x from 0 to the size of U minus 1, check for membership of S, if not a member, then add x to S, and

(2) Select (and remove) a random element from S.

In order to perform the first part of operation (1), it makes sense to me to keep a boolean vector v the size of U, where the value is true if element x is a member of set S.

However, because U is so much larger than S, choosing a random element in v and hoping that it is also an element in S does not make sense. I if U is 100 times larger than S, then it would only find an element of S, on average, one time every 100 tries.

So, in order to perform the second operation, it makes sense to maintain a list of indices of elements that are in S and select a random element from that.

The only problem now, is that there is now two copies of the same data, and they both need to be updated separately with each operation. Here is the pseudocode for the first operation:

** operation 1 - check membership and add **
input: boolean vector, v
       integer vector, S
       integer, x

if v[x] is not true:
    v[x] = true
    append x to S
return

That is relative simple, but it has to update the vector of indices even though it didn't use it. Here is the second operation:

** operation 2 - select and remove random element of S **
input: boolean vector, v
       integer vector, S

generate random integer x between 0 and size of S
set v[S[x]] to false
remove S[x] from S
return

Maintaining two copies of the data has made both of those operations more complicated, because each has to update both data structures, even if it only needs one. Is this bad practice?

The only alternative I could come up with is to use one or the other. But that makes one operation simpler, but the other more complicated. For example (only the more complicated ones are given):

** operation 1 - check membership and add**
input: integer vector, S
       integer, x

iterate over S
if x in S:
    return
else:
    append x to S
    return

So every time, it will have to iterate over the entire S, instead of a single look-up, and 

** operation 2 - select and remove random element of S **
input: boolean vector, v

while true:
    generate random integer x between 0 and size of S
    if v[x] true:
        v[x] = false
        return

Both of these seem pretty inefficient, especially if the sizes of U and S are large, and the difference between U and S is also large. Is there a way that I can perform both of these operations efficiently with only one data structure? or is there not really a big problem with maintaining two copies of the same thing?

EDIT:

The code I am writing is in c++, so I guess I am asking about c++ data structures in particular, but the question isn't really language specific.

data-structures c++ performance
3 Answers

I don't see a (major) problem with either 3 of the approaches. When deciding for one of them you have to take into consideration:

  • code readability
  • code maintainability
  • performance

Code readability

How easy and intuitive is to understand what the code does. The code should not have any surprising behavior.

All three can be reasonably equally readable if using good naming and clean structured code.

Code maintainability

How easy is is to debug, test, extend the code.

The variant with two structures has a slightly more cost. But just slightly. I don't see as much more complexity compared to the other ones. And you could have a test in your unit tests that checks the integrity of the scheme. I.e. check if the boolean vector and the integer vector agree as to what S is.

Performance

You might make assumptions all day long about what variant and by how much is faster, but at the end of the day any talk about performance is pointless without actual profiling. If performance is an important factor to you, then implement all 3 methods and measure the actual performance of them.

user_28053050

After some consideration, I think std::map might be best suited. 

#include <random>
#include <iterator>
#include <map>
#include <vector>

struct Data {};                           // Your actual Object here

constexpr auto universal_size = 100'000;  // I shrank it a little for
constexpr auto subset_size = 1'000;       // the example

std::vector<Data> U(universal_size);      // This is the indexed data store

std::map<int, Data*> S;                   // This is the subset

void add_if_not_in(int idx)               // idx is universal index.
{                                         // This is one of the
    S[idx] = &U[idx];                     // functionalities you
}                                         // requested.

void remove_by_universal_index(int idx)   // Not strictly needed.
{                                         // Removes object from 
    S.erase(idx);                         // subset, by universal
}                                         // index.

void remove_by_subset_index(int idx)      // Removes object from
{                                         // subset, by subset
    auto iter = S.begin();                // index. Used by 
    std::advance(iter, idx);              // remove_random()
    S.erase(iter);
}

std::mt19937 gen{};                       // A random generator

void remove_random()                      // The second functionality
{                                         // you requested.
    auto sz = S.size();                   // Removes one random element
    std::uniform_int_distribution<>       // from the subset.
        dis(0, sz-1);
    auto num = dis(gen);

    remove_by_subset_index(num);
}

void add_random()                         // Used to initialize subset.
{                                         // Adds one random element of
    auto sz = U.size();                   // universal set to subset.
    std::uniform_int_distribution<>
        dis(0, sz-1);
    auto idx = dis(gen);

    add_if_not_in(idx);    
}

void setup()                              // Initialize subset.
{                                         // Just add random until
    while (S.size() < subset_size)        // size is specified.
        add_random();
}

int main()                                // Try it 
{
    setup();
    add_random();
    remove_random();
}

try code online here http://coliru.stacked-crooked.com/a/8236da0ccaf05079

user_32020930
Related