CODEWITHSUNDEEP
javac++optimizationset
Truthseeker Rangwan
Truthseeker Rangwan

Reputation: 231

C++/JAVA: Efficiently find a set in the collection containing given value

Suppose that we have a collection of mutually exclusive sets
    {A,B,C,D} where A = {1,2,3}, B = {4,5,6}, C = {7,8,9}, D = {10,11,12}
And given a value Z, for example of 3, I expect it to return the index of set A, because A has 3 as its member.

The question is that how could I do it efficiently using C++ or JAVA.

My current solution: Store the A,B,C,D as a HashSet (or unordered_set in C++) in the container and loop through each set until a set containing Z is found.
    The problem is that the complexity is O(n) for the amount of sets stored in the container.

Is there any way (or any data structure to store those sets) to do that faster than O(n)?

Upvotes: 6

Views: 133

Answers (2)

leventov
leventov

Reputation: 15313

As a quick heuristic that can help try to bubble most actively used sets up in the list. It is likely that most of the time there would be one or two sets that are returned on 80-90% of requests.

int getSetIndex(Object elem) {
    Set first = sets.get(0);
    if (first.contains(elem))
        // if "index of the set" has some special meaning in your question,
        // you should save it along with the set
        return first.index();
    for (int i = 1; i < sets.size(); i++) {
        Set cur = sets.get(i);
        if (cur.contains(elem)) {
            sets.set(i, sets.get(i - 1));
            sets.set(i - 1, cur);
            return cur.index();
        }
    }
    return -1; // not found
}

Upvotes: 0

kraskevich
kraskevich

Reputation: 18566

You can create a map that maps a value to set id(for example it should map 1, 2, 3 to A, 4, 5 and 6 to B and so on). With a hash map, it can work in O(1) on average.

Upvotes: 4

Related Questions