w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
data structure best suited for key value pair evaluation

Let me fix the notation and write in python for simplicity.

What you call an ENTITY is a set of dictionaries labeled by 'keys' with lists of objects as values. For simplicity let's assume that values are numbers (but what we truly need is just comparison operation)

E1 = { 
    {'k1': [4], 'k2': [20,12]},
    {'k4': [2,20,25], 'k3': [2,3]}

E2 = { 
    {'k2': [2,3,4], 'k4': [2], 'k3': [14]},
    {'k3': [1]},
    {'k3': [12,23]}

Input is just a dictionary, again labeled by 'keys' and with lists of objects as values.

INPUT = {'k2': [2], 'k3': [14,12] }

I think you should keep arrays of values in sorted order. This should allow you to compare lists for a given key in linear time. In total the complexity for given input should be O(EKL), where E is a number of entities, K is a number of keys and L is the length of the list. Similarly, it will take O(EKL) memory.

I expect that with your bounds comparison in this case will take up to several seconds. If this is not enough then let's think further :)


EDIT: You can simply use a set of tuples (entity_id, set_id, key, value), with a balanced BST as an index for values. Then search should take around O(log n). Have you thought about a structure like this?

© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.