Find element in 4d array with special properties

If N is less than 10000, then you can't see why you can't use unordered_set. Then do one search. If there can be the same values ​​for each dimension, then you will need to track this somehow. But I don't know of any code that implements unordered_set for C. So you probably have to use C ++ for this.

If you cannot use unordered_set, then since the data is in sorted order for each dimension, you can also use binary search for each dimension. This would mean looking for no more than 15 values ​​for each dimension on average - assuming the total number of items in each dimension is less than 16K. 15 searches * 4 dimensions = 60 searches. Is it too slow?

Another improvement could be to create one large sorted and unique array of 4 dimensions and search for it instead. This would give a total of about 17 searches (assuming <= 64K items) .vs. 60, which is 3.5 times faster. However, it will also depend on how often values ​​are added to or removed from dimensions to determine if this is actually faster or not - since you will have to add and remove them from the same table. Also, remember to use a table to track duplicate values ​​- if applicable.

If the values ​​are relatively small integers - such as a billion or less, then you can use a bitmap scheme. The bitmap schema will be faster than using unordered_set for each dimension. An array of bytes can be used as a bitmap. The value set in the bitmap means that this value is present. For example, if the value is zero, then bit 0 will be set. If the value is 3, then bit 2 will be set. If the value is 5, then bit 4 will be set, and so on. So 100MB would need to be used to display all values ​​for 1 billion (2 ^ 30). If there can be duplicate values ​​in each dimension, then you will need to keep track of this,so that when a value is removed from a dimension, it is not removed from the bitmap if it does not exist in any other dimensions. If your values ​​are floating point numbers, you can convert them to ints if the total significant digits are <= 9. If the values ​​are strings or structures, then the bitmap schema might still work if you could figure out a way to translate it into a unique integer.if you could figure out a way to translate it into a unique integer.if you could figure out a way to translate it into a unique integer.